1 /**************************************************************************\
2 * Copyright (c) Kongsberg Oil & Gas Technologies AS
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are
7 * met:
8 *
9 * Redistributions of source code must retain the above copyright notice,
10 * this list of conditions and the following disclaimer.
11 *
12 * Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * Neither the name of the copyright holder nor the names of its
17 * contributors may be used to endorse or promote products derived from
18 * this software without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
24 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
25 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
26 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
30 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 \**************************************************************************/
32
33 /*!
34 \class SbDict SbDict.h Inventor/SbDict.h
35 \brief The SbDict class organizes a dictionary of keys and values.
36
37 \ingroup base
38
39 It uses hashing to quickly insert and find entries in the dictionary.
40 An entry consists of an unique key and a generic pointer.
41 */
42
43 /*!
44 \typedef uintptr_t SbDictKeyType
45
46 The type definition for a dictionary key.
47 */
48
49 /*!
50 \typedef void SbDictApplyFunc(SbDictKeyType key, void * value)
51
52 The type definition of the function to be applied to each entry.
53 */
54
55 /*!
56 \typedef void SbDictApplyDataFunc(SbDictKeyType key, void * value, void * data)
57
58 The type definition of the function with associated data that is to be
59 applied to each entry.
60 */
61
62 /*!
63 \typedef SbDictKeyType SbDictHashingFunc(const SbDictKeyType key)
64
65 The type definition of a dictionary hashing function.
66 */
67
68 // *************************************************************************
69
70 #define COIN_ALLOW_SBDICT
71 /*! \file SbDict.h */
72 #include <Inventor/SbDict.h>
73 #undef COIN_ALLOW_SBDICT
74
75 #include <cassert>
76
77 #define COIN_ALLOW_CC_HASH /* Hack to get around include protection
78 for obsoleted ADT. */
79 #include <Inventor/C/base/hash.h>
80 #undef COIN_ALLOW_CC_HASH
81 #include <Inventor/lists/SbPList.h>
82 #include <Inventor/C/base/memalloc.h>
83
84 #include "SbBasicP.h"
85
86 // *************************************************************************
87
88 /*!
89 Constructor with \a entries specifying the initial number of buckets
90 in the hash list -- so it need to be larger than 0. Other than this,
91 no special care needs to be taken in choosing the value since it is
92 always rounded up to the nearest power of two.
93 */
SbDict(const int entries)94 SbDict::SbDict(const int entries)
95 {
96 assert(entries > 0);
97 this->hashtable = cc_hash_construct(entries, 0.75f);
98 }
99
100 /*!
101 Copy constructor.
102 */
SbDict(const SbDict & from)103 SbDict::SbDict(const SbDict & from)
104 {
105 this->hashtable = NULL;
106 this->operator=(from);
107 }
108
109 /*!
110 Destructor.
111 */
~SbDict()112 SbDict::~SbDict()
113 {
114 cc_hash_destruct(this->hashtable);
115 }
116
117 extern "C" {
118
119 /*
120 Callback for copying values from one SbDict to another.
121 */
122 static
123 void
copyval(SbDictKeyType key,void * value,void * data)124 copyval(SbDictKeyType key, void * value, void * data)
125 {
126 SbDict * thisp = static_cast<SbDict *>(data);
127 thisp->enter(key, value);
128 }
129
130 } // extern "C"
131
132 /*!
133 Make a shallow copy of the contents of dictionary \a from into this
134 dictionary.
135 */
136 SbDict &
operator =(const SbDict & from)137 SbDict::operator=(const SbDict & from)
138 {
139 if (this->hashtable) {
140 // clear old values
141 this->clear();
142 cc_hash_destruct(this->hashtable);
143 }
144 this->hashtable = cc_hash_construct(cc_hash_get_num_elements(from.hashtable), 0.75f);
145 from.applyToAll(copyval, this);
146 return *this;
147 }
148
149 /*!
150 Clear all entries in the dictionary.
151 */
152 void
clear(void)153 SbDict::clear(void)
154 {
155 cc_hash_clear(this->hashtable);
156 }
157
158 /*!
159 Inserts a new entry into the dictionary. \a key should be
160 a unique number, and \a value is the generic user data.
161
162 \e If \a key does not exist in the dictionary, a new entry
163 is created and \c TRUE is returned. Otherwise, the generic user
164 data is changed to \a value, and \c FALSE is returned.
165 */
166 SbBool
enter(const Key key,void * const value)167 SbDict::enter(const Key key, void * const value)
168 {
169 return cc_hash_put(this->hashtable, key, value);
170 }
171
172 /*!
173 Searches for \a key in the dictionary. If an entry with this
174 key exists, \c TRUE is returned and the entry value is returned
175 in \a value. Otherwise, \c FALSE is returned.
176 */
177 SbBool
find(const Key key,void * & value) const178 SbDict::find(const Key key, void *& value) const
179 {
180 return cc_hash_get(this->hashtable, key, &value);
181 }
182
183 /*!
184 Removes the entry with key \a key. \c TRUE is returned if an entry
185 with this key was present, \c FALSE otherwise.
186 */
187 SbBool
remove(const Key key)188 SbDict::remove(const Key key)
189 {
190 return cc_hash_remove(this->hashtable, key);
191 }
192
193
194 // needed to support the extra applyToAll function. The actual
195 // function pointer is supplied as the closure pointer, and we just
196 // call that function from our dummy callback. This is needed since
197 // cc_hash only supports one apply function type.
198 extern "C" {
199 typedef void sbdict_dummy_apply_func(SbDict::Key, void *);
200
201 static void
sbdict_dummy_apply(SbDict::Key key,void * value,void * closure)202 sbdict_dummy_apply(SbDict::Key key, void * value, void * closure)
203 {
204 sbdict_dummy_apply_func * func = (sbdict_dummy_apply_func*) closure;
205 func(key, value);
206 }
207 }
208 /*!
209 Applies \a rtn to all entries in the dictionary.
210 */
211 void
applyToAll(SbDictApplyFunc * rtn) const212 SbDict::applyToAll(SbDictApplyFunc * rtn) const
213 {
214 cc_hash_apply(this->hashtable, sbdict_dummy_apply, function_to_object_cast<void *>(rtn));
215 }
216
217 /*!
218 \overload
219 */
220 void
applyToAll(SbDictApplyDataFunc * rtn,void * data) const221 SbDict::applyToAll(SbDictApplyDataFunc * rtn, void * data) const
222 {
223 cc_hash_apply(this->hashtable, static_cast<cc_hash_apply_func *>(rtn), data);
224 }
225
226 typedef struct {
227 SbPList * keys;
228 SbPList * values;
229 } sbdict_makeplist_data;
230
231 extern "C" {
232
233 static void
sbdict_makeplist_cb(SbDict::Key key,void * value,void * closure)234 sbdict_makeplist_cb(SbDict::Key key, void * value, void * closure)
235 {
236 sbdict_makeplist_data * data = static_cast<sbdict_makeplist_data *>(closure);
237 data->keys->append(reinterpret_cast<void *>(key));
238 data->values->append(value);
239 }
240
241 } // extern "C"
242
243 /*!
244 Creates lists with all entries in the dictionary.
245 */
246 void
makePList(SbPList & keys,SbPList & values)247 SbDict::makePList(SbPList & keys, SbPList & values)
248 {
249 sbdict_makeplist_data applydata;
250 applydata.keys = &keys;
251 applydata.values = &values;
252
253 cc_hash_apply(this->hashtable, static_cast<cc_hash_apply_func *>(sbdict_makeplist_cb), &applydata);
254 }
255
256 /*!
257 Sets a new hashing function for this dictionary. Default
258 hashing function just returns the key.
259
260 If you find that items entered into the dictionary seems to make
261 clusters in only a few buckets, you should try setting a hashing
262 function. If you're for instance using strings, you could use the
263 static SbString::hash() function (you'd need to make a static function
264 that will cast from SbDict::Key to char * of course).
265
266 This function is not part of the OIV API.
267 */
268 void
setHashingFunction(SbDictHashingFunc * func)269 SbDict::setHashingFunction(SbDictHashingFunc * func)
270 {
271 cc_hash_set_hash_func(this->hashtable, static_cast<cc_hash_func *>(func));
272 }
273