1 /******************************************************************************
2 * $Id$
3 *
4 * Project: MapServer
5 * Purpose: Implement hashTableObj class.
6 * Author: Sean Gillies, sgillies@frii.com
7 *
8 ******************************************************************************
9 * Copyright (c) 1996-2005 Regents of the University of Minnesota.
10 *
11 * Permission is hereby granted, free of charge, to any person obtaining a
12 * copy of this software and associated documentation files (the "Software"),
13 * to deal in the Software without restriction, including without limitation
14 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
15 * and/or sell copies of the Software, and to permit persons to whom the
16 * Software is furnished to do so, subject to the following conditions:
17 *
18 * The above copyright notice and this permission notice shall be included in
19 * all copies of this Software or works derived from this Software.
20 *
21 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
22 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
23 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
24 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
25 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
26 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
27 * DEALINGS IN THE SOFTWARE.
28 ****************************************************************************/
29
30 #include <ctype.h>
31
32 #include "mapserver.h"
33 #include "maphash.h"
34
35
36
hash(const char * key)37 static unsigned hash(const char *key)
38 {
39 unsigned hashval;
40
41 for(hashval=0; *key!='\0'; key++)
42 hashval = tolower(*key) + 31 * hashval;
43
44 return(hashval % MS_HASHSIZE);
45 }
46
msCreateHashTable()47 hashTableObj *msCreateHashTable()
48 {
49 int i;
50 hashTableObj *table;
51
52 table = (hashTableObj *) msSmallMalloc(sizeof(hashTableObj));
53 table->items = (struct hashObj **) msSmallMalloc(sizeof(struct hashObj *)*MS_HASHSIZE);
54
55 for (i=0; i<MS_HASHSIZE; i++)
56 table->items[i] = NULL;
57 table->numitems = 0;
58
59 return table;
60 }
61
initHashTable(hashTableObj * table)62 int initHashTable( hashTableObj *table )
63 {
64 int i;
65
66 table->items = (struct hashObj **) malloc(sizeof(struct hashObj *)*MS_HASHSIZE);
67 MS_CHECK_ALLOC(table->items, sizeof(struct hashObj *)*MS_HASHSIZE, MS_FAILURE);
68
69 for (i=0; i<MS_HASHSIZE; i++)
70 table->items[i] = NULL;
71 table->numitems = 0;
72 return MS_SUCCESS;
73 }
74
msFreeHashTable(hashTableObj * table)75 void msFreeHashTable( hashTableObj *table )
76 {
77 if( table != NULL ) {
78 msFreeHashItems(table);
79 free(table);
80 table = NULL;
81 }
82 }
83
msHashIsEmpty(hashTableObj * table)84 int msHashIsEmpty( hashTableObj *table )
85 {
86 if (table->numitems == 0 )
87 return MS_TRUE;
88 else
89 return MS_FALSE;
90 }
91
92
msFreeHashItems(hashTableObj * table)93 void msFreeHashItems( hashTableObj *table )
94 {
95 int i;
96 struct hashObj *tp=NULL;
97 struct hashObj *prev_tp=NULL;
98
99 if (table) {
100 if(table->items) {
101 for (i=0; i<MS_HASHSIZE; i++) {
102 if (table->items[i] != NULL) {
103 for (tp=table->items[i]; tp!=NULL; prev_tp=tp,tp=tp->next,free(prev_tp)) {
104 msFree(tp->key);
105 msFree(tp->data);
106 }
107 }
108 }
109 free(table->items);
110 table->items = NULL;
111 } else {
112 msSetError(MS_HASHERR, "No items allocated.", "msFreeHashItems()");
113 }
114 } else {
115 msSetError(MS_HASHERR, "Can't free NULL table", "msFreeHashItems()");
116 }
117 }
118
msInsertHashTable(hashTableObj * table,const char * key,const char * value)119 struct hashObj *msInsertHashTable(hashTableObj *table,
120 const char *key, const char *value) {
121 struct hashObj *tp;
122 unsigned hashval;
123
124 if (!table || !key || !value) {
125 msSetError(MS_HASHERR, "Invalid hash table or key",
126 "msInsertHashTable");
127 return NULL;
128 }
129
130 for (tp=table->items[hash(key)]; tp!=NULL; tp=tp->next)
131 if(strcasecmp(key, tp->key) == 0)
132 break;
133
134 if (tp == NULL) { /* not found */
135 tp = (struct hashObj *) malloc(sizeof(*tp));
136 MS_CHECK_ALLOC(tp, sizeof(*tp), NULL);
137 tp->key = msStrdup(key);
138 hashval = hash(key);
139 tp->next = table->items[hashval];
140 table->items[hashval] = tp;
141 table->numitems++;
142 } else {
143 free(tp->data);
144 }
145
146 if ((tp->data = msStrdup(value)) == NULL)
147 return NULL;
148
149 return tp;
150 }
151
msLookupHashTable(hashTableObj * table,const char * key)152 const char *msLookupHashTable(hashTableObj *table, const char *key)
153 {
154 struct hashObj *tp;
155
156 if (!table || !key) {
157 return(NULL);
158 }
159
160 for (tp=table->items[hash(key)]; tp!=NULL; tp=tp->next)
161 if (strcasecmp(key, tp->key) == 0)
162 return(tp->data);
163
164 return NULL;
165 }
166
msRemoveHashTable(hashTableObj * table,const char * key)167 int msRemoveHashTable(hashTableObj *table, const char *key)
168 {
169 struct hashObj *tp;
170 struct hashObj *prev_tp=NULL;
171 int status = MS_FAILURE;
172
173 if (!table || !key) {
174 msSetError(MS_HASHERR, "No hash table", "msRemoveHashTable");
175 return MS_FAILURE;
176 }
177
178 tp=table->items[hash(key)];
179 if (!tp) {
180 msSetError(MS_HASHERR, "No such hash entry", "msRemoveHashTable");
181 return MS_FAILURE;
182 }
183
184 prev_tp = NULL;
185 while (tp != NULL) {
186 if (strcasecmp(key, tp->key) == 0) {
187 status = MS_SUCCESS;
188 if (prev_tp) {
189 prev_tp->next = tp->next;
190 msFree(tp->key);
191 msFree(tp->data);
192 free(tp);
193 break;
194 } else {
195 table->items[hash(key)] = tp->next;
196 msFree(tp->key);
197 msFree(tp->data);
198 free(tp);
199 break;
200 }
201 }
202 prev_tp = tp;
203 tp = tp->next;
204 }
205
206 if (status == MS_SUCCESS)
207 table->numitems--;
208
209 return status;
210 }
211
msFirstKeyFromHashTable(hashTableObj * table)212 const char *msFirstKeyFromHashTable( hashTableObj *table )
213 {
214 int hash_index;
215
216 if (!table) {
217 msSetError(MS_HASHERR, "No hash table", "msFirstKeyFromHashTable");
218 return NULL;
219 }
220
221 for (hash_index = 0; hash_index < MS_HASHSIZE; hash_index++ ) {
222 if (table->items[hash_index] != NULL )
223 return table->items[hash_index]->key;
224 }
225
226 return NULL;
227 }
228
msNextKeyFromHashTable(hashTableObj * table,const char * lastKey)229 const char *msNextKeyFromHashTable( hashTableObj *table, const char *lastKey )
230 {
231 int hash_index;
232 struct hashObj *link;
233
234 if (!table) {
235 msSetError(MS_HASHERR, "No hash table", "msNextKeyFromHashTable");
236 return NULL;
237 }
238
239 if ( lastKey == NULL )
240 return msFirstKeyFromHashTable( table );
241
242 hash_index = hash(lastKey);
243 for ( link = table->items[hash_index];
244 link != NULL && strcasecmp(lastKey,link->key) != 0;
245 link = link->next ) {}
246
247 if ( link != NULL && link->next != NULL )
248 return link->next->key;
249
250 while ( ++hash_index < MS_HASHSIZE ) {
251 if ( table->items[hash_index] != NULL )
252 return table->items[hash_index]->key;
253 }
254
255 return NULL;
256 }
257
258