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