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

   1 /**************************************************************************//**
   2  * @file
   3  * A simple Hashtable.
   4  *
   5  * @note  No thread protection so you will need to use appropriate
   6  * synchronization if use spans multiple threads.
   7  *
   8  * License
   9  * -------
  10  *
  11  * Copyright(c) <2016>, AT&T Intellectual Property.  All other rights reserved.
  12  *
  13  * Redistribution and use in source and binary forms, with or without
  14  * modification, are permitted provided that the following conditions are met:
  15  *
  16  * 1. Redistributions of source code must retain the above copyright notice,
  17  *    this list of conditions and the following disclaimer.
  18  * 2. Redistributions in binary form must reproduce the above copyright notice,
  19  *    this list of conditions and the following disclaimer in the documentation
  20  *    and/or other materials provided with the distribution.
  21  * 3. All advertising materials mentioning features or use of this software
  22  *    must display the following acknowledgement:  This product includes
  23  *    software developed by the AT&T.
  24  * 4. Neither the name of AT&T nor the names of its contributors may be used to
  25  *    endorse or promote products derived from this software without specific
  26  *    prior written permission.
  27  *
  28  * THIS SOFTWARE IS PROVIDED BY AT&T INTELLECTUAL PROPERTY ''AS IS'' AND ANY
  29  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  30  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  31  * DISCLAIMED. IN NO EVENT SHALL AT&T INTELLECTUAL PROPERTY BE LIABLE FOR ANY
  32  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  33  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  34  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  35  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  36  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  37  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  38  *****************************************************************************/
  39
  40 #include <limits.h>
  41 #include <assert.h>
  42 #include <malloc.h>
  43 #include <string.h>
  44
  45 #include "hashtable.h"
  46
  47 /**************************************************************************//**
  48  * Hashtable initialization.
  49  *
  50  * Initialize the list supplied to be empty.
  51  *
  52  * @param   size  Size of hashtable
  53
  54  * @returns Hashtable pointer
  55 ******************************************************************************/
  56 /* Create a new hashtable. */
  57 HASHTABLE_T *ht_create( size_t size ) {
  58
  59         HASHTABLE_T *hashtable = NULL;
  60         size_t i;
  61
  62         if( size < 1 ) return NULL;
  63
  64         /* Allocate the table itself. */
  65         if( ( hashtable = malloc( sizeof( HASHTABLE_T ) ) ) == NULL ) {
  66                 return NULL;
  67         }
  68
  69         /* Allocate pointers to the head nodes. */
  70         if( ( hashtable->table = malloc( sizeof( ENTRY_T * ) * size ) ) == NULL ) {
  71                 return NULL;
  72         }
  73         for( i = 0; i < size; i++ ) {
  74                 hashtable->table[i] = NULL;
  75         }
  76
  77         hashtable->size = size;
  78
  79         return hashtable;
  80 }
  81
  82 /**************************************************************************//**
  83  * Hash a string for a particular hash table.
  84  *
  85  * Initialize the list supplied to be empty.
  86  *
  87  * @param   hashtable    Pointer to the hashtable
  88  * @param   key          String
  89
  90  * @returns hashvalue
  91 ******************************************************************************/
  92 size_t ht_hash( HASHTABLE_T *hashtable, char *key )
  93 {
  94
  95     size_t hash, i;
  96
  97 #ifdef HASHTABLE_USE_SIMPLE_HASH
  98     for ( hash = i = 0; i < strlen(key); hash = hash << 8, hash += key[ i++ ] );
  99 #else /* Use: Jenkins' "One At a Time Hash" === Perl "Like" Hashing */
 100     // http://en.wikipedia.org/wiki/Jenkins_hash_function
 101     for ( hash = i = 0; i < strlen(key); ++i ) {
 102         hash += key[i], hash += ( hash << 10 ), hash ^= ( hash >> 6 );
 103     }
 104     hash += ( hash << 3 ), hash ^= ( hash >> 11 ), hash += ( hash << 15 );
 105 #endif
 106
 107     return hash % hashtable->size;
 108
 109 }
 110
 111 /**************************************************************************//**
 112  * Create a key-value pair.
 113  *
 114  * @param   key     key string
 115  * @param   value   value string
 116  *
 117  * @returns hashtable entry
 118 ******************************************************************************/
 119 ENTRY_T *ht_newpair( char *key, void *value )
 120 {
 121         ENTRY_T *newpair;
 122
 123         if( ( newpair = malloc( sizeof( ENTRY_T ) ) ) == NULL ) {
 124                 return NULL;
 125         }
 126
 127         if( ( newpair->key = strdup( key ) ) == NULL ) {
 128                 return NULL;
 129         }
 130
 131         if( ( newpair->value =  value ) == NULL ) {
 132                 return NULL;
 133         }
 134
 135         newpair->next = NULL;
 136
 137         return newpair;
 138 }
 139
 140 /**************************************************************************//**
 141  * Insert a key-value pair into a hash table.
 142  *
 143  * @param   key     key string
 144  * @param   value   value string
 145  *
 146  * @returns Nothing
 147 ******************************************************************************/
 148 void ht_set( HASHTABLE_T *hashtable, char *key, void *value ) {
 149         size_t bin = 0;
 150         ENTRY_T *newpair = NULL;
 151         ENTRY_T *next = NULL;
 152         ENTRY_T *last = NULL;
 153
 154         bin = ht_hash( hashtable, key );
 155
 156         next = hashtable->table[ bin ];
 157
 158         while( next != NULL && next->key != NULL && strcmp( key, next->key ) > 0 ) {
 159                 last = next;
 160                 next = next->next;
 161         }
 162
 163         /* There's already a pair.  Let's replace that string. */
 164         if( next != NULL && next->key != NULL && strcmp( key, next->key ) == 0 ) {
 165
 166                 free( next->value );
 167                 next->value = value ;
 168
 169         /* Nope, could't find it.  Time to grow a pair. */
 170         } else {
 171                 newpair = ht_newpair( key, value );
 172
 173                 /* We're at the start of the linked list in this bin. */
 174                 if( next == hashtable->table[ bin ] ) {
 175                         newpair->next = next;
 176                         hashtable->table[ bin ] = newpair;
 177
 178                 /* We're at the end of the linked list in this bin. */
 179                 } else if ( next == NULL ) {
 180                         last->next = newpair;
 181
 182                 /* We're in the middle of the list. */
 183                 } else  {
 184                         newpair->next = next;
 185                         last->next = newpair;
 186                 }
 187         }
 188 }
 189
 190 /**************************************************************************//**
 191  *  Retrieve a key-value pair from a hash table.
 192  *
 193  * @param   key     key string
 194  *
 195  * @returns  value string
 196 ******************************************************************************/
 197 void *ht_get( HASHTABLE_T *hashtable, char *key ) {
 198         size_t bin = 0;
 199         ENTRY_T *pair;
 200
 201         bin = ht_hash( hashtable, key );
 202
 203         /* Step through the bin, looking for our value. */
 204         pair = hashtable->table[ bin ];
 205         while( pair != NULL && pair->key != NULL && strcmp( key, pair->key ) > 0 ) {
 206                 pair = pair->next;
 207         }
 208
 209         /* Did we actually find anything? */
 210         if( pair == NULL || pair->key == NULL || strcmp( key, pair->key ) != 0 ) {
 211                 return NULL;
 212
 213         } else {
 214                 return pair->value;
 215         }
 216
 217 }
 218
 219 /*
 220 int main( int argc, char **argv ) {
 221
 222         HASHTABLE_T *hashtable = ht_create( 65536 );
 223
 224         ht_set( hashtable, "key1", "inky" );
 225         ht_set( hashtable, "key2", "pinky" );
 226         ht_set( hashtable, "key3", "blinky" );
 227         ht_set( hashtable, "key4", "floyd" );
 228
 229         printf( "%s\n", ht_get( hashtable, "key1" ) );
 230         printf( "%s\n", ht_get( hashtable, "key2" ) );
 231         printf( "%s\n", ht_get( hashtable, "key3" ) );
 232         printf( "%s\n", ht_get( hashtable, "key4" ) );
 233
 234         return 0;
 235 }
 236 */