1 /******************************************************************************* 2 3 Elastic binary tree class 4 5 Fast 64-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 EBTree64!(); 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.EBTree64; 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.eb64tree; 66 import ocean.util.container.ebtree.c.ebtree: eb_node, eb_root; 67 68 /******************************************************************************* 69 70 EBTree64 class template. 71 72 Params: 73 signed = false: use 'ulong' as key type, true: use 'long'. 74 75 *******************************************************************************/ 76 77 class EBTree64 ( bool signed = false ) : IEBTree 78 { 79 import ocean.core.Verify; 80 81 /************************************************************************** 82 83 false if 'ulong' is the key type or true if it is 'long'. 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 long Key; 98 } 99 else 100 { 101 public alias ulong 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 Dual32Key 112 { 113 /********************************************************************** 114 115 false if 'uint' is the type of hi (below) or true if it is 'int'. 116 117 **********************************************************************/ 118 119 public enum is_signed = signed; 120 121 /********************************************************************** 122 123 lo: Carries the lower 32 bits of the key. 124 125 **********************************************************************/ 126 127 public uint lo; 128 129 /********************************************************************** 130 131 hi: Carries the higher 32 bits of the key. 132 133 **********************************************************************/ 134 135 static if (signed) 136 { 137 public int hi; 138 } 139 else 140 { 141 public uint hi; 142 } 143 144 /********************************************************************** 145 146 Compares this instance with rhs. 147 148 Params: 149 rhs = instance to compare with this 150 151 Returns: 152 a value less than 0 if this < rhs, 153 a value greater than 0 if this > rhs 154 or 0 if this == rhs. 155 156 **********************************************************************/ 157 158 public int opCmp ( const typeof(this) rhs ) const 159 { 160 return (this.hi > rhs.hi)? +1 : 161 (this.hi < rhs.hi)? -1 : 162 (this.lo >= rhs.lo)? (this.lo > rhs.lo) : -1; 163 } 164 165 public equals_t opEquals(Dual32Key rhs) 166 { 167 return this.opCmp(rhs) == 0; 168 } 169 170 /********************************************************************** 171 172 Obtains the key to store in the ebtree from this instance. 173 174 Returns: 175 key 176 177 **********************************************************************/ 178 179 private EBTree64!(signed).Key opCast ( ) 180 { 181 return ((cast (long) this.hi) << 0x20) | this.lo; 182 } 183 } 184 185 /************************************************************************** 186 187 Node struct, Node instances are stored in the ebtree. 188 189 **************************************************************************/ 190 191 private static Key getKey ( eb64_node* node_ ) 192 { 193 return node_.key; 194 } 195 196 mixin Node!(eb64_node, Key, getKey, 197 eb64_next, eb64_prev, eb64_prev_unique, eb64_next_unique, 198 eb64_delete); 199 200 mixin Iterators!(Node); 201 202 /************************************************************************** 203 204 Node pool interface type alias 205 206 **************************************************************************/ 207 208 public alias .INodePool!(Node) INodePool; 209 210 /************************************************************************** 211 212 Node pool instance 213 214 **************************************************************************/ 215 216 private INodePool node_pool; 217 218 /************************************************************************** 219 220 Constructor 221 222 **************************************************************************/ 223 224 public this ( ) 225 { 226 this(new NodePool!(Node)); 227 } 228 229 /************************************************************************** 230 231 Constructor 232 233 Params: 234 node_pool = node pool instance to use 235 236 **************************************************************************/ 237 238 public this ( INodePool node_pool ) 239 { 240 this.node_pool = node_pool; 241 } 242 243 mixin KeylessMethods!(Node, eb64_first, eb64_last); 244 245 /*************************************************************************** 246 247 Adds a new node to the tree, automatically inserting it in the correct 248 location to keep the tree sorted. 249 250 Params: 251 key = key of node to add 252 253 Returns: 254 pointer to the newly added node 255 256 ***************************************************************************/ 257 258 public Node* add ( Key key ) 259 out (node_out) 260 { 261 assert (node_out !is null); 262 } 263 do 264 { 265 scope (success) this.increaseNodeCount(1); 266 267 return this.add_(this.node_pool.get(), key); 268 } 269 270 /*************************************************************************** 271 272 Adds a value to the tree, automatically inserting a new node in the 273 correct location to keep the tree sorted. 274 275 Params: 276 key = value to add 277 278 Returns: 279 pointer to newly added node 280 281 ***************************************************************************/ 282 283 public Node* add ( Dual32Key key ) 284 out (node_out) 285 { 286 assert (node_out !is null); 287 } 288 do 289 { 290 return this.add(cast (Key) key); 291 } 292 293 /*************************************************************************** 294 295 Sets the key of node to key, keeping the tree sorted. 296 297 Params: 298 node = node to update key 299 key = new key for node 300 301 Returns: 302 updated node 303 304 ***************************************************************************/ 305 306 public Node* update ( return ref Node node, Key key ) 307 out (node_out) 308 { 309 assert (node_out !is null); 310 } 311 do 312 { 313 return (node.node_.key != cast (ulong) key)? 314 this.add_(node.remove(), key) : &node; 315 } 316 317 /*************************************************************************** 318 319 Sets the key of node to key, keeping the tree sorted. 320 321 Params: 322 node = node to update key 323 key = new key for node 324 325 Returns: 326 updated node 327 328 ***************************************************************************/ 329 330 public Node* update ( return ref Node node, Dual32Key key ) 331 out (node_out) 332 { 333 assert (node_out !is null); 334 } 335 do 336 { 337 return this.update(node, cast (Key) key); 338 } 339 340 /*************************************************************************** 341 342 Searches the tree for the first node whose key is <= the specified key, 343 and returns it. 344 345 Params: 346 key = key to search for 347 348 Returns: 349 first node <= than specified key, may be null if no node found 350 351 ***************************************************************************/ 352 353 public Node* firstLessEqual ( Key key ) 354 { 355 return this.ebCall!(eb64_lookup_le)(cast (ulong) key); 356 } 357 358 359 /*************************************************************************** 360 361 Searches the tree for the first node whose key is >= the specified key, 362 and returns it. 363 364 Params: 365 key = key to search for 366 367 Returns: 368 first node >= than specified key, may be null if no node found 369 370 ***************************************************************************/ 371 372 public Node* firstGreaterEqual ( Key key ) 373 { 374 return this.ebCall!(eb64_lookup_ge)(cast (ulong) key); 375 } 376 377 378 /*************************************************************************** 379 380 Searches the tree for the specified key, and returns the first node with 381 that key. 382 383 Params: 384 key = key to search for 385 386 Returns: 387 pointer to first node in tree with specified key, may be null if no 388 nodes found 389 390 ***************************************************************************/ 391 392 public Node* opIn_r ( Key key ) 393 { 394 static if (signed) 395 { 396 return this.ebCall!(eb64i_lookup)(key); 397 } 398 else 399 { 400 return this.ebCall!(eb64_lookup)(key); 401 } 402 } 403 404 405 /*************************************************************************** 406 407 Support for the 'in' operator 408 409 Aliased to opIn_r, for backwards compatibility 410 411 ***************************************************************************/ 412 413 public alias opBinaryRight ( istring op : "in" ) = opIn_r; 414 415 416 /*************************************************************************** 417 418 Adds node to the tree, automatically inserting it in the correct 419 location to keep the tree sorted. 420 421 Params: 422 node = node to add 423 key = key for node 424 425 Returns: 426 node 427 428 ***************************************************************************/ 429 430 private Node* add_ ( Node* node, Key key ) 431 out (node_out) 432 { 433 assert (node_out !is null); 434 } 435 do 436 { 437 verify (node !is null, "attempted to add null node (node pool returned null?)"); 438 439 node.node_.key = key; 440 441 static if (signed) 442 { 443 return this.ebCall!(eb64i_insert)(&node.node_); 444 } 445 else 446 { 447 return this.ebCall!(eb64_insert)(&node.node_); 448 } 449 } 450 }