veslibrary/ves_clibrary/evel/evel-library/code/evel_library/hashtable.c

   1 /*************************************************************************//**
   2  *
   3  * Copyright © 2017 AT&T Intellectual Property. All rights reserved.
   4  *
   5  * Unless otherwise specified, all software contained herein is
   6  * Licensed under the Apache License, Version 2.0 (the "License");
   7  * you may not use this file except in compliance with the License.
   8  * You may obtain a copy of the License at
   9  *        http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  * Unless required by applicable law or agreed to in writing, software
  12  * distributed under the License is distributed on an "AS IS" BASIS,
  13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14  * See the License for the specific language governing permissions and
  15  * limitations under the License.
  16  *
  17  ****************************************************************************/
  18 /**************************************************************************//**
  19  * @file
  20  * A simple Hashtable.
  21  *
  22  * @note  No thread protection so you will need to use appropriate
  23  * synchronization if use spans multiple threads.
  24  *
  25  ****************************************************************************/
  26
  27 #include <limits.h>
  28 #include <assert.h>
  29 #include <malloc.h>
  30 #include <string.h>
  31
  32 #include "hashtable.h"
  33
  34 /**************************************************************************//**
  35  * Hashtable initialization.
  36  *
  37  * Initialize the list supplied to be empty.
  38  *
  39  * @param   size  Size of hashtable
  40
  41  * @returns Hashtable pointer
  42 ******************************************************************************/
  43 /* Create a new hashtable. */
  44 HASHTABLE_T *ht_create( size_t size ) {
  45
  46         HASHTABLE_T *hashtable = NULL;
  47         size_t i;
  48
  49         if( size < 1 ) return NULL;
  50
  51         /* Allocate the table itself. */
  52         if( ( hashtable = malloc( sizeof( HASHTABLE_T ) ) ) == NULL ) {
  53                 return NULL;
  54         }
  55
  56         /* Allocate pointers to the head nodes. */
  57         if( ( hashtable->table = malloc( sizeof( ENTRY_T * ) * size ) ) == NULL ) {
  58                 return NULL;
  59         }
  60         for( i = 0; i < size; i++ ) {
  61                 hashtable->table[i] = NULL;
  62         }
  63
  64         hashtable->size = size;
  65
  66         return hashtable;
  67 }
  68
  69 /**************************************************************************//**
  70  * Hash a string for a particular hash table.
  71  *
  72  * Initialize the list supplied to be empty.
  73  *
  74  * @param   hashtable    Pointer to the hashtable
  75  * @param   key          String
  76
  77  * @returns hashvalue
  78 ******************************************************************************/
  79 size_t ht_hash( HASHTABLE_T *hashtable, char *key )
  80 {
  81
  82     size_t hash, i;
  83
  84 #ifdef HASHTABLE_USE_SIMPLE_HASH
  85     for ( hash = i = 0; i < strlen(key); hash = hash << 8, hash += key[ i++ ] );
  86 #else /* Use: Jenkins' "One At a Time Hash" === Perl "Like" Hashing */
  87     // http://en.wikipedia.org/wiki/Jenkins_hash_function
  88     for ( hash = i = 0; i < strlen(key); ++i ) {
  89         hash += key[i], hash += ( hash << 10 ), hash ^= ( hash >> 6 );
  90     }
  91     hash += ( hash << 3 ), hash ^= ( hash >> 11 ), hash += ( hash << 15 );
  92 #endif
  93
  94     return hash % hashtable->size;
  95
  96 }
  97
  98 /**************************************************************************//**
  99  * Create a key-value pair.
 100  *
 101  * @param   key     key string
 102  * @param   value   value string
 103  *
 104  * @returns hashtable entry
 105 ******************************************************************************/
 106 ENTRY_T *ht_newpair( char *key, void *value )
 107 {
 108         ENTRY_T *newpair;
 109
 110         if( ( newpair = malloc( sizeof( ENTRY_T ) ) ) == NULL ) {
 111                 return NULL;
 112         }
 113
 114         if( ( newpair->key = strdup( key ) ) == NULL ) {
 115                 return NULL;
 116         }
 117
 118         if( ( newpair->value =  value ) == NULL ) {
 119                 return NULL;
 120         }
 121
 122         newpair->next = NULL;
 123
 124         return newpair;
 125 }
 126
 127 /**************************************************************************//**
 128  * Insert a key-value pair into a hash table.
 129  *
 130  * @param   key     key string
 131  * @param   value   value string
 132  *
 133  * @returns Nothing
 134 ******************************************************************************/
 135 void ht_set( HASHTABLE_T *hashtable, char *key, void *value ) {
 136         size_t bin = 0;
 137         ENTRY_T *newpair = NULL;
 138         ENTRY_T *next = NULL;
 139         ENTRY_T *last = NULL;
 140
 141         bin = ht_hash( hashtable, key );
 142
 143         next = hashtable->table[ bin ];
 144
 145         while( next != NULL && next->key != NULL && strcmp( key, next->key ) > 0 ) {
 146                 last = next;
 147                 next = next->next;
 148         }
 149
 150         /* There's already a pair.  Let's replace that string. */
 151         if( next != NULL && next->key != NULL && strcmp( key, next->key ) == 0 ) {
 152
 153                 free( next->value );
 154                 next->value = value ;
 155
 156         /* Nope, could't find it.  Time to grow a pair. */
 157         } else {
 158                 newpair = ht_newpair( key, value );
 159
 160                 /* We're at the start of the linked list in this bin. */
 161                 if( next == hashtable->table[ bin ] ) {
 162                         newpair->next = next;
 163                         hashtable->table[ bin ] = newpair;
 164
 165                 /* We're at the end of the linked list in this bin. */
 166                 } else if ( next == NULL ) {
 167                         last->next = newpair;
 168
 169                 /* We're in the middle of the list. */
 170                 } else  {
 171                         newpair->next = next;
 172                         last->next = newpair;
 173                 }
 174         }
 175 }
 176
 177 /**************************************************************************//**
 178  *  Retrieve a key-value pair from a hash table.
 179  *
 180  * @param   key     key string
 181  *
 182  * @returns  value string
 183 ******************************************************************************/
 184 void *ht_get( HASHTABLE_T *hashtable, char *key ) {
 185         size_t bin = 0;
 186         ENTRY_T *pair;
 187
 188         bin = ht_hash( hashtable, key );
 189
 190         /* Step through the bin, looking for our value. */
 191         pair = hashtable->table[ bin ];
 192         while( pair != NULL && pair->key != NULL && strcmp( key, pair->key ) > 0 ) {
 193                 pair = pair->next;
 194         }
 195
 196         /* Did we actually find anything? */
 197         if( pair == NULL || pair->key == NULL || strcmp( key, pair->key ) != 0 ) {
 198                 return NULL;
 199
 200         } else {
 201                 return pair->value;
 202         }
 203
 204 }
 205
 206 /*
 207 int main( int argc, char **argv ) {
 208
 209         HASHTABLE_T *hashtable = ht_create( 65536 );
 210
 211         ht_set( hashtable, "key1", "inky" );
 212         ht_set( hashtable, "key2", "pinky" );
 213         ht_set( hashtable, "key3", "blinky" );
 214         ht_set( hashtable, "key4", "floyd" );
 215
 216         printf( "%s\n", ht_get( hashtable, "key1" ) );
 217         printf( "%s\n", ht_get( hashtable, "key2" ) );
 218         printf( "%s\n", ht_get( hashtable, "key3" ) );
 219         printf( "%s\n", ht_get( hashtable, "key4" ) );
 220
 221         return 0;
 222 }
 223 */