implementation of mbox folder with unique messages numbers
[claws.git] / src / chash.c
1
2 /*
3  * libEtPan! -- a mail stuff library
4  *
5  * chash - Implements generic hash tables.
6  *
7  * Copyright (c) 1999-2000, GaĆ«l Roualland <gael.roualland@iname.com>
8  * interface changes - 2002 - DINH Viet Hoa
9  * All rights reserved.
10  *
11  * Redistribution and use in source and binary forms, with or without
12  * modification, are permitted provided that the following conditions
13  * are met:
14  * 1. Redistributions of source code must retain the above copyright
15  *    notice, this list of conditions and the following disclaimer.
16  * 2. Redistributions in binary form must reproduce the above copyright
17  *    notice, this list of conditions and the following disclaimer in the
18  *    documentation and/or other materials provided with the distribution.
19  * 3. Neither the name of the libEtPan! project nor the names of its
20  *    contributors may be used to endorse or promote products derived
21  *    from this software without specific prior written permission.
22  *
23  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33  * SUCH DAMAGE.
34  */
35
36 #include <stdlib.h>
37 #include <string.h>
38
39 #include "chash.h"
40
41 /* This defines the maximum (average) number of entries per bucket.
42    The hash is resized everytime inserting an entry makes the
43    average go over that value. */
44 #define CHASH_MAXDEPTH    3
45
46 static inline unsigned int chash_func(const char * key, int len) {
47   register unsigned int c = 0, t;
48   register const char * k = key;
49   
50   while (len--) {
51     c += (c << 4) + *k++;
52     if ((t = c & 0xF0000000)) {
53       c ^= t >> 24;
54       c ^= t;
55     }
56   }
57   return c;
58 }
59
60 static inline char * chash_dup(const char * data, int len)
61 {
62   char * r;
63
64   r = (char *) malloc(len * sizeof(char));
65   if (!r)
66     return NULL;
67   memcpy(r, data, len * sizeof(char));
68   return r;
69 }
70
71 chash * chash_new(int size, int flags)
72 {
73   chash * h;
74
75   h = (chash *) malloc(sizeof(chash));
76   if (h == NULL)
77     return NULL;
78
79   h->count = 0;
80   h->cells = (struct chashcell **) calloc(size, sizeof(struct chashcell *));
81   if (h->cells == NULL) {
82     free(h);
83     return NULL;
84   }
85   h->size = size;
86   h->copykey = flags & CHASH_COPYKEY;
87   h->copyvalue = flags & CHASH_COPYVALUE;
88   
89   return h;
90 }
91
92 int chash_get(chash * hash,
93               chashdatum * key, chashdatum * result)
94 {
95   unsigned int func;
96   chashiter * iter;
97   
98   func = chash_func(key->data, key->len);
99
100   /* look for the key in existing cells */
101   iter = hash->cells[func % hash->size];
102   while (iter) {
103     if (iter->key.len == key->len && iter->func == func
104         && !memcmp(iter->key.data, key->data, key->len)) {
105       * result = iter->value; /* found */
106
107       return 0;
108     }
109     iter = iter->next;
110   }
111
112   return -1;
113 }
114
115 int chash_set(chash * hash,
116               chashdatum * key,
117               chashdatum * value,
118               chashdatum * oldvalue)
119 {
120   unsigned int func, indx;
121   chashiter * iter, * cell;
122   int r;
123
124   if (hash->count > hash->size * CHASH_MAXDEPTH) {
125     r = chash_resize(hash, (hash->count / CHASH_MAXDEPTH) * 2 + 1);
126     if (r < 0)
127       goto err;
128   }
129
130   func = chash_func(key->data, key->len);
131   indx = func % hash->size;
132
133   /* look for the key in existing cells */
134   iter = hash->cells[indx];
135   while (iter) {
136     if (iter->key.len == key->len && iter->func == func
137         && !memcmp(iter->key.data, key->data, key->len)) {
138       /* found, replacing entry */
139       if (hash->copyvalue) {
140         char * data;
141
142         data = chash_dup(value->data, value->len);
143         if (data == NULL)
144           goto err;
145
146         free(iter->value.data);
147         iter->value.data = data;
148         iter->value.len = value->len;
149       } else {
150         if (oldvalue != NULL) {
151           oldvalue->data = iter->value.data;
152           oldvalue->len = iter->value.len;
153         }
154         iter->value.data = value->data;
155         iter->value.len = value->len;
156       }
157       if (!hash->copykey)
158         iter->key.data = key->data;
159
160       if (oldvalue != NULL) {
161         oldvalue->data = value->data;
162         oldvalue->len = value->len;
163       }
164
165       return 0;
166     }
167     iter = iter->next;
168   }
169   
170   if (oldvalue != NULL) {
171     oldvalue->data = NULL;
172     oldvalue->len = 0;
173   }
174   
175   /* not found, adding entry */
176   cell = (struct chashcell *) malloc(sizeof(struct chashcell));
177   if (cell == NULL)
178     goto err;
179
180   if (hash->copykey) {
181     cell->key.data = chash_dup(key->data, key->len);
182     if (cell->key.data == NULL)
183       goto free;
184   }
185   else
186     cell->key.data = key->data;
187
188   cell->key.len = key->len;
189   if (hash->copyvalue) {
190     cell->value.data = chash_dup(value->data, value->len);
191     if (cell->value.data == NULL)
192       goto free_key_data;
193   }
194   else
195     cell->value.data = value->data;
196
197   cell->value.len = value->len;
198   cell->func = func;
199   cell->next = hash->cells[indx];
200   hash->cells[indx] = cell;
201   hash->count++;
202
203   return 0;
204   
205  free_key_data:
206   if (hash->copykey)
207     free(cell->key.data);
208  free:
209   free(cell);
210  err:
211   return -1;
212 }
213
214 int chash_delete(chash * hash, chashdatum * key, chashdatum * oldvalue)
215 {
216   /*  chashdatum result = { NULL, TRUE }; */
217   unsigned int func, indx;
218   chashiter * iter, * old;
219
220   /*  
221   if (!keylen)
222     keylen = strlen(key) + 1;  
223   */
224
225   func = chash_func(key->data, key->len);
226   indx = func % hash->size;
227
228   /* look for the key in existing cells */
229   old = NULL;
230   iter = hash->cells[indx];
231   while (iter) {
232     if (iter->key.len == key->len && iter->func == func
233         && !memcmp(iter->key.data, key->data, key->len)) {
234       /* found, deleting */
235       if (old)
236         old->next = iter->next;
237       else
238         hash->cells[indx] = iter->next;
239       if (hash->copykey)
240         free(iter->key.data);
241       if (hash->copyvalue)
242         free(iter->value.data);
243       else {
244         if (oldvalue != NULL) {
245           oldvalue->data = iter->value.data;
246           oldvalue->len = iter->value.len;
247         }
248       }
249       free(iter);
250       hash->count--;
251       return 0;
252     }
253     old = iter;
254     iter = iter->next;
255   }
256
257   return -1; /* not found */
258 }
259
260 void chash_free(chash * hash) {
261   int indx;
262   chashiter * iter, * next;
263
264   /* browse the hash table */
265   for(indx = 0; indx < hash->size; indx++) {
266     iter = hash->cells[indx];
267     while (iter) {
268       next = iter->next;
269       if (hash->copykey)
270         free(iter->key.data);
271       if (hash->copyvalue)
272         free(iter->value.data);
273       free(iter);
274       iter = next;
275     }
276   }
277   free(hash->cells);
278   free(hash);
279 }
280
281 void chash_clear(chash * hash) {
282   int indx;
283   chashiter * iter, * next;
284
285   /* browse the hash table */
286   for(indx = 0; indx < hash->size; indx++) {
287     iter = hash->cells[indx];
288     while (iter) {
289       next = iter->next;
290       if (hash->copykey)
291         free(iter->key.data);
292       if (hash->copyvalue)
293         free(iter->value.data);
294       free(iter);
295       iter = next;
296     }
297   }
298   memset(hash->cells, 0, hash->size * sizeof(* hash->cells));
299   hash->count = 0;
300 }
301
302 chashiter * chash_begin(chash * hash) {
303   chashiter * iter;
304   int indx = 0;
305   
306   iter = hash->cells[0];
307   while(!iter) {
308     indx++;
309     if (indx >= hash->size)
310       return NULL;
311     iter = hash->cells[indx];
312   }
313   return iter;
314 }
315
316 chashiter * chash_next(chash * hash, chashiter * iter) {
317   int indx;
318
319   if (!iter)
320     return NULL;
321
322   indx = iter->func % hash->size;
323   iter = iter->next;
324
325   while(!iter) {
326     indx++;
327     if (indx >= hash->size)
328       return NULL;
329     iter = hash->cells[indx];
330   }
331   return iter;
332 }
333
334 int chash_resize(chash * hash, int size)
335 {
336   struct chashcell ** cells;
337   int indx, nindx;
338   chashiter * iter, * next;
339   
340   if (hash->size == size)
341     return 0;
342
343   cells = (struct chashcell **) calloc(size, sizeof(struct chashcell *));
344   if (!cells)
345     return -1;
346
347   /* browse initial hash and copy items in second hash */
348   for(indx = 0; indx < hash->size; indx++) {
349     iter = hash->cells[indx];
350     while (iter) {
351       next = iter->next;
352       nindx = iter->func % size;
353       iter->next = cells[nindx];
354       cells[nindx] = iter;
355       iter = next;
356     }
357   }
358   free(hash->cells);
359   hash->size = size;
360   hash->cells = cells;
361
362   return 0;
363 }
364
365 #ifdef NO_MACROS
366 int chash_count(chash * hash) {
367   return hash->count;
368 }
369
370 int chash_size(chash * hash) {
371   return hash->size;
372 }
373
374 void chash_value(chashiter * iter, chashdatum * result) {
375   * result = iter->value;
376 }
377
378 void chash_key(chashiter * iter, chashdatum * result) {
379   * result = iter->key;
380 }
381 #endif