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 }