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

annotate PrivateHash.c @ 6:ec5c00d4023e

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