1 /******************************************************************************* 2 3 Elastic binary tree class 4 5 Fast 32-bit value binary tree class based on the ebtree library from 6 HAProxy. 7 8 You need to have the library installed and link with -lebtree. 9 10 Usage example: 11 12 --- 13 14 import ocean.util.container.ebtree.EBTree64; 15 16 // Create a tree 17 auto tree = new EBTree32!(); 18 19 // Add some values to the tree 20 for ( uint i; i < 100; i++ ) 21 { 22 tree.add(i); 23 } 24 25 // Get the lowest value in the tree 26 auto lowest = tree.first; 27 28 // Get the highest value in the tree 29 auto lowest = tree.last; 30 31 // Iterate over all nodes in the key whose values are <= 50 32 foreach ( node; tree.lessEqual(50) ) 33 { 34 // node value is node.key 35 } 36 37 // Empty the tree 38 tree.clear; 39 40 --- 41 42 Copyright: 43 Copyright (c) 2009-2016 dunnhumby Germany GmbH. 44 All rights reserved. 45 46 License: 47 Boost Software License Version 1.0. See LICENSE_BOOST.txt for details. 48 Alternatively, this file may be distributed under the terms of the Tango 49 3-Clause BSD License (see LICENSE_BSD.txt for details). 50 51 *******************************************************************************/ 52 53 module ocean.util.container.ebtree.EBTree32; 54 55 56 import ocean.meta.types.Qualifiers; 57 58 import ocean.util.container.ebtree.model.IEBTree, 59 ocean.util.container.ebtree.model.Node, 60 ocean.util.container.ebtree.model.KeylessMethods, 61 ocean.util.container.ebtree.model.Iterators; 62 63 import ocean.util.container.ebtree.nodepool.NodePool; 64 65 public import ocean.util.container.ebtree.c.eb32tree; 66 import ocean.util.container.ebtree.c.ebtree: eb_node, eb_root; 67 68 /******************************************************************************* 69 70 EBTree32 class template. 71 72 Params: 73 signed = false: use 'uint' as key type, true: use 'int'. 74 75 *******************************************************************************/ 76 77 class EBTree32 ( bool signed = false ) : IEBTree 78 { 79 import ocean.core.Verify; 80 81 /************************************************************************** 82 83 false if 'uint' is the key type or true if it is 'int'. 84 85 **************************************************************************/ 86 87 public static immutable signed_key = signed; 88 89 /************************************************************************** 90 91 Key type alias 92 93 **************************************************************************/ 94 95 static if (signed) 96 { 97 public alias int Key; 98 } 99 else 100 { 101 public alias uint Key; 102 } 103 104 /************************************************************************** 105 106 Dual32Key struct, allows the usage of two 32-bit integer values as a 107 combined 64-bit key. 108 109 **************************************************************************/ 110 111 struct Dual16Key 112 { 113 /********************************************************************** 114 115 false if 'ushort' is the type of hi (below) or true if it is 116 'short'. 117 118 **********************************************************************/ 119 120 public enum is_signed = signed; 121 122 /********************************************************************** 123 124 lo: Carries the lower 16 bits of the key. 125 126 **********************************************************************/ 127 128 public ushort lo; 129 130 /********************************************************************** 131 132 hi: Carries the higher 16 bits of the key. 133 134 **********************************************************************/ 135 136 static if (signed) 137 { 138 public short hi; 139 } 140 else 141 { 142 public ushort hi; 143 } 144 145 /********************************************************************** 146 147 Compares this instance with other. 148 149 Params: 150 rhs = instance to compare with this 151 152 Returns: 153 a value less than 0 if this < rhs, 154 a value greater than 0 if this > rhs 155 or 0 if this == rhs. 156 157 **********************************************************************/ 158 159 public int opCmp ( const typeof(this) rhs ) const 160 { 161 return (this.hi > rhs.hi)? +1 : 162 (this.hi < rhs.hi)? -1 : 163 (this.lo >= rhs.lo)? (this.lo > rhs.lo) : -1; 164 } 165 166 /********************************************************************** 167 168 Obtains the key to store in the ebtree from this instance. 169 170 Returns: 171 key 172 173 **********************************************************************/ 174 175 private EBTree32!(signed).Key opCast ( ) 176 { 177 return ((cast (int) this.hi) << 0x10) | this.lo; 178 } 179 } 180 181 /************************************************************************** 182 183 Obtains the key of node_; required by the Node mixin. 184 185 Params: 186 node_ = node to obtain key 187 188 Returns: 189 node key 190 191 **************************************************************************/ 192 193 private static Key getKey ( eb32_node* node_ ) 194 { 195 verify (node_ !is null); 196 return node_.key; 197 } 198 199 /*************************************************************************** 200 201 Node struct mixin. Elements of Node are stored in the tree. 202 @see ocean.util.container.ebtree.model.KeylessMethods. 203 204 ***************************************************************************/ 205 206 mixin Node!(eb32_node, Key, getKey, 207 eb32_next, eb32_prev, eb32_prev_unique, eb32_next_unique, 208 eb32_delete); 209 210 /*************************************************************************** 211 212 Mixin of iterators. @see ocean.util.container.ebtree.model.KeylessMethods. 213 214 ***************************************************************************/ 215 216 mixin Iterators!(Node); 217 218 /************************************************************************** 219 220 Node pool interface type alias 221 222 **************************************************************************/ 223 224 public alias .INodePool!(Node) INodePool; 225 226 /************************************************************************** 227 228 Node pool instance 229 230 **************************************************************************/ 231 232 private static immutable INodePool node_pool; 233 234 /************************************************************************** 235 236 Constructor 237 238 **************************************************************************/ 239 240 public this ( ) 241 { 242 this(new NodePool!(Node)); 243 } 244 245 /************************************************************************** 246 247 Constructor 248 249 Params: 250 node_pool = node pool instance to use 251 252 **************************************************************************/ 253 254 public this ( INodePool node_pool ) 255 { 256 this.node_pool = node_pool; 257 } 258 259 /*************************************************************************** 260 261 Mixin of methods. @see ocean.util.container.ebtree.model.KeylessMethods. 262 263 ***************************************************************************/ 264 265 mixin KeylessMethods!(Node, eb32_first, eb32_last); 266 267 /*************************************************************************** 268 269 Adds a new node to the tree, automatically inserting it in the correct 270 location to keep the tree sorted. 271 272 Params: 273 key = key of node to add 274 275 Returns: 276 pointer to the newly added node 277 278 ***************************************************************************/ 279 280 public Node* add ( Key key ) 281 out (node_out) 282 { 283 assert (node_out !is null); 284 } 285 do 286 { 287 scope (success) this.increaseNodeCount(1); 288 289 return this.add_(this.node_pool.get(), key); 290 } 291 292 /*************************************************************************** 293 294 Adds a value to the tree, automatically inserting a new node in the 295 correct location to keep the tree sorted. 296 297 Params: 298 key = value to add 299 300 Returns: 301 pointer to newly added node 302 303 ***************************************************************************/ 304 305 public Node* add ( Dual16Key key ) 306 out (node_out) 307 { 308 assert (node_out !is null); 309 } 310 do 311 { 312 return this.add(cast (Key) key); 313 } 314 315 /*************************************************************************** 316 317 Sets the key of node to key, keeping the tree sorted. 318 319 Params: 320 node = node to update key 321 key = new key for node 322 323 Returns: 324 updated node 325 326 ***************************************************************************/ 327 328 public Node* update ( return ref Node node, Key key ) 329 out (node_out) 330 { 331 assert (node_out !is null); 332 } 333 do 334 { 335 return (node.node_.key != cast (ulong) key)? 336 this.add_(node.remove(), key) : &node; 337 } 338 339 /*************************************************************************** 340 341 Sets the key of node to key, keeping the tree sorted. 342 343 Params: 344 node = node to update key 345 key = new key for node 346 347 Returns: 348 updated node 349 350 ***************************************************************************/ 351 352 public Node* update ( return ref Node node, Dual16Key key ) 353 out (node_out) 354 { 355 assert (node_out !is null); 356 } 357 do 358 { 359 return this.update(node, cast (Key) key); 360 } 361 362 /*************************************************************************** 363 364 Adds a value to the tree, automatically inserting a new node in the 365 correct location to keep the tree sorted. 366 367 Params: 368 key = value to add 369 370 Returns: 371 pointer to newly added node 372 373 ***************************************************************************/ 374 375 public Node* add ( Dual16Key key ) 376 out (node_out) 377 { 378 assert (node_out !is null); 379 } 380 do 381 { 382 return this.add(cast (Key) key); 383 } 384 385 /*************************************************************************** 386 387 Searches the tree for the first node whose key is <= the specified key, 388 and returns it. 389 390 Params: 391 key = key to search for 392 393 Returns: 394 first node <= than specified key, may be null if no node found 395 396 ***************************************************************************/ 397 398 public Node* firstLessEqual ( Key key ) 399 { 400 return this.ebCall!(eb32_lookup_le)(cast (uint) key); 401 } 402 403 404 /*************************************************************************** 405 406 Searches the tree for the first node whose key is >= the specified key, 407 and returns it. 408 409 Params: 410 key = key to search for 411 412 Returns: 413 first node >= than specified key, may be null if no node found 414 415 ***************************************************************************/ 416 417 public Node* firstGreaterEqual ( Key key ) 418 { 419 return this.ebCall!(eb32_lookup_ge)(cast (uint) key); 420 } 421 422 423 /*************************************************************************** 424 425 Searches the tree for the specified key, and returns the first node with 426 that key. 427 428 Params: 429 key = key to search for 430 431 Returns: 432 pointer to first node in tree with specified key, may be null if no 433 nodes found 434 435 ***************************************************************************/ 436 437 public Node* opIn_r ( Key key ) 438 { 439 static if (signed) 440 { 441 return this.ebCall!(eb32i_lookup)(key); 442 } 443 else 444 { 445 return this.ebCall!(eb32_lookup)(key); 446 } 447 } 448 449 450 /*************************************************************************** 451 452 Support for the 'in' operator 453 454 Aliased to opIn_r, for backwards compatibility 455 456 ***************************************************************************/ 457 458 public alias opBinaryRight ( istring op : "in" ) = opIn_r; 459 460 461 /*************************************************************************** 462 463 Adds a value to the tree, automatically inserting a new node in the 464 correct location to keep the tree sorted. 465 466 Params: 467 key_in = value to add 468 469 Returns: 470 pointer to newly added node 471 472 ***************************************************************************/ 473 474 private Node* add_ ( Node* node, Key key ) 475 out (node_out) 476 { 477 assert (node_out !is null); 478 } 479 do 480 { 481 verify (node !is null, "attempted to add null node (node pool returned null?)"); 482 node.node_.key = key; 483 484 static if (signed) 485 { 486 return this.ebCall!(eb32i_insert)(&node.node_); 487 } 488 else 489 { 490 return this.ebCall!(eb32_insert)(&node.node_); 491 } 492 } 493 }