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

comparison PrivateHash.c @ 1:5900d90f5d71

find changesets by author, revision, files, or words in the commit message
Works -- fixed some minor bugs -- VMSHW_matrix_mult working
author Me
date Wed, 28 Jul 2010 13:14:54 -0700
parents ee3ad252427e
children e6fe47763ee6
comparison
equal deleted inserted replaced
0:f0e4ce38c5d6 1:5157320b1061
1 /* 1 /*
2 * Copyright 2009 OpenSourceCodeStewardshipFoundation.org 2 * Copyright 2009 OpenSourceCodeStewardshipFoundation.org
3 * Licensed under GNU General Public License version 2 3 * Licensed under GNU General Public License version 2
4 * 4 *
5 * NOTE: this version of SRSW correct as of April 25, 2010
6 * 5 *
7 * Author: seanhalle@yahoo.com 6 * Author: seanhalle@yahoo.com
8 */ 7 */
9 8
10 9
21 { HashTable * retTable; 20 { HashTable * retTable;
22 retTable = malloc( sizeof( HashTable ) ); 21 retTable = malloc( sizeof( HashTable ) );
23 22
24 retTable->freeEntryContentFn = freeFn; 23 retTable->freeEntryContentFn = freeFn;
25 24
26 retTable->entries = malloc( numHashSlots * sizeof(HashEntry *) ); 25 retTable->entries = malloc( numHashSlots * sizeof(HashEntry *) );
27 retTable->tableSz = numHashSlots; 26 retTable->numEntries = 0;
27 retTable->tableSz = numHashSlots;
28 28
29 nullOutTablesArray( retTable ); 29 nullOutTablesArray( retTable );
30 30
31 return retTable; 31 return retTable;
32 } 32 }
33 33
34 void 34 void
35 doubleTableSize( HashTable *table ) 35 doubleTableSize( HashTable *table )
36 { int i, oldTableSz, newTableSz; 36 { int i, oldTableSz, newTableSz;
37 HashEntry *entry, **oldEntries, **newEntries; 37 HashEntry *entry, *nextEntry, **oldEntries, **newEntries;
38 38
39 oldTableSz = table->tableSz; 39 oldTableSz = table->tableSz;
40 oldEntries = table->entries; 40 oldEntries = table->entries;
41 41
42 newTableSz = 2 * oldTableSz + 1; 42 newTableSz = 2 * oldTableSz + 1;
49 // move all the entries from old to new 49 // move all the entries from old to new
50 for( i=0; i < oldTableSz; i++ ) 50 for( i=0; i < oldTableSz; i++ )
51 { if( oldEntries[i] != NULL ) 51 { if( oldEntries[i] != NULL )
52 { entry = oldEntries[i]; 52 { entry = oldEntries[i];
53 while( entry != NULL ) 53 while( entry != NULL )
54 { 54 { nextEntry = entry->next;
55 addEntryToTable( entry, table ); //does not allocate anything 55 entry->next = NULL;
56 entry = entry->next; 56 putEntryIntoTable( entry, table ); //does not allocate anything
57 entry = nextEntry;
57 } 58 }
58 } 59 }
59 } 60 }
60 } 61 }
61 62
62 void 63 void
63 nullOutTablesArray( HashTable *table ) 64 nullOutTablesArray( HashTable *table )
64 { int i, tableSz; 65 { int i, tableSz;
65 tableSz = table->tableSz; 66 tableSz = table->tableSz;
66 HashEntry ** entries = table->entries; 67 HashEntry ** entries = table->entries;
67 for( i = 0; i < tableSz; i++ ) 68 for( i = 0; i < tableSz; i++ )
68 entries[ i ] = NULL; 69 entries[ i ] = NULL;
69 } 70 }
70 71
71 unsigned int 72 unsigned int
72 hashThisKey( char *s, int hashSz ) 73 hashThisKey( char *s, int hashSz )
73 { unsigned int h = 0; 74 { unsigned int h = 0;
74 75
75 for( ; *s != 0; s++ ) 76 for( ; *s != 0; s++ )
76 h = *s + h*31; 77 h = *s + h*31;
77 return h % hashSz; 78 return h % hashSz;
78 } 79 }
79 80
80 /*Need this to be separated out, for use in both getParam and putParam 81 /*Need this to be separated out, for use in both getParam and putParam
81 */ 82 */
82 HashEntry * 83 HashEntry *
83 getEntryFromTable( char *key, HashTable * table ) 84 getEntryFromTable( char *key, HashTable * table )
84 { unsigned int 85 { unsigned int
85 hashIndex = hashKey( key, table->tableSz ); 86 hashIndex = hashThisKey( key, table->tableSz );
86 HashEntry* 87 HashEntry*
87 hashEntry = table->entries[ hashIndex ]; 88 hashEntry = table->entries[ hashIndex ];
88 for( ; hashEntry != NULL; hashEntry = hashEntry->next ) 89 for( ; hashEntry != NULL; hashEntry = hashEntry->next )
89 { if( strcmp( hashEntry->key, key ) == 0 ) return hashEntry; 90 { if( strcmp( hashEntry->key, key ) == 0 ) return hashEntry;
90 } 91 }
91 return NULL; 92 return NULL;
92 } 93 }
93 94
94 void * 95 void *
95 getValueFromTable( char *key, HashTable * table ) 96 getValueFromTable( char *key, HashTable * table )
96 { HashEntry *entry; 97 { HashEntry *entry;
97 entry = lookupKeyInHash( key, table ); 98 entry = getEntryFromTable( key, table );
98 if( entry == NULL ) return NULL; 99 if( entry == NULL ) return NULL;
99 100
100 return entry->content; 101 return entry->content;
101 } 102 }
102 103
104
105 /*If key already has a value, clobber the old one and replace it
106 */
103 int 107 int
104 addToTable( char* key, void *content, HashTable *table ) 108 addValueIntoTable( char* key, void *content, HashTable *table )
105 { unsigned int hashIdx; 109 { unsigned int hashIdx;
106 HashEntry* hashEntry; 110 HashEntry* hashEntry;
107 111
108 hashEntry = getEntryFromTable( key, table ); 112 hashEntry = getEntryFromTable( key, table );
109 if( hashEntry == NULL ) 113 if( hashEntry == NULL )
110 { hashIdx = hashThisKey( key, table->tableSz ); 114 { hashIdx = hashThisKey( key, table->tableSz );
111 hashEntry = (HashEntry*) malloc( sizeof( HashEntry ) ); 115 hashEntry = (HashEntry*) malloc( sizeof( HashEntry ) );
112 if( hashEntry == NULL ) return 0; 116 if( hashEntry == NULL ) return 0;
113 hashEntry->key = strdup_m( key ); //TODO: figure out soln for incr Sz 117 hashEntry->key = strdup( key ); //TODO: figure out soln for incr Sz
114 if( hashEntry->key == NULL ) return 0; 118 if( hashEntry->key == NULL ) return 0;
115 hashEntry->next = (table->entries)[hashIdx]; 119 hashEntry->next = (table->entries)[hashIdx];
116 (table->entries)[hashIdx] = hashEntry; 120 (table->entries)[hashIdx] = hashEntry;
117 table->numEntries += 1; 121 table->numEntries += 1;
118 if( table->tableSz < table->numEntries ) doubleTableSize( table ); 122 if( table->tableSz < table->numEntries ) doubleTableSize( table );
123 hashEntry->content = content; 127 hashEntry->content = content;
124 return 1; 128 return 1;
125 } 129 }
126 130
127 int 131 int
128 addEntryToTable( HashEntry *entry, HashTable *table ) 132 putEntryIntoTable( HashEntry *entry, HashTable *table )
129 { unsigned int hashIdx; 133 { unsigned int hashIdx;
130 HashEntry* testEntry; 134 HashEntry* testEntry;
131 135
132 testEntry = getEntryFromTable( entry->key, table ); 136 testEntry = getEntryFromTable( entry->key, table );
133 if( testEntry == NULL ) 137 if( testEntry == NULL )
144 freeHashEntryUsing( entry, table ); 148 freeHashEntryUsing( entry, table );
145 } 149 }
146 return 1; 150 return 1;
147 } 151 }
148 152
153
149 bool8 154 bool8
150 deleteEntryFromTable( char *key, HashTable *table ) 155 deleteEntryFromTable( char *key, HashTable *table )
151 { 156 { HashEntry *hashEntry;
152 table->numEntries -= 1; 157 HashEntry **addrOfHashEntryPtr;
153 158 unsigned int hashIndex;
154 } 159
155 160 hashIndex = hashThisKey( key, table->tableSz );
156 161 addrOfHashEntryPtr = &( table->entries[ hashIndex ] );
157 char* 162 hashEntry = *addrOfHashEntryPtr;
158 strdup_m( char *o ) 163 while( hashEntry != NULL )
159 { int len = strlen(o)+1; 164 { if( strcmp( hashEntry->key, key ) == 0 )
160 char *ns = (char*) malloc( len * sizeof(char) ); 165 {
161 strcpy( ns, o ); 166 *addrOfHashEntryPtr = hashEntry->next;
162 return ns; 167 //TODO: Free the contents of entry?
163 } 168 freeHashEntryButNotContent( hashEntry );
164 169 table->numEntries -= 1;
170 return TRUE;
171 }
172 addrOfHashEntryPtr = &( hashEntry->next );
173 hashEntry = *addrOfHashEntryPtr;
174 }
175 return FALSE;
176 }
177
178
165 /* debugging function displays the hashtable in (key.value) pairs 179 /* debugging function displays the hashtable in (key.value) pairs
166 */ 180 */
167 /*void hashTableToString( HashTable * table ) 181 /*void hashTableToString( HashTable * table )
168 { int i; 182 { int i;
169 HashEntry *t; 183 HashEntry *t;
192 { 206 {
193 table->freeEntryContentFn = fnPtr; 207 table->freeEntryContentFn = fnPtr;
194 } 208 }
195 */ 209 */
196 210
197 void 211 void
198 freeHashTable( HashTable *table ) 212 freeHashTable( HashTable *table )
199 { int i; 213 { int i;
200 HashEntry *hashEntry, *temp, **entries; 214 HashEntry *hashEntry, *temp, **entries;
201 215
202 entries = table->entries; 216 entries = table->entries;
211 } 225 }
212 } 226 }
213 } 227 }
214 } 228 }
215 229
216 void 230 void
217 freeHashEntryUsing( HashEntry *entry, HashTable *table ) 231 freeHashEntryUsing( HashEntry *entry, HashTable *table )
218 { 232 {
219 if( entry->content != NULL ) 233 if( entry->content != NULL )
220 (*(table->freeEntryContentFn))( entry->content ); 234 (*(table->freeEntryContentFn))( entry->content );
221 free( entry->key ); //was malloc'd above, so free it 235 free( entry->key ); //was malloc'd above, so free it
222 free( entry ); 236 free( entry );
223 } 237 }
224 238
239 void
240 freeHashEntryButNotContent( HashEntry *entry )
241 {
242 free( entry->key ); //was malloc'd above, so free it
243 free( entry );
244 }
245