Skip to content

Instantly share code, notes, and snippets.

@mitul1208

mitul1208/hash.c

Forked from tonious/hash.c
Created July 12, 2016 15:37
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save mitul1208/b86779bcda385d8e397a9aadaa151c84 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save mitul1208/b86779bcda385d8e397a9aadaa151c84 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. @tonious tonious revised this gist Nov 18, 2011. 1 changed file with 3 additions and 3 deletions.
    6 changes: 3 additions & 3 deletions hash.c
    View file
    Original file line number Diff line number Diff line change
    @@ -1,10 +1,10 @@
    #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>

    #define _XOPEN_SOURCE 500 /* Enable certain library functions (strdup) on linux. See feature_test_macros(7) */

    struct entry_s {
    char *key;
    char *value;
    @@ -166,4 +166,4 @@ int main( int argc, char **argv ) {
    printf( "%s\n", ht_get( hashtable, "key4" ) );

    return 0;
    }
    }
  2. @tonious tonious revised this gist Nov 18, 2011. 1 changed file with 2 additions and 0 deletions.
    2 changes: 2 additions & 0 deletions hash.c
    View file
    Original file line number Diff line number Diff line change
    @@ -3,6 +3,8 @@
    #include <limits.h>
    #include <string.h>

    #define _XOPEN_SOURCE 500 /* Enable certain library functions (strdup) on linux. See feature_test_macros(7) */

    struct entry_s {
    char *key;
    char *value;
  3. @tonious tonious revised this gist Nov 18, 2011. 1 changed file with 113 additions and 112 deletions.
    225 changes: 113 additions & 112 deletions hash.c
    View file
    Original file line number Diff line number Diff line change
    @@ -4,163 +4,164 @@
    #include <string.h>

    struct entry_s {
    char *key;
    char *value;
    struct entry_s *next;
    char *key;
    char *value;
    struct entry_s *next;
    };

    typedef struct entry_s entry_t;

    struct hashtable_s {
    int size;
    struct entry_s **table;
    int size;
    struct entry_s **table;
    };

    typedef struct hashtable_s hashtable_t;


    // Create a new hashtable.
    /* Create a new hashtable. */
    hashtable_t *ht_create( int size ) {

    hashtable_t *hashtable = NULL;
    int i;
    hashtable_t *hashtable = NULL;
    int i;

    if( size < 1 ) return NULL;
    if( size < 1 ) return NULL;

    // Allocate the table itself.
    if( ( hashtable = malloc( sizeof( hashtable_t ) ) ) == NULL ) {
    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;
    }
    /* 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;
    hashtable->size = size;

    return hashtable;
    return hashtable;
    }

    // Hash a string for a particular hash table.
    /* Hash a string for a particular hash table. */
    int ht_hash( hashtable_t *hashtable, char *key ) {

    unsigned long int hashval;
    int i = 0;
    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++;
    }
    /* Convert our string to an integer */
    while( hashval < ULONG_MAX && i < strlen( key ) ) {
    hashval = hashval << 8;
    hashval += key[ i ];
    i++;
    }

    return hashval % hashtable->size;
    return hashval % hashtable->size;
    }

    // Create a key-value pair.
    /* Create a key-value pair. */
    entry_t *ht_newpair( char *key, char *value ) {
    entry_t *newpair;
    entry_t *newpair;

    if( ( newpair = malloc( sizeof( entry_t ) ) ) == NULL ) {
    return NULL;
    }
    if( ( newpair = malloc( sizeof( entry_t ) ) ) == NULL ) {
    return NULL;
    }

    if( ( newpair->key = strdup( key ) ) == NULL ) {
    return NULL;
    }
    if( ( newpair->key = strdup( key ) ) == NULL ) {
    return NULL;
    }

    if( ( newpair->value = strdup( value ) ) == NULL ) {
    return NULL;
    }
    if( ( newpair->value = strdup( value ) ) == NULL ) {
    return NULL;
    }

    newpair->next = NULL;
    newpair->next = NULL;

    return newpair;
    return newpair;
    }

    // Insert a key-value pair into a hash table.
    /* 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;
    }
    }
    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.
    /* Retrieve a key-value pair from a hash table. */
    char *ht_get( hashtable_t *hashtable, char *key ) {
    int bin = 0;
    entry_t *pair;
    int bin = 0;
    entry_t *pair;

    bin = ht_hash( hashtable, key );
    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;
    }
    /* 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;
    /* Did we actually find anything? */
    if( pair == NULL || pair->key == NULL || strcmp( key, pair->key ) != 0 ) {
    return NULL;

    } else {
    return pair->value;
    }
    } else {
    return pair->value;
    }
    }


    int main( char *argc, char *argv ) {
    int main( int argc, char **argv ) {

    hashtable_t *hashtable = ht_create( 65536 );
    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" );
    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" ) );
    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;
    }
  4. @tonious tonious created this gist Nov 18, 2011.
    166 changes: 166 additions & 0 deletions hash.c
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,166 @@
    #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( char *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" ) );

    }