Initial revision
[blender.git] / source / blender / blenlib / intern / BLI_ghash.c
1 /**
2  * $Id$
3  *
4  * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version. The Blender
10  * Foundation also sells licenses for use in proprietary software under
11  * the Blender License.  See http://www.blender.org/BL/ for information
12  * about this.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program; if not, write to the Free Software Foundation,
21  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
22  *
23  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
24  * All rights reserved.
25  *
26  * The Original Code is: all of this file.
27  *
28  * Contributor(s): none yet.
29  *
30  * ***** END GPL/BL DUAL LICENSE BLOCK *****
31  * A general (pointer -> pointer) hash table ADT
32  */
33
34 #include <stdlib.h>
35 #include <string.h>
36
37 #include "MEM_guardedalloc.h"
38
39 #include "BLI_ghash.h"
40
41 /***/
42
43 static unsigned int hashsizes[]= {
44         1, 3, 5, 11, 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209, 
45         16411, 32771, 65537, 131101, 262147, 524309, 1048583, 2097169, 
46         4194319, 8388617, 16777259, 33554467, 67108879, 134217757, 
47         268435459
48 };
49
50 /***/
51
52 typedef struct Entry Entry;
53 struct Entry {
54         Entry *next;
55         
56         void *key, *val;
57 };
58
59 struct GHash {
60         GHashHashFP     hashfp;
61         GHashCmpFP      cmpfp;
62         
63         Entry **buckets;
64         int nbuckets, nentries, cursize;
65 };
66
67 /***/
68
69 GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp) {
70         GHash *gh= MEM_mallocN(sizeof(*gh), "GHash");
71         gh->hashfp= hashfp;
72         gh->cmpfp= cmpfp;
73         
74         gh->cursize= 0;
75         gh->nentries= 0;
76         gh->nbuckets= hashsizes[gh->cursize];
77         
78         gh->buckets= malloc(gh->nbuckets*sizeof(*gh->buckets));
79         memset(gh->buckets, 0, gh->nbuckets*sizeof(*gh->buckets));
80         
81         return gh;
82 }
83
84 void BLI_ghash_insert(GHash *gh, void *key, void *val) {
85         unsigned int hash= gh->hashfp(key)%gh->nbuckets;
86         Entry *e= malloc(sizeof(*e));
87
88         e->key= key;
89         e->val= val;
90         e->next= gh->buckets[hash];
91         gh->buckets[hash]= e;
92         
93         if (++gh->nentries>gh->nbuckets*3) {
94                 Entry *e, **old= gh->buckets;
95                 int i, nold= gh->nbuckets;
96                 
97                 gh->nbuckets= hashsizes[++gh->cursize];
98                 gh->buckets= malloc(gh->nbuckets*sizeof(*gh->buckets));
99                 memset(gh->buckets, 0, gh->nbuckets*sizeof(*gh->buckets));
100                 
101                 for (i=0; i<nold; i++) {
102                         for (e= old[i]; e;) {
103                                 Entry *n= e->next;
104                                 
105                                 hash= gh->hashfp(e->key)%gh->nbuckets;
106                                 e->next= gh->buckets[hash];
107                                 gh->buckets[hash]= e;
108                                 
109                                 e= n;
110                         }
111                 }
112                 
113                 free(old);
114         }
115 }
116
117 void* BLI_ghash_lookup(GHash *gh, void *key) {
118         unsigned int hash= gh->hashfp(key)%gh->nbuckets;
119         Entry *e;
120         
121         for (e= gh->buckets[hash]; e; e= e->next)
122                 if (gh->cmpfp(key, e->key)==0)
123                         return e->val;
124         
125         return NULL;
126 }
127
128 int BLI_ghash_haskey(GHash *gh, void *key) {
129         unsigned int hash= gh->hashfp(key)%gh->nbuckets;
130         Entry *e;
131         
132         for (e= gh->buckets[hash]; e; e= e->next)
133                 if (gh->cmpfp(key, e->key)==0)
134                         return 1;
135         
136         return 0;
137 }
138
139 void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp) {
140         int i;
141         
142         for (i=0; i<gh->nbuckets; i++) {
143                 Entry *e;
144                 
145                 for (e= gh->buckets[i]; e; ) {
146                         Entry *n= e->next;
147                         
148                         if (keyfreefp) keyfreefp(e->key);
149                         if (valfreefp) valfreefp(e->val);
150                         free(e);
151                         
152                         e= n;
153                 }
154         }
155         
156         free(gh->buckets);
157         MEM_freeN(gh);
158 }
159
160 /***/
161
162 unsigned int BLI_ghashutil_ptrhash(void *key) {
163         return (unsigned int) key;
164 }
165 int BLI_ghashutil_ptrcmp(void *a, void *b) {
166         if (a==b)
167                 return 0;
168         else
169                 return (a<b)?-1:1;
170 }
171
172 unsigned int BLI_ghashutil_strhash(void *ptr) {
173         char *s= ptr;
174         unsigned int i= 0;
175         unsigned char c;
176         
177         while (c= *s++)
178                 i= i*37 + c;
179                 
180         return i;
181 }
182 int BLI_ghashutil_strcmp(void *a, void *b) {
183         return strcmp(a, b);
184 }