← Back to branch summary

~siretart/ubuntu/utopic/blender/libav10

« back to all changes in this revision

Viewing changes to source/blender/blenlib/intern/edgehash.c

  • Committer: Package Import Robot
  • Author(s): Matthias Klose
  • Date: 2014-02-19 11:24:23 UTC
  • mfrom: (14.2.23 sid)
  • Revision ID: package-import@ubuntu.com-20140219112423-rkmaz2m7ha06d4tk
Tags: 2.69-3ubuntu1
* Merge with Debian; remaining changes:
  - Configure without OpenImageIO on armhf, as it is not available on
    Ubuntu.

Show diffs side-by-side

added added

removed removed

Lines of Context:
source/blender/blenlib/intern/edgehash.c
18
18
 * Contributor(s): Daniel Dunbar, Joseph Eagar
19
19
 *
20
20
 * ***** END GPL LICENSE BLOCK *****
21
 
 * A general (pointer -> pointer) hash table ADT
22
21
 */
23
22
 
24
23
/** \file blender/blenlib/intern/edgehash.c
25
24
 *  \ingroup bli
26
25
 *
 
26
 * A general (pointer -> pointer) hash table ADT
 
27
 *
27
28
 * \note Based on 'BLI_ghash.c', make sure these stay in sync.
28
29
 */
29
30
 
37
38
#include "BLI_utildefines.h"
38
39
#include "BLI_edgehash.h"
39
40
#include "BLI_mempool.h"
40
 
 
41
 
#ifdef __GNUC__
42
 
#  pragma GCC diagnostic error "-Wsign-conversion"
43
 
#  if (__GNUC__ * 100 + __GNUC_MINOR__) >= 406  /* gcc4.6+ only */
44
 
#    pragma GCC diagnostic error "-Wsign-compare"
45
 
#    pragma GCC diagnostic error "-Wconversion"
46
 
#  endif
47
 
#endif
 
41
#include "BLI_strict_flags.h"
48
42
 
49
43
/**************inlined code************/
50
44
static const unsigned int _ehash_hashsizes[] = {
54
48
        268435459
55
49
};
56
50
 
57
 
#define EDGE_HASH(v0, v1)  ((v0 * 39) ^ (v1 * 31))
 
51
/* internal flag to ensure sets values aren't used */
 
52
#ifndef NDEBUG
 
53
#  define EDGEHASH_FLAG_IS_SET (1 << 8)
 
54
#  define IS_EDGEHASH_ASSERT(eh) BLI_assert((eh->flag & EDGEHASH_FLAG_IS_SET) == 0)
 
55
// #  define IS_EDGESET_ASSERT(es) BLI_assert((es->flag & EDGEHASH_FLAG_IS_SET) != 0)
 
56
#else
 
57
#  define IS_EDGEHASH_ASSERT(eh)
 
58
// #  define IS_EDGESET_ASSERT(es)
 
59
#endif
58
60
 
59
61
/* ensure v0 is smaller */
60
62
#define EDGE_ORD(v0, v1) \
66
68
 
67
69
/***/
68
70
 
69
 
typedef struct EdgeEntry EdgeEntry;
70
 
struct EdgeEntry {
71
 
        EdgeEntry *next;
 
71
typedef struct EdgeEntry {
 
72
        struct EdgeEntry *next;
72
73
        unsigned int v0, v1;
73
74
        void *val;
74
 
};
 
75
} EdgeEntry;
75
76
 
76
77
struct EdgeHash {
77
78
        EdgeEntry **buckets;
78
79
        BLI_mempool *epool;
79
 
        unsigned int nbuckets, nentries, cursize;
 
80
        unsigned int nbuckets, nentries;
 
81
        unsigned int cursize, flag;
80
82
};
81
83
 
82
 
/***/
83
 
 
84
 
EdgeHash *BLI_edgehash_new(void)
85
 
{
86
 
        EdgeHash *eh = MEM_callocN(sizeof(*eh), "EdgeHash");
 
84
 
 
85
/* -------------------------------------------------------------------- */
 
86
/* EdgeHash API */
 
87
 
 
88
/** \name Internal Utility API
 
89
 * \{ */
 
90
 
 
91
/**
 
92
 * Get the hash for a key.
 
93
 */
 
94
BLI_INLINE unsigned int edgehash_keyhash(EdgeHash *eh, unsigned int v0, unsigned int v1)
 
95
{
 
96
        BLI_assert(v0 < v1);
 
97
 
 
98
        return ((v0 * 39) ^ (v1 * 31)) % eh->nbuckets;
 
99
}
 
100
 
 
101
/**
 
102
 * Check if the number of items in the GHash is large enough to require more buckets.
 
103
 */
 
104
BLI_INLINE bool edgehash_test_expand_buckets(const unsigned int nentries, const unsigned int nbuckets)
 
105
{
 
106
        return (nentries > nbuckets * 3);
 
107
}
 
108
 
 
109
/**
 
110
 * Expand buckets to the next size up.
 
111
 */
 
112
BLI_INLINE void edgehash_resize_buckets(EdgeHash *eh, const unsigned int nbuckets)
 
113
{
 
114
        EdgeEntry **buckets_old = eh->buckets;
 
115
        EdgeEntry **buckets_new;
 
116
        const unsigned int nbuckets_old = eh->nbuckets;
 
117
        unsigned int i;
 
118
        EdgeEntry *e;
 
119
 
 
120
        BLI_assert(eh->nbuckets != nbuckets);
 
121
 
 
122
        eh->nbuckets = nbuckets;
 
123
        buckets_new = MEM_callocN(eh->nbuckets * sizeof(*eh->buckets), "eh buckets");
 
124
 
 
125
        for (i = 0; i < nbuckets_old; i++) {
 
126
                EdgeEntry *e_next;
 
127
                for (e = buckets_old[i]; e; e = e_next) {
 
128
                        const unsigned hash = edgehash_keyhash(eh, e->v0, e->v1);
 
129
                        e_next = e->next;
 
130
                        e->next = buckets_new[hash];
 
131
                        buckets_new[hash] = e;
 
132
                }
 
133
        }
 
134
 
 
135
        eh->buckets = buckets_new;
 
136
        MEM_freeN(buckets_old);
 
137
}
 
138
 
 
139
/**
 
140
 * Increase initial bucket size to match a reserved ammount.
 
141
 */
 
142
BLI_INLINE void edgehash_buckets_reserve(EdgeHash *eh, const unsigned int nentries_reserve)
 
143
{
 
144
        while (edgehash_test_expand_buckets(nentries_reserve, eh->nbuckets)) {
 
145
                eh->nbuckets = _ehash_hashsizes[++eh->cursize];
 
146
        }
 
147
}
 
148
 
 
149
/**
 
150
 * Internal lookup function.
 
151
 * Takes a hash argument to avoid calling #ghash_keyhash multiple times.
 
152
 */
 
153
BLI_INLINE EdgeEntry *edgehash_lookup_entry_ex(EdgeHash *eh, unsigned int v0, unsigned int v1,
 
154
                                               const unsigned int hash)
 
155
{
 
156
        EdgeEntry *e;
 
157
        BLI_assert(v0 < v1);
 
158
        for (e = eh->buckets[hash]; e; e = e->next) {
 
159
                if (UNLIKELY(v0 == e->v0 && v1 == e->v1)) {
 
160
                        return e;
 
161
                }
 
162
        }
 
163
        return NULL;
 
164
}
 
165
 
 
166
/**
 
167
 * Internal lookup function. Only wraps #edgehash_lookup_entry_ex
 
168
 */
 
169
BLI_INLINE EdgeEntry *edgehash_lookup_entry(EdgeHash *eh, unsigned int v0, unsigned int v1)
 
170
{
 
171
        unsigned int hash;
 
172
        EDGE_ORD(v0, v1); /* ensure v0 is smaller */
 
173
        hash = edgehash_keyhash(eh, v0, v1);
 
174
        return edgehash_lookup_entry_ex(eh, v0, v1, hash);
 
175
}
 
176
 
 
177
 
 
178
static EdgeHash *edgehash_new(const char *info,
 
179
                              const unsigned int nentries_reserve,
 
180
                              const unsigned int entry_size)
 
181
{
 
182
        EdgeHash *eh = MEM_mallocN(sizeof(*eh), info);
 
183
 
 
184
        eh->nbuckets = _ehash_hashsizes[0];  /* eh->cursize */
 
185
        eh->nentries = 0;
87
186
        eh->cursize = 0;
88
 
        eh->nentries = 0;
89
 
        eh->nbuckets = _ehash_hashsizes[eh->cursize];
90
 
        
91
 
        eh->buckets = MEM_callocN(eh->nbuckets * sizeof(*eh->buckets), "eh buckets 2");
92
 
        eh->epool = BLI_mempool_create(sizeof(EdgeEntry), 512, 512, BLI_MEMPOOL_SYSMALLOC);
 
187
        eh->flag = 0;
 
188
 
 
189
        /* if we have reserved the number of elements that this hash will contain */
 
190
        if (nentries_reserve) {
 
191
                edgehash_buckets_reserve(eh, nentries_reserve);
 
192
        }
 
193
 
 
194
        eh->buckets = MEM_callocN(eh->nbuckets * sizeof(*eh->buckets), "eh buckets");
 
195
        eh->epool = BLI_mempool_create(entry_size, 512, 512, BLI_MEMPOOL_SYSMALLOC);
93
196
 
94
197
        return eh;
95
198
}
96
199
 
97
 
 
 
200
/**
 
201
 * Internal insert function.
 
202
 * Takes a hash argument to avoid calling #edgehash_keyhash multiple times.
 
203
 */
 
204
BLI_INLINE void edgehash_insert_ex(EdgeHash *eh, unsigned int v0, unsigned int v1, void *val,
 
205
                                   unsigned int hash)
 
206
{
 
207
        EdgeEntry *e = BLI_mempool_alloc(eh->epool);
 
208
 
 
209
        BLI_assert((eh->flag & EDGEHASH_FLAG_ALLOW_DUPES) || (BLI_edgehash_haskey(eh, v0, v1) == 0));
 
210
        IS_EDGEHASH_ASSERT(eh);
 
211
 
 
212
        /* this helps to track down errors with bad edge data */
 
213
        BLI_assert(v0 < v1);
 
214
        BLI_assert(v0 != v1);
 
215
 
 
216
        e->next = eh->buckets[hash];
 
217
        e->v0 = v0;
 
218
        e->v1 = v1;
 
219
        e->val = val;
 
220
        eh->buckets[hash] = e;
 
221
 
 
222
        if (UNLIKELY(edgehash_test_expand_buckets(++eh->nentries, eh->nbuckets))) {
 
223
                edgehash_resize_buckets(eh, _ehash_hashsizes[++eh->cursize]);
 
224
        }
 
225
}
 
226
 
 
227
/**
 
228
 * Insert function that doesn't set the value (use for EdgeSet)
 
229
 */
 
230
BLI_INLINE void edgehash_insert_ex_keyonly(EdgeHash *eh, unsigned int v0, unsigned int v1,
 
231
                                           unsigned int hash)
 
232
{
 
233
        EdgeEntry *e = BLI_mempool_alloc(eh->epool);
 
234
 
 
235
        BLI_assert((eh->flag & EDGEHASH_FLAG_ALLOW_DUPES) || (BLI_edgehash_haskey(eh, v0, v1) == 0));
 
236
 
 
237
        /* this helps to track down errors with bad edge data */
 
238
        BLI_assert(v0 < v1);
 
239
        BLI_assert(v0 != v1);
 
240
 
 
241
        e->next = eh->buckets[hash];
 
242
        e->v0 = v0;
 
243
        e->v1 = v1;
 
244
        /* intentionally leave value unset */
 
245
        eh->buckets[hash] = e;
 
246
 
 
247
        if (UNLIKELY(edgehash_test_expand_buckets(++eh->nentries, eh->nbuckets))) {
 
248
                edgehash_resize_buckets(eh, _ehash_hashsizes[++eh->cursize]);
 
249
        }
 
250
}
 
251
 
 
252
BLI_INLINE void edgehash_insert(EdgeHash *eh, unsigned int v0, unsigned int v1, void *val)
 
253
{
 
254
        unsigned int hash;
 
255
        EDGE_ORD(v0, v1); /* ensure v0 is smaller */
 
256
        hash = edgehash_keyhash(eh, v0, v1);
 
257
        edgehash_insert_ex(eh, v0, v1, val, hash);
 
258
}
 
259
 
 
260
/**
 
261
 * Run free callbacks for freeing entries.
 
262
 */
 
263
static void edgehash_free_cb(EdgeHash *eh, EdgeHashFreeFP valfreefp)
 
264
{
 
265
        unsigned int i;
 
266
 
 
267
        BLI_assert(valfreefp);
 
268
 
 
269
        for (i = 0; i < eh->nbuckets; i++) {
 
270
                EdgeEntry *e;
 
271
 
 
272
                for (e = eh->buckets[i]; e; ) {
 
273
                        EdgeEntry *e_next = e->next;
 
274
 
 
275
                        if (valfreefp) valfreefp(e->val);
 
276
 
 
277
                        e = e_next;
 
278
                }
 
279
        }
 
280
}
 
281
 
 
282
/** \} */
 
283
 
 
284
 
 
285
/** \name Public API
 
286
 * \{ */
 
287
 
 
288
/* Public API */
 
289
 
 
290
EdgeHash *BLI_edgehash_new_ex(const char *info,
 
291
                              const unsigned int nentries_reserve)
 
292
{
 
293
        return edgehash_new(info,
 
294
                            nentries_reserve,
 
295
                            sizeof(EdgeEntry));
 
296
}
 
297
 
 
298
EdgeHash *BLI_edgehash_new(const char *info)
 
299
{
 
300
        return BLI_edgehash_new_ex(info, 0);
 
301
}
 
302
 
 
303
/**
 
304
 * Insert edge (\a v0, \a v1) into hash with given value, does
 
305
 * not check for duplicates.
 
306
 */
98
307
void BLI_edgehash_insert(EdgeHash *eh, unsigned int v0, unsigned int v1, void *val)
99
308
{
 
309
        edgehash_insert(eh, v0, v1, val);
 
310
}
 
311
 
 
312
/**
 
313
 * Assign a new value to a key that may already be in edgehash.
 
314
 */
 
315
bool BLI_edgehash_reinsert(EdgeHash *eh, unsigned int v0, unsigned int v1, void *val)
 
316
{
100
317
        unsigned int hash;
101
 
        EdgeEntry *e = BLI_mempool_alloc(eh->epool);
 
318
        EdgeEntry *e;
102
319
 
103
 
        /* this helps to track down errors with bad edge data */
104
 
        BLI_assert(v0 != v1);
 
320
        IS_EDGEHASH_ASSERT(eh);
105
321
 
106
322
        EDGE_ORD(v0, v1); /* ensure v0 is smaller */
107
 
 
108
 
        hash = EDGE_HASH(v0, v1) % eh->nbuckets;
109
 
 
110
 
        e->next = eh->buckets[hash];
111
 
        e->v0 = v0;
112
 
        e->v1 = v1;
113
 
        e->val = val;
114
 
        eh->buckets[hash] = e;
115
 
 
116
 
        if (UNLIKELY(++eh->nentries > eh->nbuckets / 2)) {
117
 
                EdgeEntry **old = eh->buckets;
118
 
                const unsigned int nold = eh->nbuckets;
119
 
                unsigned int i;
120
 
 
121
 
                eh->nbuckets = _ehash_hashsizes[++eh->cursize];
122
 
                eh->buckets = MEM_callocN(eh->nbuckets * sizeof(*eh->buckets), "eh buckets");
123
 
 
124
 
                for (i = 0; i < nold; i++) {
125
 
                        EdgeEntry *e_next;
126
 
                        for (e = old[i]; e; e = e_next) {
127
 
                                e_next = e->next;
128
 
                                hash = EDGE_HASH(e->v0, e->v1) % eh->nbuckets;
129
 
                                e->next = eh->buckets[hash];
130
 
                                eh->buckets[hash] = e;
131
 
                        }
132
 
                }
133
 
 
134
 
                MEM_freeN(old);
 
323
        hash = edgehash_keyhash(eh, v0, v1);
 
324
 
 
325
        e = edgehash_lookup_entry_ex(eh, v0, v1, hash);
 
326
        if (e) {
 
327
                e->val = val;
 
328
                return false;
 
329
        }
 
330
        else {
 
331
                edgehash_insert_ex(eh, v0, v1, val, hash);
 
332
                return true;
135
333
        }
136
334
}
137
335
 
 
336
/**
 
337
 * Return pointer to value for given edge (\a v0, \a v1),
 
338
 * or NULL if key does not exist in hash.
 
339
 */
138
340
void **BLI_edgehash_lookup_p(EdgeHash *eh, unsigned int v0, unsigned int v1)
139
341
{
140
 
        unsigned int hash;
141
 
        EdgeEntry *e;
142
 
 
143
 
        EDGE_ORD(v0, v1); /* ensure v0 is smaller */
144
 
 
145
 
        hash = EDGE_HASH(v0, v1) % eh->nbuckets;
146
 
        for (e = eh->buckets[hash]; e; e = e->next)
147
 
                if (v0 == e->v0 && v1 == e->v1)
148
 
                        return &e->val;
149
 
 
150
 
        return NULL;
 
342
        EdgeEntry *e = edgehash_lookup_entry(eh, v0, v1);
 
343
        IS_EDGEHASH_ASSERT(eh);
 
344
        return e ? &e->val : NULL;
151
345
}
152
346
 
 
347
/**
 
348
 * Return value for given edge (\a v0, \a v1), or NULL if
 
349
 * if key does not exist in hash. (If need exists
 
350
 * to differentiate between key-value being NULL and
 
351
 * lack of key then see BLI_edgehash_lookup_p().
 
352
 */
153
353
void *BLI_edgehash_lookup(EdgeHash *eh, unsigned int v0, unsigned int v1)
154
354
{
155
 
        void **value_p = BLI_edgehash_lookup_p(eh, v0, v1);
156
 
 
157
 
        return value_p ? *value_p : NULL;
 
355
        EdgeEntry *e = edgehash_lookup_entry(eh, v0, v1);
 
356
        IS_EDGEHASH_ASSERT(eh);
 
357
        return e ? e->val : NULL;
158
358
}
159
359
 
 
360
/**
 
361
 * Return boolean true/false if edge (v0,v1) in hash.
 
362
 */
160
363
bool BLI_edgehash_haskey(EdgeHash *eh, unsigned int v0, unsigned int v1)
161
364
{
162
 
        return BLI_edgehash_lookup_p(eh, v0, v1) != NULL;
 
365
        return (edgehash_lookup_entry(eh, v0, v1) != NULL);
163
366
}
164
367
 
 
368
/**
 
369
 * Return number of keys in hash.
 
370
 */
165
371
int BLI_edgehash_size(EdgeHash *eh)
166
372
{
167
373
        return (int)eh->nentries;
168
374
}
169
375
 
170
 
void BLI_edgehash_clear(EdgeHash *eh, EdgeHashFreeFP valfreefp)
 
376
/**
 
377
 * Remove all edges from hash.
 
378
 */
 
379
void BLI_edgehash_clear_ex(EdgeHash *eh, EdgeHashFreeFP valfreefp,
 
380
                           const unsigned int nentries_reserve)
171
381
{
172
 
        unsigned int i;
173
 
        
174
 
        for (i = 0; i < eh->nbuckets; i++) {
175
 
                EdgeEntry *e;
176
 
                
177
 
                for (e = eh->buckets[i]; e; ) {
178
 
                        EdgeEntry *n = e->next;
179
 
                        
180
 
                        if (valfreefp) valfreefp(e->val);
181
 
                        BLI_mempool_free(eh->epool, e);
182
 
                        
183
 
                        e = n;
184
 
                }
185
 
                eh->buckets[i] = NULL;
 
382
        if (valfreefp)
 
383
                edgehash_free_cb(eh, valfreefp);
 
384
 
 
385
        eh->nbuckets = _ehash_hashsizes[0];  /* eh->cursize */
 
386
        eh->nentries = 0;
 
387
        eh->cursize = 0;
 
388
 
 
389
        if (nentries_reserve) {
 
390
                edgehash_buckets_reserve(eh, nentries_reserve);
186
391
        }
187
392
 
188
 
        eh->nentries = 0;
 
393
        MEM_freeN(eh->buckets);
 
394
        eh->buckets = MEM_callocN(eh->nbuckets * sizeof(*eh->buckets), "eh buckets");
 
395
 
 
396
        BLI_mempool_clear_ex(eh->epool, nentries_reserve ? (int)nentries_reserve : -1);
189
397
}
190
398
 
191
399
void BLI_edgehash_free(EdgeHash *eh, EdgeHashFreeFP valfreefp)
192
400
{
193
 
        BLI_edgehash_clear(eh, valfreefp);
 
401
        BLI_assert((int)eh->nentries == BLI_mempool_count(eh->epool));
 
402
 
 
403
        if (valfreefp)
 
404
                edgehash_free_cb(eh, valfreefp);
194
405
 
195
406
        BLI_mempool_destroy(eh->epool);
196
407
 
199
410
}
200
411
 
201
412
 
202
 
/***/
 
413
void BLI_edgehash_flag_set(EdgeHash *eh, unsigned int flag)
 
414
{
 
415
        eh->flag |= flag;
 
416
}
 
417
 
 
418
void BLI_edgehash_flag_clear(EdgeHash *eh, unsigned int flag)
 
419
{
 
420
        eh->flag &= ~flag;
 
421
}
 
422
 
 
423
/** \} */
 
424
 
 
425
 
 
426
/* -------------------------------------------------------------------- */
 
427
/* EdgeHash Iterator API */
 
428
 
 
429
/** \name Iterator API
 
430
 * \{ */
203
431
 
204
432
struct EdgeHashIterator {
205
433
        EdgeHash *eh;
207
435
        EdgeEntry *curEntry;
208
436
};
209
437
 
 
438
 
 
439
/**
 
440
 * Create a new EdgeHashIterator. The hash table must not be mutated
 
441
 * while the iterator is in use, and the iterator will step exactly
 
442
 * BLI_edgehash_size(gh) times before becoming done.
 
443
 */
210
444
EdgeHashIterator *BLI_edgehashIterator_new(EdgeHash *eh)
211
445
{
212
446
        EdgeHashIterator *ehi = MEM_mallocN(sizeof(*ehi), "eh iter");
221
455
        }
222
456
        return ehi;
223
457
}
 
458
 
 
459
/**
 
460
 * Free an EdgeHashIterator.
 
461
 */
224
462
void BLI_edgehashIterator_free(EdgeHashIterator *ehi)
225
463
{
226
464
        MEM_freeN(ehi);
227
465
}
228
466
 
 
467
/**
 
468
 * Retrieve the key from an iterator.
 
469
 */
229
470
void BLI_edgehashIterator_getKey(EdgeHashIterator *ehi, unsigned int *v0_r, unsigned int *v1_r)
230
471
{
231
472
        if (ehi->curEntry) {
233
474
                *v1_r = ehi->curEntry->v1;
234
475
        }
235
476
}
 
477
 
 
478
/**
 
479
 * Retrieve the value from an iterator.
 
480
 */
236
481
void *BLI_edgehashIterator_getValue(EdgeHashIterator *ehi)
237
482
{
238
483
        return ehi->curEntry ? ehi->curEntry->val : NULL;
239
484
}
240
485
 
 
486
/**
 
487
 * Retrieve the pointer to the value from an iterator.
 
488
 */
 
489
void **BLI_edgehashIterator_getValue_p(EdgeHashIterator *ehi)
 
490
{
 
491
        return ehi->curEntry ? &ehi->curEntry->val : NULL;
 
492
}
 
493
 
 
494
/**
 
495
 * Set the value for an iterator.
 
496
 */
241
497
void BLI_edgehashIterator_setValue(EdgeHashIterator *ehi, void *val)
242
498
{
243
499
        if (ehi->curEntry) {
245
501
        }
246
502
}
247
503
 
 
504
/**
 
505
 * Steps the iterator to the next index.
 
506
 */
248
507
void BLI_edgehashIterator_step(EdgeHashIterator *ehi)
249
508
{
250
509
        if (ehi->curEntry) {
259
518
                }
260
519
        }
261
520
}
 
521
 
 
522
/**
 
523
 * Determine if an iterator is done.
 
524
 */
262
525
bool BLI_edgehashIterator_isDone(EdgeHashIterator *ehi)
263
526
{
264
527
        return (ehi->curEntry == NULL);
265
528
}
 
529
 
 
530
/** \} */
 
531
 
 
532
/* -------------------------------------------------------------------- */
 
533
/* EdgeSet API */
 
534
 
 
535
/* Use edgehash API to give 'set' functionality */
 
536
 
 
537
/** \name EdgeSet Functions
 
538
 * \{ */
 
539
EdgeSet *BLI_edgeset_new_ex(const char *info,
 
540
                                  const unsigned int nentries_reserve)
 
541
{
 
542
        EdgeSet *es = (EdgeSet *)edgehash_new(info,
 
543
                                              nentries_reserve,
 
544
                                              sizeof(EdgeEntry) - sizeof(void *));
 
545
#ifndef NDEBUG
 
546
        ((EdgeHash *)es)->flag |= EDGEHASH_FLAG_IS_SET;
 
547
#endif
 
548
        return es;
 
549
}
 
550
 
 
551
EdgeSet *BLI_edgeset_new(const char *info)
 
552
{
 
553
        return BLI_edgeset_new_ex(info, 0);
 
554
}
 
555
 
 
556
int BLI_edgeset_size(EdgeSet *es)
 
557
{
 
558
        return (int)((EdgeHash *)es)->nentries;
 
559
}
 
560
 
 
561
/**
 
562
 * Adds the key to the set (no checks for unique keys!).
 
563
 * Matching #BLI_edgehash_insert
 
564
 */
 
565
void BLI_edgeset_insert(EdgeSet *es, unsigned int v0, unsigned int v1)
 
566
{
 
567
        unsigned int hash;
 
568
        EDGE_ORD(v0, v1); /* ensure v0 is smaller */
 
569
        hash = edgehash_keyhash((EdgeHash *)es, v0, v1);
 
570
        edgehash_insert_ex_keyonly((EdgeHash *)es, v0, v1, hash);
 
571
}
 
572
 
 
573
/**
 
574
 * Assign a new value to a key that may already be in edgehash.
 
575
 */
 
576
bool BLI_edgeset_reinsert(EdgeSet *es, unsigned int v0, unsigned int v1)
 
577
{
 
578
        unsigned int hash;
 
579
        EdgeEntry *e;
 
580
 
 
581
        EDGE_ORD(v0, v1); /* ensure v0 is smaller */
 
582
        hash = edgehash_keyhash((EdgeHash *)es, v0, v1);
 
583
 
 
584
        e = edgehash_lookup_entry_ex((EdgeHash *)es, v0, v1, hash);
 
585
        if (e) {
 
586
                return false;
 
587
        }
 
588
        else {
 
589
                edgehash_insert_ex_keyonly((EdgeHash *)es, v0, v1, hash);
 
590
                return true;
 
591
        }
 
592
}
 
593
 
 
594
bool BLI_edgeset_haskey(EdgeSet *es, unsigned int v0, unsigned int v1)
 
595
{
 
596
        return (edgehash_lookup_entry((EdgeHash *)es, v0, v1) != NULL);
 
597
}
 
598
 
 
599
 
 
600
void BLI_edgeset_free(EdgeSet *es)
 
601
{
 
602
        BLI_edgehash_free((EdgeHash *)es, NULL);
 
603
}
 
604
 
 
605
/** \} */