Mercurial > cgi-bin > hgwebdir.cgi > VMS > C_Libraries > Hash_impl

annotate PrivateHash.c @ 0:ee3ad252427e

find changesets by author, revision, files, or words in the commit message
Initial add
author Me
date Sat, 22 May 2010 19:49:28 -0700
parents
children 5900d90f5d71
rev   line source
Me@0 1 /*
Me@0 2 * Copyright 2009 OpenSourceCodeStewardshipFoundation.org
Me@0 3 * Licensed under GNU General Public License version 2
Me@0 4 *
Me@0 5 * NOTE: this version of SRSW correct as of April 25, 2010
Me@0 6 *
Me@0 7 * Author: seanhalle@yahoo.com
Me@0 8 */
Me@0 9
Me@0 10
Me@0 11 #include <stdio.h>
Me@0 12 #include <string.h>
Me@0 13 #include <errno.h>
Me@0 14 #include <stdlib.h>
Me@0 15
Me@0 16 #include "PrivateHash.h"
Me@0 17
Me@0 18
Me@0 19 HashTable *
Me@0 20 makeHashTable( int numHashSlots, FreeEntryContentFnPtr freeFn )
Me@0 21 { HashTable * retTable;
Me@0 22 retTable = malloc( sizeof( HashTable ) );
Me@0 23
Me@0 24 retTable->freeEntryContentFn = freeFn;
Me@0 25
Me@0 26 retTable->entries = malloc( numHashSlots * sizeof(HashEntry *) );
Me@0 27 retTable->tableSz = numHashSlots;
Me@0 28
Me@0 29 nullOutTablesArray( retTable );
Me@0 30
Me@0 31 return retTable;
Me@0 32 }
Me@0 33
Me@0 34 void
Me@0 35 doubleTableSize( HashTable *table )
Me@0 36 { int i, oldTableSz, newTableSz;
Me@0 37 HashEntry *entry, **oldEntries, **newEntries;
Me@0 38
Me@0 39 oldTableSz = table->tableSz;
Me@0 40 oldEntries = table->entries;
Me@0 41
Me@0 42 newTableSz = 2 * oldTableSz + 1;
Me@0 43 newEntries = malloc( newTableSz * sizeof(HashEntry *) );
Me@0 44
Me@0 45 table->tableSz = newTableSz;
Me@0 46 table->entries = newEntries;
Me@0 47 table->numEntries = 0; //about to add them all back!
Me@0 48
Me@0 49 // move all the entries from old to new
Me@0 50 for( i=0; i < oldTableSz; i++ )
Me@0 51 { if( oldEntries[i] != NULL )
Me@0 52 { entry = oldEntries[i];
Me@0 53 while( entry != NULL )
Me@0 54 {
Me@0 55 addEntryToTable( entry, table ); //does not allocate anything
Me@0 56 entry = entry->next;
Me@0 57 }
Me@0 58 }
Me@0 59 }
Me@0 60 }
Me@0 61
Me@0 62 void
Me@0 63 nullOutTablesArray( HashTable *table )
Me@0 64 { int i, tableSz;
Me@0 65 tableSz = table->tableSz;
Me@0 66 HashEntry ** entries = table->entries;
Me@0 67 for( i = 0; i < tableSz; i++ )
Me@0 68 entries[ i ] = NULL;
Me@0 69 }
Me@0 70
Me@0 71 unsigned int
Me@0 72 hashThisKey( char *s, int hashSz )
Me@0 73 { unsigned int h = 0;
Me@0 74
Me@0 75 for( ; *s != 0; s++ )
Me@0 76 h = *s + h*31;
Me@0 77 return h % hashSz;
Me@0 78 }
Me@0 79
Me@0 80 /*Need this to be separated out, for use in both getParam and putParam
Me@0 81 */
Me@0 82 HashEntry *
Me@0 83 getEntryFromTable( char *key, HashTable * table )
Me@0 84 { unsigned int
Me@0 85 hashIndex = hashKey( key, table->tableSz );
Me@0 86 HashEntry*
Me@0 87 hashEntry = table->entries[ hashIndex ];
Me@0 88 for( ; hashEntry != NULL; hashEntry = hashEntry->next )
Me@0 89 { if( strcmp( hashEntry->key, key ) == 0 ) return hashEntry;
Me@0 90 }
Me@0 91 return NULL;
Me@0 92 }
Me@0 93
Me@0 94 void *
Me@0 95 getValueFromTable( char *key, HashTable * table )
Me@0 96 { HashEntry *entry;
Me@0 97 entry = lookupKeyInHash( key, table );
Me@0 98 if( entry == NULL ) return NULL;
Me@0 99
Me@0 100 return entry->content;
Me@0 101 }
Me@0 102
Me@0 103 int
Me@0 104 addToTable( char* key, void *content, HashTable *table )
Me@0 105 { unsigned int hashIdx;
Me@0 106 HashEntry* hashEntry;
Me@0 107
Me@0 108 hashEntry = getEntryFromTable( key, table );
Me@0 109 if( hashEntry == NULL )
Me@0 110 { hashIdx = hashThisKey( key, table->tableSz );
Me@0 111 hashEntry = (HashEntry*) malloc( sizeof( HashEntry ) );
Me@0 112 if( hashEntry == NULL ) return 0;
Me@0 113 hashEntry->key = strdup_m( key ); //TODO: figure out soln for incr Sz
Me@0 114 if( hashEntry->key == NULL ) return 0;
Me@0 115 hashEntry->next = (table->entries)[hashIdx];
Me@0 116 (table->entries)[hashIdx] = hashEntry;
Me@0 117 table->numEntries += 1;
Me@0 118 if( table->tableSz < table->numEntries ) doubleTableSize( table );
Me@0 119 }
Me@0 120 else
Me@0 121 { (*(table->freeEntryContentFn))( hashEntry->content );
Me@0 122 }
Me@0 123 hashEntry->content = content;
Me@0 124 return 1;
Me@0 125 }
Me@0 126
Me@0 127 int
Me@0 128 addEntryToTable( HashEntry *entry, HashTable *table )
Me@0 129 { unsigned int hashIdx;
Me@0 130 HashEntry* testEntry;
Me@0 131
Me@0 132 testEntry = getEntryFromTable( entry->key, table );
Me@0 133 if( testEntry == NULL )
Me@0 134 { hashIdx = hashThisKey( entry->key, table->tableSz );
Me@0 135 entry->next = (table->entries)[hashIdx];
Me@0 136 (table->entries)[hashIdx] = entry;
Me@0 137 table->numEntries += 1;
Me@0 138 if( table->tableSz < table->numEntries ) doubleTableSize( table );
Me@0 139 }
Me@0 140 else
Me@0 141 { (*(table->freeEntryContentFn))( testEntry->content );
Me@0 142 testEntry->content = entry->content;
Me@0 143 entry->content = NULL;
Me@0 144 freeHashEntryUsing( entry, table );
Me@0 145 }
Me@0 146 return 1;
Me@0 147 }
Me@0 148
Me@0 149 bool8
Me@0 150 deleteEntryFromTable( char *key, HashTable *table )
Me@0 151 {
Me@0 152 table->numEntries -= 1;
Me@0 153
Me@0 154 }
Me@0 155
Me@0 156
Me@0 157 char*
Me@0 158 strdup_m( char *o )
Me@0 159 { int len = strlen(o)+1;
Me@0 160 char *ns = (char*) malloc( len * sizeof(char) );
Me@0 161 strcpy( ns, o );
Me@0 162 return ns;
Me@0 163 }
Me@0 164
Me@0 165 /* debugging function displays the hashtable in (key.value) pairs
Me@0 166 */
Me@0 167 /*void hashTableToString( HashTable * table )
Me@0 168 { int i;
Me@0 169 HashEntry *t;
Me@0 170 for( i = 0; i < table->tableSz; i++ )
Me@0 171 { t = entries[i];
Me@0 172 if( t == NULL )
Me@0 173 strcat_m( retStr, &"()" );
Me@0 174 else
Me@0 175 { strcat_m( retStr, &"(" );
Me@0 176 for( ; t != NULL; t = t->next )
Me@0 177 { strcat_m( retStr, &" " );
Me@0 178 strcat_m( retStr, t->key );
Me@0 179 strcat_m( retStr, &"." );
Me@0 180 strcat_m( retStr, paramToString( t->param ) );
Me@0 181 strcat_m( retStr, &" " );
Me@0 182 }
Me@0 183 strcat_m( retStr, &")" );
Me@0 184 }
Me@0 185 }
Me@0 186 }
Me@0 187 */
Me@0 188
Me@0 189 /*
Me@0 190 void
Me@0 191 setFnToFreeEntryContent( HashTable *table, FreeEntryContentFnPtr fnPtr )
Me@0 192 {
Me@0 193 table->freeEntryContentFn = fnPtr;
Me@0 194 }
Me@0 195 */
Me@0 196
Me@0 197 void
Me@0 198 freeHashTable( HashTable *table )
Me@0 199 { int i;
Me@0 200 HashEntry *hashEntry, *temp, **entries;
Me@0 201
Me@0 202 entries = table->entries;
Me@0 203 for( i=0; i < table->tableSz; i++ )
Me@0 204 { if( entries[i] != NULL )
Me@0 205 { hashEntry = entries[i];
Me@0 206 while( hashEntry != NULL )
Me@0 207 {
Me@0 208 temp = hashEntry->next;
Me@0 209 freeHashEntryUsing( hashEntry, table );
Me@0 210 hashEntry = temp;
Me@0 211 }
Me@0 212 }
Me@0 213 }
Me@0 214 }
Me@0 215
Me@0 216 void
Me@0 217 freeHashEntryUsing( HashEntry *entry, HashTable *table )
Me@0 218 {
Me@0 219 if( entry->content != NULL )
Me@0 220 (*(table->freeEntryContentFn))( entry->content );
Me@0 221 free( entry->key ); //was malloc'd above, so free it
Me@0 222 free( entry );
Me@0 223 }
Me@0 224