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

annotate PrivateHash.c @ 17:774396bc53b4

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