Last active
February 17, 2023 02:25
-
-
Save tonious/1377667 to your computer and use it in GitHub Desktop.
A quick hashtable implementation in c.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* Read this comment first: https://gist.github.com/tonious/1377667#gistcomment-2277101 | |
* 2017-12-05 | |
* | |
* -- T. | |
*/ | |
#define _XOPEN_SOURCE 500 /* Enable certain library functions (strdup) on linux. See feature_test_macros(7) */ | |
#include <stdlib.h> | |
#include <stdio.h> | |
#include <limits.h> | |
#include <string.h> | |
struct entry_s { | |
char *key; | |
char *value; | |
struct entry_s *next; | |
}; | |
typedef struct entry_s entry_t; | |
struct hashtable_s { | |
int size; | |
struct entry_s **table; | |
}; | |
typedef struct hashtable_s hashtable_t; | |
/* Create a new hashtable. */ | |
hashtable_t *ht_create( int size ) { | |
hashtable_t *hashtable = NULL; | |
int i; | |
if( size < 1 ) return NULL; | |
/* Allocate the table itself. */ | |
if( ( hashtable = malloc( sizeof( hashtable_t ) ) ) == NULL ) { | |
return NULL; | |
} | |
/* Allocate pointers to the head nodes. */ | |
if( ( hashtable->table = malloc( sizeof( entry_t * ) * size ) ) == NULL ) { | |
return NULL; | |
} | |
for( i = 0; i < size; i++ ) { | |
hashtable->table[i] = NULL; | |
} | |
hashtable->size = size; | |
return hashtable; | |
} | |
/* Hash a string for a particular hash table. */ | |
int ht_hash( hashtable_t *hashtable, char *key ) { | |
unsigned long int hashval; | |
int i = 0; | |
/* Convert our string to an integer */ | |
while( hashval < ULONG_MAX && i < strlen( key ) ) { | |
hashval = hashval << 8; | |
hashval += key[ i ]; | |
i++; | |
} | |
return hashval % hashtable->size; | |
} | |
/* Create a key-value pair. */ | |
entry_t *ht_newpair( char *key, char *value ) { | |
entry_t *newpair; | |
if( ( newpair = malloc( sizeof( entry_t ) ) ) == NULL ) { | |
return NULL; | |
} | |
if( ( newpair->key = strdup( key ) ) == NULL ) { | |
return NULL; | |
} | |
if( ( newpair->value = strdup( value ) ) == NULL ) { | |
return NULL; | |
} | |
newpair->next = NULL; | |
return newpair; | |
} | |
/* Insert a key-value pair into a hash table. */ | |
void ht_set( hashtable_t *hashtable, char *key, char *value ) { | |
int bin = 0; | |
entry_t *newpair = NULL; | |
entry_t *next = NULL; | |
entry_t *last = NULL; | |
bin = ht_hash( hashtable, key ); | |
next = hashtable->table[ bin ]; | |
while( next != NULL && next->key != NULL && strcmp( key, next->key ) > 0 ) { | |
last = next; | |
next = next->next; | |
} | |
/* There's already a pair. Let's replace that string. */ | |
if( next != NULL && next->key != NULL && strcmp( key, next->key ) == 0 ) { | |
free( next->value ); | |
next->value = strdup( value ); | |
/* Nope, could't find it. Time to grow a pair. */ | |
} else { | |
newpair = ht_newpair( key, value ); | |
/* We're at the start of the linked list in this bin. */ | |
if( next == hashtable->table[ bin ] ) { | |
newpair->next = next; | |
hashtable->table[ bin ] = newpair; | |
/* We're at the end of the linked list in this bin. */ | |
} else if ( next == NULL ) { | |
last->next = newpair; | |
/* We're in the middle of the list. */ | |
} else { | |
newpair->next = next; | |
last->next = newpair; | |
} | |
} | |
} | |
/* Retrieve a key-value pair from a hash table. */ | |
char *ht_get( hashtable_t *hashtable, char *key ) { | |
int bin = 0; | |
entry_t *pair; | |
bin = ht_hash( hashtable, key ); | |
/* Step through the bin, looking for our value. */ | |
pair = hashtable->table[ bin ]; | |
while( pair != NULL && pair->key != NULL && strcmp( key, pair->key ) > 0 ) { | |
pair = pair->next; | |
} | |
/* Did we actually find anything? */ | |
if( pair == NULL || pair->key == NULL || strcmp( key, pair->key ) != 0 ) { | |
return NULL; | |
} else { | |
return pair->value; | |
} | |
} | |
int main( int argc, char **argv ) { | |
hashtable_t *hashtable = ht_create( 65536 ); | |
ht_set( hashtable, "key1", "inky" ); | |
ht_set( hashtable, "key2", "pinky" ); | |
ht_set( hashtable, "key3", "blinky" ); | |
ht_set( hashtable, "key4", "floyd" ); | |
printf( "%s\n", ht_get( hashtable, "key1" ) ); | |
printf( "%s\n", ht_get( hashtable, "key2" ) ); | |
printf( "%s\n", ht_get( hashtable, "key3" ) ); | |
printf( "%s\n", ht_get( hashtable, "key4" ) ); | |
return 0; | |
} |
@tonious, I'm just seeing this reply! Man, thanks for this, it's working great after tweaking it just a bit, have had no complaints so far!
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
@fgl82, I just took a look at
simplemenu
, and I agree. This actually isn't a horrible solution for your purposes. It's still a horrible solution for all other purposes 😁.I'd recommend using a better hashing algorithm. perlboy-emeritus has a great comment on this. But that's a fine stroke, and won't matter in your use case.
FWIW, I have a gameboy zero build that I really like, but emulation station really is too heavy for the way I use it. I can't wait to see how
simplemenu
turns out.