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

annotate PrivateHash.c @ 3:e6fe47763ee6

find changesets by author, revision, files, or words in the commit message
Updated copyright
author Me
date Sat, 11 Sep 2010 07:57:41 -0700
parents 5900d90f5d71
children 1ee100564408
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@0 21 retTable = malloc( sizeof( HashTable ) );
Me@0 22
Me@0 23 retTable->freeEntryContentFn = freeFn;
Me@0 24
Me@1 25 retTable->entries = 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@0 43 newEntries = 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@0 115 hashEntry = (HashEntry*) malloc( sizeof( HashEntry ) );
Me@0 116 if( hashEntry == NULL ) return 0;
Me@1 117 hashEntry->key = strdup( key ); //TODO: figure out soln for incr Sz
Me@0 118 if( hashEntry->key == NULL ) return 0;
Me@0 119 hashEntry->next = (table->entries)[hashIdx];
Me@0 120 (table->entries)[hashIdx] = hashEntry;
Me@0 121 table->numEntries += 1;
Me@0 122 if( table->tableSz < table->numEntries ) doubleTableSize( table );
Me@0 123 }
Me@0 124 else
Me@0 125 { (*(table->freeEntryContentFn))( hashEntry->content );
Me@0 126 }
Me@0 127 hashEntry->content = content;
Me@0 128 return 1;
Me@0 129 }
Me@0 130
Me@0 131 int
Me@1 132 putEntryIntoTable( HashEntry *entry, HashTable *table )
Me@0 133 { unsigned int hashIdx;
Me@0 134 HashEntry* testEntry;
Me@0 135
Me@0 136 testEntry = getEntryFromTable( entry->key, table );
Me@0 137 if( testEntry == NULL )
Me@0 138 { hashIdx = hashThisKey( entry->key, table->tableSz );
Me@0 139 entry->next = (table->entries)[hashIdx];
Me@0 140 (table->entries)[hashIdx] = entry;
Me@0 141 table->numEntries += 1;
Me@0 142 if( table->tableSz < table->numEntries ) doubleTableSize( table );
Me@0 143 }
Me@0 144 else
Me@0 145 { (*(table->freeEntryContentFn))( testEntry->content );
Me@0 146 testEntry->content = entry->content;
Me@0 147 entry->content = NULL;
Me@0 148 freeHashEntryUsing( entry, table );
Me@0 149 }
Me@0 150 return 1;
Me@0 151 }
Me@0 152
Me@1 153
Me@0 154 bool8
Me@0 155 deleteEntryFromTable( char *key, HashTable *table )
Me@1 156 { HashEntry *hashEntry;
Me@1 157 HashEntry **addrOfHashEntryPtr;
Me@1 158 unsigned int hashIndex;
Me@0 159
Me@1 160 hashIndex = hashThisKey( key, table->tableSz );
Me@1 161 addrOfHashEntryPtr = &( table->entries[ hashIndex ] );
Me@1 162 hashEntry = *addrOfHashEntryPtr;
Me@1 163 while( hashEntry != NULL )
Me@1 164 { if( strcmp( hashEntry->key, key ) == 0 )
Me@1 165 {
Me@1 166 *addrOfHashEntryPtr = hashEntry->next;
Me@1 167 //TODO: Free the contents of entry?
Me@1 168 freeHashEntryButNotContent( hashEntry );
Me@1 169 table->numEntries -= 1;
Me@1 170 return TRUE;
Me@1 171 }
Me@1 172 addrOfHashEntryPtr = &( hashEntry->next );
Me@1 173 hashEntry = *addrOfHashEntryPtr;
Me@1 174 }
Me@1 175 return FALSE;
Me@0 176 }
Me@0 177
Me@1 178
Me@0 179 /* debugging function displays the hashtable in (key.value) pairs
Me@0 180 */
Me@0 181 /*void hashTableToString( HashTable * table )
Me@0 182 { int i;
Me@0 183 HashEntry *t;
Me@0 184 for( i = 0; i < table->tableSz; i++ )
Me@0 185 { t = entries[i];
Me@0 186 if( t == NULL )
Me@0 187 strcat_m( retStr, &"()" );
Me@0 188 else
Me@0 189 { strcat_m( retStr, &"(" );
Me@0 190 for( ; t != NULL; t = t->next )
Me@0 191 { strcat_m( retStr, &" " );
Me@0 192 strcat_m( retStr, t->key );
Me@0 193 strcat_m( retStr, &"." );
Me@0 194 strcat_m( retStr, paramToString( t->param ) );
Me@0 195 strcat_m( retStr, &" " );
Me@0 196 }
Me@0 197 strcat_m( retStr, &")" );
Me@0 198 }
Me@0 199 }
Me@0 200 }
Me@0 201 */
Me@0 202
Me@0 203 /*
Me@0 204 void
Me@0 205 setFnToFreeEntryContent( HashTable *table, FreeEntryContentFnPtr fnPtr )
Me@0 206 {
Me@0 207 table->freeEntryContentFn = fnPtr;
Me@0 208 }
Me@0 209 */
Me@0 210
Me@1 211 void
Me@0 212 freeHashTable( HashTable *table )
Me@0 213 { int i;
Me@0 214 HashEntry *hashEntry, *temp, **entries;
Me@0 215
Me@0 216 entries = table->entries;
Me@0 217 for( i=0; i < table->tableSz; i++ )
Me@0 218 { if( entries[i] != NULL )
Me@0 219 { hashEntry = entries[i];
Me@0 220 while( hashEntry != NULL )
Me@0 221 {
Me@0 222 temp = hashEntry->next;
Me@0 223 freeHashEntryUsing( hashEntry, table );
Me@0 224 hashEntry = temp;
Me@0 225 }
Me@0 226 }
Me@0 227 }
Me@0 228 }
Me@0 229
Me@1 230 void
Me@0 231 freeHashEntryUsing( HashEntry *entry, HashTable *table )
Me@0 232 {
Me@0 233 if( entry->content != NULL )
Me@0 234 (*(table->freeEntryContentFn))( entry->content );
Me@0 235 free( entry->key ); //was malloc'd above, so free it
Me@0 236 free( entry );
Me@0 237 }
Me@0 238
Me@1 239 void
Me@1 240 freeHashEntryButNotContent( HashEntry *entry )
Me@1 241 {
Me@1 242 free( entry->key ); //was malloc'd above, so free it
Me@1 243 free( entry );
Me@1 244 }
Me@1 245