Mercurial > cgi-bin > hgwebdir.cgi > VMS > C_Libraries > Hash_impl
changeset 0:ee3ad252427e
Initial add
author | Me |
---|---|
date | Sat, 22 May 2010 19:49:28 -0700 |
parents | |
children | 5900d90f5d71 |
files | PrivateHash.c PrivateHash.h |
diffstat | 2 files changed, 284 insertions(+), 0 deletions(-) [+] |
line diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/PrivateHash.c Sat May 22 19:49:28 2010 -0700 1.3 @@ -0,0 +1,224 @@ 1.4 +/* 1.5 + * Copyright 2009 OpenSourceCodeStewardshipFoundation.org 1.6 + * Licensed under GNU General Public License version 2 1.7 + * 1.8 + * NOTE: this version of SRSW correct as of April 25, 2010 1.9 + * 1.10 + * Author: seanhalle@yahoo.com 1.11 + */ 1.12 + 1.13 + 1.14 +#include <stdio.h> 1.15 +#include <string.h> 1.16 +#include <errno.h> 1.17 +#include <stdlib.h> 1.18 + 1.19 +#include "PrivateHash.h" 1.20 + 1.21 + 1.22 + HashTable * 1.23 +makeHashTable( int numHashSlots, FreeEntryContentFnPtr freeFn ) 1.24 + { HashTable * retTable; 1.25 + retTable = malloc( sizeof( HashTable ) ); 1.26 + 1.27 + retTable->freeEntryContentFn = freeFn; 1.28 + 1.29 + retTable->entries = malloc( numHashSlots * sizeof(HashEntry *) ); 1.30 + retTable->tableSz = numHashSlots; 1.31 + 1.32 + nullOutTablesArray( retTable ); 1.33 + 1.34 + return retTable; 1.35 + } 1.36 + 1.37 + void 1.38 +doubleTableSize( HashTable *table ) 1.39 + { int i, oldTableSz, newTableSz; 1.40 + HashEntry *entry, **oldEntries, **newEntries; 1.41 + 1.42 + oldTableSz = table->tableSz; 1.43 + oldEntries = table->entries; 1.44 + 1.45 + newTableSz = 2 * oldTableSz + 1; 1.46 + newEntries = malloc( newTableSz * sizeof(HashEntry *) ); 1.47 + 1.48 + table->tableSz = newTableSz; 1.49 + table->entries = newEntries; 1.50 + table->numEntries = 0; //about to add them all back! 1.51 + 1.52 + // move all the entries from old to new 1.53 + for( i=0; i < oldTableSz; i++ ) 1.54 + { if( oldEntries[i] != NULL ) 1.55 + { entry = oldEntries[i]; 1.56 + while( entry != NULL ) 1.57 + { 1.58 + addEntryToTable( entry, table ); //does not allocate anything 1.59 + entry = entry->next; 1.60 + } 1.61 + } 1.62 + } 1.63 + } 1.64 + 1.65 + void 1.66 +nullOutTablesArray( HashTable *table ) 1.67 + { int i, tableSz; 1.68 + tableSz = table->tableSz; 1.69 + HashEntry ** entries = table->entries; 1.70 + for( i = 0; i < tableSz; i++ ) 1.71 + entries[ i ] = NULL; 1.72 + } 1.73 + 1.74 + unsigned int 1.75 +hashThisKey( char *s, int hashSz ) 1.76 + { unsigned int h = 0; 1.77 + 1.78 + for( ; *s != 0; s++ ) 1.79 + h = *s + h*31; 1.80 + return h % hashSz; 1.81 + } 1.82 + 1.83 +/*Need this to be separated out, for use in both getParam and putParam 1.84 + */ 1.85 + HashEntry * 1.86 +getEntryFromTable( char *key, HashTable * table ) 1.87 + { unsigned int 1.88 + hashIndex = hashKey( key, table->tableSz ); 1.89 + HashEntry* 1.90 + hashEntry = table->entries[ hashIndex ]; 1.91 + for( ; hashEntry != NULL; hashEntry = hashEntry->next ) 1.92 + { if( strcmp( hashEntry->key, key ) == 0 ) return hashEntry; 1.93 + } 1.94 + return NULL; 1.95 + } 1.96 + 1.97 + void * 1.98 +getValueFromTable( char *key, HashTable * table ) 1.99 + { HashEntry *entry; 1.100 + entry = lookupKeyInHash( key, table ); 1.101 + if( entry == NULL ) return NULL; 1.102 + 1.103 + return entry->content; 1.104 + } 1.105 + 1.106 + int 1.107 +addToTable( char* key, void *content, HashTable *table ) 1.108 + { unsigned int hashIdx; 1.109 + HashEntry* hashEntry; 1.110 + 1.111 + hashEntry = getEntryFromTable( key, table ); 1.112 + if( hashEntry == NULL ) 1.113 + { hashIdx = hashThisKey( key, table->tableSz ); 1.114 + hashEntry = (HashEntry*) malloc( sizeof( HashEntry ) ); 1.115 + if( hashEntry == NULL ) return 0; 1.116 + hashEntry->key = strdup_m( key ); //TODO: figure out soln for incr Sz 1.117 + if( hashEntry->key == NULL ) return 0; 1.118 + hashEntry->next = (table->entries)[hashIdx]; 1.119 + (table->entries)[hashIdx] = hashEntry; 1.120 + table->numEntries += 1; 1.121 + if( table->tableSz < table->numEntries ) doubleTableSize( table ); 1.122 + } 1.123 + else 1.124 + { (*(table->freeEntryContentFn))( hashEntry->content ); 1.125 + } 1.126 + hashEntry->content = content; 1.127 + return 1; 1.128 + } 1.129 + 1.130 + int 1.131 +addEntryToTable( HashEntry *entry, HashTable *table ) 1.132 + { unsigned int hashIdx; 1.133 + HashEntry* testEntry; 1.134 + 1.135 + testEntry = getEntryFromTable( entry->key, table ); 1.136 + if( testEntry == NULL ) 1.137 + { hashIdx = hashThisKey( entry->key, table->tableSz ); 1.138 + entry->next = (table->entries)[hashIdx]; 1.139 + (table->entries)[hashIdx] = entry; 1.140 + table->numEntries += 1; 1.141 + if( table->tableSz < table->numEntries ) doubleTableSize( table ); 1.142 + } 1.143 + else 1.144 + { (*(table->freeEntryContentFn))( testEntry->content ); 1.145 + testEntry->content = entry->content; 1.146 + entry->content = NULL; 1.147 + freeHashEntryUsing( entry, table ); 1.148 + } 1.149 + return 1; 1.150 + } 1.151 + 1.152 + bool8 1.153 +deleteEntryFromTable( char *key, HashTable *table ) 1.154 + { 1.155 + table->numEntries -= 1; 1.156 + 1.157 + } 1.158 + 1.159 + 1.160 + char* 1.161 +strdup_m( char *o ) 1.162 + { int len = strlen(o)+1; 1.163 + char *ns = (char*) malloc( len * sizeof(char) ); 1.164 + strcpy( ns, o ); 1.165 + return ns; 1.166 + } 1.167 + 1.168 +/* debugging function displays the hashtable in (key.value) pairs 1.169 +*/ 1.170 +/*void hashTableToString( HashTable * table ) 1.171 + { int i; 1.172 + HashEntry *t; 1.173 + for( i = 0; i < table->tableSz; i++ ) 1.174 + { t = entries[i]; 1.175 + if( t == NULL ) 1.176 + strcat_m( retStr, &"()" ); 1.177 + else 1.178 + { strcat_m( retStr, &"(" ); 1.179 + for( ; t != NULL; t = t->next ) 1.180 + { strcat_m( retStr, &" " ); 1.181 + strcat_m( retStr, t->key ); 1.182 + strcat_m( retStr, &"." ); 1.183 + strcat_m( retStr, paramToString( t->param ) ); 1.184 + strcat_m( retStr, &" " ); 1.185 + } 1.186 + strcat_m( retStr, &")" ); 1.187 + } 1.188 + } 1.189 + } 1.190 +*/ 1.191 + 1.192 +/* 1.193 + void 1.194 +setFnToFreeEntryContent( HashTable *table, FreeEntryContentFnPtr fnPtr ) 1.195 + { 1.196 + table->freeEntryContentFn = fnPtr; 1.197 + } 1.198 +*/ 1.199 + 1.200 + void 1.201 +freeHashTable( HashTable *table ) 1.202 + { int i; 1.203 + HashEntry *hashEntry, *temp, **entries; 1.204 + 1.205 + entries = table->entries; 1.206 + for( i=0; i < table->tableSz; i++ ) 1.207 + { if( entries[i] != NULL ) 1.208 + { hashEntry = entries[i]; 1.209 + while( hashEntry != NULL ) 1.210 + { 1.211 + temp = hashEntry->next; 1.212 + freeHashEntryUsing( hashEntry, table ); 1.213 + hashEntry = temp; 1.214 + } 1.215 + } 1.216 + } 1.217 + } 1.218 + 1.219 + void 1.220 +freeHashEntryUsing( HashEntry *entry, HashTable *table ) 1.221 + { 1.222 + if( entry->content != NULL ) 1.223 + (*(table->freeEntryContentFn))( entry->content ); 1.224 + free( entry->key ); //was malloc'd above, so free it 1.225 + free( entry ); 1.226 + } 1.227 +
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 2.2 +++ b/PrivateHash.h Sat May 22 19:49:28 2010 -0700 2.3 @@ -0,0 +1,60 @@ 2.4 +/* 2.5 + * Copyright 2009 OpenSourceStewardshipFoundation.org 2.6 + * Licensed under GNU General Public License version 2 2.7 + * 2.8 + * Author: seanhalle@yahoo.com 2.9 + */ 2.10 + 2.11 +#ifndef _PRIVATE_HASH_H 2.12 +#define _PRIVATE_HASH_H 2.13 + 2.14 + 2.15 +#define TRUE 1 2.16 +#define FALSE 0 2.17 + 2.18 + 2.19 +#define HASHSIZE 101 2.20 + 2.21 +typedef struct _HashEntry HashEntry; 2.22 + 2.23 +struct _HashEntry 2.24 + { 2.25 + char *key; 2.26 + void *content; 2.27 + HashEntry *next; 2.28 + }; 2.29 + 2.30 +typedef void (*FreeEntryContentFnPtr) ( void * ); 2.31 + 2.32 +typedef struct 2.33 + { int tableSz; 2.34 + int numEntries; 2.35 + HashEntry* *entries; 2.36 + FreeEntryContentFnPtr freeEntryContentFn; 2.37 + } 2.38 +HashTable; 2.39 + 2.40 +//=========================================================================== 2.41 +// Internal functions 2.42 +void freeHashEntryUsing( HashEntry *entry, HashTable *table ); 2.43 +char* strdup_m(char *o); 2.44 +unsigned int hashThisKey( char *s, int hashSz ); 2.45 +void nullOutTablesArray( HashTable *table ); 2.46 +void *getEntryFromTable( char *key, HashTable *table ); 2.47 +void doubleTableSize( HashTable *table ); 2.48 +void addEntryToTable( HashEntry *entry, HashTable *table ); 2.49 + 2.50 +//=========================================================================== 2.51 +// Public functions 2.52 +HashTable *makeHashTable( int numHashSlots, FreeEntryContentFnPtr freeFn ); 2.53 + 2.54 +void *getValueFromTable( char *key, HashTable *table ); 2.55 +bool8 deleteEntryFromTable( char *key, HashTable *table ); 2.56 +bool8 deleteEntrysValueInTable( char *key, HashTable *table ); 2.57 + 2.58 +int addToTable( char* key, void *content, HashTable *table ); 2.59 +void freeTable( HashTable *table ); 2.60 +//char *paramBagToString( ParamBag * bag ) 2.61 + 2.62 +#endif /* _PRIVATE_HASH_H */ 2.63 +