1 /******************************************************************************* 2 3 Elastic binary tree class 4 5 Fast 128-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 Copyright: 11 Copyright (c) 2009-2016 dunnhumby Germany GmbH. 12 All rights reserved. 13 14 License: 15 Boost Software License Version 1.0. See LICENSE_BOOST.txt for details. 16 Alternatively, this file may be distributed under the terms of the Tango 17 3-Clause BSD License (see LICENSE_BSD.txt for details). 18 19 *******************************************************************************/ 20 21 module ocean.util.container.ebtree.EBTree128; 22 23 24 import ocean.meta.types.Qualifiers; 25 26 import ocean.util.container.ebtree.model.IEBTree, 27 ocean.util.container.ebtree.model.Node, 28 ocean.util.container.ebtree.model.KeylessMethods, 29 ocean.util.container.ebtree.model.Iterators; 30 31 import ocean.util.container.ebtree.nodepool.NodePool; 32 33 public import ocean.util.container.ebtree.c.eb128tree; 34 import ocean.util.container.ebtree.c.ebtree: eb_node, eb_root; 35 36 import ocean.core.Test; 37 38 /******************************************************************************* 39 40 EBTree64 class template. 41 42 Params: 43 signed = false: use the 'ucent' surrogate as key type, true: 'cent'. 44 45 *******************************************************************************/ 46 47 class EBTree128 ( bool signed = false ) : IEBTree 48 { 49 import ocean.core.Verify; 50 51 /************************************************************************** 52 53 false if the 'ucent' surrogate is the key type or true if 'cent'. 54 55 **************************************************************************/ 56 57 public static immutable signed_key = signed; 58 59 /************************************************************************** 60 61 Key struct, acts as a 'ucent'/'cent' surrogate, using two 64-bit integer 62 values as a combined 128-bit key. 63 64 **************************************************************************/ 65 66 struct Key 67 { 68 /********************************************************************** 69 70 false if 'uint' is the type of hi (below) or true if it is 'int'. 71 72 **********************************************************************/ 73 74 public enum is_signed = signed; 75 76 /********************************************************************** 77 78 lo: Carries the lower 64 bits of the key. 79 80 **********************************************************************/ 81 82 public ulong lo; 83 84 /********************************************************************** 85 86 hi: Carries the higher 64 bits of the key. 87 88 **********************************************************************/ 89 90 static if (signed) 91 { 92 public long hi; 93 } 94 else 95 { 96 public ulong hi; 97 } 98 99 /********************************************************************** 100 101 Compares this instance with rhs. 102 103 Params: 104 rhs = instance to compare with this 105 106 Returns: 107 a value less than 0 if this < rhs, 108 a value greater than 0 if this > rhs 109 or 0 if this == rhs. 110 111 **********************************************************************/ 112 113 public int opCmp ( const typeof(this) rhs ) const 114 { 115 static if (signed) 116 { 117 return eb128i_cmp_264(this.lo, this.hi, rhs.lo, rhs.hi); 118 } 119 else 120 { 121 return eb128_cmp_264(this.lo, this.hi, rhs.lo, rhs.hi); 122 } 123 } 124 125 public equals_t opEquals(Key rhs) 126 { 127 return this.opCmp(rhs) == 0; 128 } 129 } 130 131 /********************************************************************** 132 133 Obtains the key of this node. 134 135 Returns: 136 key 137 138 **********************************************************************/ 139 140 private static Key getKey ( eb128_node* node_ ) 141 { 142 Key result; 143 144 static if (signed) 145 { 146 eb128i_node_getkey_264(node_, &result.lo, &result.hi); 147 } 148 else 149 { 150 eb128_node_getkey_264(node_, &result.lo, &result.hi); 151 } 152 153 return result; 154 } 155 156 /************************************************************************** 157 158 Node struct, Node instances are stored in the ebtree. 159 160 **************************************************************************/ 161 162 mixin Node!(eb128_node, Key, getKey, 163 eb128_next, eb128_prev, eb128_prev_unique, eb128_next_unique, 164 eb128_delete); 165 166 mixin Iterators!(Node); 167 168 /************************************************************************** 169 170 Node pool interface type alias 171 172 **************************************************************************/ 173 174 public alias .INodePool!(Node) INodePool; 175 176 /************************************************************************** 177 178 Node pool instance 179 180 **************************************************************************/ 181 182 private INodePool node_pool; 183 184 /************************************************************************** 185 186 Constructor 187 188 **************************************************************************/ 189 190 public this ( ) 191 { 192 this(new NodePool!(Node)); 193 } 194 195 /************************************************************************** 196 197 Constructor 198 199 Params: 200 node_pool = node pool instance to use 201 202 **************************************************************************/ 203 204 public this ( INodePool node_pool ) 205 { 206 this.node_pool = node_pool; 207 } 208 209 mixin KeylessMethods!(Node, eb128_first, eb128_last); 210 211 /*************************************************************************** 212 213 Adds a new node to the tree, automatically inserting it in the correct 214 location to keep the tree sorted. 215 216 Params: 217 key = key of node to add 218 219 Returns: 220 pointer to the newly added node 221 222 ***************************************************************************/ 223 224 public Node* add ( Key key ) 225 out (node_out) 226 { 227 assert (node_out !is null); 228 } 229 do 230 { 231 scope (success) this.increaseNodeCount(1); 232 233 return this.add_(this.node_pool.get(), key); 234 } 235 236 /*************************************************************************** 237 238 Sets the key of node to key, keeping the tree sorted. 239 240 Params: 241 node = node to update key 242 key = new key for node 243 244 Returns: 245 updated node 246 247 ***************************************************************************/ 248 249 public Node* update ( return ref Node node, Key key ) 250 out (node_out) 251 { 252 assert (node_out !is null); 253 } 254 do 255 { 256 return (node.key != key)? this.add_(node.remove(), key) : &node; 257 } 258 259 /*************************************************************************** 260 261 Recycles the nodes back to the node pool and call the super class 262 clear() 263 264 ***************************************************************************/ 265 266 public override void clear() 267 { 268 foreach(ref node; this) 269 { 270 this.node_pool.recycle(&node); 271 } 272 super.clear(); 273 } 274 275 /*************************************************************************** 276 277 Searches the tree for the first node whose key is <= the specified key, 278 and returns it. 279 280 Params: 281 key = key to search for 282 283 Returns: 284 first node <= than specified key, may be null if no node found 285 286 ***************************************************************************/ 287 288 public Node* firstLessEqual ( Key key ) 289 { 290 return this.ebCall!(eb128_lookup_le_264)(key.lo, cast (ulong) key.hi); 291 } 292 293 294 /*************************************************************************** 295 296 Searches the tree for the first node whose key is >= the specified key, 297 and returns it. 298 299 Params: 300 key = key to search for 301 302 Returns: 303 first node >= than specified key, may be null if no node found 304 305 ***************************************************************************/ 306 307 public Node* firstGreaterEqual ( Key key ) 308 { 309 return this.ebCall!(eb128_lookup_ge_264)(key.lo, cast (ulong) key.hi); 310 } 311 312 313 /*************************************************************************** 314 315 Searches the tree for the specified key, and returns the first node with 316 that key. 317 318 Params: 319 key = key to search for 320 321 Returns: 322 pointer to first node in tree with specified key, may be null if no 323 nodes found 324 325 ***************************************************************************/ 326 327 public Node* opIn_r ( Key key ) 328 { 329 static if (signed) 330 { 331 return this.ebCall!(eb128i_lookup_264)(key.lo, key.hi); 332 } 333 else 334 { 335 return this.ebCall!(eb128_lookup_264)(key.lo, key.hi); 336 } 337 } 338 339 340 /*************************************************************************** 341 342 Support for the 'in' operator 343 344 Aliased to opIn_r, for backwards compatibility 345 346 ***************************************************************************/ 347 348 public alias opBinaryRight ( istring op : "in" ) = opIn_r; 349 350 351 /*************************************************************************** 352 353 Adds node to the tree, automatically inserting it in the correct 354 location to keep the tree sorted. 355 356 Params: 357 node = node to add 358 key = key for node 359 360 Returns: 361 node 362 363 ***************************************************************************/ 364 365 private Node* add_ ( Node* node, Key key ) 366 out (node_out) 367 { 368 assert (node_out !is null); 369 } 370 do 371 { 372 verify (node !is null, "attempted to add null node (node pool returned null?)"); 373 374 static if (signed) 375 { 376 eb128i_node_setkey_264(&node.node_, key.lo, key.hi); 377 378 return this.ebCall!(eb128i_insert)(&node.node_); 379 } 380 else 381 { 382 eb128_node_setkey_264(&node.node_, key.lo, key.hi); 383 384 return this.ebCall!(eb128_insert)(&node.node_); 385 } 386 } 387 } 388 389 unittest 390 { 391 EBTree128!(true).Key signed_a; 392 signed_a.hi = 0xFFFF_FFFF_FFFF_FFFF; 393 signed_a.lo = 0x1FFF_FFFF_FFFF_FFFF; 394 395 EBTree128!(true).Key signed_b; 396 signed_b.hi = 0x1; 397 signed_b.lo = 0x0; 398 399 400 // In signed arithmetics, a should be less than b 401 test!("<")(signed_a, signed_b); 402 403 404 EBTree128!().Key unsigned_a; 405 unsigned_a.hi = 0xFFFF_FFFF_FFFF_FFFF; 406 unsigned_a.lo = 0x1FFF_FFFF_FFFF_FFFF; 407 408 EBTree128!().Key unsigned_b; 409 unsigned_b.hi = 0x1; 410 unsigned_b.lo = 0x0; 411 412 // In unsigned arithmetics, a should be greatereater than b 413 test!(">")(unsigned_a, unsigned_b); 414 }