1 /**************************************************************************//**
5 * @note No thread protection so you will need to use appropriate
6 * synchronization if use spans multiple threads.
11 * Copyright(c) <2016>, AT&T Intellectual Property. All other rights reserved.
13 * Redistribution and use in source and binary forms, with or without
14 * modification, are permitted provided that the following conditions are met:
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.
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 *****************************************************************************/
45 #include "hashtable.h"
47 /**************************************************************************//**
48 * Hashtable initialization.
50 * Initialize the list supplied to be empty.
52 * @param size Size of hashtable
54 * @returns Hashtable pointer
55 ******************************************************************************/
56 /* Create a new hashtable. */
57 HASHTABLE_T *ht_create( size_t size ) {
59 HASHTABLE_T *hashtable = NULL;
62 if( size < 1 ) return NULL;
64 /* Allocate the table itself. */
65 if( ( hashtable = malloc( sizeof( HASHTABLE_T ) ) ) == NULL ) {
69 /* Allocate pointers to the head nodes. */
70 if( ( hashtable->table = malloc( sizeof( ENTRY_T * ) * size ) ) == NULL ) {
73 for( i = 0; i < size; i++ ) {
74 hashtable->table[i] = NULL;
77 hashtable->size = size;
82 /**************************************************************************//**
83 * Hash a string for a particular hash table.
85 * Initialize the list supplied to be empty.
87 * @param hashtable Pointer to the hashtable
91 ******************************************************************************/
92 size_t ht_hash( HASHTABLE_T *hashtable, char *key )
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 );
104 hash += ( hash << 3 ), hash ^= ( hash >> 11 ), hash += ( hash << 15 );
107 return hash % hashtable->size;
111 /**************************************************************************//**
112 * Create a key-value pair.
114 * @param key key string
115 * @param value value string
117 * @returns hashtable entry
118 ******************************************************************************/
119 ENTRY_T *ht_newpair( char *key, void *value )
123 if( ( newpair = malloc( sizeof( ENTRY_T ) ) ) == NULL ) {
127 if( ( newpair->key = strdup( key ) ) == NULL ) {
131 if( ( newpair->value = value ) == NULL ) {
135 newpair->next = NULL;
140 /**************************************************************************//**
141 * Insert a key-value pair into a hash table.
143 * @param key key string
144 * @param value value string
147 ******************************************************************************/
148 void ht_set( HASHTABLE_T *hashtable, char *key, void *value ) {
150 ENTRY_T *newpair = NULL;
151 ENTRY_T *next = NULL;
152 ENTRY_T *last = NULL;
154 bin = ht_hash( hashtable, key );
156 next = hashtable->table[ bin ];
158 while( next != NULL && next->key != NULL && strcmp( key, next->key ) > 0 ) {
163 /* There's already a pair. Let's replace that string. */
164 if( next != NULL && next->key != NULL && strcmp( key, next->key ) == 0 ) {
167 next->value = value ;
169 /* Nope, could't find it. Time to grow a pair. */
171 newpair = ht_newpair( key, value );
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;
178 /* We're at the end of the linked list in this bin. */
179 } else if ( next == NULL ) {
180 last->next = newpair;
182 /* We're in the middle of the list. */
184 newpair->next = next;
185 last->next = newpair;
190 /**************************************************************************//**
191 * Retrieve a key-value pair from a hash table.
193 * @param key key string
195 * @returns value string
196 ******************************************************************************/
197 void *ht_get( HASHTABLE_T *hashtable, char *key ) {
201 bin = ht_hash( hashtable, key );
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 ) {
209 /* Did we actually find anything? */
210 if( pair == NULL || pair->key == NULL || strcmp( key, pair->key ) != 0 ) {
220 int main( int argc, char **argv ) {
222 HASHTABLE_T *hashtable = ht_create( 65536 );
224 ht_set( hashtable, "key1", "inky" );
225 ht_set( hashtable, "key2", "pinky" );
226 ht_set( hashtable, "key3", "blinky" );
227 ht_set( hashtable, "key4", "floyd" );
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" ) );