ocean.util.container.ebtree.c.eb128tree source code

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 );