vnfs/VES5.0/evel/evel-library/code/evel_library/hashtable.c

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