2ccc28dc07b22a8a724a141607af72166ffab846
[blender.git] / source / blender / blenlib / BLI_ghash.h
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): none yet.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27  
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  */
35
36 #ifdef __cplusplus
37 extern "C" {
38 #endif
39
40 typedef unsigned int  (*GHashHashFP)     (const void *key);
41 typedef int           (*GHashCmpFP)      (const void *a, const void *b);
42 typedef void          (*GHashKeyFreeFP)  (void *key);
43 typedef void          (*GHashValFreeFP)  (void *val);
44
45 typedef struct Entry {
46         struct Entry *next;
47
48         void *key, *val;
49 } Entry;
50
51 typedef struct GHash {
52         GHashHashFP hashfp;
53         GHashCmpFP cmpfp;
54
55         Entry **buckets;
56         struct BLI_mempool *entrypool;
57         int nbuckets, nentries, cursize;
58 } GHash;
59
60 typedef struct GHashIterator {
61         GHash *gh;
62         int curBucket;
63         struct Entry *curEntry;
64 } GHashIterator;
65
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 bool   BLI_ghash_remove(GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
73 void  *BLI_ghash_pop(GHash *gh, void *key, GHashKeyFreeFP keyfreefp);
74 bool    BLI_ghash_haskey(GHash *gh, const void *key);
75 int    BLI_ghash_size(GHash *gh);
76
77 /* *** */
78
79 /**
80  * Create a new GHashIterator. The hash table must not be mutated
81  * while the iterator is in use, and the iterator will step exactly
82  * BLI_ghash_size(gh) times before becoming done.
83  *
84  * \param gh The GHash to iterate over.
85  * \return Pointer to a new DynStr.
86  */
87 GHashIterator *BLI_ghashIterator_new(GHash *gh);
88 /**
89  * Init an already allocated GHashIterator. The hash table must not
90  * be mutated while the iterator is in use, and the iterator will
91  * step exactly BLI_ghash_size(gh) times before becoming done.
92  *
93  * \param ghi The GHashIterator to initialize.
94  * \param gh The GHash to iterate over.
95  */
96 void BLI_ghashIterator_init(GHashIterator *ghi, GHash *gh);
97 /**
98  * Free a GHashIterator.
99  *
100  * \param ghi The iterator to free.
101  */
102 void            BLI_ghashIterator_free(GHashIterator *ghi);
103
104 /**
105  * Retrieve the key from an iterator.
106  *
107  * \param ghi The iterator.
108  * \return The key at the current index, or NULL if the
109  * iterator is done.
110  */
111 void           *BLI_ghashIterator_getKey(GHashIterator *ghi);
112 /**
113  * Retrieve the value from an iterator.
114  *
115  * \param ghi The iterator.
116  * \return The value at the current index, or NULL if the
117  * iterator is done.
118  */
119 void           *BLI_ghashIterator_getValue(GHashIterator *ghi);
120 /**
121  * Steps the iterator to the next index.
122  *
123  * \param ghi The iterator.
124  */
125 void            BLI_ghashIterator_step(GHashIterator *ghi);
126 /**
127  * Determine if an iterator is done (has reached the end of
128  * the hash table).
129  *
130  * \param ghi The iterator.
131  * \return True if done, False otherwise.
132  */
133 int             BLI_ghashIterator_notDone(GHashIterator *ghi);
134
135 #define GHASH_ITER(gh_iter_, ghash_)                                          \
136         for (BLI_ghashIterator_init(&gh_iter_, ghash_);                           \
137              BLI_ghashIterator_notDone(&gh_iter_);                                \
138              BLI_ghashIterator_step(&gh_iter_))
139
140 /* *** */
141
142 unsigned int    BLI_ghashutil_ptrhash(const void *key);
143 int             BLI_ghashutil_ptrcmp(const void *a, const void *b);
144
145 unsigned int    BLI_ghashutil_strhash(const void *key);
146 int             BLI_ghashutil_strcmp(const void *a, const void *b);
147
148 unsigned int    BLI_ghashutil_inthash(const void *ptr);
149 int             BLI_ghashutil_intcmp(const void *a, const void *b);
150
151 GHash          *BLI_ghash_ptr_new(const char *info);
152 GHash          *BLI_ghash_str_new(const char *info);
153 GHash          *BLI_ghash_int_new(const char *info);
154 GHash          *BLI_ghash_pair_new(const char *info);
155
156 typedef struct GHashPair {
157         const void *first;
158         const void *second;
159 } GHashPair;
160
161 GHashPair      *BLI_ghashutil_pairalloc(const void *first, const void *second);
162 unsigned int    BLI_ghashutil_pairhash(const void *ptr);
163 int             BLI_ghashutil_paircmp(const void *a, const void *b);
164 void            BLI_ghashutil_pairfree(void *ptr);
165
166 #ifdef __cplusplus
167 }
168 #endif
169
170 #endif /* __BLI_GHASH_H__ */