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

annotate PrivateHash.c @ 15:093cad17d992

find changesets by author, revision, files, or words in the commit message
Removed VMS__malloc and free, added .brch__default (expls why removed)
author Me@portablequad
date Sat, 11 Feb 2012 18:00:56 -0800
parents 7c4d2bf121a9
children
rev   line source
Me@15 1 /*
Me@15 2 * Copyright 2009 OpenSourceStewardshipFoundation.org
Me@15 3 * Licensed under GNU General Public License version 2
Me@15 4 *
Me@15 5 *
Me@15 6 * Author: seanhalle@yahoo.com
Me@15 7 */
Me@15 8
Me@15 9 #include "PrivateHash.h"
Me@15 10
Me@15 11
Me@15 12 HashTable *
Me@15 13 makeHashTable( int numHashSlots, FreeEntryContentFnPtr freeFn )
Me@15 14 { HashTable * retTable;
Me@15 15 retTable = malloc( sizeof( HashTable ) );
Me@15 16
Me@15 17 retTable->freeEntryContentFn = freeFn;
Me@15 18
Me@15 19 retTable->entries = malloc( numHashSlots * sizeof(HashEntry *) );
Me@15 20 retTable->numEntries = 0;
Me@15 21 retTable->tableSz = numHashSlots;
Me@15 22
Me@15 23 nullOutTablesArray( retTable );
Me@15 24
Me@15 25 return retTable;
Me@15 26 }
Me@15 27
Me@15 28 void
Me@15 29 doubleTableSize( HashTable *table )
Me@15 30 { int i, oldTableSz, newTableSz;
Me@15 31 HashEntry *entry, *nextEntry, **oldEntries, **newEntries;
Me@15 32
Me@15 33 oldTableSz = table->tableSz;
Me@15 34 oldEntries = table->entries;
Me@15 35
Me@15 36 newTableSz = 2 * oldTableSz + 1;
Me@15 37 newEntries = malloc( newTableSz * sizeof(HashEntry *) );
Me@15 38
Me@15 39 table->tableSz = newTableSz;
Me@15 40 table->entries = newEntries;
Me@15 41 table->numEntries = 0; //about to add them all back!
Me@15 42
Me@15 43 // move all the entries from old to new
Me@15 44 for( i=0; i < oldTableSz; i++ )
Me@15 45 { if( oldEntries[i] != NULL )
Me@15 46 { entry = oldEntries[i];
Me@15 47 while( entry != NULL )
Me@15 48 { nextEntry = entry->next;
Me@15 49 entry->next = NULL;
Me@15 50 putEntryIntoTable( entry, table ); //does not allocate anything
Me@15 51 entry = nextEntry;
Me@15 52 }
Me@15 53 }
Me@15 54 }
Me@15 55 }
Me@15 56
Me@15 57 void
Me@15 58 nullOutTablesArray( HashTable *table )
Me@15 59 { int i, tableSz;
Me@15 60 tableSz = table->tableSz;
Me@15 61 HashEntry ** entries = table->entries;
Me@15 62 for( i = 0; i < tableSz; i++ )
Me@15 63 entries[ i ] = NULL;
Me@15 64 }
Me@15 65
Me@15 66 unsigned int
Me@15 67 hashThisKey( char* s, int hashSz )
Me@15 68 { unsigned int h = 0;
Me@15 69 unsigned int i;
Me@15 70 hashkey_t* key = (hashkey_t*)s;
Me@15 71
Me@15 72 for(i=0 ; i<sizeof(hashkey_t); i++ )
Me@15 73 h = key->hashable[i] + h*31;
Me@15 74 return h % hashSz;
Me@15 75 }
Me@15 76
Me@15 77 /*Need this to be separated out, for use in both getParam and putParam
Me@15 78 */
Me@15 79 HashEntry *
Me@15 80 getEntryFromTable( char *key, HashTable * table )
Me@15 81 { unsigned int
Me@15 82 hashIndex = hashThisKey( key, table->tableSz );
Me@15 83 HashEntry*
Me@15 84 hashEntry = table->entries[ hashIndex ];
Me@15 85 for( ; hashEntry != NULL; hashEntry = hashEntry->next )
Me@15 86 {
Me@15 87 if( memcmp( hashEntry->key, key, sizeof(hashkey_t) ) == 0 )
Me@15 88 return hashEntry;
Me@15 89 }
Me@15 90 return NULL;
Me@15 91 }
Me@15 92
Me@15 93 void *
Me@15 94 getValueFromTable( char *key, HashTable * table )
Me@15 95 { HashEntry *entry;
Me@15 96 entry = getEntryFromTable( key, table );
Me@15 97 if( entry == NULL ) return NULL;
Me@15 98
Me@15 99 return entry->content;
Me@15 100 }
Me@15 101
Me@15 102
Me@15 103 /*If key already has a value, clobber the old one and replace it
Me@15 104 */
Me@15 105 int
Me@15 106 addValueIntoTable( char* key, void *content, HashTable *table )
Me@15 107 { unsigned int hashIdx;
Me@15 108 HashEntry* hashEntry;
Me@15 109
Me@15 110 hashEntry = getEntryFromTable( key, table );
Me@15 111 if( hashEntry == NULL )
Me@15 112 { hashIdx = hashThisKey( key, table->tableSz );
Me@15 113 hashEntry = (HashEntry*) malloc( sizeof( HashEntry ) );
Me@15 114 if( hashEntry == NULL ) return 0;
Me@15 115 hashEntry->key = malloc( sizeof(hashkey_t) );
Me@15 116 if( hashEntry->key == NULL ) return 0;
Me@15 117 memcpy( hashEntry->key, key, sizeof(hashkey_t) );
Me@15 118 hashEntry->next = (table->entries)[hashIdx];
Me@15 119 (table->entries)[hashIdx] = hashEntry;
Me@15 120 table->numEntries += 1;
Me@15 121 if( table->tableSz < table->numEntries ) doubleTableSize( table );
Me@15 122 }
Me@15 123 else
Me@15 124 { (*(table->freeEntryContentFn))( hashEntry->content );
Me@15 125 }
Me@15 126 hashEntry->content = content;
Me@15 127 return 1;
Me@15 128 }
Me@15 129
Me@15 130 int
Me@15 131 putEntryIntoTable( HashEntry *entry, HashTable *table )
Me@15 132 { unsigned int hashIdx;
Me@15 133 HashEntry* testEntry;
Me@15 134
Me@15 135 testEntry = getEntryFromTable( entry->key, table );
Me@15 136 if( testEntry == NULL )
Me@15 137 { hashIdx = hashThisKey( entry->key, table->tableSz );
Me@15 138 entry->next = (table->entries)[hashIdx];
Me@15 139 (table->entries)[hashIdx] = entry;
Me@15 140 table->numEntries += 1;
Me@15 141 if( table->tableSz < table->numEntries ) doubleTableSize( table );
Me@15 142 }
Me@15 143 else
Me@15 144 { (*(table->freeEntryContentFn))( testEntry->content );
Me@15 145 //being lazy -- will create bug in code that relies on having ptr to
Me@15 146 // elem given to insert into table!
Me@15 147 testEntry->content = entry->content;
Me@15 148 entry->content = NULL;
Me@15 149 freeHashEntryButNotContent( entry );
Me@15 150 }
Me@15 151 return 1;
Me@15 152 }
Me@15 153
Me@15 154 /*Better version
Me@15 155 */
Me@15 156 void
Me@15 157 untested_putEntryIntoTable( HashEntry *entry, HashTable * table )
Me@15 158 { HashEntry *testEntry, *prevEntry = NULL;
Me@15 159 unsigned int
Me@15 160 hashIndex = hashThisKey( entry->key, table->tableSz );
Me@15 161
Me@15 162 testEntry = table->entries[ hashIndex ];
Me@15 163 for( ; testEntry != NULL; testEntry = testEntry->next )
Me@15 164 { if( memcmp( testEntry->key, entry->key, sizeof(hashkey_t)) == 0 )
Me@15 165 { if( prevEntry == NULL )
Me@15 166 { table->entries[hashIndex] = entry;
Me@15 167 entry->next = testEntry->next;
Me@15 168 }
Me@15 169 else
Me@15 170 { prevEntry->next = entry;
Me@15 171 entry->next = testEntry->next;
Me@15 172 }
Me@15 173 freeHashEntryUsing( testEntry, table ); //frees content too!
Me@15 174 return;
Me@15 175 }
Me@15 176 }
Me@15 177 //wasn't found, so insert
Me@15 178 entry->next = table->entries[hashIndex];
Me@15 179 table->entries[hashIndex] = entry;
Me@15 180 }
Me@15 181
Me@15 182
Me@15 183
Me@15 184 bool8
Me@15 185 deleteEntryFromTable( char *key, HashTable *table )
Me@15 186 { HashEntry *hashEntry;
Me@15 187 HashEntry **addrOfHashEntryPtr;
Me@15 188 unsigned int hashIndex;
Me@15 189
Me@15 190 hashIndex = hashThisKey( key, table->tableSz );
Me@15 191 addrOfHashEntryPtr = &( table->entries[ hashIndex ] );
Me@15 192 hashEntry = *addrOfHashEntryPtr;
Me@15 193 while( hashEntry != NULL )
Me@15 194 { if( memcmp( hashEntry->key, key, sizeof(hashkey_t) ) == 0 )
Me@15 195 {
Me@15 196 *addrOfHashEntryPtr = hashEntry->next;
Me@15 197 //TODO: Free the contents of entry?
Me@15 198 freeHashEntryButNotContent( hashEntry );
Me@15 199 table->numEntries -= 1;
Me@15 200 return TRUE;
Me@15 201 }
Me@15 202 addrOfHashEntryPtr = &( hashEntry->next );
Me@15 203 hashEntry = *addrOfHashEntryPtr;
Me@15 204 }
Me@15 205 return FALSE;
Me@15 206 }
Me@15 207
Me@15 208 void
Me@15 209 freeHashTable( HashTable *table )
Me@15 210 { int i;
Me@15 211 HashEntry *hashEntry, *temp, **entries;
Me@15 212
Me@15 213 entries = table->entries;
Me@15 214 for( i=0; i < table->tableSz; i++ )
Me@15 215 { if( entries[i] != NULL )
Me@15 216 { hashEntry = entries[i];
Me@15 217 while( hashEntry != NULL )
Me@15 218 {
Me@15 219 temp = hashEntry->next;
Me@15 220 freeHashEntryUsing( hashEntry, table );
Me@15 221 hashEntry = temp;
Me@15 222 }
Me@15 223 }
Me@15 224 }
Me@15 225 }
Me@15 226
Me@15 227 void
Me@15 228 freeHashEntryUsing( HashEntry *entry, HashTable *table )
Me@15 229 {
Me@15 230 if( entry->content != NULL )
Me@15 231 (*(table->freeEntryContentFn))( entry->content );
Me@15 232 free( entry->key ); //was malloc'd above, so free it
Me@15 233 free( entry );
Me@15 234 }
Me@15 235
Me@15 236 void
Me@15 237 freeHashEntryButNotContent( HashEntry *entry )
Me@15 238 {
Me@15 239 free( entry->key ); //was malloc'd above, so free it
Me@15 240 free( entry );
Me@15 241 }
Me@15 242