1 #pragma once
2 
3 /** @file the_Foundation/blockhash.h  Hash object that uses Block for keys and Object for values.
4 
5 @authors Copyright (c) 2017 Jaakko Keränen <jaakko.keranen@iki.fi>
6 
7 @par License
8 
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
11 
12 1. Redistributions of source code must retain the above copyright notice, this
13    list of conditions and the following disclaimer.
14 2. Redistributions in binary form must reproduce the above copyright notice,
15    this list of conditions and the following disclaimer in the documentation
16    and/or other materials provided with the distribution.
17 
18 <small>THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
20 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
21 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
22 ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
23 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
24 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
25 ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
27 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.</small>
28 */
29 
30 #include "hash.h"
31 #include "block.h"
32 #include "object.h"
33 
34 iBeginPublic
35 
36 /** @name BlockHashNode */
37 ///@{
38 iDeclareType(BlockHashNode)
39 
40 iBeginDeclareClass(BlockHashNode)
41     iBlockHashNode *    (*newNode)  (const iBlock *key, const iAnyObject *object);
42     iHashKey            (*hashKey)  (const iBlock *key);
43 iEndDeclareClass(BlockHashNode)
44 
45 struct Impl_BlockHashNode {
46     iHashNode node;
47     iBlock keyBlock;
48     iAnyObject *object;
49 };
50 
51 iBlockHashNode *    new_BlockHashNode       (const iBlock *key, const iAnyObject *object);
52 iHashKey            hashKey_BlockHashNode   (const iBlock *key);
53 void                deinit_BlockHashNode    (iBlockHashNode *);
54 
55 #define             key_BlockHashNode(d)    iConstCast(iBlock *, (&((const iBlockHashNode *) (d))->keyBlock))
56 ///@}
57 
58 iDeclareClass(BlockHash)
59 
60 struct Impl_BlockHash {
61     iObject object;
62     iHash hash;
63     const iBlockHashNodeClass *nodeClass;
64 };
65 
66 iDeclareObjectConstruction(BlockHash)
67 
68 void                setNodeClass_BlockHash  (iBlockHash *, const iBlockHashNodeClass *nodeClass);
69 
70 #define             size_BlockHash(d)       size_Hash(&(d)->hash)
71 #define             isEmpty_BlockHash(d)    isEmpty_Hash(&(d)->hash)
72 
73 iBool               contains_BlockHash      (const iBlockHash *, const iBlock *key);
74 const iAnyObject *  constValue_BlockHash    (const iBlockHash *, const iBlock *key);
75 iAnyObject *        value_BlockHash         (iBlockHash *, const iBlock *key);
76 
77 void                clear_BlockHash         (iBlockHash *);
78 
79 /**
80  * Inserts a key-value node into the BlockHash.
81  *
82  * @param key    Key string. A copy is made of the key and stored in the node.
83  * @param value  Value object.
84  *
85  * @return @c iTrue, if the a new key-value node was added and the size of the hash
86  * increased as a result. @c False, if an existing one was replaced.
87  */
88 iBool       insert_BlockHash       (iBlockHash *, const iBlock *key, const iAnyObject *value);
89 
90 iBool       remove_BlockHash       (iBlockHash *, const iBlock *key);
91 
92 void        insertValues_BlockHash       (iBlockHash *, const iBlock *key, const iAnyObject *value, ...);
93 void        insertValuesCStr_BlockHash   (iBlockHash *, const char *key, const iAnyObject *value, ...);
94 
95 /** @name Iterators */
96 ///@{
97 iDeclareIterator(BlockHash, iBlockHash *)
98 const iBlock *  key_BlockHashIterator(iBlockHashIterator *);
99 void            remove_BlockHashIterator(iBlockHashIterator *);
100 struct IteratorImpl_BlockHash {
101     union {
102         iBlockHashNode *value;
103         iHashIterator iter;
104     };
105     iBlockHash *blockHash;
106 };
107 
108 iDeclareConstIterator(BlockHash, const iBlockHash *)
109 const iBlock *  key_BlockHashConstIterator(iBlockHashConstIterator *);
110 struct ConstIteratorImpl_BlockHash {
111     union {
112         const iBlockHashNode *value;
113         iHashConstIterator iter;
114     };
115 };
116 ///@}
117 
118 /*-------------------------------------------------------------------------------------*/
119 /* Deriving specialized hashes: */
120 
121 #define iDeclareBlockHash(typeName, keyType, valueType) \
122     typedef iBlockHash i##typeName; \
123     typedef i##keyType i##typeName##Key; \
124     typedef iBlockHashNode i##typeName##Node; \
125     typedef iBlockHashNodeClass i##typeName##NodeClass; \
126     iDeclareClassOnly(typeName) \
127     \
128     i##typeName##Node *     new_##typeName##Node        (const i##keyType *key, const i##valueType *object); \
129     void                    deinit_##typeName##Node     (i##typeName##Node *); \
130     const i##keyType *      key_##typeName##Node        (const i##typeName##Node *); \
131     void                    initKey_##typeName##Node    (const i##typeName##Node *, i##keyType *key); \
132     i##valueType *          value_##typeName##Node      (const i##typeName##Node *); \
133     void                    initBlock_##typeName##Key   (const i##keyType *key, iBlock *); \
134     \
135     iDeclareObjectConstruction(typeName) \
136     \
137     iLocalDef size_t    size_##typeName     (const i##typeName *d) { return size_BlockHash(d); } \
138     iLocalDef iBool     isEmpty_##typeName  (const i##typeName *d) { return isEmpty_BlockHash(d); } \
139     \
140     iBool                   contains_##typeName     (const i##typeName *, const i##keyType *key); \
141     const i##valueType *    constValue_##typeName   (const i##typeName *, const i##keyType *key); \
142     i##valueType *          value_##typeName        (i##typeName *, const i##keyType *key); \
143     \
144     iLocalDef void      clear_##typeName    (i##typeName *d) { clear_BlockHash(d); } \
145     \
146     iBool                   insert_##typeName   (i##typeName *, const i##keyType *key, const i##valueType *value); \
147     iBool                   remove_##typeName   (i##typeName *, const i##keyType *key); \
148     \
149     iDeclareIterator(typeName, i##typeName *) \
150     \
151     const i##keyType *      key_##typeName##Iterator(i##typeName##Iterator *); \
152     void                    remove_##typeName##Iterator(i##typeName##Iterator *); \
153     struct IteratorImpl_##typeName { \
154         iHashIterator iter; \
155         i##typeName##Node *value; \
156     }; \
157     \
158     iDeclareConstIterator(typeName, const i##typeName *) \
159     \
160     const i##keyType * key_##typeName##ConstIterator(i##typeName##ConstIterator *); \
161     struct ConstIteratorImpl_##typeName { \
162         iHashConstIterator iter; \
163         const i##typeName##Node *value; \
164     };
165 
166 /**
167  * Functions that must be defined manually:
168  * - key_<typeName>Node(d): returns the key as-is (if available)
169  * - initKey_<typeName>Node(d, key): copies the Block back to an existing keyType instance
170  * - initBlock_<typeName>Key(key, block): initializes a Block with the key data
171  */
172 #define iDefineBlockHash(typeName, keyType, valueType) \
173     iDefineClass(typeName) \
174     iDefineObjectConstruction(typeName) \
175     \
176     static iBeginDefineClass(typeName##Node) \
177         .newNode = (iBlockHashNode *(*)(const iBlock *, const iAnyObject *)) new_##typeName##Node, \
178         .hashKey = hashKey_BlockHashNode, \
179     iEndDefineClass(typeName##Node) \
180     \
181     i##typeName##Node *new_##typeName##Node(const i##keyType *key, const i##valueType *object) { \
182         iBlock bkey; initBlock_##typeName##Key(key, &bkey); \
183         void *elem = new_BlockHashNode(&bkey, object); \
184         deinit_Block(&bkey); \
185         return elem; \
186     } \
187     \
188     void deinit_##typeName##Node(i##typeName##Node *d) { deinit_BlockHashNode(d); } \
189     \
190     i##valueType *value_##typeName##Node(const i##typeName##Node *d) { \
191         return (i##valueType *) d->object; \
192     } \
193     \
194     void init_##typeName(i##typeName *d) { \
195         init_BlockHash(d); \
196         setNodeClass_BlockHash(d, (const iBlockHashNodeClass *) &Class_##typeName##Node); \
197     } \
198     \
199     void deinit_##typeName(i##typeName *d) { \
200         deinit_BlockHash(d); \
201     } \
202     \
203     iBool contains_##typeName(const i##typeName *d, const i##keyType *key) { \
204         iBlock bkey; initBlock_##typeName##Key(key, &bkey); \
205         iBool res = contains_BlockHash(d, &bkey); \
206         deinit_Block(&bkey); \
207         return res; \
208     } \
209     \
210     const i##valueType *constValue_##typeName(const i##typeName *d, const i##keyType *key) { \
211         iBlock bkey; initBlock_##typeName##Key(key, &bkey); \
212         const i##valueType *obj = (const i##valueType *) constValue_BlockHash(d, &bkey); \
213         deinit_Block(&bkey); \
214         return obj; \
215     } \
216     \
217     i##valueType *value_##typeName(i##typeName *d, const i##keyType *key) { \
218         iBlock bkey; initBlock_##typeName##Key(key, &bkey); \
219         i##valueType *obj = (i##valueType *) value_BlockHash(d, &bkey); \
220         deinit_Block(&bkey); \
221         return obj; \
222     } \
223     \
224     iBool insert_##typeName(i##typeName *d, const i##keyType *key, const i##valueType *value) { \
225         iBlock bkey; initBlock_##typeName##Key(key, &bkey); \
226         iBool res = insert_BlockHash(d, &bkey, value); \
227         deinit_Block(&bkey); \
228         return res; \
229     } \
230     \
231     iBool remove_##typeName(i##typeName *d, const i##keyType *key) { \
232         iBlock bkey; initBlock_##typeName##Key(key, &bkey); \
233         iBool res = remove_BlockHash(d, &bkey); \
234         deinit_Block(&bkey); \
235         return res; \
236     } \
237     \
238     void init_##typeName##Iterator(i##typeName##Iterator *d, i##typeName *hash) { \
239         init_HashIterator(&d->iter, &hash->hash); \
240         d->value = (i##typeName##Node *) d->iter.value; \
241     } \
242     \
243     void next_##typeName##Iterator(i##typeName##Iterator *d) { \
244         next_HashIterator(&d->iter); \
245         d->value = (i##typeName##Node *) d->iter.value; \
246     } \
247     \
248     const i##keyType *key_##typeName##Iterator(i##typeName##Iterator *d) { \
249         return key_##typeName##Node(d->value); \
250     } \
251     \
252     void remove_##typeName##Iterator(i##typeName##Iterator *d) { \
253         remove_BlockHashIterator((iBlockHashIterator *) d); \
254     } \
255     \
256     void init_##typeName##ConstIterator(i##typeName##ConstIterator *d, const i##typeName *hash) { \
257         init_HashConstIterator(&d->iter, &hash->hash); \
258         d->value = (const i##typeName##Node *) d->iter.value; \
259     } \
260     \
261     void next_##typeName##ConstIterator(i##typeName##ConstIterator *d) { \
262         next_HashConstIterator(&d->iter); \
263         d->value = (const i##typeName##Node *) d->iter.value; \
264     } \
265     \
266     const i##keyType *key_##typeName##ConstIterator(i##typeName##ConstIterator *d) { \
267         return key_##typeName##Node(d->value); \
268     }
269 
270 #define iDefinePlainKeyBlockHash(typeName, keyType, valueType) \
271     iDefineBlockHash(typeName, keyType, valueType) \
272     \
273     const i##keyType *key_##typeName##Node(const i##typeName##Node *d) { \
274         return constData_Block(&d->keyBlock); \
275     } \
276     \
277     void initKey_##typeName##Node(const i##typeName##Node *d, i##keyType *key) { \
278         iAssert(size_Block(&d->keyBlock) == sizeof(i##keyType)); \
279         memcpy(key, constData_Block(&d->keyBlock), sizeof(i##keyType)); \
280     } \
281     \
282     void initBlock_##typeName##Key(const i##keyType *d, iBlock *block) { \
283         initData_Block(block, d, sizeof(i##keyType)); \
284     }
285 
286 iEndPublic
287