← Back to branch summary

~siretart/ubuntu/utopic/blender/libav10

« back to all changes in this revision

Viewing changes to source/blender/blenlib/BLI_ghash.h

  • Committer: Package Import Robot
  • Author(s): Matteo F. Vescovi
  • Date: 2012-07-23 08:54:18 UTC
  • mfrom: (14.2.16 sid)
  • mto: (14.2.19 sid)
  • mto: This revision was merged to the branch mainline in revision 42.
  • Revision ID: package-import@ubuntu.com-20120723085418-9foz30v6afaf5ffs
Tags: 2.63a-2
http://bugs.debian.org/658075
* debian/: Cycles support added (Closes: #658075)
  For now, this top feature has been enabled only
  on [any-amd64 any-i386] architectures because
  of OpenImageIO failing on all others
* debian/: scripts installation path changed
  from /usr/lib to /usr/share:
  + debian/patches/: patchset re-worked for path changing
  + debian/control: "Breaks" field added on yafaray-exporter

Show diffs side-by-side

added added

removed removed

Lines of Context:
source/blender/blenlib/BLI_ghash.h
1
 
/**
2
 
 * A general (pointer -> pointer) hash table ADT
3
 
 * 
4
 
 * $Id: BLI_ghash.h 28640 2010-05-07 07:54:25Z campbellbarton $
5
 
 *
 
1
/*
6
2
 * ***** BEGIN GPL LICENSE BLOCK *****
7
3
 *
8
4
 * This program is free software; you can redistribute it and/or
29
25
 * ***** END GPL LICENSE BLOCK *****
30
26
 */
31
27
 
32
 
#ifndef BLI_GHASH_H
33
 
#define BLI_GHASH_H
 
28
#ifndef __BLI_GHASH_H__
 
29
#define __BLI_GHASH_H__
 
30
 
 
31
/** \file BLI_ghash.h
 
32
 *  \ingroup bli
 
33
 *  \brief A general (pointer -> pointer) hash table ADT
 
34
 */
34
35
 
35
36
#ifdef __cplusplus
36
37
extern "C" {
37
38
#endif
38
39
 
39
 
#include "stdio.h"
40
 
#include "stdlib.h"
41
 
#include "string.h"
42
 
 
43
 
#include "BKE_utildefines.h"
44
 
#include "MEM_guardedalloc.h"
45
 
 
46
 
#include "BLI_mempool.h"
47
 
#include "BLI_blenlib.h"
48
 
 
49
 
typedef unsigned int    (*GHashHashFP)          (void *key);
50
 
typedef int                             (*GHashCmpFP)           (void *a, void *b);
 
40
typedef unsigned int    (*GHashHashFP)          (const void *key);
 
41
typedef int                             (*GHashCmpFP)           (const void *a, const void *b);
51
42
typedef void                    (*GHashKeyFreeFP)       (void *key);
52
43
typedef void                    (*GHashValFreeFP)       (void *val);
53
44
 
54
45
typedef struct Entry {
55
46
        struct Entry *next;
56
 
        
 
47
 
57
48
        void *key, *val;
58
49
} Entry;
59
50
 
60
51
typedef struct GHash {
61
52
        GHashHashFP     hashfp;
62
53
        GHashCmpFP      cmpfp;
63
 
        
 
54
 
64
55
        Entry **buckets;
65
56
        struct BLI_mempool *entrypool;
66
57
        int nbuckets, nentries, cursize;
72
63
        struct Entry *curEntry;
73
64
} GHashIterator;
74
65
 
75
 
GHash*  BLI_ghash_new           (GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info);
76
 
void    BLI_ghash_free          (GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
77
 
 
78
 
//BM_INLINE void        BLI_ghash_insert        (GHash *gh, void *key, void *val);
79
 
//BM_INLINE int         BLI_ghash_remove        (GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
80
 
//BM_INLINE void*       BLI_ghash_lookup        (GHash *gh, void *key);
81
 
//BM_INLINE int         BLI_ghash_haskey        (GHash *gh, void *key);
82
 
 
83
 
int             BLI_ghash_size          (GHash *gh);
 
66
/* *** */
 
67
 
 
68
GHash* BLI_ghash_new   (GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info);
 
69
void   BLI_ghash_free  (GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
 
70
void   BLI_ghash_insert(GHash *gh, void *key, void *val);
 
71
void * BLI_ghash_lookup(GHash *gh, const void *key);
 
72
int    BLI_ghash_remove(GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
 
73
int    BLI_ghash_haskey(GHash *gh, void *key);
 
74
int        BLI_ghash_size  (GHash *gh);
84
75
 
85
76
/* *** */
86
77
 
89
80
         * while the iterator is in use, and the iterator will step exactly
90
81
         * BLI_ghash_size(gh) times before becoming done.
91
82
         * 
92
 
         * @param gh The GHash to iterate over.
93
 
         * @return Pointer to a new DynStr.
 
83
         * \param gh The GHash to iterate over.
 
84
         * \return Pointer to a new DynStr.
94
85
         */
95
86
GHashIterator*  BLI_ghashIterator_new           (GHash *gh);
96
87
        /**
98
89
         * be mutated while the iterator is in use, and the iterator will
99
90
         * step exactly BLI_ghash_size(gh) times before becoming done.
100
91
         * 
101
 
         * @param ghi The GHashIterator to initialize.
102
 
         * @param gh The GHash to iterate over.
 
92
         * \param ghi The GHashIterator to initialize.
 
93
         * \param gh The GHash to iterate over.
103
94
         */
104
95
void BLI_ghashIterator_init(GHashIterator *ghi, GHash *gh);
105
96
        /**
106
97
         * Free a GHashIterator.
107
98
         *
108
 
         * @param ghi The iterator to free.
 
99
         * \param ghi The iterator to free.
109
100
         */
110
101
void                    BLI_ghashIterator_free          (GHashIterator *ghi);
111
102
 
112
103
        /**
113
104
         * Retrieve the key from an iterator.
114
105
         *
115
 
         * @param ghi The iterator.
116
 
         * @return The key at the current index, or NULL if the 
 
106
         * \param ghi The iterator.
 
107
         * \return The key at the current index, or NULL if the 
117
108
         * iterator is done.
118
109
         */
119
110
void*                   BLI_ghashIterator_getKey        (GHashIterator *ghi);
120
111
        /**
121
112
         * Retrieve the value from an iterator.
122
113
         *
123
 
         * @param ghi The iterator.
124
 
         * @return The value at the current index, or NULL if the 
 
114
         * \param ghi The iterator.
 
115
         * \return The value at the current index, or NULL if the 
125
116
         * iterator is done.
126
117
         */
127
118
void*                   BLI_ghashIterator_getValue      (GHashIterator *ghi);
128
119
        /**
129
120
         * Steps the iterator to the next index.
130
121
         *
131
 
         * @param ghi The iterator.
 
122
         * \param ghi The iterator.
132
123
         */
133
124
void                    BLI_ghashIterator_step          (GHashIterator *ghi);
134
125
        /**
135
126
         * Determine if an iterator is done (has reached the end of
136
127
         * the hash table).
137
128
         *
138
 
         * @param ghi The iterator.
139
 
         * @return True if done, False otherwise.
 
129
         * \param ghi The iterator.
 
130
         * \return True if done, False otherwise.
140
131
         */
141
132
int                             BLI_ghashIterator_isDone        (GHashIterator *ghi);
142
133
 
143
134
/* *** */
144
135
 
145
 
unsigned int    BLI_ghashutil_ptrhash   (void *key);
146
 
int                             BLI_ghashutil_ptrcmp    (void *a, void *b);
147
 
 
148
 
unsigned int    BLI_ghashutil_strhash   (void *key);
149
 
int                             BLI_ghashutil_strcmp    (void *a, void *b);
150
 
 
151
 
unsigned int    BLI_ghashutil_inthash   (void *ptr);
152
 
int                             BLI_ghashutil_intcmp(void *a, void *b);
153
 
 
154
 
/*begin of macro-inlined functions*/
155
 
extern unsigned int hashsizes[];
156
 
 
157
 
#if 0
158
 
#define BLI_ghash_insert(gh, _k, _v){\
159
 
        unsigned int _hash= (gh)->hashfp(_k)%gh->nbuckets;\
160
 
        Entry *_e= BLI_mempool_alloc((gh)->entrypool);\
161
 
        _e->key= _k;\
162
 
        _e->val= _v;\
163
 
        _e->next= (gh)->buckets[_hash];\
164
 
        (gh)->buckets[_hash]= _e;\
165
 
        if (++(gh)->nentries>(gh)->nbuckets*3) {\
166
 
                Entry *_e, **_old= (gh)->buckets;\
167
 
                int _i, _nold= (gh)->nbuckets;\
168
 
                (gh)->nbuckets= hashsizes[++(gh)->cursize];\
169
 
                (gh)->buckets= malloc((gh)->nbuckets*sizeof(*(gh)->buckets));\
170
 
                memset((gh)->buckets, 0, (gh)->nbuckets*sizeof(*(gh)->buckets));\
171
 
                for (_i=0; _i<_nold; _i++) {\
172
 
                        for (_e= _old[_i]; _e;) {\
173
 
                                Entry *_n= _e->next;\
174
 
                                _hash= (gh)->hashfp(_e->key)%(gh)->nbuckets;\
175
 
                                _e->next= (gh)->buckets[_hash];\
176
 
                                (gh)->buckets[_hash]= _e;\
177
 
                                _e= _n;\
178
 
                        }\
179
 
                }\
180
 
                free(_old); } }
181
 
#endif
182
 
 
183
 
/*---------inlined functions---------*/
184
 
BM_INLINE void BLI_ghash_insert(GHash *gh, void *key, void *val) {
185
 
        unsigned int hash= gh->hashfp(key)%gh->nbuckets;
186
 
        Entry *e= (Entry*) BLI_mempool_alloc(gh->entrypool);
187
 
 
188
 
        e->key= key;
189
 
        e->val= val;
190
 
        e->next= gh->buckets[hash];
191
 
        gh->buckets[hash]= e;
192
 
        
193
 
        if (++gh->nentries>(float)gh->nbuckets/2) {
194
 
                Entry *e, **old= gh->buckets;
195
 
                int i, nold= gh->nbuckets;
196
 
                
197
 
                gh->nbuckets= hashsizes[++gh->cursize];
198
 
                gh->buckets= (Entry**)MEM_mallocN(gh->nbuckets*sizeof(*gh->buckets), "buckets");
199
 
                memset(gh->buckets, 0, gh->nbuckets*sizeof(*gh->buckets));
200
 
                
201
 
                for (i=0; i<nold; i++) {
202
 
                        for (e= old[i]; e;) {
203
 
                                Entry *n= e->next;
204
 
                                
205
 
                                hash= gh->hashfp(e->key)%gh->nbuckets;
206
 
                                e->next= gh->buckets[hash];
207
 
                                gh->buckets[hash]= e;
208
 
                                
209
 
                                e= n;
210
 
                        }
211
 
                }
212
 
                
213
 
                MEM_freeN(old);
214
 
        }
215
 
}
216
 
 
217
 
BM_INLINE void* BLI_ghash_lookup(GHash *gh, void *key) 
218
 
{
219
 
        if(gh) {
220
 
                unsigned int hash= gh->hashfp(key)%gh->nbuckets;
221
 
                Entry *e;
222
 
                
223
 
                for (e= gh->buckets[hash]; e; e= e->next)
224
 
                        if (gh->cmpfp(key, e->key)==0)
225
 
                                return e->val;
226
 
        }       
227
 
        return NULL;
228
 
}
229
 
 
230
 
BM_INLINE int BLI_ghash_remove (GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
231
 
{
232
 
        unsigned int hash= gh->hashfp(key)%gh->nbuckets;
233
 
        Entry *e;
234
 
        Entry *p = 0;
235
 
 
236
 
        for (e= gh->buckets[hash]; e; e= e->next) {
237
 
                if (gh->cmpfp(key, e->key)==0) {
238
 
                        Entry *n= e->next;
239
 
 
240
 
                        if (keyfreefp) keyfreefp(e->key);
241
 
                        if (valfreefp) valfreefp(e->val);
242
 
                        BLI_mempool_free(gh->entrypool, e);
243
 
 
244
 
 
245
 
                        e= n;
246
 
                        if (p)
247
 
                                p->next = n;
248
 
                        else
249
 
                                gh->buckets[hash] = n;
250
 
 
251
 
                        --gh->nentries;
252
 
                        return 1;
253
 
                }
254
 
                p = e;
255
 
        }
256
 
 
257
 
        return 0;
258
 
}
259
 
 
260
 
BM_INLINE int BLI_ghash_haskey(GHash *gh, void *key) {
261
 
        unsigned int hash= gh->hashfp(key)%gh->nbuckets;
262
 
        Entry *e;
263
 
        
264
 
        for (e= gh->buckets[hash]; e; e= e->next)
265
 
                if (gh->cmpfp(key, e->key)==0)
266
 
                        return 1;
267
 
        
268
 
        return 0;
269
 
}
 
136
unsigned int    BLI_ghashutil_ptrhash   (const void *key);
 
137
int                             BLI_ghashutil_ptrcmp    (const void *a, const void *b);
 
138
 
 
139
unsigned int    BLI_ghashutil_strhash   (const void *key);
 
140
int                             BLI_ghashutil_strcmp    (const void *a, const void *b);
 
141
 
 
142
unsigned int    BLI_ghashutil_inthash   (const void *ptr);
 
143
int                             BLI_ghashutil_intcmp    (const void *a, const void *b);
 
144
 
 
145
typedef struct GHashPair {
 
146
        const void *first;
 
147
        const void *second;
 
148
} GHashPair;
 
149
 
 
150
GHashPair*              BLI_ghashutil_pairalloc (const void *first, const void *second);
 
151
unsigned int    BLI_ghashutil_pairhash  (const void *ptr);
 
152
int                             BLI_ghashutil_paircmp   (const void *a, const void *b);
 
153
void                    BLI_ghashutil_pairfree  (void *ptr);
270
154
 
271
155
#ifdef __cplusplus
272
156
}
273
157
#endif
274
158
 
275
 
#endif
 
159
#endif /* __BLI_GHASH_H__ */