1 /*************************************************************************//**
3 * Copyright © 2017 AT&T Intellectual Property. All rights reserved.
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
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.
17 * ECOMP is a trademark and service mark of AT&T Intellectual Property.
18 ****************************************************************************/
19 /**************************************************************************//**
23 * @note No thread protection so you will need to use appropriate
24 * synchronization if use spans multiple threads.
26 ****************************************************************************/
33 #include "hashtable.h"
35 /**************************************************************************//**
36 * Hashtable initialization.
38 * Initialize the list supplied to be empty.
40 * @param size Size of hashtable
42 * @returns Hashtable pointer
43 ******************************************************************************/
44 /* Create a new hashtable. */
45 HASHTABLE_T *ht_create( size_t size ) {
47 HASHTABLE_T *hashtable = NULL;
50 if( size < 1 ) return NULL;
52 /* Allocate the table itself. */
53 if( ( hashtable = malloc( sizeof( HASHTABLE_T ) ) ) == NULL ) {
57 /* Allocate pointers to the head nodes. */
58 if( ( hashtable->table = malloc( sizeof( ENTRY_T * ) * size ) ) == NULL ) {
61 for( i = 0; i < size; i++ ) {
62 hashtable->table[i] = NULL;
65 hashtable->size = size;
70 /**************************************************************************//**
71 * Hash a string for a particular hash table.
73 * Initialize the list supplied to be empty.
75 * @param hashtable Pointer to the hashtable
79 ******************************************************************************/
80 size_t ht_hash( HASHTABLE_T *hashtable, char *key )
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 );
92 hash += ( hash << 3 ), hash ^= ( hash >> 11 ), hash += ( hash << 15 );
95 return hash % hashtable->size;
99 /**************************************************************************//**
100 * Create a key-value pair.
102 * @param key key string
103 * @param value value string
105 * @returns hashtable entry
106 ******************************************************************************/
107 ENTRY_T *ht_newpair( char *key, void *value )
111 if( ( newpair = malloc( sizeof( ENTRY_T ) ) ) == NULL ) {
115 if( ( newpair->key = strdup( key ) ) == NULL ) {
119 if( ( newpair->value = value ) == NULL ) {
123 newpair->next = NULL;
128 /**************************************************************************//**
129 * Insert a key-value pair into a hash table.
131 * @param key key string
132 * @param value value string
135 ******************************************************************************/
136 void ht_set( HASHTABLE_T *hashtable, char *key, void *value ) {
138 ENTRY_T *newpair = NULL;
139 ENTRY_T *next = NULL;
140 ENTRY_T *last = NULL;
142 bin = ht_hash( hashtable, key );
144 next = hashtable->table[ bin ];
146 while( next != NULL && next->key != NULL && strcmp( key, next->key ) > 0 ) {
151 /* There's already a pair. Let's replace that string. */
152 if( next != NULL && next->key != NULL && strcmp( key, next->key ) == 0 ) {
155 next->value = value ;
157 /* Nope, could't find it. Time to grow a pair. */
159 newpair = ht_newpair( key, value );
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;
166 /* We're at the end of the linked list in this bin. */
167 } else if ( next == NULL ) {
168 last->next = newpair;
170 /* We're in the middle of the list. */
172 newpair->next = next;
173 last->next = newpair;
178 /**************************************************************************//**
179 * Retrieve a key-value pair from a hash table.
181 * @param key key string
183 * @returns value string
184 ******************************************************************************/
185 void *ht_get( HASHTABLE_T *hashtable, char *key ) {
189 bin = ht_hash( hashtable, key );
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 ) {
197 /* Did we actually find anything? */
198 if( pair == NULL || pair->key == NULL || strcmp( key, pair->key ) != 0 ) {
208 int main( int argc, char **argv ) {
210 HASHTABLE_T *hashtable = ht_create( 65536 );
212 ht_set( hashtable, "key1", "inky" );
213 ht_set( hashtable, "key2", "pinky" );
214 ht_set( hashtable, "key3", "blinky" );
215 ht_set( hashtable, "key4", "floyd" );
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" ) );