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

annotate PrivateHash.c @ 12:40ec8f9583d8

find changesets by author, revision, files, or words in the commit message
include statements adapted to the new folder structure
author hausers
date Thu, 09 Feb 2012 15:49:46 +0100
parents 8b225987970d
children 5b89d57e5d10 093cad17d992
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
msach@9 74 hashThisKey( char* s, int hashSz )
Me@0 75 { unsigned int h = 0;
msach@9 76 unsigned int i;
msach@9 77 hashkey_t* key = (hashkey_t*)s;
Me@0 78
msach@9 79 for(i=0 ; i<sizeof(hashkey_t); i++ )
msach@9 80 h = key->hashable[i] + h*31;
Me@0 81 return h % hashSz;
Me@0 82 }
Me@0 83
Me@0 84 /*Need this to be separated out, for use in both getParam and putParam
Me@0 85 */
Me@1 86 HashEntry *
Me@0 87 getEntryFromTable( char *key, HashTable * table )
Me@0 88 { unsigned int
Me@1 89 hashIndex = hashThisKey( key, table->tableSz );
Me@0 90 HashEntry*
Me@0 91 hashEntry = table->entries[ hashIndex ];
Me@0 92 for( ; hashEntry != NULL; hashEntry = hashEntry->next )
msach@9 93 {
msach@9 94 if( memcmp( hashEntry->key, key, sizeof(hashkey_t) ) == 0 )
msach@9 95 return hashEntry;
Me@0 96 }
Me@0 97 return NULL;
Me@0 98 }
Me@0 99
Me@1 100 void *
Me@0 101 getValueFromTable( char *key, HashTable * table )
Me@0 102 { HashEntry *entry;
Me@1 103 entry = getEntryFromTable( key, table );
Me@0 104 if( entry == NULL ) return NULL;
Me@0 105
Me@0 106 return entry->content;
Me@0 107 }
Me@0 108
Me@1 109
Me@1 110 /*If key already has a value, clobber the old one and replace it
Me@1 111 */
Me@0 112 int
Me@1 113 addValueIntoTable( char* key, void *content, HashTable *table )
Me@0 114 { unsigned int hashIdx;
Me@0 115 HashEntry* hashEntry;
Me@0 116
Me@0 117 hashEntry = getEntryFromTable( key, table );
Me@0 118 if( hashEntry == NULL )
Me@0 119 { hashIdx = hashThisKey( key, table->tableSz );
Me@4 120 hashEntry = (HashEntry*) VMS__malloc( sizeof( HashEntry ) );
Me@0 121 if( hashEntry == NULL ) return 0;
msach@9 122 hashEntry->key = VMS__malloc( sizeof(hashkey_t) );
Me@0 123 if( hashEntry->key == NULL ) return 0;
msach@9 124 memcpy( hashEntry->key, key, sizeof(hashkey_t) );
Me@0 125 hashEntry->next = (table->entries)[hashIdx];
Me@0 126 (table->entries)[hashIdx] = hashEntry;
Me@0 127 table->numEntries += 1;
Me@0 128 if( table->tableSz < table->numEntries ) doubleTableSize( table );
Me@0 129 }
Me@0 130 else
Me@0 131 { (*(table->freeEntryContentFn))( hashEntry->content );
Me@0 132 }
Me@0 133 hashEntry->content = content;
Me@0 134 return 1;
Me@0 135 }
Me@0 136
Me@0 137 int
Me@1 138 putEntryIntoTable( HashEntry *entry, HashTable *table )
Me@0 139 { unsigned int hashIdx;
Me@0 140 HashEntry* testEntry;
Me@0 141
Me@0 142 testEntry = getEntryFromTable( entry->key, table );
Me@0 143 if( testEntry == NULL )
Me@0 144 { hashIdx = hashThisKey( entry->key, table->tableSz );
Me@0 145 entry->next = (table->entries)[hashIdx];
Me@0 146 (table->entries)[hashIdx] = entry;
Me@0 147 table->numEntries += 1;
Me@0 148 if( table->tableSz < table->numEntries ) doubleTableSize( table );
Me@0 149 }
Me@0 150 else
Me@0 151 { (*(table->freeEntryContentFn))( testEntry->content );
Me@5 152 //being lazy -- will create bug in code that relies on having ptr to
Me@5 153 // elem given to insert into table!
Me@0 154 testEntry->content = entry->content;
Me@0 155 entry->content = NULL;
Me@5 156 freeHashEntryButNotContent( entry );
Me@0 157 }
Me@0 158 return 1;
Me@0 159 }
Me@0 160
Me@5 161 /*Better version
Me@5 162 */
msach@7 163 void
Me@5 164 untested_putEntryIntoTable( HashEntry *entry, HashTable * table )
Me@5 165 { HashEntry *testEntry, *prevEntry = NULL;
Me@5 166 unsigned int
Me@5 167 hashIndex = hashThisKey( entry->key, table->tableSz );
Me@5 168
Me@5 169 testEntry = table->entries[ hashIndex ];
Me@5 170 for( ; testEntry != NULL; testEntry = testEntry->next )
msach@9 171 { if( memcmp( testEntry->key, entry->key, sizeof(hashkey_t)) == 0 )
Me@5 172 { if( prevEntry == NULL )
Me@5 173 { table->entries[hashIndex] = entry;
Me@5 174 entry->next = testEntry->next;
Me@5 175 }
Me@5 176 else
Me@5 177 { prevEntry->next = entry;
Me@5 178 entry->next = testEntry->next;
Me@5 179 }
Me@5 180 freeHashEntryUsing( testEntry, table ); //frees content too!
Me@5 181 return;
Me@5 182 }
Me@5 183 }
Me@5 184 //wasn't found, so insert
Me@5 185 entry->next = table->entries[hashIndex];
Me@5 186 table->entries[hashIndex] = entry;
Me@5 187 }
Me@5 188
Me@5 189
Me@1 190
Me@0 191 bool8
Me@0 192 deleteEntryFromTable( char *key, HashTable *table )
Me@1 193 { HashEntry *hashEntry;
Me@1 194 HashEntry **addrOfHashEntryPtr;
Me@1 195 unsigned int hashIndex;
Me@0 196
Me@1 197 hashIndex = hashThisKey( key, table->tableSz );
Me@1 198 addrOfHashEntryPtr = &( table->entries[ hashIndex ] );
Me@1 199 hashEntry = *addrOfHashEntryPtr;
Me@1 200 while( hashEntry != NULL )
msach@9 201 { if( memcmp( hashEntry->key, key, sizeof(hashkey_t) ) == 0 )
Me@1 202 {
Me@1 203 *addrOfHashEntryPtr = hashEntry->next;
Me@1 204 //TODO: Free the contents of entry?
Me@1 205 freeHashEntryButNotContent( hashEntry );
Me@1 206 table->numEntries -= 1;
Me@1 207 return TRUE;
Me@1 208 }
Me@1 209 addrOfHashEntryPtr = &( hashEntry->next );
Me@1 210 hashEntry = *addrOfHashEntryPtr;
Me@1 211 }
Me@1 212 return FALSE;
Me@0 213 }
Me@1 214
Me@1 215 void
Me@0 216 freeHashTable( HashTable *table )
Me@0 217 { int i;
Me@0 218 HashEntry *hashEntry, *temp, **entries;
Me@0 219
Me@0 220 entries = table->entries;
Me@0 221 for( i=0; i < table->tableSz; i++ )
Me@0 222 { if( entries[i] != NULL )
Me@0 223 { hashEntry = entries[i];
Me@0 224 while( hashEntry != NULL )
Me@0 225 {
Me@0 226 temp = hashEntry->next;
Me@0 227 freeHashEntryUsing( hashEntry, table );
Me@0 228 hashEntry = temp;
Me@0 229 }
Me@0 230 }
Me@0 231 }
Me@0 232 }
Me@0 233
Me@1 234 void
Me@0 235 freeHashEntryUsing( HashEntry *entry, HashTable *table )
Me@0 236 {
Me@0 237 if( entry->content != NULL )
Me@0 238 (*(table->freeEntryContentFn))( entry->content );
Me@4 239 VMS__free( entry->key ); //was VMS__malloc'd above, so free it
Me@4 240 VMS__free( entry );
Me@0 241 }
Me@0 242
Me@1 243 void
Me@1 244 freeHashEntryButNotContent( HashEntry *entry )
Me@1 245 {
Me@4 246 VMS__free( entry->key ); //was VMS__malloc'd above, so free it
Me@4 247 VMS__free( entry );
Me@1 248 }
Me@1 249