merge with trunk at r27259 and commit of a patch by anthony jones to fix msvc (though...
[blender-staging.git] / source / blender / blenlib / BLI_edgehash.h
1 /**
2  * A general unordered 2-int pair hash table ADT
3  * 
4  * $Id$
5  *
6  * ***** BEGIN GPL LICENSE BLOCK *****
7  *
8  * This program is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU General Public License
10  * as published by the Free Software Foundation; either version 2
11  * of the License, or (at your option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License
19  * along with this program; if not, write to the Free Software Foundation,
20  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
21  *
22  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
23  * All rights reserved.
24  *
25  * The Original Code is: none of this file.
26  *
27  * Contributor(s): Daniel Dunbar
28  *
29  * ***** END GPL LICENSE BLOCK *****
30  */
31  
32 #ifndef BLI_EDGEHASH_H
33 #define BLI_EDGEHASH_H
34
35 #include "MEM_guardedalloc.h"
36 #include "BKE_utildefines.h"
37 #include "BLI_mempool.h"
38
39 struct EdgeHash;
40 struct EdgeHashIterator;
41 typedef struct EdgeHash EdgeHash;
42 typedef struct EdgeHashIterator EdgeHashIterator;
43
44 typedef void    (*EdgeHashFreeFP)(void *key);
45
46 EdgeHash*               BLI_edgehash_new                (void);
47 void                    BLI_edgehash_free               (EdgeHash *eh, EdgeHashFreeFP valfreefp);
48
49         /* Insert edge (v0,v1) into hash with given value, does
50          * not check for duplicates.
51          */
52 //void                  BLI_edgehash_insert             (EdgeHash *eh, int v0, int v1, void *val);
53
54         /* Return value for given edge (v0,v1), or NULL if
55          * if key does not exist in hash. (If need exists 
56          * to differentiate between key-value being NULL and 
57          * lack of key then see BLI_edgehash_lookup_p().
58          */
59 //void*                 BLI_edgehash_lookup             (EdgeHash *eh, int v0, int v1);
60
61         /* Return pointer to value for given edge (v0,v1),
62          * or NULL if key does not exist in hash.
63          */
64 //void**                        BLI_edgehash_lookup_p   (EdgeHash *eh, int v0, int v1);
65
66         /* Return boolean true/false if edge (v0,v1) in hash. */
67 //int                           BLI_edgehash_haskey             (EdgeHash *eh, int v0, int v1);
68
69         /* Return number of keys in hash. */
70 int                             BLI_edgehash_size               (EdgeHash *eh);
71
72         /* Remove all edges from hash. */
73 void                    BLI_edgehash_clear              (EdgeHash *eh, EdgeHashFreeFP valfreefp);
74
75 /***/
76
77         /**
78          * Create a new EdgeHashIterator. The hash table must not be mutated
79          * while the iterator is in use, and the iterator will step exactly
80          * BLI_edgehash_size(gh) times before becoming done.
81          */
82 EdgeHashIterator*       BLI_edgehashIterator_new                (EdgeHash *eh);
83
84         /* Free an EdgeHashIterator. */
85 void                            BLI_edgehashIterator_free               (EdgeHashIterator *ehi);
86
87         /* Retrieve the key from an iterator. */
88 void                            BLI_edgehashIterator_getKey             (EdgeHashIterator *ehi, int *v0_r, int *v1_r);
89         
90         /* Retrieve the value from an iterator. */
91 void*                           BLI_edgehashIterator_getValue   (EdgeHashIterator *ehi);
92
93         /* Set the value for an iterator. */
94 void                            BLI_edgehashIterator_setValue   (EdgeHashIterator *ehi, void *val);
95
96         /* Steps the iterator to the next index. */
97 void                            BLI_edgehashIterator_step               (EdgeHashIterator *ehi);
98
99         /* Determine if an iterator is done. */
100 int                                     BLI_edgehashIterator_isDone             (EdgeHashIterator *ehi);
101
102 /**************inlined code************/
103 static unsigned int _ehash_hashsizes[]= {
104         1, 3, 5, 11, 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209, 
105         16411, 32771, 65537, 131101, 262147, 524309, 1048583, 2097169, 
106         4194319, 8388617, 16777259, 33554467, 67108879, 134217757, 
107         268435459
108 };
109
110 #define EDGEHASH(v0,v1)         ((v0*39)^(v1*31))
111
112 /***/
113
114 typedef struct EdgeEntry EdgeEntry;
115 struct EdgeEntry {
116         EdgeEntry *next;
117         int v0, v1;
118         void *val;
119 };
120
121 struct EdgeHash {
122         EdgeEntry **buckets;
123         BLI_mempool *epool;
124         int nbuckets, nentries, cursize;
125 };
126
127
128 BM_INLINE void BLI_edgehash_insert(EdgeHash *eh, int v0, int v1, void *val) {
129         unsigned int hash;
130         EdgeEntry *e= BLI_mempool_alloc(eh->epool);
131
132         if (v1<v0) {
133                 v0 ^= v1;
134                 v1 ^= v0;
135                 v0 ^= v1;
136         }
137         hash = EDGEHASH(v0,v1)%eh->nbuckets;
138
139         e->v0 = v0;
140         e->v1 = v1;
141         e->val = val;
142         e->next= eh->buckets[hash];
143         eh->buckets[hash]= e;
144         
145         if (++eh->nentries>eh->nbuckets*3) {
146                 EdgeEntry *e, **old= eh->buckets;
147                 int i, nold= eh->nbuckets;
148                 
149                 eh->nbuckets= _ehash_hashsizes[++eh->cursize];
150                 eh->buckets= MEM_mallocN(eh->nbuckets*sizeof(*eh->buckets), "eh buckets");
151                 BMEMSET(eh->buckets, 0, eh->nbuckets*sizeof(*eh->buckets));
152                 
153                 for (i=0; i<nold; i++) {
154                         for (e= old[i]; e;) {
155                                 EdgeEntry *n= e->next;
156                                 
157                                 hash= EDGEHASH(e->v0,e->v1)%eh->nbuckets;
158                                 e->next= eh->buckets[hash];
159                                 eh->buckets[hash]= e;
160                                 
161                                 e= n;
162                         }
163                 }
164                 
165                 MEM_freeN(old);
166         }
167 }
168
169 BM_INLINE void** BLI_edgehash_lookup_p(EdgeHash *eh, int v0, int v1) {
170         unsigned int hash;
171         EdgeEntry *e;
172
173         if (v1<v0) {
174                 v0 ^= v1;
175                 v1 ^= v0;
176                 v0 ^= v1;
177         }
178         hash = EDGEHASH(v0,v1)%eh->nbuckets;
179         for (e= eh->buckets[hash]; e; e= e->next)
180                 if (v0==e->v0 && v1==e->v1)
181                         return &e->val;
182         
183         return NULL;
184 }
185
186 BM_INLINE void* BLI_edgehash_lookup(EdgeHash *eh, int v0, int v1) {
187         void **value_p = BLI_edgehash_lookup_p(eh,v0,v1);
188
189         return value_p?*value_p:NULL;
190 }
191
192 BM_INLINE int BLI_edgehash_haskey(EdgeHash *eh, int v0, int v1) {
193         return BLI_edgehash_lookup_p(eh, v0, v1)!=NULL;
194 }
195
196 #endif
197