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

annotate PrivateHash.c @ 10:ce35f7028eba

find changesets by author, revision, files, or words in the commit message
Closing branch
author Merten Sach <msach@mailbox.tu-berlin.de>
date Wed, 28 Sep 2011 13:40:38 +0200
parents e072db5aa783
children
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@8 117 hashEntry->key = VMS__strDup( key );
Me@0 118 hashEntry->next = (table->entries)[hashIdx];
Me@0 119 (table->entries)[hashIdx] = hashEntry;
Me@0 120 table->numEntries += 1;
Me@0 121 if( table->tableSz < table->numEntries ) doubleTableSize( table );
Me@0 122 }
Me@0 123 else
Me@0 124 { (*(table->freeEntryContentFn))( hashEntry->content );
Me@0 125 }
Me@0 126 hashEntry->content = content;
Me@0 127 return 1;
Me@0 128 }
Me@0 129
Me@0 130 int
Me@1 131 putEntryIntoTable( HashEntry *entry, HashTable *table )
Me@0 132 { unsigned int hashIdx;
Me@0 133 HashEntry* testEntry;
Me@0 134
Me@0 135 testEntry = getEntryFromTable( entry->key, table );
Me@0 136 if( testEntry == NULL )
Me@0 137 { hashIdx = hashThisKey( entry->key, table->tableSz );
Me@0 138 entry->next = (table->entries)[hashIdx];
Me@0 139 (table->entries)[hashIdx] = entry;
Me@0 140 table->numEntries += 1;
Me@0 141 if( table->tableSz < table->numEntries ) doubleTableSize( table );
Me@0 142 }
Me@0 143 else
Me@0 144 { (*(table->freeEntryContentFn))( testEntry->content );
Me@5 145 //being lazy -- will create bug in code that relies on having ptr to
Me@5 146 // elem given to insert into table!
Me@0 147 testEntry->content = entry->content;
Me@0 148 entry->content = NULL;
Me@5 149 freeHashEntryButNotContent( entry );
Me@0 150 }
Me@0 151 return 1;
Me@0 152 }
Me@0 153
Me@5 154 /*Better version
Me@5 155 */
Me@5 156 int
Me@5 157 untested_putEntryIntoTable( HashEntry *entry, HashTable * table )
Me@5 158 { HashEntry *testEntry, *prevEntry = NULL;
Me@5 159 unsigned int
Me@5 160 hashIndex = hashThisKey( entry->key, table->tableSz );
Me@5 161
Me@5 162 testEntry = table->entries[ hashIndex ];
Me@5 163 for( ; testEntry != NULL; testEntry = testEntry->next )
Me@5 164 { if( strcmp( testEntry->key, entry->key ) == 0 )
Me@5 165 { if( prevEntry == NULL )
Me@5 166 { table->entries[hashIndex] = entry;
Me@5 167 entry->next = testEntry->next;
Me@5 168 }
Me@5 169 else
Me@5 170 { prevEntry->next = entry;
Me@5 171 entry->next = testEntry->next;
Me@5 172 }
Me@5 173 freeHashEntryUsing( testEntry, table ); //frees content too!
Me@5 174 return;
Me@5 175 }
Me@5 176 }
Me@5 177 //wasn't found, so insert
Me@5 178 entry->next = table->entries[hashIndex];
Me@5 179 table->entries[hashIndex] = entry;
Me@5 180 }
Me@5 181
Me@5 182
Me@1 183
Me@0 184 bool8
Me@0 185 deleteEntryFromTable( char *key, HashTable *table )
Me@1 186 { HashEntry *hashEntry;
Me@1 187 HashEntry **addrOfHashEntryPtr;
Me@1 188 unsigned int hashIndex;
Me@0 189
Me@1 190 hashIndex = hashThisKey( key, table->tableSz );
Me@1 191 addrOfHashEntryPtr = &( table->entries[ hashIndex ] );
Me@1 192 hashEntry = *addrOfHashEntryPtr;
Me@1 193 while( hashEntry != NULL )
Me@1 194 { if( strcmp( hashEntry->key, key ) == 0 )
Me@1 195 {
Me@1 196 *addrOfHashEntryPtr = hashEntry->next;
Me@1 197 //TODO: Free the contents of entry?
Me@1 198 freeHashEntryButNotContent( hashEntry );
Me@1 199 table->numEntries -= 1;
Me@1 200 return TRUE;
Me@1 201 }
Me@1 202 addrOfHashEntryPtr = &( hashEntry->next );
Me@1 203 hashEntry = *addrOfHashEntryPtr;
Me@1 204 }
Me@1 205 return FALSE;
Me@0 206 }
Me@0 207
Me@1 208
Me@0 209 /* debugging function displays the hashtable in (key.value) pairs
Me@0 210 */
Me@0 211 /*void hashTableToString( HashTable * table )
Me@0 212 { int i;
Me@0 213 HashEntry *t;
Me@0 214 for( i = 0; i < table->tableSz; i++ )
Me@0 215 { t = entries[i];
Me@0 216 if( t == NULL )
Me@0 217 strcat_m( retStr, &"()" );
Me@0 218 else
Me@0 219 { strcat_m( retStr, &"(" );
Me@0 220 for( ; t != NULL; t = t->next )
Me@0 221 { strcat_m( retStr, &" " );
Me@0 222 strcat_m( retStr, t->key );
Me@0 223 strcat_m( retStr, &"." );
Me@0 224 strcat_m( retStr, paramToString( t->param ) );
Me@0 225 strcat_m( retStr, &" " );
Me@0 226 }
Me@0 227 strcat_m( retStr, &")" );
Me@0 228 }
Me@0 229 }
Me@0 230 }
Me@0 231 */
Me@0 232
Me@0 233 /*
Me@0 234 void
Me@0 235 setFnToFreeEntryContent( HashTable *table, FreeEntryContentFnPtr fnPtr )
Me@0 236 {
Me@0 237 table->freeEntryContentFn = fnPtr;
Me@0 238 }
Me@0 239 */
Me@0 240
Me@1 241 void
Me@0 242 freeHashTable( HashTable *table )
Me@0 243 { int i;
Me@0 244 HashEntry *hashEntry, *temp, **entries;
Me@0 245
Me@0 246 entries = table->entries;
Me@0 247 for( i=0; i < table->tableSz; i++ )
Me@0 248 { if( entries[i] != NULL )
Me@0 249 { hashEntry = entries[i];
Me@0 250 while( hashEntry != NULL )
Me@0 251 {
Me@0 252 temp = hashEntry->next;
Me@0 253 freeHashEntryUsing( hashEntry, table );
Me@0 254 hashEntry = temp;
Me@0 255 }
Me@0 256 }
Me@0 257 }
Me@0 258 }
Me@0 259
Me@1 260 void
Me@0 261 freeHashEntryUsing( HashEntry *entry, HashTable *table )
Me@0 262 {
Me@0 263 if( entry->content != NULL )
Me@0 264 (*(table->freeEntryContentFn))( entry->content );
Me@4 265 VMS__free( entry->key ); //was VMS__malloc'd above, so free it
Me@4 266 VMS__free( entry );
Me@0 267 }
Me@0 268
Me@1 269 void
Me@1 270 freeHashEntryButNotContent( HashEntry *entry )
Me@1 271 {
Me@4 272 VMS__free( entry->key ); //was VMS__malloc'd above, so free it
Me@4 273 VMS__free( entry );
Me@1 274 }
Me@1 275