merge with trunk at r31523
[blender.git] / source / blender / blenlib / intern / BLI_ghash.c
1 /**
2  * $Id$
3  *
4  * ***** BEGIN GPL 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.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19  *
20  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
21  * All rights reserved.
22  *
23  * The Original Code is: all of this file.
24  *
25  * Contributor(s): none yet.
26  *
27  * ***** END GPL LICENSE BLOCK *****
28  * A general (pointer -> pointer) hash table ADT
29  */
30
31 #include "MEM_guardedalloc.h"
32
33 #include "BLI_ghash.h"
34 #include "BLO_sys_types.h" // for intptr_t support
35 /***/
36
37 unsigned int hashsizes[]= {
38         5, 11, 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209, 
39         16411, 32771, 65537, 131101, 262147, 524309, 1048583, 2097169, 
40         4194319, 8388617, 16777259, 33554467, 67108879, 134217757, 
41         268435459
42 };
43
44 /***/
45
46 /***/
47
48 GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info) {
49         GHash *gh= MEM_mallocN(sizeof(*gh), info);
50         gh->hashfp= hashfp;
51         gh->cmpfp= cmpfp;
52         gh->entrypool = BLI_mempool_create(sizeof(Entry), 64, 64, 1, 0);
53
54         gh->cursize= 0;
55         gh->nentries= 0;
56         gh->nbuckets= hashsizes[gh->cursize];
57         
58         gh->buckets= MEM_mallocN(gh->nbuckets*sizeof(*gh->buckets), "buckets");
59         memset(gh->buckets, 0, gh->nbuckets*sizeof(*gh->buckets));
60         
61         return gh;
62 }
63
64 #ifdef BLI_ghash_insert
65 #undef BLI_ghash_insert
66 #endif
67
68 int BLI_ghash_size(GHash *gh) {
69         return gh->nentries;
70 }
71
72 void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp) {
73         int i;
74         
75         if (keyfreefp || valfreefp) {
76                 for (i=0; i<gh->nbuckets; i++) {
77                         Entry *e;
78                         
79                         for (e= gh->buckets[i]; e; ) {
80                                 Entry *n= e->next;
81                                 
82                                 if (keyfreefp) keyfreefp(e->key);
83                                 if (valfreefp) valfreefp(e->val);
84
85                                 e= n;
86                         }
87                 }
88         }
89         
90         MEM_freeN(gh->buckets);
91         BLI_mempool_destroy(gh->entrypool);
92         gh->buckets = 0;
93         gh->nentries = 0;
94         gh->nbuckets = 0;
95         MEM_freeN(gh);
96 }
97
98 /***/
99
100 GHashIterator *BLI_ghashIterator_new(GHash *gh) {
101         GHashIterator *ghi= MEM_mallocN(sizeof(*ghi), "ghash iterator");
102         ghi->gh= gh;
103         ghi->curEntry= NULL;
104         ghi->curBucket= -1;
105         while (!ghi->curEntry) {
106                 ghi->curBucket++;
107                 if (ghi->curBucket==ghi->gh->nbuckets)
108                         break;
109                 ghi->curEntry= ghi->gh->buckets[ghi->curBucket];
110         }
111         return ghi;
112 }
113 void BLI_ghashIterator_init(GHashIterator *ghi, GHash *gh) {
114         ghi->gh= gh;
115         ghi->curEntry= NULL;
116         ghi->curBucket= -1;
117         while (!ghi->curEntry) {
118                 ghi->curBucket++;
119                 if (ghi->curBucket==ghi->gh->nbuckets)
120                         break;
121                 ghi->curEntry= ghi->gh->buckets[ghi->curBucket];
122         }
123 }
124 void BLI_ghashIterator_free(GHashIterator *ghi) {
125         MEM_freeN(ghi);
126 }
127
128 void *BLI_ghashIterator_getKey(GHashIterator *ghi) {
129         return ghi->curEntry?ghi->curEntry->key:NULL;
130 }
131 void *BLI_ghashIterator_getValue(GHashIterator *ghi) {
132         return ghi->curEntry?ghi->curEntry->val:NULL;
133 }
134
135 void BLI_ghashIterator_step(GHashIterator *ghi) {
136         if (ghi->curEntry) {
137                 ghi->curEntry= ghi->curEntry->next;
138                 while (!ghi->curEntry) {
139                         ghi->curBucket++;
140                         if (ghi->curBucket==ghi->gh->nbuckets)
141                                 break;
142                         ghi->curEntry= ghi->gh->buckets[ghi->curBucket];
143                 }
144         }
145 }
146 int BLI_ghashIterator_isDone(GHashIterator *ghi) {
147         return !ghi->curEntry;
148 }
149
150 /***/
151
152 unsigned int BLI_ghashutil_ptrhash(void *key) {
153         return (unsigned int)(intptr_t)key;
154 }
155 int BLI_ghashutil_ptrcmp(void *a, void *b) {
156         if (a==b)
157                 return 0;
158         else
159                 return (a<b)?-1:1;
160 }
161
162 unsigned int BLI_ghashutil_inthash(void *ptr) {
163         uintptr_t key = (uintptr_t)ptr;
164
165         key += ~(key << 16);
166         key ^=  (key >>  5);
167         key +=  (key <<  3);
168         key ^=  (key >> 13);
169         key += ~(key <<  9);
170         key ^=  (key >> 17);
171
172           return (unsigned int)(key & 0xffffffff);
173 }
174
175 int BLI_ghashutil_intcmp(void *a, void *b) {
176         if (a==b)
177                 return 0;
178         else
179                 return (a<b)?-1:1;
180 }
181
182 unsigned int BLI_ghashutil_strhash(void *ptr) {
183         char *s= ptr;
184         unsigned int i= 0;
185         unsigned char c;
186         
187         while ( (c= *s++) )
188                 i= i*37 + c;
189                 
190         return i;
191 }
192 int BLI_ghashutil_strcmp(void *a, void *b) {
193         return strcmp(a, b);
194 }