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