merge with/from trunk at r35190
[blender.git] / source / blender / blenlib / BLI_edgehash.h
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: none of this file.
24  *
25  * Contributor(s): Daniel Dunbar
26  *
27  * ***** END GPL LICENSE BLOCK *****
28  */
29  
30 #ifndef BLI_EDGEHASH_H
31 #define BLI_EDGEHASH_H
32
33 /** \file BLI_storage.h
34  *  \ingroup bli
35  *  \author Daniel Dunbar
36  *  \brief A general unordered 2-int pair hash table ADT.
37  */
38
39 #include "MEM_guardedalloc.h"
40 #include "BKE_utildefines.h"
41 #include "BLI_mempool.h"
42
43 struct EdgeHash;
44 struct EdgeHashIterator;
45 typedef struct EdgeHash EdgeHash;
46 typedef struct EdgeHashIterator EdgeHashIterator;
47
48 typedef void    (*EdgeHashFreeFP)(void *key);
49
50 EdgeHash*               BLI_edgehash_new                (void);
51 void                    BLI_edgehash_free               (EdgeHash *eh, EdgeHashFreeFP valfreefp);
52
53         /* Insert edge (v0,v1) into hash with given value, does
54          * not check for duplicates.
55          */
56 //void                  BLI_edgehash_insert             (EdgeHash *eh, int v0, int v1, void *val);
57
58         /* Return value for given edge (v0,v1), or NULL if
59          * if key does not exist in hash. (If need exists 
60          * to differentiate between key-value being NULL and 
61          * lack of key then see BLI_edgehash_lookup_p().
62          */
63 //void*                 BLI_edgehash_lookup             (EdgeHash *eh, int v0, int v1);
64
65         /* Return pointer to value for given edge (v0,v1),
66          * or NULL if key does not exist in hash.
67          */
68 //void**                        BLI_edgehash_lookup_p   (EdgeHash *eh, int v0, int v1);
69
70         /* Return boolean true/false if edge (v0,v1) in hash. */
71 //int                           BLI_edgehash_haskey             (EdgeHash *eh, int v0, int v1);
72
73         /* Return number of keys in hash. */
74 int                             BLI_edgehash_size               (EdgeHash *eh);
75
76         /* Remove all edges from hash. */
77 void                    BLI_edgehash_clear              (EdgeHash *eh, EdgeHashFreeFP valfreefp);
78
79 /***/
80
81         /**
82          * Create a new EdgeHashIterator. The hash table must not be mutated
83          * while the iterator is in use, and the iterator will step exactly
84          * BLI_edgehash_size(gh) times before becoming done.
85          */
86 EdgeHashIterator*       BLI_edgehashIterator_new                (EdgeHash *eh);
87
88         /* Free an EdgeHashIterator. */
89 void                            BLI_edgehashIterator_free               (EdgeHashIterator *ehi);
90
91         /* Retrieve the key from an iterator. */
92 void                            BLI_edgehashIterator_getKey             (EdgeHashIterator *ehi, int *v0_r, int *v1_r);
93         
94         /* Retrieve the value from an iterator. */
95 void*                           BLI_edgehashIterator_getValue   (EdgeHashIterator *ehi);
96
97         /* Set the value for an iterator. */
98 void                            BLI_edgehashIterator_setValue   (EdgeHashIterator *ehi, void *val);
99
100         /* Steps the iterator to the next index. */
101 void                            BLI_edgehashIterator_step               (EdgeHashIterator *ehi);
102
103         /* Determine if an iterator is done. */
104 int                                     BLI_edgehashIterator_isDone             (EdgeHashIterator *ehi);
105
106 /**************inlined code************/
107 static unsigned int _ehash_hashsizes[]= {
108         1, 3, 5, 11, 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209, 
109         16411, 32771, 65537, 131101, 262147, 524309, 1048583, 2097169, 
110         4194319, 8388617, 16777259, 33554467, 67108879, 134217757, 
111         268435459
112 };
113
114 #define EDGEHASH(v0,v1)         ((v0*39)^(v1*31))
115
116 /***/
117
118 typedef struct EdgeEntry EdgeEntry;
119 struct EdgeEntry {
120         EdgeEntry *next;
121         int v0, v1;
122         void *val;
123 };
124
125 struct EdgeHash {
126         EdgeEntry **buckets;
127         BLI_mempool *epool;
128         int nbuckets, nentries, cursize;
129 };
130
131
132 BM_INLINE void BLI_edgehash_insert(EdgeHash *eh, int v0, int v1, void *val) {
133         unsigned int hash;
134         EdgeEntry *e= BLI_mempool_alloc(eh->epool);
135
136         if (v1<v0) {
137                 v0 ^= v1;
138                 v1 ^= v0;
139                 v0 ^= v1;
140         }
141         hash = EDGEHASH(v0,v1)%eh->nbuckets;
142
143         e->v0 = v0;
144         e->v1 = v1;
145         e->val = val;
146         e->next= eh->buckets[hash];
147         eh->buckets[hash]= e;
148         
149         if (++eh->nentries>eh->nbuckets*3) {
150                 EdgeEntry *e, **old= eh->buckets;
151                 int i, nold= eh->nbuckets;
152                 
153                 eh->nbuckets= _ehash_hashsizes[++eh->cursize];
154                 eh->buckets= MEM_mallocN(eh->nbuckets*sizeof(*eh->buckets), "eh buckets");
155                 BMEMSET(eh->buckets, 0, eh->nbuckets*sizeof(*eh->buckets));
156                 
157                 for (i=0; i<nold; i++) {
158                         for (e= old[i]; e;) {
159                                 EdgeEntry *n= e->next;
160                                 
161                                 hash= EDGEHASH(e->v0,e->v1)%eh->nbuckets;
162                                 e->next= eh->buckets[hash];
163                                 eh->buckets[hash]= e;
164                                 
165                                 e= n;
166                         }
167                 }
168                 
169                 MEM_freeN(old);
170         }
171 }
172
173 BM_INLINE void** BLI_edgehash_lookup_p(EdgeHash *eh, int v0, int v1) {
174         unsigned int hash;
175         EdgeEntry *e;
176
177         if (v1<v0) {
178                 v0 ^= v1;
179                 v1 ^= v0;
180                 v0 ^= v1;
181         }
182         hash = EDGEHASH(v0,v1)%eh->nbuckets;
183         for (e= eh->buckets[hash]; e; e= e->next)
184                 if (v0==e->v0 && v1==e->v1)
185                         return &e->val;
186         
187         return NULL;
188 }
189
190 BM_INLINE void* BLI_edgehash_lookup(EdgeHash *eh, int v0, int v1) {
191         void **value_p = BLI_edgehash_lookup_p(eh,v0,v1);
192
193         return value_p?*value_p:NULL;
194 }
195
196 BM_INLINE int BLI_edgehash_haskey(EdgeHash *eh, int v0, int v1) {
197         return BLI_edgehash_lookup_p(eh, v0, v1)!=NULL;
198 }
199
200 #endif
201