1 /******************************************************************************* 2 3 EBtree based map. 4 5 Compared to a standard HashMap, a tree-based map is useful in situations 6 where the number of elements in the map is hard to predict. The overhead 7 of an ebtree is very low compared to a hash map, as the overhead of a hash 8 map is the whole bucket set array, while for an ebtree is only a little 9 struct. Additionally, any tree modification is permitted during the 10 iteration. 11 12 The map internally allocates internal nodes which contain elements 13 using `malloc`, so they are invisible to the GC. 14 15 Copyright: Copyright (c) 2016-2018 dunnhumby Germany GmbH. All rights reserved 16 17 License: 18 Boost Software License Version 1.0. See LICENSE.txt for details. 19 20 *******************************************************************************/ 21 22 module ocean.util.container.map.TreeMap; 23 24 import ocean.util.container.ebtree.c.eb64tree; 25 import ocean.util.container.ebtree.c.ebtree; 26 27 /******************************************************************************* 28 29 Params: 30 T = user value type to store 31 32 *******************************************************************************/ 33 34 struct TreeMap ( T ) 35 { 36 import ocean.meta.types.Qualifiers; 37 38 /*************************************************************************** 39 40 Internal node structure. 41 42 ***************************************************************************/ 43 44 private struct Node 45 { 46 /*********************************************************************** 47 48 Internal ebtree node 49 50 ***********************************************************************/ 51 52 eb64_node node; 53 54 /********************************************************************** 55 56 User's value 57 58 **********************************************************************/ 59 60 T value; 61 } 62 63 /*************************************************************************** 64 65 The `malloc` allocator. 66 67 ***************************************************************************/ 68 69 private static MallocAllocator allocator; 70 71 /*************************************************************************** 72 73 The ebtree root. 74 75 ***************************************************************************/ 76 77 private eb_root root = empty_unique_ebtroot; 78 79 /*************************************************************************** 80 81 Returns: 82 true if the map is empty or false if it contains elements. 83 84 ***************************************************************************/ 85 86 public bool is_empty ( ) // const 87 { 88 return this.root.is_empty(); 89 } 90 91 /*************************************************************************** 92 93 Reinitialises the internal tree struct. 94 95 This method should be called only if it is known that the tree is empty, 96 otherwise pointers to malloc-allocated nodes are lost so they cannot be 97 deallocated. 98 99 ***************************************************************************/ 100 101 public void reinit ( ) 102 { 103 this.root = eb_root.init; 104 this.root.unique = true; 105 } 106 107 /*************************************************************************** 108 109 Adds a new node to the map for key or obtains the existing if already in 110 the map. 111 112 Params: 113 key = the key to add a new node for or obtain the existing one 114 added = outputs true a new node was added or false if key was found 115 in the map so that the existing node is returned 116 117 Returns: 118 the node associated with key. If added is true then it was newly 119 created and added, otherwise it is the already existing node in the 120 tree. 121 122 ***************************************************************************/ 123 124 public T* put ( ulong key, out bool added ) 125 { 126 return &(this.put_(key, added).value); 127 } 128 129 /*********************************************************************** 130 131 Looks up the value for key in the map. 132 133 Params: 134 key = the key to look up node for 135 136 Returns: 137 the value associated with key or null if not found. 138 139 ***********************************************************************/ 140 141 private T* opBinaryRight (string op : "in") ( ulong key ) 142 { 143 return &((cast(Node*)eb64_lookup(&this.root, key)).value); 144 } 145 146 /*********************************************************************** 147 148 Obtains the first value in the map. 149 150 Returns: 151 the first value or `null` if the map is empty. 152 153 ***********************************************************************/ 154 155 public T* first () 156 { 157 return this.getBoundary!(true)(); 158 } 159 160 /*********************************************************************** 161 162 Obtains the last value in the map. 163 164 Returns: 165 the last value or `null` if the map is empty. 166 167 ***********************************************************************/ 168 169 public T* last () 170 { 171 return this.getBoundary!(false)(); 172 } 173 174 /*********************************************************************** 175 176 foreach iterator over nodes in the tree. Any tree modification is 177 permitted during iteration. 178 179 ***********************************************************************/ 180 181 public int opApply ( scope int delegate ( ref ulong key, ref T* value ) dg ) 182 { 183 int stop = 0; 184 185 for (auto eb_node = eb64_first(&this.root); eb_node && !stop;) 186 { 187 // Backup node.next here because dg() may change or delete node! 188 auto next = eb_node.next; 189 auto node = cast(Node*)eb_node; 190 auto value_ptr = &node.value; 191 stop = dg(node.node.key, value_ptr); 192 eb_node = next; 193 } 194 195 return stop; 196 } 197 198 199 /*********************************************************************** 200 201 Removes the element pointed by `key` from the map and deallocates it. 202 203 All pointers tied to this element are no longer valid from this 204 point. 205 206 Params: 207 key = the key of the node to remove 208 209 Returns: 210 true if the element with the key was found, 211 false if not. 212 213 ***********************************************************************/ 214 215 public bool remove ( ulong key ) 216 { 217 if (auto node = this.nodeForKey(key)) 218 { 219 this.remove_(*node); 220 return true; 221 } 222 else 223 { 224 return false; 225 } 226 } 227 228 /*********************************************************************** 229 230 Removes node from the map and deallocates it. 231 232 DO NOT USE node from this point! 233 234 Params: 235 node = the node to remove 236 237 ***********************************************************************/ 238 239 private static void remove_ ( ref Node node ) 240 { 241 static if (is(Node == eb64_node)) 242 eb64_delete(&node); 243 else 244 eb64_delete(&node.tupleof[0]); 245 246 allocator.deallocate(&node); 247 } 248 249 /*********************************************************************** 250 251 Obtains the first or last value in the map. 252 253 Params: 254 first = `true`: obtain the first node, 255 `false`: obtain the last node 256 257 Returns: 258 the first or last value or `null` if the map is empty. 259 260 ***********************************************************************/ 261 262 private T* getBoundary ( bool first = true ) ( ) 263 { 264 static if (first) 265 alias eb64_first eb64_function; 266 else 267 alias eb64_last eb64_function; 268 269 return &((cast(Node*)eb64_function(&this.root)).value); 270 } 271 272 /*********************************************************************** 273 274 Looks up the node for key in the map. 275 276 Params: 277 key = the key to look up node for 278 279 Returns: 280 the node associated with key or null if not found. 281 282 ***********************************************************************/ 283 284 private Node* nodeForKey ( ulong key ) 285 { 286 return cast(Node*)eb64_lookup(&this.root, key); 287 } 288 289 /*************************************************************************** 290 291 Adds a new node to the map for key or obtains the existing if already in 292 the map. 293 294 Params: 295 key = the key to add a new node for or obtain the existing one 296 added = outputs true a new node was added or false if key was found 297 in the map so that the existing node is returned 298 299 Returns: 300 the node associated with key. If added is true then it was newly 301 created and added, otherwise it is the already existing node in the 302 tree. 303 304 ***************************************************************************/ 305 306 private Node* put_ ( ulong key, out bool added ) 307 { 308 Node* node = allocator.allocate(); 309 310 static if (is(Node == eb64_node)) 311 alias node ebnode; 312 else 313 eb64_node* ebnode = &node.tupleof[0]; 314 315 ebnode.key = key; 316 eb64_node* added_ebnode = eb64_insert(&this.root, ebnode); 317 added = added_ebnode is ebnode; 318 319 if (!added) 320 allocator.deallocate(node); 321 322 return cast(Node*)added_ebnode; 323 } 324 325 /*************************************************************************** 326 327 `malloc` allocator for `Node`. Deallocating keeps a spare item as an 328 optimisation for the frequent situation of allocating an item, then 329 noticing it isn't actually needed and freeing it (this happens in 330 `put()` when a duplicate is detected). 331 332 ***************************************************************************/ 333 334 private struct MallocAllocator 335 { 336 import core.stdc.stdlib: malloc, free, exit, EXIT_FAILURE; 337 import core.stdc.stdio: stderr, fputs; 338 339 /*********************************************************************** 340 341 The spare node, set by `deallocate()` and used by `allocate()`. 342 343 ***********************************************************************/ 344 345 Node* spare = null; 346 347 /*********************************************************************** 348 349 Allocates a new or reuses the spare node. The returned node should 350 be deallocated by `deallocate()` when not used any more. 351 352 If `malloc` fails, prints out an error message and terminates the 353 process with `EXIT_FAILURE`. 354 355 Returns: 356 an initialised node ready to use. 357 358 ***********************************************************************/ 359 360 Node* allocate ( ) 361 { 362 if (auto node = this.spare) 363 { 364 this.spare = null; 365 return node; 366 } 367 368 if (auto node = cast(Node*)malloc(Node.sizeof)) 369 { 370 *node = (*node).init; 371 return node; 372 } 373 else 374 { 375 enum istring msg = "malloc(" ~ Node.sizeof.stringof ~ 376 ") failed: Out of memory\n\0"; 377 fputs(msg.ptr, stderr); 378 exit(EXIT_FAILURE); 379 assert(false); 380 } 381 } 382 383 /*********************************************************************** 384 385 Deallocates node or stores it in the spare item. 386 387 Params: 388 node = the item to deallocate, previously obtained by 389 `allocate()` 390 391 ***********************************************************************/ 392 393 void deallocate ( Node* node ) 394 { 395 if (this.spare is null) 396 { 397 *node = (*node).init; 398 this.spare = node; 399 } 400 else 401 { 402 free(node); 403 } 404 } 405 } 406 } 407 408 version (unittest) 409 { 410 import ocean.core.Test; 411 } 412 413 /// 414 unittest 415 { 416 TreeMap!(char[2]) map; 417 418 bool added; 419 auto value_ptr = map.put(1, added); 420 test!("==")(added, true); 421 422 (*value_ptr)[] = "AA"; 423 (*map.put(2, added))[] = "AB"; 424 (*map.put(3, added))[] = "AC"; 425 426 foreach (id, value; map) 427 { 428 switch (id) 429 { 430 case 1: 431 test!("==")((*value)[], "AA"); 432 break; 433 434 case 2: 435 test!("==")((*value)[], "AB"); 436 break; 437 438 case 3: 439 test!("==")((*value)[], "AC"); 440 break; 441 442 default: 443 test(false); 444 break; 445 } 446 } 447 448 map.remove(2); 449 foreach (id, value; map) 450 { 451 switch (id) 452 { 453 case 1: 454 test!("==")((*value)[], "AA"); 455 break; 456 457 case 3: 458 test!("==")((*value)[], "AC"); 459 break; 460 461 default: 462 test(false); 463 break; 464 } 465 } 466 467 test!("==")((*map.first)[], "AA"); 468 test!("==")((*map.last)[], "AC"); 469 } 470 471 /******************************************************************************* 472 473 An empty unique ebtree root. 474 475 The value is generated via CTFE. 476 477 *******************************************************************************/ 478 479 private static immutable eb_root empty_unique_ebtroot = 480 function ( ) 481 { 482 eb_root root; 483 root.unique = true; 484 return root; 485 }();