summaryrefslogtreecommitdiff
path: root/src/hash.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/hash.c')
-rwxr-xr-xsrc/hash.c665
1 files changed, 0 insertions, 665 deletions
diff --git a/src/hash.c b/src/hash.c
deleted file mode 100755
index a8076ae..0000000
--- a/src/hash.c
+++ /dev/null
@@ -1,665 +0,0 @@
-/************************************************************************
- hash.c - This module maintains a hash table of key/value pairs.
- Keys can be strings of any size, or numbers up to size
- unsigned long (HASHKEYTYPE).
- Values should be a pointer to some data you wish to store.
- See hash_usage() for an example of use.
- ************************************************************************/
-
-#include <stdlib.h>
-#include <stdio.h>
-#include <stdarg.h>
-#include <string.h>
-#include <time.h>
-#include <stdarg.h>
-
-#include "hash.h"
-
-// Enums
-typedef enum {FindEmpty = 0, FindExisting = 1} enumFind;
-
-// Structs
-struct ROW
-{
- HASHKEYTYPE Key;
- int Type;
- void * Data;
-};
-
-struct HASHTABLE_T
-{
- int KeyIsString;
- unsigned long MaxLoad;
- unsigned long MaxRows;
- unsigned long ItemCount;
- struct ROW *Rows;
-};
-
-// Function prototypes
-static void hash_expand(HASHTABLE OldTable);
-
-// Current module name (used by error processing)
-static char *module = "hash";
-
-// Error list
-static const char *ERR_MUST_CREATE_HASH_TABLE_FIRST = "You must create the hash table before using it!";
-static const char *ERR_NOT_STRING_TABLE = "Not a string hash table!";
-
-// Deleted entry indicator
-static const int Empty = 0x00000000;
-static const int InUse = 0x11111111;
-static const int Deleted = 0xffffffff;
-
-// Expand the table when the usage exceeds this amount (80%)
-static double LoadFactor = 0.8;
-
-
-/************************************************************************
- ExitEarly - Quit the program early
- ************************************************************************/
-static void ExitEarly(const char *strModule, const char *strFunction, const char *errmsg, ...)
-{
- va_list args;
- fprintf(stderr, "Error in module %s, function %s: ", strModule, strFunction);
- va_start(args, errmsg);
- vfprintf(stderr, errmsg, args);
- va_end(args);
- exit(1);
-}
-
-/************************************************************************
- hash1 - Calculate a hash value for the desired key
- ************************************************************************/
-static HASHKEYTYPE hash1(HASHKEYTYPE Key, BOOL KeyIsString)
-{
-
- if (!KeyIsString)
- {
- return Key;
- }
- else
- {
- unsigned char *s = (unsigned char *)Key;
- HASHKEYTYPE h = 0;
- while (*s)
- h = h * 31UL + *s++;
- return h ;
- }
-}
-
-/************************************************************************
- hash2 - Calculate a secondary hash value for the desired key
- ************************************************************************/
-static HASHKEYTYPE hash2(HASHKEYTYPE Key, BOOL KeyIsString)
-{
- return hash1(Key, KeyIsString) >> 3;
-}
-
-/************************************************************************
- NextPrime - Return the next prime number past a certain number.
- ************************************************************************/
-static unsigned long NextPrime(unsigned long NumberDesired)
-{
- unsigned long i;
- unsigned long HalfwayPoint;
- int IsDivisible ;
-
- do
- {
- NumberDesired++;
- IsDivisible = FALSE;
- HalfwayPoint = NumberDesired / 2;
- for (i = 2; i <= HalfwayPoint; i++)
- {
- if (NumberDesired % i == 0)
- {
- IsDivisible = TRUE;
- break;
- }
- }
- } while (IsDivisible);
-
- return NumberDesired;
-
-};
-
-/************************************************************************
- hash_create - Create a new hash table
- ************************************************************************/
-HASHTABLE hash_create(unsigned long InitialSize, BOOL KeyIsString)
-{
- HASHTABLE table;
-
- // Allocate space for the hash table.
- table = malloc(sizeof(*table));
- memset( table, 0, sizeof(*table) );
-
- // Minimum size of hash table is 8.
- if (InitialSize < 8 )
- InitialSize = 8;
-
- // Allocate it large enough so that it's not more than 80% full.
- InitialSize = (unsigned long)(InitialSize * 1.25);
-
- // Allocate space for the rows in the hash table
- InitialSize = NextPrime(InitialSize);
- table->MaxLoad = (unsigned long)(InitialSize * LoadFactor);
- table->MaxRows = InitialSize;
- table->Rows = malloc(InitialSize * sizeof(struct ROW));
- table->KeyIsString = KeyIsString;
-
- memset( table->Rows, 0, InitialSize * sizeof(struct ROW) );
-
-
- return table;
-
-}
-
-
-/************************************************************************
- hash_destroy - Destroy a hash table.
- ************************************************************************/
-HASHTABLE hash_destroy(HASHTABLE table)
-{
- char *function = "hash_destroy";
-
- // Make sure the table is valid
- if (table == NULL)
- ExitEarly(module, function, ERR_MUST_CREATE_HASH_TABLE_FIRST);
-
- // Free the rows in the table
- free(table->Rows);
-
- // Free the table itself
- free(table);
-
- // Return NULL
- return NULL;
-}
-
-
-/************************************************************************
- FindSlot - Find a slot in the hash table, either empty or existing.
- ************************************************************************/
-static int FindSlot(HASHTABLE table, HASHKEYTYPE Key, int FindMethod, HASHKEYTYPE *Slot)
-{
- char *function = "FindSlot";
- HASHKEYTYPE hash = 0;
- unsigned long i;
- HASHKEYTYPE AddlAmt = 0;
-
- // Hash the key.
- hash = (HASHKEYTYPE)(hash1(Key, table->KeyIsString) % table->MaxRows);
-
- // Perform the lookup a maximum of MaxRows times.
- for (i = 0; i < table->MaxRows; i++)
- {
- // Are we supposed to find an empty slot or look for an existing key?
- if (FindMethod == FindExisting)
- {
- // Look for an existing key
- if (table->Rows[hash].Type == Empty)
- {
- // Couldn't find the key
- return FALSE;
- }
- else if (table->Rows[hash].Type == InUse &&
- ( (table->KeyIsString && strcmp((char *)table->Rows[hash].Key, (char *)Key) == 0) ||
- (!table->KeyIsString && table->Rows[hash].Key == Key) ) )
-
- {
- // Found the key
- *Slot = hash;
- return TRUE;
- }
- }
- else
- {
- // Look for an empty slot to insert the new key into
- if (table->Rows[hash].Type != InUse)
- {
- // Found a spot
- *Slot = hash;
- return TRUE;
- }
- else if ( (table->KeyIsString && strcmp((char *)table->Rows[hash].Key, (char *)Key) == 0) ||
- (!table->KeyIsString && table->Rows[hash].Key == Key) )
- {
- // Key already exists!
- return FALSE;
- }
- }
-
- // Rehash the hash and try again.
- if (AddlAmt == 0)
- AddlAmt = (HASHKEYTYPE)(hash2(Key, table->KeyIsString) % (table->MaxRows >> 3) + 1);
- hash = (hash + AddlAmt) % table->MaxRows;
-
- }
-
- // Searched the whole table unsuccessfully! :-O
- // Should never hit this point, because the table expands when it gets too full.
- ExitEarly(module, function, "Findslot failed!");
- return FALSE;
-}
-
-
-/************************************************************************
- hash_add - Add an item to a hash table.
- ************************************************************************/
-BOOL hash_add(HASHTABLE table, HASHKEYTYPE Key, const void *Data)
-{
- char *function = "hash_add";
- HASHKEYTYPE position;
-
- if (table == NULL)
- ExitEarly(module, function, ERR_MUST_CREATE_HASH_TABLE_FIRST);
-
- // Do not let the table become overloaded
- if (table->ItemCount > table->MaxLoad)
- hash_expand(table);
-
- // Search for an empty slot
- if (FindSlot(table, Key, FindEmpty, &position))
- {
- // Insert the data into the table.
- table->Rows[position].Key = Key;
- table->Rows[position].Type = InUse;
- table->Rows[position].Data = (void *)Data;
- table->ItemCount++;
- return TRUE;
- }
- else
- {
- // The entry already exists!
- return FALSE;
- }
-}
-
-
-/************************************************************************
- hash_addstring - Add an string to a hash table.
- ************************************************************************/
-BOOL hash_addstring(HASHTABLE table, char * Key, const void * Data)
-{
- char *function = "hash_addstring";
-
- if (table == NULL)
- ExitEarly(module, function, ERR_MUST_CREATE_HASH_TABLE_FIRST);
- if (table->KeyIsString == FALSE)
- ExitEarly(module, function, ERR_NOT_STRING_TABLE);
- return hash_add(table, (HASHKEYTYPE)Key, Data);
-}
-
-/************************************************************************
- hash_remove - Remove an item from a hash table.
- ************************************************************************/
-void *hash_remove(HASHTABLE table, HASHKEYTYPE Key)
-{
- char *function = "hash_remove";
- void *Data;
- unsigned int position;
-
- if (table == NULL)
- ExitEarly(module, function, ERR_MUST_CREATE_HASH_TABLE_FIRST);
-
- if (FindSlot(table, Key, FindExisting, &position))
- {
- // Found the item, now mark it as deleted.
- Data = table->Rows[position].Data;
- table->Rows[position].Key = 0;
- table->Rows[position].Type = Deleted;
- table->Rows[position].Data = 0;
- table->ItemCount--;
- return Data;
- }
- else
- {
- // Couldn't find the item to remove it.
- return NULL;
- }
-}
-
-/************************************************************************
- hash_lookup - Lookup an item from a hash table.
- ************************************************************************/
-void *hash_lookup(HASHTABLE table, HASHKEYTYPE Key)
-{
- char *function = "hash_lookup";
- HASHKEYTYPE position;
-
- if (table == NULL)
- ExitEarly(module, function, ERR_MUST_CREATE_HASH_TABLE_FIRST);
-
- if (FindSlot(table, Key, FindExisting, &position))
- return table->Rows[position].Data;
- else
- return NULL;
-}
-
-/************************************************************************
- hash_exists - Returns whether or not a key exists in the table.
- ************************************************************************/
-BOOL hash_exists(HASHTABLE table, HASHKEYTYPE Key)
-{
- char *function = "hash_lookup";
- HASHKEYTYPE position;
-
- if (table == NULL)
- ExitEarly(module, function, ERR_MUST_CREATE_HASH_TABLE_FIRST);
-
- if (FindSlot(table, Key, FindExisting, &position))
- return TRUE;
- else
- return FALSE;
-}
-
-/************************************************************************
- hash_count - Return a count of all items in the hash table
- ************************************************************************/
-extern size_t hash_count(HASHTABLE table)
-{
- char *function = "hash_count";
- if (table == NULL)
- ExitEarly(module, function, ERR_MUST_CREATE_HASH_TABLE_FIRST);
-
- return table->ItemCount;
-}
-
-/************************************************************************
- hash_expand - Expand the hash table to accommodate more entries.
- ************************************************************************/
-static void hash_expand(HASHTABLE OldTable)
-{
- HASHTABLE NewTable;
- unsigned long i;
-
- // Create a new temporary table
- NewTable = hash_create(OldTable->MaxRows * 2, OldTable->KeyIsString);
-
- // Add the data from the old table into the new table
- for (i = 0; i < OldTable->MaxRows; i++)
- {
- if (OldTable->Rows[i].Type == InUse)
- hash_add(NewTable, OldTable->Rows[i].Key, OldTable->Rows[i].Data);
- }
-
- // Free the old table rows
- free(OldTable->Rows);
-
- // Overlay the old table values with the temporary table values.
- OldTable->MaxRows = NewTable->MaxRows;
- OldTable->MaxLoad = NewTable->MaxLoad;
- OldTable->ItemCount = NewTable->ItemCount;
- OldTable->Rows = NewTable->Rows;
-
- // Destroy the temporary table
- NewTable->Rows = NULL;
- free(NewTable);
-}
-
-/************************************************************************
- hash_search - Search for an item in the hashtable.
- ************************************************************************/
-extern void *hash_search(HASHTABLE table, BOOL (*Search)(HASHKEYTYPE key, void *, va_list), ...)
-{
- va_list args;
- unsigned int i;
- void *p = NULL;
-
- va_start(args, Search);
- for (i = 0; i < table->MaxRows; i++)
- {
- if (table->Rows[i].Type != Deleted &&
- table->Rows[i].Type != Empty)
- {
- if (Search(table->Rows[i].Key, table->Rows[i].Data, args) != FALSE)
- {
- p = table->Rows[i].Data;
- break;
- }
- }
- }
- va_end(args);
- return p;
-}
-
-/************************************************************************
- hash_searchwithvalist - Search for an item in the hashtable.
- A va_list has already been passed in, no need to extract one.
- ************************************************************************/
-extern void *hash_searchwithvalist(HASHTABLE table, BOOL (*Search)(HASHKEYTYPE key, void *, va_list), va_list args)
-{
- unsigned int i;
- void *p = NULL;
-
- for (i = 0; i < table->MaxRows; i++)
- {
- if (table->Rows[i].Type != Deleted &&
- table->Rows[i].Type != Empty)
- {
- if (Search(table->Rows[i].Key, table->Rows[i].Data, args) != FALSE)
- {
- p = table->Rows[i].Data;
- break;
- }
- }
- }
- return p;
-}
-
-/************************************************************************
- * hash_usage - Example of how to use this module.
- ************************************************************************/
-struct person_t
-{
- int ID;
- char Name[32];
- int Age;
-};
-
-extern void hash_usage(void)
-{
- void *table;
- struct person_t *p;
- struct person_t *lookup;
- char *StringKey = "Lloyd";
- int NumberKey = 1234567;
-
- // Create some data to store
- p = malloc(sizeof(*p));
- memset ( p, 0 ,sizeof( *p));
- p->ID = NumberKey;
- p->Age = 20;
- sprintf(p->Name, StringKey);
-
- // Numeric hash example
-
- // Create the hash table
- table = hash_create(10, FALSE);
-
- // Add a key/value pair to the table
- if (hash_add(table, p->ID, p) == FALSE)
- printf("Entry already exists!");
-
- // Lookup a key/value pair in the table
- if ((lookup = hash_lookup(table, NumberKey)) == FALSE)
- printf("Entry not found!");
- else
- printf("Person found by ID: %d. Name is: %s\n", lookup->ID, lookup->Name);
-
- // Remove a key/value pair from the table
- if ((lookup = hash_remove(table, NumberKey)) == FALSE)
- printf("Entry not found!");
- else
- // you COULD free lookup here, but we're not done with it.
- ;
-
- // Free the table.
- table = hash_destroy(table);
-
-
- // String hash example
-
- // Create the hash table
- table = hash_create(10, TRUE);
-
- // Add a key/value pair to the table
- if (hash_add(table, (HASHKEYTYPE)p->Name, p) == FALSE)
- printf("Entry already exists!");
-
- // Lookup a key/value pair in the table
- if ((lookup = hash_lookup(table, (HASHKEYTYPE)StringKey)) == FALSE)
- printf("Entry not found!");
- else
- printf("Person found by name: %s. ID is: %d\n", lookup->Name, lookup->ID);
-
- // Remove a key/value pair from the table
- if ((lookup = hash_remove(table, (HASHKEYTYPE)StringKey)) == FALSE)
- printf("Entry not found!");
- else
- free(lookup);
-
- // Free the table.
- table = hash_destroy(table);
-}
-
-/************************************************************************
- hash_test - Test the hash table.
- ************************************************************************/
-static BOOL Search(HASHKEYTYPE key, void *p, va_list args)
-{
- char *s = p;
- char *find = va_arg(args, char *);
- if (strcmp(s, find) == 0)
- return TRUE;
- else
- return FALSE;
-}
-
-static BOOL Iterate(HASHKEYTYPE key, void *p, va_list args)
-{
- // Just iterate a counter.
- unsigned int *i = va_arg(args, unsigned int *);
- *i = *i + 1;
- // Return false to keep searching.
- return FALSE;
-}
-
-extern BOOL hash_test(void)
-{
- HASHTABLE table;
- HASHTABLE strings;
- int i;
- int max = 1000000;
- clock_t start;
- char **s;
- char temp[80];
- char *fmt = "\t%-8s %4d milliseconds, %8d per second.\n";
- unsigned int ctr = 0;
-
- // Logical tests
- table = hash_create(8, FALSE);
- if (hash_add(table, 0, &table) == FALSE) return FALSE;
- if (hash_add(table, 1, &table) == FALSE) return FALSE;
- if (hash_add(table, 0xffffffff, &table) == FALSE) return FALSE;
-
- strings = hash_create(8, TRUE);
- if (hash_add(strings, (HASHKEYTYPE)"test1", &strings) == FALSE) return FALSE;
- if (hash_add(strings, (HASHKEYTYPE)"test2", &strings) == FALSE) return FALSE;
- if (hash_add(strings, (HASHKEYTYPE)"test3", &strings) == FALSE) return FALSE;
-
- if (hash_lookup(table, 0) != &table) return FALSE;
- if (hash_lookup(table, 1) != &table) return FALSE;
- if (hash_lookup(table, 0xffffffff) != &table) return FALSE;
-
- if (hash_lookup(strings, (HASHKEYTYPE)"test1") != &strings) return FALSE;
- if (hash_lookup(strings, (HASHKEYTYPE)"test2") != &strings) return FALSE;
- if (hash_lookup(strings, (HASHKEYTYPE)"test3") != &strings) return FALSE;
-
- if (hash_remove(strings, (HASHKEYTYPE)"test1") != &strings) return FALSE;
- if (hash_lookup(strings, (HASHKEYTYPE)"test1") != FALSE) return FALSE;
-
- if (hash_destroy(table) != NULL) return FALSE;
- if (hash_destroy(strings) != NULL) return FALSE;
-
-
- // Stress tests for numbers
- printf("HASH Numeric Tests for %d items\n", max);
- table = hash_create(max, FALSE);
-
- start = clock();
- for (i = 0; i < max; i++)
- hash_add(table, i, &table);
- printf(fmt, "Adds:", clock() - start, (max * CLOCKS_PER_SEC)/(clock() - start));
-
- start = clock();
- for (i = 0; i < max; i++)
- if (hash_lookup(table, i) != &table)
- break;
- printf(fmt, "Lookups:", clock() - start, (max * CLOCKS_PER_SEC)/(clock() - start));
-
- start = clock();
- for (i = 0; i < max; i++)
- if (hash_remove(table, i) != &table)
- break;
- printf(fmt, "Deletes:", clock() - start, (max * CLOCKS_PER_SEC)/(clock() - start));
- if (hash_count(table) != 0)
- return FALSE;
- table = hash_destroy(table);
-
- // Stress tests for strings
- printf("HASH strings Tests for %d items\n", max);
- table = hash_create(max, TRUE);
- s = malloc(sizeof(*s) * max);
- memset ( s, 0 ,sizeof( *s)*max);
-
- for (i = 0; i < max; i++)
- {
- sprintf(temp, "Item %d", i);
- s[i] = strdup(temp);
- }
-
- start = clock();
- for (i = 0; i < max; i++)
- hash_add(table, (HASHKEYTYPE)s[i], s[i]);
- printf(fmt, "Adds:", clock() - start, (max * CLOCKS_PER_SEC)/(clock() - start));
-
- start = clock();
- for (i = 0; i < max; i++)
- if (hash_lookup(table, (HASHKEYTYPE)s[i]) != s[i])
- break;
- printf(fmt, "Lookups:", clock() - start, (max * CLOCKS_PER_SEC)/(clock() - start));
-
- // Test searching
- if (hash_search(table, Search, "Item 271") != s[271])
- return FALSE;
- if (hash_search(table, Search, "Not Found") != FALSE)
- return FALSE;
-
- // Test iterating
- ctr = 0;
- start = clock();
- hash_search(table, Iterate, &ctr);
- printf(fmt, "Iterate:", clock() - start, (max * CLOCKS_PER_SEC)/(clock() - start));
- printf("\t\t(Ctr is %u)\n", ctr);
-
- // Test deleting
- start = clock();
- for (i = 0; i < max; i++)
- if (hash_remove(table, (HASHKEYTYPE)s[i]) != s[i])
- break;
- printf(fmt, "Deletes:", clock() - start, (max * CLOCKS_PER_SEC)/(clock() - start));
- if (hash_count(table) != 0)
- return FALSE;
- table = hash_destroy(table);
-
- // Free the test strings
- for (i = 0; i < max; i++)
- free(s[i]);
-
-
- return TRUE;
-}
-
-
generated by cgit v1.1 at 2024-07-06 00:46:08 +0000