1 /****************************************************************************** 2 3 Bindings for Elastic Binary Trees library's operations on 128bit nodes. 4 5 This module contains the D binding of the library functions of eb128tree.h. 6 Please consult the original header documentation for details. 7 8 eb128tree.h uses a 128-bit integer type for the node keys, which is not a 9 part of the standard C language but provided as an extension by GCC 4.6 and 10 later for targets that support it. These targets include x86-64 but not x86. 11 12 @see http://gcc.gnu.org/onlinedocs/gcc-4.6.2/gcc/_005f_005fint128.html 13 @see http://gcc.gnu.org/gcc-4.6/changes.html 14 15 Since cent/ucent are currently not implemented, they need to be emulated 16 by two 64-bit integer values (int + uint for cent, uint + uint for ucent). 17 eb128tree.c provides dual-64-bit functions to interchange the 128-bit keys. 18 19 You need to have the library installed and link with -lebtree. 20 21 Copyright: 22 Copyright (c) 2009-2016 dunnhumby Germany GmbH. 23 All rights reserved. 24 25 License: 26 Boost Software License Version 1.0. See LICENSE_BOOST.txt for details. 27 Alternatively, this file may be distributed under the terms of the Tango 28 3-Clause BSD License (see LICENSE_BSD.txt for details). 29 30 Bear in mind this module provides bindings to an external library that 31 has its own license, which might be more restrictive. Please check the 32 external library license to see which conditions apply for linking. 33 34 ******************************************************************************/ 35 36 module ocean.util.container.ebtree.c.eb128tree; 37 38 39 40 import ocean.meta.types.Qualifiers; 41 import ocean.util.container.ebtree.c.ebtree: eb_root, eb_node; 42 43 44 /****************************************************************************** 45 46 ucent emulator struct 47 48 ******************************************************************************/ 49 50 struct UCent 51 { 52 /************************************************************************** 53 54 lo contains the lower, hi the higher 64 bits of the ucent value. 55 56 **************************************************************************/ 57 58 ulong lo, hi; 59 60 /************************************************************************** 61 62 Compares this instance to other in the same way as the libebtree does. 63 64 Params: 65 rhs = instance to compare against this 66 67 Returns: 68 a value less than 0 if this < rhs, 69 a value greater than 0 if this > rhs 70 or 0 if this == rhs. 71 72 **************************************************************************/ 73 74 public int opCmp ( const typeof(this) rhs ) const 75 { 76 return eb128_cmp_264(this.tupleof, rhs.tupleof); 77 } 78 79 public equals_t opEquals(UCent rhs) 80 { 81 return this.opCmp(rhs) == 0; 82 } 83 } 84 85 /****************************************************************************** 86 87 cent emulator struct 88 89 ******************************************************************************/ 90 91 struct Cent 92 { 93 /************************************************************************** 94 95 lo contains the lower, hi the higher 64 bits of the ucent value. 96 97 **************************************************************************/ 98 99 ulong lo; 100 long hi; 101 102 /************************************************************************** 103 104 Compares this instance to other in the same way as the libebtree does. 105 106 Params: 107 rhs = instance to compare against this 108 109 Returns: 110 a value less than 0 if this < rhs, 111 a value greater than 0 if this > rhs 112 or 0 if this == rhs. 113 114 **************************************************************************/ 115 116 public int opCmp ( const typeof(this) rhs ) const 117 { 118 return eb128i_cmp_264(this.tupleof, rhs.tupleof); 119 } 120 121 public equals_t opEquals(Cent rhs) 122 { 123 return this.opCmp(rhs) == 0; 124 } 125 } 126 127 /// See original's library documentation for details. 128 struct eb128_node 129 { 130 eb_node node; // the tree node, must be at the beginning 131 private ubyte[16] key_; 132 133 /************************************************************************** 134 135 Evaluates to Cent if signed is true or to UCent otherwise. 136 137 **************************************************************************/ 138 139 template UC ( bool signed ) 140 { 141 static if (signed) 142 { 143 alias Cent UC; 144 } 145 else 146 { 147 alias UCent UC; 148 } 149 } 150 151 /************************************************************************** 152 153 Sets the key. 154 155 Params: 156 key_ = new key 157 158 Returns: 159 new key. 160 161 **************************************************************************/ 162 163 UCent key ( ) ( UCent key_ ) 164 { 165 eb128_node_setkey_264(&this, key_.lo, key_.hi); 166 167 return key_; 168 } 169 170 /************************************************************************** 171 172 ditto 173 174 **************************************************************************/ 175 176 Cent key ( ) ( Cent key_ ) 177 { 178 eb128i_node_setkey_264(&this, key_.lo, key_.hi); 179 180 return key_; 181 } 182 183 /************************************************************************** 184 185 Gets the key. 186 187 Params: 188 signed = true: the key was originally a Cent, false: it was a UCent 189 190 Returns: 191 the current key. 192 193 **************************************************************************/ 194 195 UC!(signed) key ( bool signed = false ) ( ) 196 { 197 static if (signed) 198 { 199 Cent result; 200 201 eb128i_node_getkey_264(&this, &result.lo, &result.hi); 202 } 203 else 204 { 205 UCent result; 206 207 eb128_node_getkey_264(&this, &result.lo, &result.hi); 208 } 209 210 return result; 211 } 212 213 /// Return next node in the tree, skipping duplicates, or NULL if none 214 215 typeof(&this) next ( ) 216 { 217 return eb128_next(&this); 218 } 219 220 /// Return previous node in the tree, or NULL if none 221 222 typeof(&this) prev ( ) 223 { 224 return eb128_prev(&this); 225 } 226 227 /// Return next node in the tree, skipping duplicates, or NULL if none 228 229 typeof(&this) next_unique ( ) 230 { 231 return eb128_next_unique(&this); 232 } 233 234 /// Return previous node in the tree, skipping duplicates, or NULL if none 235 236 typeof(&this) prev_unique ( ) 237 { 238 return eb128_prev_unique(&this); 239 } 240 } 241 242 extern (C): 243 244 /// Return leftmost node in the tree, or NULL if none 245 eb128_node* eb128_first(eb_root* root); 246 247 /// Return rightmost node in the tree, or NULL if none 248 eb128_node* eb128_last(eb_root* root); 249 250 /// Return next node in the tree, or NULL if none 251 eb128_node* eb128_next(eb128_node* eb128); 252 253 /// Return previous node in the tree, or NULL if none 254 eb128_node* eb128_prev(eb128_node* eb128); 255 256 /// Return next node in the tree, skipping duplicates, or NULL if none 257 eb128_node* eb128_next_unique(eb128_node* eb128); 258 259 /// Return previous node in the tree, skipping duplicates, or NULL if none 260 eb128_node* eb128_prev_unique(eb128_node* eb128); 261 262 /// Delete node from the tree if it was linked in. Mark the node unused. 263 void eb128_delete(eb128_node* eb128); 264 265 /// See original's library documentation for details. 266 eb128_node* eb128_lookup_264 ( eb_root* root, ulong lo, ulong hi ); 267 268 /// See original's library documentation for details. 269 eb128_node* eb128i_lookup_264 ( eb_root* root, ulong lo, long hi ); 270 271 /// See original's library documentation for details. 272 eb128_node* eb128_lookup_le_264 ( eb_root* root, ulong lo, ulong hi ); 273 274 /// See original's library documentation for details. 275 eb128_node* eb128_lookup_ge_264 ( eb_root* root, ulong lo, ulong hi ); 276 277 /// See original's library documentation for details. 278 eb128_node* eb128_insert ( eb_root* root, eb128_node* neww ); 279 280 /// See original's library documentation for details. 281 eb128_node* eb128i_insert ( eb_root* root, eb128_node* neww ); 282 283 /****************************************************************************** 284 285 Tells whether a is less than b. a and b are uint128_t values composed from 286 alo and ahi or blo and bhi, respectively. 287 288 Params: 289 alo = value of the lower 64 bits of a 290 ahi = value of the higher 64 bits of a 291 blo = value of the lower 64 bits of b 292 ahi = value of the higher 64 bits of b 293 294 Returns: 295 true if a < b or false otherwise. 296 297 ******************************************************************************/ 298 299 bool eb128_less_264 ( ulong alo, ulong ahi, ulong blo, ulong bhi ); 300 301 /****************************************************************************** 302 303 Tells whether a is less than or equal to b. a and b are uint128_t values 304 composed from alo and ahi or blo and bhi, respectively. 305 306 Params: 307 alo = value of the lower 64 bits of a 308 ahi = value of the higher 64 bits of a 309 blo = value of the lower 64 bits of b 310 ahi = value of the higher 64 bits of b 311 312 Returns: 313 true if a <= b or false otherwise. 314 315 ******************************************************************************/ 316 317 bool eb128_less_or_equal_264 ( ulong alo, ulong ahi, ulong blo, ulong bhi ); 318 319 /****************************************************************************** 320 321 Tells whether a is equal to b. a and b are uint128_t values 322 composed from alo and ahi or blo and bhi, respectively. 323 324 Params: 325 alo = value of the lower 64 bits of a 326 ahi = value of the higher 64 bits of a 327 blo = value of the lower 64 bits of b 328 ahi = value of the higher 64 bits of b 329 330 Returns: 331 true if a == b or false otherwise. 332 333 ******************************************************************************/ 334 335 bool eb128_equal_264 ( ulong alo, ulong ahi, ulong blo, ulong bhi ); 336 337 /****************************************************************************** 338 339 Tells whether a is greater than or equal to b. a and b are uint128_t values 340 composed from alo and ahi or blo and bhi, respectively. 341 342 Params: 343 alo = value of the lower 64 bits of a 344 ahi = value of the higher 64 bits of a 345 blo = value of the lower 64 bits of b 346 ahi = value of the higher 64 bits of b 347 348 Returns: 349 true if a >= b or false otherwise. 350 351 ******************************************************************************/ 352 353 bool eb128_greater_or_equal_264 ( ulong alo, ulong ahi, ulong blo, ulong bhi ); 354 355 /****************************************************************************** 356 357 Tells whether a is greater than b. a and b are uint128_t values 358 composed from alo and ahi or blo and bhi, respectively. 359 360 Params: 361 alo = value of the lower 64 bits of a 362 ahi = value of the higher 64 bits of a 363 blo = value of the lower 64 bits of b 364 ahi = value of the higher 64 bits of b 365 366 Returns: 367 true if a <= b or false otherwise. 368 369 ******************************************************************************/ 370 371 bool eb128_greater_264 ( ulong alo, ulong ahi, ulong blo, ulong bhi ); 372 373 /****************************************************************************** 374 375 Compares a and b in a qsort callback/D opCmp fashion. a and b are uint128_t 376 values composed from alo and ahi or blo and bhi, respectively. 377 378 Params: 379 alo = value of the lower 64 bits of a 380 ahi = value of the higher 64 bits of a 381 blo = value of the lower 64 bits of b 382 ahi = value of the higher 64 bits of b 383 384 Returns: 385 a value less than 0 if a < b, 386 a value greater than 0 if a > b 387 or 0 if a == b. 388 389 ******************************************************************************/ 390 391 int eb128_cmp_264 ( ulong alo, ulong ahi, ulong blo, ulong bhi ); 392 393 /****************************************************************************** 394 395 Tells whether a is less than b. a and b are int128_t values composed from 396 alo and ahi or blo and bhi, respectively. 397 398 Params: 399 alo = value of the lower 64 bits of a 400 ahi = value of the higher 64 bits of a 401 blo = value of the lower 64 bits of b 402 ahi = value of the higher 64 bits of b 403 404 Returns: 405 true if a < b or false otherwise. 406 407 ******************************************************************************/ 408 409 bool eb128i_less_264 ( ulong alo, long ahi, ulong blo, long bhi ); 410 411 /****************************************************************************** 412 413 Tells whether a is less than or equal to b. a and b are int128_t values 414 composed from alo and ahi or blo and bhi, respectively. 415 416 Params: 417 alo = value of the lower 64 bits of a 418 ahi = value of the higher 64 bits of a 419 blo = value of the lower 64 bits of b 420 ahi = value of the higher 64 bits of b 421 422 Returns: 423 true if a <= b or false otherwise. 424 425 ******************************************************************************/ 426 427 bool eb128i_less_or_equal_264 ( ulong alo, long ahi, ulong blo, long bhi ); 428 429 /****************************************************************************** 430 431 Tells whether a is equal to b. a and b are int128_t values composed from 432 alo and ahi or blo and bhi, respectively. 433 434 Params: 435 alo = value of the lower 64 bits of a 436 ahi = value of the higher 64 bits of a 437 blo = value of the lower 64 bits of b 438 ahi = value of the higher 64 bits of b 439 440 Returns: 441 true if a == b or false otherwise. 442 443 ******************************************************************************/ 444 445 bool eb128i_equal_264 ( ulong alo, long ahi, ulong blo, long bhi ); 446 447 /****************************************************************************** 448 449 Tells whether a is greater or equal to than b. a and b are int128_t values 450 composed from alo and ahi or blo and bhi, respectively. 451 452 Params: 453 alo = value of the lower 64 bits of a 454 ahi = value of the higher 64 bits of a 455 blo = value of the lower 64 bits of b 456 ahi = value of the higher 64 bits of b 457 458 Returns: 459 true if a >= b or false otherwise. 460 461 ******************************************************************************/ 462 463 bool eb128i_greater_or_equal_264 ( ulong alo, long ahi, ulong blo, long bhi ); 464 465 /****************************************************************************** 466 467 Tells whether a is greater than b. a and b are int128_t values composed from 468 alo and ahi or blo and bhi, respectively. 469 470 Params: 471 alo = value of the lower 64 bits of a 472 ahi = value of the higher 64 bits of a 473 blo = value of the lower 64 bits of b 474 ahi = value of the higher 64 bits of b 475 476 Returns: 477 true if a > b or false otherwise. 478 479 ******************************************************************************/ 480 481 bool eb128i_greater_264 ( ulong alo, long ahi, ulong blo, long bhi); 482 483 /****************************************************************************** 484 485 Compares a and b in a qsort callback/D opCmp fashion. a and b are int128_t 486 values composed from alo and ahi or blo and bhi, respectively. 487 488 Params: 489 alo = value of the lower 64 bits of a 490 ahi = value of the higher 64 bits of a 491 blo = value of the lower 64 bits of b 492 ahi = value of the higher 64 bits of b 493 494 Returns: 495 a value less than 0 if a < b, 496 a value greater than 0 if a > b 497 or 0 if a == b. 498 499 ******************************************************************************/ 500 501 int eb128i_cmp_264 ( ulong alo, long ahi, ulong blo, long bhi ); 502 503 /****************************************************************************** 504 505 Sets node->key to an uint128_t value composed from lo and hi. 506 507 Params: 508 node = node to set the key 509 lo = value of the lower 64 value bits of node->key 510 hi = value of the higher 64 value bits of node->key 511 512 Returns: 513 node 514 515 ******************************************************************************/ 516 517 eb128_node* eb128_node_setkey_264 ( eb128_node* node, ulong lo, ulong hi ); 518 519 /****************************************************************************** 520 521 Sets node->key to an int128_t value composed from lo and hi. 522 523 Params: 524 node = node to set the key 525 lo = value of the lower 64 value bits of node->key 526 hi = value of the higher 64 value bits of node->key 527 528 Returns: 529 node 530 531 ******************************************************************************/ 532 533 eb128_node* eb128i_node_setkey_264 ( eb128_node* node, long lo, ulong hi ); 534 535 /****************************************************************************** 536 537 Obtains node->key,and decomposes it into two uint64_t values. This assumes 538 that the key was originally unsigned, e.g. set by eb128_node_setkey_264(). 539 540 Params: 541 node = node to obtain the key 542 lo = output of the value of the lower 64 value bits of node->key 543 hi = output of the value of the higher 64 value bits of node->key 544 545 ******************************************************************************/ 546 547 void eb128_node_getkey_264 ( eb128_node* node, ulong* lo, ulong* hi ); 548 549 /****************************************************************************** 550 551 Obtains node->key,and decomposes it into an int64_t and an uint64_t value. 552 This assumes that the key was originally signed, e.g. set by 553 eb128i_node_setkey_264(). 554 555 Params: 556 node = node to obtain the key 557 lo = output of the value of the lower 64 value bits of node->key 558 hi = output of the value of the higher 64 value bits of node->key 559 560 ******************************************************************************/ 561 562 void eb128i_node_getkey_264 ( eb128_node* node, ulong* lo, long* hi );