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

annotate PrivateHash.c @ 5:e072db5aa783

find changesets by author, revision, files, or words in the commit message
Fixed bug -- strdup snuck a malloc in -- and added better insert Entry
author Me
date Tue, 02 Nov 2010 16:45:50 -0700
parents 1ee100564408
children ec5c00d4023e bac20745c52e
rev   line source
Me@0 1 /*
Me@3 2 * Copyright 2009 OpenSourceStewardshipFoundation.org
Me@0 3 * Licensed under GNU General Public License version 2
Me@0 4 *
Me@0 5 *
Me@0 6 * Author: seanhalle@yahoo.com
Me@0 7 */
Me@0 8
Me@0 9
Me@0 10 #include <stdio.h>
Me@0 11 #include <string.h>
Me@0 12 #include <errno.h>
Me@0 13 #include <stdlib.h>
Me@0 14
Me@0 15 #include "PrivateHash.h"
Me@0 16
Me@0 17
Me@0 18 HashTable *
Me@0 19 makeHashTable( int numHashSlots, FreeEntryContentFnPtr freeFn )
Me@0 20 { HashTable * retTable;
Me@4 21 retTable = VMS__malloc( sizeof( HashTable ) );
Me@0 22
Me@0 23 retTable->freeEntryContentFn = freeFn;
Me@0 24
Me@4 25 retTable->entries = VMS__malloc( numHashSlots * sizeof(HashEntry *) );
Me@1 26 retTable->numEntries = 0;
Me@1 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@1 37 HashEntry *entry, *nextEntry, **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@4 43 newEntries = VMS__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@1 54 { nextEntry = entry->next;
Me@1 55 entry->next = NULL;
Me@1 56 putEntryIntoTable( entry, table ); //does not allocate anything
Me@1 57 entry = nextEntry;
Me@0 58 }
Me@0 59 }
Me@0 60 }
Me@0 61 }
Me@0 62
Me@1 63 void
Me@0 64 nullOutTablesArray( HashTable *table )
Me@0 65 { int i, tableSz;
Me@0 66 tableSz = table->tableSz;
Me@0 67 HashEntry ** entries = table->entries;
Me@0 68 for( i = 0; i < tableSz; i++ )
Me@0 69 entries[ i ] = NULL;
Me@0 70 }
Me@0 71
Me@1 72 unsigned int
Me@0 73 hashThisKey( char *s, int hashSz )
Me@0 74 { unsigned int h = 0;
Me@0 75
Me@0 76 for( ; *s != 0; s++ )
Me@0 77 h = *s + h*31;
Me@0 78 return h % hashSz;
Me@0 79 }
Me@0 80
Me@0 81 /*Need this to be separated out, for use in both getParam and putParam
Me@0 82 */
Me@1 83 HashEntry *
Me@0 84 getEntryFromTable( char *key, HashTable * table )
Me@0 85 { unsigned int
Me@1 86 hashIndex = hashThisKey( key, table->tableSz );
Me@0 87 HashEntry*
Me@0 88 hashEntry = table->entries[ hashIndex ];
Me@0 89 for( ; hashEntry != NULL; hashEntry = hashEntry->next )
Me@0 90 { if( strcmp( hashEntry->key, key ) == 0 ) return hashEntry;
Me@0 91 }
Me@0 92 return NULL;
Me@0 93 }
Me@0 94
Me@1 95 void *
Me@0 96 getValueFromTable( char *key, HashTable * table )
Me@0 97 { HashEntry *entry;
Me@1 98 entry = getEntryFromTable( key, table );
Me@0 99 if( entry == NULL ) return NULL;
Me@0 100
Me@0 101 return entry->content;
Me@0 102 }
Me@0 103
Me@1 104
Me@1 105 /*If key already has a value, clobber the old one and replace it
Me@1 106 */
Me@0 107 int
Me@1 108 addValueIntoTable( char* key, void *content, HashTable *table )
Me@0 109 { unsigned int hashIdx;
Me@0 110 HashEntry* hashEntry;
Me@0 111
Me@0 112 hashEntry = getEntryFromTable( key, table );
Me@0 113 if( hashEntry == NULL )
Me@0 114 { hashIdx = hashThisKey( key, table->tableSz );
Me@4 115 hashEntry = (HashEntry*) VMS__malloc( sizeof( HashEntry ) );
Me@0 116 if( hashEntry == NULL ) return 0;
Me@5 117 hashEntry->key = VMS__malloc( strlen(key) );
Me@0 118 if( hashEntry->key == NULL ) return 0;
Me@5 119 strcpy( hashEntry->key, key );
Me@0 120 hashEntry->next = (table->entries)[hashIdx];
Me@0 121 (table->entries)[hashIdx] = hashEntry;
Me@0 122 table->numEntries += 1;
Me@0 123 if( table->tableSz < table->numEntries ) doubleTableSize( table );
Me@0 124 }
Me@0 125 else
Me@0 126 { (*(table->freeEntryContentFn))( hashEntry->content );
Me@0 127 }
Me@0 128 hashEntry->content = content;
Me@0 129 return 1;
Me@0 130 }
Me@0 131
Me@0 132 int
Me@1 133 putEntryIntoTable( HashEntry *entry, HashTable *table )
Me@0 134 { unsigned int hashIdx;
Me@0 135 HashEntry* testEntry;
Me@0 136
Me@0 137 testEntry = getEntryFromTable( entry->key, table );
Me@0 138 if( testEntry == NULL )
Me@0 139 { hashIdx = hashThisKey( entry->key, table->tableSz );
Me@0 140 entry->next = (table->entries)[hashIdx];
Me@0 141 (table->entries)[hashIdx] = entry;
Me@0 142 table->numEntries += 1;
Me@0 143 if( table->tableSz < table->numEntries ) doubleTableSize( table );
Me@0 144 }
Me@0 145 else
Me@0 146 { (*(table->freeEntryContentFn))( testEntry->content );
Me@5 147 //being lazy -- will create bug in code that relies on having ptr to
Me@5 148 // elem given to insert into table!
Me@0 149 testEntry->content = entry->content;
Me@0 150 entry->content = NULL;
Me@5 151 freeHashEntryButNotContent( entry );
Me@0 152 }
Me@0 153 return 1;
Me@0 154 }
Me@0 155
Me@5 156 /*Better version
Me@5 157 */
Me@5 158 int
Me@5 159 untested_putEntryIntoTable( HashEntry *entry, HashTable * table )
Me@5 160 { HashEntry *testEntry, *prevEntry = NULL;
Me@5 161 unsigned int
Me@5 162 hashIndex = hashThisKey( entry->key, table->tableSz );
Me@5 163
Me@5 164 testEntry = table->entries[ hashIndex ];
Me@5 165 for( ; testEntry != NULL; testEntry = testEntry->next )
Me@5 166 { if( strcmp( testEntry->key, entry->key ) == 0 )
Me@5 167 { if( prevEntry == NULL )
Me@5 168 { table->entries[hashIndex] = entry;
Me@5 169 entry->next = testEntry->next;
Me@5 170 }
Me@5 171 else
Me@5 172 { prevEntry->next = entry;
Me@5 173 entry->next = testEntry->next;
Me@5 174 }
Me@5 175 freeHashEntryUsing( testEntry, table ); //frees content too!
Me@5 176 return;
Me@5 177 }
Me@5 178 }
Me@5 179 //wasn't found, so insert
Me@5 180 entry->next = table->entries[hashIndex];
Me@5 181 table->entries[hashIndex] = entry;
Me@5 182 }
Me@5 183
Me@5 184
Me@1 185
Me@0 186 bool8
Me@0 187 deleteEntryFromTable( char *key, HashTable *table )
Me@1 188 { HashEntry *hashEntry;
Me@1 189 HashEntry **addrOfHashEntryPtr;
Me@1 190 unsigned int hashIndex;
Me@0 191
Me@1 192 hashIndex = hashThisKey( key, table->tableSz );
Me@1 193 addrOfHashEntryPtr = &( table->entries[ hashIndex ] );
Me@1 194 hashEntry = *addrOfHashEntryPtr;
Me@1 195 while( hashEntry != NULL )
Me@1 196 { if( strcmp( hashEntry->key, key ) == 0 )
Me@1 197 {
Me@1 198 *addrOfHashEntryPtr = hashEntry->next;
Me@1 199 //TODO: Free the contents of entry?
Me@1 200 freeHashEntryButNotContent( hashEntry );
Me@1 201 table->numEntries -= 1;
Me@1 202 return TRUE;
Me@1 203 }
Me@1 204 addrOfHashEntryPtr = &( hashEntry->next );
Me@1 205 hashEntry = *addrOfHashEntryPtr;
Me@1 206 }
Me@1 207 return FALSE;
Me@0 208 }
Me@0 209
Me@1 210
Me@0 211 /* debugging function displays the hashtable in (key.value) pairs
Me@0 212 */
Me@0 213 /*void hashTableToString( HashTable * table )
Me@0 214 { int i;
Me@0 215 HashEntry *t;
Me@0 216 for( i = 0; i < table->tableSz; i++ )
Me@0 217 { t = entries[i];
Me@0 218 if( t == NULL )
Me@0 219 strcat_m( retStr, &"()" );
Me@0 220 else
Me@0 221 { strcat_m( retStr, &"(" );
Me@0 222 for( ; t != NULL; t = t->next )
Me@0 223 { strcat_m( retStr, &" " );
Me@0 224 strcat_m( retStr, t->key );
Me@0 225 strcat_m( retStr, &"." );
Me@0 226 strcat_m( retStr, paramToString( t->param ) );
Me@0 227 strcat_m( retStr, &" " );
Me@0 228 }
Me@0 229 strcat_m( retStr, &")" );
Me@0 230 }
Me@0 231 }
Me@0 232 }
Me@0 233 */
Me@0 234
Me@0 235 /*
Me@0 236 void
Me@0 237 setFnToFreeEntryContent( HashTable *table, FreeEntryContentFnPtr fnPtr )
Me@0 238 {
Me@0 239 table->freeEntryContentFn = fnPtr;
Me@0 240 }
Me@0 241 */
Me@0 242
Me@1 243 void
Me@0 244 freeHashTable( HashTable *table )
Me@0 245 { int i;
Me@0 246 HashEntry *hashEntry, *temp, **entries;
Me@0 247
Me@0 248 entries = table->entries;
Me@0 249 for( i=0; i < table->tableSz; i++ )
Me@0 250 { if( entries[i] != NULL )
Me@0 251 { hashEntry = entries[i];
Me@0 252 while( hashEntry != NULL )
Me@0 253 {
Me@0 254 temp = hashEntry->next;
Me@0 255 freeHashEntryUsing( hashEntry, table );
Me@0 256 hashEntry = temp;
Me@0 257 }
Me@0 258 }
Me@0 259 }
Me@0 260 }
Me@0 261
Me@1 262 void
Me@0 263 freeHashEntryUsing( HashEntry *entry, HashTable *table )
Me@0 264 {
Me@0 265 if( entry->content != NULL )
Me@0 266 (*(table->freeEntryContentFn))( entry->content );
Me@4 267 VMS__free( entry->key ); //was VMS__malloc'd above, so free it
Me@4 268 VMS__free( entry );
Me@0 269 }
Me@0 270
Me@1 271 void
Me@1 272 freeHashEntryButNotContent( HashEntry *entry )
Me@1 273 {
Me@4 274 VMS__free( entry->key ); //was VMS__malloc'd above, so free it
Me@4 275 VMS__free( entry );
Me@1 276 }
Me@1 277