VMS/C_Libraries/Hash_impl: e6fe47763ee6 PrivateHash.c

view PrivateHash.c @ 3:e6fe47763ee6

Updated copyright

author	Me
date	Sat, 11 Sep 2010 07:57:41 -0700
parents	5900d90f5d71
children	1ee100564408

line source

1 /*

3 * Licensed under GNU General Public License version 2

4 *

5 *

6 * Author: seanhalle@yahoo.com

7 */

10 #include <stdio.h>

11 #include <string.h>

12 #include <errno.h>

13 #include <stdlib.h>

15 #include "PrivateHash.h"

18 HashTable *

19 makeHashTable( int numHashSlots, FreeEntryContentFnPtr freeFn )

20 { HashTable * retTable;

21 retTable = malloc( sizeof( HashTable ) );

23 retTable->freeEntryContentFn = freeFn;

25 retTable->entries = malloc( numHashSlots * sizeof(HashEntry *) );

26 retTable->numEntries = 0;

27 retTable->tableSz = numHashSlots;

29 nullOutTablesArray( retTable );

31 return retTable;

32 }

34 void

35 doubleTableSize( HashTable *table )

36 { int i, oldTableSz, newTableSz;

37 HashEntry *entry, *nextEntry, **oldEntries, **newEntries;

39 oldTableSz = table->tableSz;

40 oldEntries = table->entries;

42 newTableSz = 2 * oldTableSz + 1;

43 newEntries = malloc( newTableSz * sizeof(HashEntry *) );

45 table->tableSz = newTableSz;

46 table->entries = newEntries;

47 table->numEntries = 0; //about to add them all back!

49 // move all the entries from old to new

50 for( i=0; i < oldTableSz; i++ )

51 { if( oldEntries[i] != NULL )

52 { entry = oldEntries[i];

53 while( entry != NULL )

54 { nextEntry = entry->next;

55 entry->next = NULL;

56 putEntryIntoTable( entry, table ); //does not allocate anything

57 entry = nextEntry;

58 }

59 }

60 }

61 }

63 void

64 nullOutTablesArray( HashTable *table )

65 { int i, tableSz;

66 tableSz = table->tableSz;

67 HashEntry ** entries = table->entries;

68 for( i = 0; i < tableSz; i++ )

69 entries[ i ] = NULL;

70 }

72 unsigned int

73 hashThisKey( char *s, int hashSz )

74 { unsigned int h = 0;

76 for( ; *s != 0; s++ )

77 h = *s + h*31;

78 return h % hashSz;

79 }

81 /*Need this to be separated out, for use in both getParam and putParam

82 */

83 HashEntry *

84 getEntryFromTable( char *key, HashTable * table )

85 { unsigned int

86 hashIndex = hashThisKey( key, table->tableSz );

87 HashEntry*

88 hashEntry = table->entries[ hashIndex ];

89 for( ; hashEntry != NULL; hashEntry = hashEntry->next )

90 { if( strcmp( hashEntry->key, key ) == 0 ) return hashEntry;

91 }

92 return NULL;

93 }

95 void *

96 getValueFromTable( char *key, HashTable * table )

97 { HashEntry *entry;

98 entry = getEntryFromTable( key, table );

99 if( entry == NULL ) return NULL;

100

101 return entry->content;

102 }

103

104

105 /*If key already has a value, clobber the old one and replace it

106 */

107 int

108 addValueIntoTable( char* key, void *content, HashTable *table )

109 { unsigned int hashIdx;

110 HashEntry* hashEntry;

111

112 hashEntry = getEntryFromTable( key, table );

113 if( hashEntry == NULL )

114 { hashIdx = hashThisKey( key, table->tableSz );

115 hashEntry = (HashEntry*) malloc( sizeof( HashEntry ) );

116 if( hashEntry == NULL ) return 0;

117 hashEntry->key = strdup( key ); //TODO: figure out soln for incr Sz

118 if( hashEntry->key == NULL ) return 0;

119 hashEntry->next = (table->entries)[hashIdx];

120 (table->entries)[hashIdx] = hashEntry;

121 table->numEntries += 1;

122 if( table->tableSz < table->numEntries ) doubleTableSize( table );

123 }

124 else

125 { (*(table->freeEntryContentFn))( hashEntry->content );

126 }

127 hashEntry->content = content;

128 return 1;

129 }

130

131 int

132 putEntryIntoTable( HashEntry *entry, HashTable *table )

133 { unsigned int hashIdx;

134 HashEntry* testEntry;

135

136 testEntry = getEntryFromTable( entry->key, table );

137 if( testEntry == NULL )

138 { hashIdx = hashThisKey( entry->key, table->tableSz );

139 entry->next = (table->entries)[hashIdx];

140 (table->entries)[hashIdx] = entry;

141 table->numEntries += 1;

142 if( table->tableSz < table->numEntries ) doubleTableSize( table );

143 }

144 else

145 { (*(table->freeEntryContentFn))( testEntry->content );

146 testEntry->content = entry->content;

147 entry->content = NULL;

148 freeHashEntryUsing( entry, table );

149 }

150 return 1;

151 }

152

153

154 bool8

155 deleteEntryFromTable( char *key, HashTable *table )

156 { HashEntry *hashEntry;

157 HashEntry **addrOfHashEntryPtr;

158 unsigned int hashIndex;

159

160 hashIndex = hashThisKey( key, table->tableSz );

161 addrOfHashEntryPtr = &( table->entries[ hashIndex ] );

162 hashEntry = *addrOfHashEntryPtr;

163 while( hashEntry != NULL )

164 { if( strcmp( hashEntry->key, key ) == 0 )

165 {

166 *addrOfHashEntryPtr = hashEntry->next;

167 //TODO: Free the contents of entry?

168 freeHashEntryButNotContent( hashEntry );

169 table->numEntries -= 1;

170 return TRUE;

171 }

172 addrOfHashEntryPtr = &( hashEntry->next );

173 hashEntry = *addrOfHashEntryPtr;

174 }

175 return FALSE;

176 }

177

178

179 /* debugging function displays the hashtable in (key.value) pairs

180 */

181 /*void hashTableToString( HashTable * table )

182 { int i;

183 HashEntry *t;

184 for( i = 0; i < table->tableSz; i++ )

185 { t = entries[i];

186 if( t == NULL )

187 strcat_m( retStr, &"()" );

188 else

189 { strcat_m( retStr, &"(" );

190 for( ; t != NULL; t = t->next )

191 { strcat_m( retStr, &" " );

192 strcat_m( retStr, t->key );

193 strcat_m( retStr, &"." );

194 strcat_m( retStr, paramToString( t->param ) );

195 strcat_m( retStr, &" " );

196 }

197 strcat_m( retStr, &")" );

198 }

199 }

200 }

201 */

202

203 /*

204 void

205 setFnToFreeEntryContent( HashTable *table, FreeEntryContentFnPtr fnPtr )

206 {

207 table->freeEntryContentFn = fnPtr;

208 }

209 */

210

211 void

212 freeHashTable( HashTable *table )

213 { int i;

214 HashEntry *hashEntry, *temp, **entries;

215

216 entries = table->entries;

217 for( i=0; i < table->tableSz; i++ )

218 { if( entries[i] != NULL )

219 { hashEntry = entries[i];

220 while( hashEntry != NULL )

221 {

222 temp = hashEntry->next;

223 freeHashEntryUsing( hashEntry, table );

224 hashEntry = temp;

225 }

226 }

227 }

228 }

229

230 void

231 freeHashEntryUsing( HashEntry *entry, HashTable *table )

232 {

233 if( entry->content != NULL )

234 (*(table->freeEntryContentFn))( entry->content );

235 free( entry->key ); //was malloc'd above, so free it

236 free( entry );

237 }

238

239 void

240 freeHashEntryButNotContent( HashEntry *entry )

241 {

242 free( entry->key ); //was malloc'd above, so free it

243 free( entry );

244 }

245

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

view PrivateHash.c @ 3:e6fe47763ee6