File Coverage

TreeRBXS.xs
Criterion Covered Total %
statement 687 830 82.7
branch 473 876 54.0
condition n/a
subroutine n/a
pod n/a
total 1160 1706 68.0


line stmt bran cond sub pod time code
1             #include "EXTERN.h"
2             #include "perl.h"
3             #include "XSUB.h"
4             #include "ppport.h"
5              
6             /* The core Red/Black algorithm which operates on rbtree_node_t */
7             #include "rbtree.h"
8              
9             struct TreeRBXS;
10             struct TreeRBXS_item;
11              
12             #define AUTOCREATE 1
13             #define OR_DIE 2
14              
15             #define KEY_TYPE_ANY 1
16             #define KEY_TYPE_CLAIM 2
17             #define KEY_TYPE_INT 3
18             #define KEY_TYPE_FLOAT 4
19             #define KEY_TYPE_BSTR 5
20             #define KEY_TYPE_USTR 6
21             #define KEY_TYPE_MAX 6
22              
23             /* I am only using foldEQ for parsing user parameters, not for the sort functions,
24             * so this should be fine for Perl < 5.14 */
25             #ifndef foldEQ
26             static bool shim_foldEQ(const char *s1, const char *s2, int len) {
27             for (--len; len >= 0; --len)
28             if (toLOWER(s1[len]) != toLOWER(s2[len]))
29             return 0;
30             return 1;
31             }
32             #define foldEQ shim_foldEQ
33             #endif
34              
35 35           static int parse_key_type(SV *type_sv) {
36             const char *str;
37             size_t len;
38 35           int key_type= -1;
39 35 100         if (SvIOK(type_sv)) {
40 27 50         key_type= SvIV(type_sv);
41 27 50         if (key_type < 1 || key_type > KEY_TYPE_MAX)
    50          
42 27           key_type= -1;
43             }
44 8 50         else if (SvPOK(type_sv)) {
45 8 50         str= SvPV(type_sv, len);
46 8 100         if (len > 9 && foldEQ(str, "KEY_TYPE_", 9)) {
    50          
47 2           str += 9;
48 2           len -= 9;
49             }
50 15 50         key_type= (len == 3 && foldEQ(str, "ANY", 3))? KEY_TYPE_ANY
51 16 100         : (len == 5 && foldEQ(str, "CLAIM", 5))? KEY_TYPE_CLAIM
    0          
52 23 50         : (len == 3 && foldEQ(str, "INT", 3))? KEY_TYPE_INT
    50          
53 16 100         : (len == 5 && foldEQ(str, "FLOAT", 5))? KEY_TYPE_FLOAT
    0          
54 3 50         : (len == 4 && foldEQ(str, "BSTR", 4))? KEY_TYPE_BSTR
    50          
55 2 50         : (len == 4 && foldEQ(str, "USTR", 4))? KEY_TYPE_USTR
    0          
56 0 0         : -1;
57             }
58 35           return key_type;
59             }
60              
61 16           static const char *get_key_type_name(int key_type) {
62 16           switch (key_type) {
63 5           case KEY_TYPE_ANY: return "KEY_TYPE_ANY";
64 0           case KEY_TYPE_CLAIM: return "KEY_TYPE_CLAIM";
65 2           case KEY_TYPE_INT: return "KEY_TYPE_INT";
66 2           case KEY_TYPE_FLOAT: return "KEY_TYPE_FLOAT";
67 4           case KEY_TYPE_BSTR: return "KEY_TYPE_BSTR";
68 3           case KEY_TYPE_USTR: return "KEY_TYPE_USTR";
69 0           default: return NULL;
70             }
71             }
72              
73             typedef int TreeRBXS_cmp_fn(struct TreeRBXS *tree, struct TreeRBXS_item *a, struct TreeRBXS_item *b);
74             static TreeRBXS_cmp_fn TreeRBXS_cmp_int;
75             static TreeRBXS_cmp_fn TreeRBXS_cmp_float;
76             static TreeRBXS_cmp_fn TreeRBXS_cmp_memcmp;
77             static TreeRBXS_cmp_fn TreeRBXS_cmp_utf8;
78             static TreeRBXS_cmp_fn TreeRBXS_cmp_numsplit;
79             static TreeRBXS_cmp_fn TreeRBXS_cmp_perl;
80             static TreeRBXS_cmp_fn TreeRBXS_cmp_perl_cb;
81              
82             #define CMP_PERL 1
83             #define CMP_INT 2
84             #define CMP_FLOAT 3
85             #define CMP_MEMCMP 4
86             #define CMP_UTF8 5
87             #define CMP_SUB 6
88             #define CMP_NUMSPLIT 7
89             #define CMP_MAX 7
90              
91 7           static int parse_cmp_fn(SV *cmp_sv) {
92             const char *str;
93             size_t len;
94 7           int cmp_id= -1;
95 7 100         if (SvROK(cmp_sv) && SvTYPE(SvRV(cmp_sv)) == SVt_PVCV)
    50          
96 4           cmp_id= CMP_SUB;
97 3 100         else if (SvIOK(cmp_sv)) {
98 2 50         cmp_id= SvIV(cmp_sv);
99 2 50         if (cmp_id < 1 || cmp_id > CMP_MAX || cmp_id == CMP_SUB)
    50          
    50          
100 2           cmp_id= -1;
101             }
102 1 50         else if (SvPOK(cmp_sv)) {
103 1 50         str= SvPV(cmp_sv, len);
104 1 50         if (len > 4 && foldEQ(str, "CMP_", 4)) {
    50          
105 0           str += 4;
106 0           len -= 4;
107             }
108 1 0         cmp_id= (len == 4 && foldEQ(str, "PERL", 4))? CMP_PERL
109 2 50         : (len == 3 && foldEQ(str, "INT", 3))? CMP_INT
    0          
110 2 50         : (len == 5 && foldEQ(str, "FLOAT", 5))? CMP_FLOAT
    0          
111 2 50         : (len == 6 && foldEQ(str, "MEMCMP", 6))? CMP_MEMCMP
    0          
112 2 50         : (len == 4 && foldEQ(str, "UTF8", 4))? CMP_UTF8
    0          
113 3 50         : (len == 8 && foldEQ(str, "NUMSPLIT", 8))? CMP_NUMSPLIT
    50          
114             //: (len == 7 && foldEQ(str, "SUB", 3))? CMP_SUB can only be requested by a CV*
115 2 50         : -1;
116             }
117 7           return cmp_id;
118             }
119              
120 8           static const char * get_cmp_name(int cmp_id) {
121 8           switch (cmp_id) {
122 1           case CMP_PERL: return "CMP_PERL";
123 1           case CMP_INT: return "CMP_INT";
124 1           case CMP_FLOAT: return "CMP_FLOAT";
125 1           case CMP_MEMCMP: return "CMP_MEMCMP";
126 1           case CMP_UTF8: return "CMP_UTF8";
127 3           case CMP_NUMSPLIT: return "CMP_NUMSPLIT";
128 0           default: return NULL;
129             }
130             }
131              
132             #define GET_EQ 0
133             #define GET_GE 1
134             #define GET_LE 2
135             #define GET_GT 3
136             #define GET_LT 4
137             #define GET_NEXT 5
138             #define GET_PREV 6
139             #define GET_EQ_LAST 7
140             #define GET_LE_LAST 8
141             #define GET_MAX 8
142              
143 34           static int parse_lookup_mode(SV *mode_sv) {
144             int mode;
145             size_t len;
146             char *mode_str;
147              
148 34           mode= -1;
149 34 50         if (SvIOK(mode_sv)) {
150 34 50         mode= SvIV(mode_sv);
151 34 50         if (mode < 0 || mode > GET_MAX)
    50          
152 34           mode= -1;
153 0 0         } else if (SvPOK(mode_sv)) {
154 0 0         mode_str= SvPV(mode_sv, len);
155 0 0         if (len > 4 && foldEQ(mode_str, "GET_", 4)) {
    0          
156 0           mode_str+= 4;
157 0           len -= 4;
158             }
159             // Allow alternate syntax of "==" etc, 'eq' etc, or any of the official constant names
160 0           switch (mode_str[0]) {
161 0 0         case '<': mode= len == 1? GET_LT : len == 2 && mode_str[1] == '='? GET_LE : -1; break;
    0          
    0          
162 0 0         case '>': mode= len == 1? GET_GT : len == 2 && mode_str[1] == '='? GET_GE : -1; break;
    0          
    0          
163 0 0         case '=': mode= len == 2 && mode_str[1] == '='? GET_EQ : -1; break;
    0          
164 0 0         case '-': mode= len == 2 && mode_str[1] == '-'? GET_PREV : -1; break;
    0          
165 0 0         case '+': mode= len == 2 && mode_str[1] == '+'? GET_NEXT : -1; break;
    0          
166             case 'E': case 'e':
167 0 0         mode= len == 2 && (mode_str[1] == 'q' || mode_str[1] == 'Q')? GET_EQ
    0          
168 0 0         : len == 7 && foldEQ(mode_str, "EQ_LAST", 7)? GET_EQ_LAST
    0          
169 0 0         : -1;
170 0           break;
171             case 'G': case 'g':
172 0 0         mode= len == 2 && (mode_str[1] == 't' || mode_str[1] == 'T')? GET_GT
    0          
173 0 0         : len == 2 && (mode_str[1] == 'e' || mode_str[1] == 'E')? GET_GE
    0          
    0          
174 0 0         : -1;
175 0           break;
176             case 'L': case 'l':
177 0 0         mode= len == 2 && (mode_str[1] == 't' || mode_str[1] == 'T')? GET_LT
    0          
178 0 0         : len == 2 && (mode_str[1] == 'e' || mode_str[1] == 'E')? GET_LE
    0          
    0          
179 0 0         : len == 7 && foldEQ(mode_str, "LE_LAST", 7)? GET_LE_LAST
    0          
180 0 0         : -1;
181 0           break;
182 0 0         case 'P': case 'p': mode= foldEQ(mode_str, "PREV", 4)? GET_PREV : -1; break;
183 0 0         case 'N': case 'n': mode= foldEQ(mode_str, "NEXT", 4)? GET_NEXT : -1; break;
184             }
185             }
186 34           return mode;
187             }
188              
189             #define EXPORT_ENUM(x) newCONSTSUB(stash, #x, new_enum_dualvar(x, newSVpvs_share(#x)))
190 234           static SV * new_enum_dualvar(IV ival, SV *name) {
191 234 50         SvUPGRADE(name, SVt_PVNV);
192 234           SvIV_set(name, ival);
193 234           SvIOK_on(name);
194 234           SvREADONLY_on(name);
195 234           return name;
196             }
197              
198             // Struct attached to each instance of Tree::RB::XS
199             struct TreeRBXS {
200             SV *owner; // points to Tree::RB::XS internal HV (not ref)
201             TreeRBXS_cmp_fn *compare; // internal compare function. Always set and never changed.
202             SV *compare_callback; // user-supplied compare. May be NULL, but can never be changed.
203             int key_type; // must always be set and never changed
204             int compare_fn_id; // indicates which compare is in use, for debugging
205             bool allow_duplicates; // flag to affect behavior of insert. may be changed.
206             bool compat_list_get; // flag to enable full compat with Tree::RB's list context behavior
207             rbtree_node_t root_sentinel; // parent-of-root, used by rbtree implementation.
208             rbtree_node_t leaf_sentinel; // dummy node used by rbtree implementation.
209             struct TreeRBXS_iter *hashiter;// iterator used for TIEHASH
210             bool hashiterset; // true if the hashiter has been set manually with hseek
211             };
212              
213             static void TreeRBXS_assert_structure(struct TreeRBXS *tree);
214             struct TreeRBXS_iter * TreeRBXS_get_hashiter(struct TreeRBXS *tree);
215             static struct TreeRBXS_item *TreeRBXS_find_item(struct TreeRBXS *tree, struct TreeRBXS_item *key, int mode);
216             static void TreeRBXS_destroy(struct TreeRBXS *tree);
217              
218             #define TreeRBXS_get_root(tree) ((tree)->root_sentinel.left)
219             #define TreeRBXS_get_count(tree) ((tree)->root_sentinel.left->count)
220              
221             #define OFS_TreeRBXS_FIELD_root_sentinel ( ((char*) &(((struct TreeRBXS*)(void*)10000)->root_sentinel)) - ((char*)10000) )
222             #define GET_TreeRBXS_FROM_root_sentinel(node) ((struct TreeRBXS*) (((char*)node) - OFS_TreeRBXS_FIELD_root_sentinel))
223              
224             #define OFS_TreeRBXS_item_FIELD_rbnode ( ((char*) &(((struct TreeRBXS_item *)(void*)10000)->rbnode)) - ((char*)10000) )
225             #define GET_TreeRBXS_item_FROM_rbnode(node) ((struct TreeRBXS_item*) (((char*)node) - OFS_TreeRBXS_item_FIELD_rbnode))
226              
227             // Struct attached to each instance of Tree::RB::XS::Node
228             // I named it 'item' instead of 'node' to prevent confusion with the actual
229             // rbtree_node_t used by the underlying library.
230             struct TreeRBXS_item {
231             SV *owner; // points to Tree::RB::XS::Node internal SV (not ref), or NULL if not wrapped
232             rbtree_node_t rbnode; // actual red/black left/right/color/parent/count fields
233             union itemkey_u { // key variations are overlapped to save space
234             IV ikey;
235             NV nkey;
236             const char *ckey;
237             SV *svkey;
238             } keyunion;
239             struct TreeRBXS_iter *iter; // linked list of iterators who reference this item
240             SV *value; // value will be set unless struct is just used as a search key
241             size_t key_type: 4,
242             #if SIZE_MAX == 0xFFFFFFFF
243             #define CKEYLEN_MAX ((((size_t)1)<<28)-1)
244             ckeylen: 28;
245             #else
246             #define CKEYLEN_MAX ((((size_t)1)<<60)-1)
247             ckeylen: 60;
248             #endif
249             char extra[];
250             };
251              
252             static void TreeRBXS_init_tmp_item(struct TreeRBXS_item *item, struct TreeRBXS *tree, SV *key, SV *value);
253             static struct TreeRBXS_item * TreeRBXS_new_item_from_tmp_item(struct TreeRBXS_item *src);
254             static struct TreeRBXS* TreeRBXS_item_get_tree(struct TreeRBXS_item *item);
255             static void TreeRBXS_item_advance_all_iters(struct TreeRBXS_item* item);
256             static void TreeRBXS_item_detach_iter(struct TreeRBXS_item *item, struct TreeRBXS_iter *iter);
257             static void TreeRBXS_item_detach_owner(struct TreeRBXS_item* item);
258             static void TreeRBXS_item_free(struct TreeRBXS_item *item);
259              
260             struct TreeRBXS_iter {
261             struct TreeRBXS *tree;
262             SV *owner;
263             struct TreeRBXS_iter *next_iter;
264             struct TreeRBXS_item *item;
265             int reverse;
266             };
267              
268             static void TreeRBXS_iter_rewind(struct TreeRBXS_iter *iter);
269             static void TreeRBXS_iter_set_item(struct TreeRBXS_iter *iter, struct TreeRBXS_item *item);
270             static void TreeRBXS_iter_advance(struct TreeRBXS_iter *iter, IV ofs);
271             static void TreeRBXS_iter_free(struct TreeRBXS_iter *iter);
272              
273 15           static void TreeRBXS_assert_structure(struct TreeRBXS *tree) {
274             int err;
275             rbtree_node_t *node;
276             struct TreeRBXS_item *item;
277             struct TreeRBXS_iter *iter;
278              
279 15 50         if (!tree) croak("tree is NULL");
280 15 50         if (!tree->owner) croak("no owner");
281 15 50         if (tree->key_type < 0 || tree->key_type > KEY_TYPE_MAX) croak("bad key_type");
    50          
282 15 50         if (!tree->compare) croak("no compare function");
283 15 50         if ((err= rbtree_check_structure(&tree->root_sentinel, (int(*)(void*,void*,void*)) tree->compare, tree, -OFS_TreeRBXS_item_FIELD_rbnode)))
284 0           croak("tree structure damaged: %d", err);
285 15 50         if (TreeRBXS_get_count(tree)) {
286 15           node= rbtree_node_left_leaf(tree->root_sentinel.left);
287 470023 100         while (node) {
288 470008           item= GET_TreeRBXS_item_FROM_rbnode(node);
289 470008 50         if (item->key_type != tree->key_type)
290 0           croak("node key_type doesn't match tree");
291 470008 50         if (!item->value)
292 0           croak("node value SV lost");
293 470008 50         if (item->iter) {
294 0           iter= item->iter;
295 0 0         while (iter) {
296 0 0         if (!iter->owner) croak("Iterator lacks owner reference");
297 0 0         if (iter->item != item) croak("Iterator referenced by wrong item");
298 0           iter= iter->next_iter;
299             }
300             }
301 470008           node= rbtree_node_next(node);
302             }
303             }
304             //warn("Tree is healthy");
305 15           }
306              
307 28           struct TreeRBXS_iter * TreeRBXS_get_hashiter(struct TreeRBXS *tree) {
308             // This iterator is owned by the tree. All other iterators would hold a reference to the tree.
309 28 100         if (!tree->hashiter) {
310 1           Newxz(tree->hashiter, 1, struct TreeRBXS_iter);
311 1           tree->hashiter->tree= tree;
312             }
313 28           return tree->hashiter;
314             }
315              
316             /* For insert/put, there needs to be a node created before it can be
317             * inserted. But if the insert fails, the item needs cleaned up.
318             * This initializes a temporary incomplete item on the stack that can be
319             * used for searching without the expense of allocating buffers etc.
320             * The temporary item does not require any destructor/cleanup.
321             */
322 470493           static void TreeRBXS_init_tmp_item(struct TreeRBXS_item *item, struct TreeRBXS *tree, SV *key, SV *value) {
323 470493           size_t len= 0;
324              
325             // all fields should start NULL just to be safe
326 470493           memset(item, 0, sizeof(*item));
327             // copy key type from tree
328 470493           item->key_type= tree->key_type;
329             // set up the keys.
330 470493           switch (item->key_type) {
331             case KEY_TYPE_ANY:
332 130168           case KEY_TYPE_CLAIM: item->keyunion.svkey= key; break;
333 110168 50         case KEY_TYPE_INT: item->keyunion.ikey= SvIV(key); break;
334 110055 100         case KEY_TYPE_FLOAT: item->keyunion.nkey= SvNV(key); break;
335             // STR and BSTR assume that the 'key' SV has a longer lifespan than the use of the tmp item,
336             // and directly reference the PV pointer. The insert and search algorithms should not be
337             // calling into Perl for their entire execution.
338             case KEY_TYPE_USTR:
339 10023 50         item->keyunion.ckey= SvPVutf8(key, len);
340             if (0)
341             case KEY_TYPE_BSTR:
342 110079 100         item->keyunion.ckey= SvPVbyte(key, len);
343             // the ckeylen is a bit field, so can't go the full range of size_t
344 120102 50         if (len > CKEYLEN_MAX)
345 0           croak("String length %ld exceeds maximum %ld for optimized key_type", (long)len, CKEYLEN_MAX);
346 120102           item->ckeylen= len;
347 120102           break;
348             default:
349 0           croak("BUG: un-handled key_type");
350             }
351 470493           item->value= value;
352 470493           }
353              
354             /* When insert has decided that the temporary node is permitted ot be inserted,
355             * this function allocates a real item struct with its own reference counts
356             * and buffer data, etc.
357             */
358 470212           static struct TreeRBXS_item * TreeRBXS_new_item_from_tmp_item(struct TreeRBXS_item *src) {
359             struct TreeRBXS_item *dst;
360             size_t len;
361             /* If the item references a string that is not managed by a SV,
362             copy that into the space at the end of the allocated block. */
363 470212 100         if (src->key_type == KEY_TYPE_USTR || src->key_type == KEY_TYPE_BSTR) {
    100          
364 120049           len= src->ckeylen;
365 120049           Newxc(dst, sizeof(struct TreeRBXS_item) + len + 1, char, struct TreeRBXS_item);
366 120049           memset(dst, 0, sizeof(struct TreeRBXS_item));
367 120049           memcpy(dst->extra, src->keyunion.ckey, len);
368 120049           dst->extra[len]= '\0';
369 120049           dst->keyunion.ckey= dst->extra;
370 120049           dst->ckeylen= src->ckeylen;
371             }
372             else {
373 350163           Newxz(dst, 1, struct TreeRBXS_item);
374 350163           switch (src->key_type) {
375 120084           case KEY_TYPE_ANY: dst->keyunion.svkey= newSVsv(src->keyunion.svkey);
376             if (0)
377 10000           case KEY_TYPE_CLAIM: dst->keyunion.svkey= SvREFCNT_inc(src->keyunion.svkey);
378 130084           SvREADONLY_on(dst->keyunion.svkey);
379 130084           break;
380 110076           case KEY_TYPE_INT: dst->keyunion.ikey= src->keyunion.ikey; break;
381 110003           case KEY_TYPE_FLOAT: dst->keyunion.nkey= src->keyunion.nkey; break;
382             default:
383 0           croak("BUG: un-handled key_type %d", src->key_type);
384             }
385             }
386 470212           dst->key_type= src->key_type;
387 470212           dst->value= newSVsv(src->value);
388 470212           return dst;
389             }
390              
391 23           static struct TreeRBXS* TreeRBXS_item_get_tree(struct TreeRBXS_item *item) {
392 23           rbtree_node_t *node= rbtree_node_rootsentinel(&item->rbnode);
393 23 100         return node? GET_TreeRBXS_FROM_root_sentinel(node) : NULL;
394             }
395              
396 470212           static void TreeRBXS_item_free(struct TreeRBXS_item *item) {
397             //warn("TreeRBXS_item_free");
398 470212 100         switch (item->key_type) {
399             case KEY_TYPE_ANY:
400 130084           case KEY_TYPE_CLAIM: SvREFCNT_dec(item->keyunion.svkey); break;
401             }
402 470212 50         if (item->value)
403 470212           SvREFCNT_dec(item->value);
404 470212           Safefree(item);
405 470212           }
406              
407 90           static void TreeRBXS_item_detach_owner(struct TreeRBXS_item* item) {
408             //warn("TreeRBXS_item_detach_owner");
409             /* the MAGIC of owner doens't need changed because the only time this gets called
410             is when something else is taking care of that. */
411             //if (item->owner != NULL) {
412             // TreeRBXS_set_magic_item(item->owner, NULL);
413             //}
414 90           item->owner= NULL;
415             /* The tree is the other 'owner' of the node. If the item is not in the tree,
416             then this was the last reference, and it needs freed. */
417 90 100         if (!rbtree_node_is_in_tree(&item->rbnode))
418 10           TreeRBXS_item_free(item);
419 90           }
420              
421 1499           static void TreeRBXS_item_detach_iter(struct TreeRBXS_item *item, struct TreeRBXS_iter *iter) {
422             struct TreeRBXS_iter **cur;
423              
424             // Linked-list remove
425 15330 50         for (cur= &item->iter; *cur; cur= &((*cur)->next_iter)) {
426 15330 100         if (*cur == iter) {
427 1499           *cur= iter->next_iter;
428 1499           iter->next_iter= NULL;
429 1499           iter->item= NULL;
430 1499           return;
431             }
432             }
433 0           croak("BUG: iterator not found in item's linked list");
434             }
435              
436 6           static void TreeRBXS_iter_rewind(struct TreeRBXS_iter *iter) {
437 12           rbtree_node_t *node= iter->reverse
438 2           ? rbtree_node_right_leaf(TreeRBXS_get_root(iter->tree))
439 6 100         : rbtree_node_left_leaf(TreeRBXS_get_root(iter->tree));
440 6 50         TreeRBXS_iter_set_item(iter, node? GET_TreeRBXS_item_FROM_rbnode(node) : NULL);
441 6           }
442              
443 1743           static void TreeRBXS_iter_set_item(struct TreeRBXS_iter *iter, struct TreeRBXS_item *item) {
444             struct TreeRBXS_iter **cur;
445              
446 1743 100         if (iter->item == item)
447 19           return;
448              
449 1724 100         if (iter->item)
450 1484           TreeRBXS_item_detach_iter(iter->item, iter);
451              
452 1724 100         if (item) {
453 1533           iter->item= item;
454             // linked-list insert
455 1533           iter->next_iter= item->iter;
456 1533           item->iter= iter;
457             }
458             }
459              
460 1520           static void TreeRBXS_iter_advance(struct TreeRBXS_iter *iter, IV ofs) {
461             rbtree_node_t *node;
462             size_t pos, newpos, cnt;
463              
464 1520 50         if (!iter->tree)
465 0           croak("BUG: iterator lost tree");
466             // Most common case
467 1520 100         if (ofs == 1) {
468 761 100         if (iter->item) {
469 746           node= &iter->item->rbnode;
470 746 100         node= iter->reverse? rbtree_node_prev(node) : rbtree_node_next(node);
471 761 100         TreeRBXS_iter_set_item(iter, node? GET_TreeRBXS_item_FROM_rbnode(node) : NULL);
472             }
473             // nothing to do at end of iteration
474             }
475             else {
476             // More advanced case falls back to by-index, since the log(n) of indexes is likely
477             // about the same as a few hops forward or backward, and because reversing from EOF
478             // means there isn't a current node to step from anyway.
479 759           cnt= TreeRBXS_get_count(iter->tree);
480             // rbtree measures index in size_t, but this function applies a signed offset to it
481             // of possibly a different word length. Also, clamp overflows to the ends of the
482             // range of nodes and don't wrap.
483 1518           pos= !iter->item? cnt
484 1496 100         : !iter->reverse? rbtree_node_index(&iter->item->rbnode)
485             // For reverse iterators, swap the scale so that math goes upward
486 737 100         : cnt - 1 - rbtree_node_index(&iter->item->rbnode);
487 759 100         if (ofs > 0) {
488 754 100         newpos= (UV)ofs < (cnt-pos)? pos + ofs : cnt;
489             } else {
490 5           ofs= -ofs;
491 5 50         newpos= (pos < ofs)? 0 : pos - ofs;
492             }
493             // swap back for reverse iterators
494 759 100         if (iter->reverse) newpos= cnt - 1 - newpos;
495 759           node= rbtree_node_child_at_index(TreeRBXS_get_root(iter->tree), (size_t)newpos);
496 759 100         TreeRBXS_iter_set_item(iter, node? GET_TreeRBXS_item_FROM_rbnode(node) : NULL);
497             }
498 1520           }
499              
500             // Optimized version of advance that applies to all iters pointing at a node.
501             // Calling advance in a loop is probably fine except for the edge case of
502             // iterators piling up on eachother as nodes get removed from the tree.
503 12           static void TreeRBXS_item_advance_all_iters(struct TreeRBXS_item* item) {
504             rbtree_node_t *node;
505 12           struct TreeRBXS_item *next_item= NULL, *prev_item= NULL;
506             struct TreeRBXS_iter *iter, *next;
507            
508             // Dissolve a linked list to move the iters to the previous or next item's linked list
509 88 100         for (iter= item->iter; iter; iter= next) {
510 76           next= iter->next_iter;
511             // Is it a forward or backward iter?
512 76 100         if (iter->reverse) {
513 30 100         if (!prev_item) {
514 20           node= rbtree_node_prev(&item->rbnode);
515 20 100         if (node)
516 3           prev_item= GET_TreeRBXS_item_FROM_rbnode(node);
517             else {
518             // end of iteration
519 17           iter->item= NULL;
520 17           iter->next_iter= NULL;
521 17           continue;
522             }
523             }
524 13           iter->item= prev_item;
525             // linked list add head node
526 13           iter->next_iter= prev_item->iter;
527 13           prev_item->iter= iter;
528             }
529             // else forward iter
530             else {
531 46 100         if (!next_item) {
532 25           node= rbtree_node_next(&item->rbnode);
533 25 100         if (node)
534 8           next_item= GET_TreeRBXS_item_FROM_rbnode(node);
535             else {
536             // end of iteration
537 17           iter->item= NULL;
538 17           iter->next_iter= NULL;
539 17           continue;
540             }
541             }
542 29           iter->item= next_item;
543             // linked list add head node
544 29           iter->next_iter= next_item->iter;
545 29           next_item->iter= iter;
546             }
547             }
548 12           }
549              
550 470212           static void TreeRBXS_item_detach_tree(struct TreeRBXS_item* item, struct TreeRBXS *tree) {
551             //warn("TreeRBXS_item_detach_tree");
552             //warn("detach tree %p %p key %d", item, tree, (int) item->keyunion.ikey);
553 470212 100         if (rbtree_node_is_in_tree(&item->rbnode)) {
554             // If any iterator points to this node, move it to the following node.
555 26 100         if (item->iter)
556 12           TreeRBXS_item_advance_all_iters(item);
557 26           rbtree_node_prune(&item->rbnode);
558             }
559             /* The item could be owned by a tree or by a Node/Iterator, or both.
560             If the tree releases the reference, the Node/Iterator will be the owner.
561             Else the tree was the only owner, and the node needs freed */
562 470212 100         if (!item->owner)
563 470202           TreeRBXS_item_free(item);
564 470212           }
565              
566 230           static void TreeRBXS_iter_free(struct TreeRBXS_iter *iter) {
567 230 100         if (iter->item)
568 15           TreeRBXS_item_detach_iter(iter->item, iter);
569 230 50         if (iter->tree) {
570 230 100         if (iter->tree->hashiter == iter)
571 1           iter->tree->hashiter= NULL;
572             else
573 229           SvREFCNT_dec(iter->tree->owner);
574             }
575 230           Safefree(iter);
576 230           }
577              
578 45           static void TreeRBXS_destroy(struct TreeRBXS *tree) {
579             //warn("TreeRBXS_destroy");
580 45           rbtree_clear(&tree->root_sentinel, (void (*)(void *, void *)) &TreeRBXS_item_detach_tree, -OFS_TreeRBXS_item_FIELD_rbnode, tree);
581 45 100         if (tree->compare_callback)
582 4           SvREFCNT_dec(tree->compare_callback);
583 45 100         if (tree->hashiter)
584 1           TreeRBXS_iter_free(tree->hashiter);
585 45           }
586              
587 250           static struct TreeRBXS_item *TreeRBXS_find_item(struct TreeRBXS *tree, struct TreeRBXS_item *key, int mode) {
588             rbtree_node_t *first, *last;
589 250           rbtree_node_t *node= NULL;
590              
591             // Need to ensure we find the *first* matching node for a key,
592             // to deal with the case of duplicate keys.
593 250 100         if (rbtree_find_all(
594             &tree->root_sentinel,
595             key,
596 250           (int(*)(void*,void*,void*)) tree->compare,
597             tree, -OFS_TreeRBXS_item_FIELD_rbnode,
598             &first, &last, NULL)
599             ) {
600             // Found an exact match. First and last are the range of nodes matching.
601 241           switch (mode) {
602             case GET_EQ:
603             case GET_GE:
604 228           case GET_LE: node= first; break;
605             case GET_EQ_LAST:
606 5           case GET_LE_LAST: node= last; break;
607             case GET_LT:
608 4           case GET_PREV: node= rbtree_node_prev(first); break;
609             case GET_GT:
610 4           case GET_NEXT: node= rbtree_node_next(last); break;
611 241           default: croak("BUG: unhandled mode");
612             }
613             } else {
614             // Didn't find an exact match. First and last are the bounds of what would have matched.
615 9           switch (mode) {
616             case GET_EQ:
617 1           case GET_EQ_LAST: node= NULL; break;
618             case GET_GE:
619 3           case GET_GT: node= last; break;
620             case GET_LE:
621             case GET_LE_LAST:
622 3           case GET_LT: node= first; break;
623             case GET_PREV:
624 2           case GET_NEXT: node= NULL; break;
625 0           default: croak("BUG: unhandled mode");
626             }
627             }
628 250 100         return node? GET_TreeRBXS_item_FROM_rbnode(node) : NULL;
629             }
630              
631             /*----------------------------------------------------------------------------
632             * Comparison Functions.
633             * These conform to the rbtree_compare_fn signature of a context followed by
634             * two "key" pointers. In this case, the keys are TreeRBXS_item structs
635             * and the actual key field depends on the key_type of the node. However,
636             * for speed, the key_type is assumed to have been chosen correctly for the
637             * comparison function during _init
638             */
639              
640             // Compare integers which were both already decoded from the original SVs
641 3205069           static int TreeRBXS_cmp_int(struct TreeRBXS *tree, struct TreeRBXS_item *a, struct TreeRBXS_item *b) {
642             //warn(" int compare %p (%d) <=> %p (%d)", a, (int)a->keyunion.ikey, b, (int)b->keyunion.ikey);
643 3205069           IV diff= a->keyunion.ikey - b->keyunion.ikey;
644 3205069 100         return diff < 0? -1 : diff > 0? 1 : 0; /* shrink from IV to int might lose upper bits */
645             }
646              
647             // Compare floats which were both already decoded from the original SVs
648 3204660           static int TreeRBXS_cmp_float(struct TreeRBXS *tree, struct TreeRBXS_item *a, struct TreeRBXS_item *b) {
649 3204660           NV diff= a->keyunion.nkey - b->keyunion.nkey;
650 3204660 100         return diff < 0? -1 : diff > 0? 1 : 0;
651             }
652              
653             // Compare C strings using memcmp, on raw byte values. The strings have been pre-processed to
654             // be comparable with memcmp, by case-folding, or making sure both are UTF-8, etc.
655 3055939           static int TreeRBXS_cmp_memcmp(struct TreeRBXS *tree, struct TreeRBXS_item *a, struct TreeRBXS_item *b) {
656 3055939           size_t alen= a->ckeylen, blen= b->ckeylen;
657 3055939           int cmp= memcmp(a->keyunion.ckey, b->keyunion.ckey, alen < blen? alen : blen);
658 3055939 100         return cmp? cmp : alen < blen? -1 : alen > blen? 1 : 0;
    100          
659             }
660              
661             //#define DEBUG_NUMSPLIT(args...) warn(args)
662             #define DEBUG_NUMSPLIT(args...)
663 234           static int TreeRBXS_cmp_numsplit(struct TreeRBXS *tree, struct TreeRBXS_item *a, struct TreeRBXS_item *b) {
664             const char *apos, *alim, *amark;
665             const char *bpos, *blim, *bmark;
666             size_t alen, blen;
667 234           bool a_utf8= false, b_utf8= false;
668             int cmp;
669              
670 234           switch (tree->key_type) {
671             case KEY_TYPE_USTR:
672 78           a_utf8= b_utf8= true;
673             case KEY_TYPE_BSTR:
674 156           apos= a->keyunion.ckey; alim= apos + a->ckeylen;
675 156           bpos= b->keyunion.ckey; blim= bpos + b->ckeylen;
676 156           break;
677             case KEY_TYPE_ANY:
678             case KEY_TYPE_CLAIM:
679             #if PERL_VERSION_LT(5,14,0)
680             // before 5.14, need to force both to utf8 if either are utf8
681             if (SvUTF8(a->keyunion.svkey) || SvUTF8(b->keyunion.svkey)) {
682             apos= SvPVutf8(a->keyunion.svkey, alen);
683             bpos= SvPVutf8(b->keyunion.svkey, blen);
684             a_utf8= b_utf8= true;
685             } else
686             #else
687             // After 5.14, can compare utf8 with bytes without converting the buffer
688 78           a_utf8= SvUTF8(a->keyunion.svkey);
689 78           b_utf8= SvUTF8(b->keyunion.svkey);
690             #endif
691             {
692 78 50         apos= SvPV(a->keyunion.svkey, alen);
693 78 50         bpos= SvPV(b->keyunion.svkey, blen);
694             }
695 78           alim= apos + alen;
696 78           blim= bpos + blen;
697 78           break;
698 0           default: croak("BUG");
699             }
700              
701             DEBUG_NUMSPLIT("compare '%.*s' | '%.*s'", (int)(alim-apos), apos, (int)(blim-bpos), bpos);
702 285 50         while (apos < alim && bpos < blim) {
    100          
703             // Step forward as long as both strings are identical
704 375 100         while (apos < alim && bpos < blim && *apos == *bpos && !isdigit(*apos))
    50          
    100          
    100          
705 102           apos++, bpos++;
706             // find the next start of digits along the strings
707 273           amark= apos;
708 567 100         while (apos < alim && !isdigit(*apos)) apos++;
    100          
709 273           bmark= bpos;
710 417 100         while (bpos < blim && !isdigit(*bpos)) bpos++;
    100          
711 273           alen= apos - amark;
712 273           blen= bpos - bmark;
713             // compare the non-digit portions found in each string
714 273 100         if (alen || blen) {
    100          
715             // If one of the non-digit spans was length=0, then we are comparing digits (or EOF)
716             // with string, and digits sort first.
717 78 100         if (alen == 0) { DEBUG_NUMSPLIT("a EOF or digit, b has chars, -1"); return -1; }
718 66 100         if (blen == 0) { DEBUG_NUMSPLIT("b EOF or digit, a has chars, 1"); return 1; }
719             // else compare the portions in common.
720             #if PERL_VERSION_GE(5,14,0)
721 24 50         if (a_utf8 != b_utf8) {
722 0           cmp= a_utf8? -bytes_cmp_utf8(bmark, blen, amark, alen)
723 0 0         : bytes_cmp_utf8(amark, alen, bmark, blen);
724 0 0         if (cmp) { DEBUG_NUMSPLIT("bytes_cmp_utf8('%.*s','%.*s')= %d", (int)alen, amark, (int)blen, bmark, cmp); return cmp; }
725             } else
726             #endif
727             {
728 24           cmp= memcmp(amark, bmark, alen < blen? alen : blen);
729 24 50         if (cmp) { DEBUG_NUMSPLIT("memcmp('%.*s','%.*s') = %d", (int)alen, amark, (int)blen, bmark, cmp); return cmp; }
730 0 0         if (alen < blen) { DEBUG_NUMSPLIT("alen < blen = -1"); return -1; }
731 0 0         if (alen > blen) { DEBUG_NUMSPLIT("alen > blen = 1"); return -1; }
732             }
733             }
734             // If one of the strings ran out of characters, it is the lesser one.
735 195 100         if (!(apos < alim && bpos < blim)) break;
    50          
736             // compare the digit portions found in each string
737             // Find the start of nonzero digits
738 567 50         while (apos < alim && *apos == '0') apos++;
    100          
739 195 50         while (bpos < blim && *bpos == '0') bpos++;
    100          
740 192           amark= apos;
741 192           bmark= bpos;
742             // find the first differing digit
743 354 50         while (apos < alim && bpos < blim && *apos == *bpos && isdigit(*apos))
    100          
    100          
    100          
744 162           apos++, bpos++;
745             // If there are more digits to consider beyond the first mismatch (or EOF) then need to
746             // find the end of the digits and see which number was longer.
747 192 50         if ((apos < alim && isdigit(*apos)) || (bpos < blim && isdigit(*bpos))) {
    100          
    100          
    100          
748 141 50         if (apos == alim) { DEBUG_NUMSPLIT("b has more digits = -1"); return -1; }
749 141 100         if (bpos == blim) { DEBUG_NUMSPLIT("a has more digits = 1"); return 1; }
750             // If the strings happen to be the same length, this will be the deciding character
751 138           cmp= *apos - *bpos;
752             // find the end of digits
753 342 100         while (apos < alim && isdigit(*apos)) apos++;
    100          
754 324 100         while (bpos < blim && isdigit(*bpos)) bpos++;
    100          
755             // Whichever number is longer is greater
756 138           alen= apos - amark;
757 138           blen= bpos - bmark;
758 138 100         if (alen < blen) { DEBUG_NUMSPLIT("b numerically greater = -1"); return -1; }
759 96 100         if (alen > blen) { DEBUG_NUMSPLIT("a numerically greater = 1"); return 1; }
760             // Else they're the same length, and the 'cmp' captured earlier is the answer.
761             DEBUG_NUMSPLIT("%.*s <=> %.*s = %d", (int)alen, amark, (int)blen, bmark, cmp);
762 51           return cmp;
763             }
764             // Else they're equal, continue to the next component.
765             }
766             // One or both of the strings ran out of characters
767 15 50         if (bpos < blim) { DEBUG_NUMSPLIT("b is longer '%.*s' = -1", (int)(blim-bpos), bpos); return -1; }
768 15 100         if (apos < alim) { DEBUG_NUMSPLIT("a is longer '%.*s' = 1", (int)(alim-apos), apos); return 1; }
769             DEBUG_NUMSPLIT("identical");
770 234           return 0;
771             }
772              
773             // Compare SV items using Perl's 'cmp' operator
774 416045           static int TreeRBXS_cmp_perl(struct TreeRBXS *tree, struct TreeRBXS_item *a, struct TreeRBXS_item *b) {
775 416045           return sv_cmp(a->keyunion.svkey, b->keyunion.svkey);
776             }
777              
778             // Compare SV items using a user-supplied perl callback
779 3204664           static int TreeRBXS_cmp_perl_cb(struct TreeRBXS *tree, struct TreeRBXS_item *a, struct TreeRBXS_item *b) {
780             int ret;
781 3204664           dSP;
782 3204664           ENTER;
783             // There are a max of $tree_depth comparisons to do during an insert or search,
784             // so should be safe to not free temporaries for a little bit.
785 3204664 50         PUSHMARK(SP);
786 3204664 50         EXTEND(SP, 2);
787 3204664           PUSHs(a->keyunion.svkey);
788 3204664           PUSHs(b->keyunion.svkey);
789 3204664           PUTBACK;
790 3204664 50         if (call_sv(tree->compare_callback, G_SCALAR) != 1)
791 0           croak("stack assertion failed");
792 3204664           SPAGAIN;
793 3204664 50         ret= POPi;
794 3204664           PUTBACK;
795             // FREETMPS;
796 3204664           LEAVE;
797 3204664           return ret;
798             }
799              
800             /*------------------------------------------------------------------------------------
801             * Definitions of Perl MAGIC that attach C structs to Perl SVs
802             * All instances of Tree::RB::XS have a magic-attached struct TreeRBXS
803             * All instances of Tree::RB::XS::Node have a magic-attached struct TreeRBXS_item
804             */
805              
806             // destructor for Tree::RB::XS
807 45           static int TreeRBXS_magic_free(pTHX_ SV* sv, MAGIC* mg) {
808 45 50         if (mg->mg_ptr) {
809 45           TreeRBXS_destroy((struct TreeRBXS*) mg->mg_ptr);
810 45           Safefree(mg->mg_ptr);
811 45           mg->mg_ptr= NULL;
812             }
813 45           return 0; // ignored anyway
814             }
815             #ifdef USE_ITHREADS
816             static int TreeRBXS_magic_dup(pTHX_ MAGIC *mg, CLONE_PARAMS *param) {
817             croak("This object cannot be shared between threads");
818             return 0;
819             };
820             #else
821             #define TreeRBXS_magic_dup 0
822             #endif
823              
824             // magic table for Tree::RB::XS
825             static MGVTBL TreeRBXS_magic_vt= {
826             0, /* get */
827             0, /* write */
828             0, /* length */
829             0, /* clear */
830             TreeRBXS_magic_free,
831             0, /* copy */
832             TreeRBXS_magic_dup
833             #ifdef MGf_LOCAL
834             ,0
835             #endif
836             };
837              
838             // destructor for Tree::RB::XS::Node
839 90           static int TreeRBXS_item_magic_free(pTHX_ SV* sv, MAGIC* mg) {
840 90 50         if (mg->mg_ptr) {
841 90           TreeRBXS_item_detach_owner((struct TreeRBXS_item*) mg->mg_ptr);
842 90           mg->mg_ptr= NULL;
843             }
844 90           return 0;
845             }
846              
847             // magic table for Tree::RB::XS::Node
848             static MGVTBL TreeRBXS_item_magic_vt= {
849             0, /* get */
850             0, /* write */
851             0, /* length */
852             0, /* clear */
853             TreeRBXS_item_magic_free,
854             0, /* copy */
855             TreeRBXS_magic_dup
856             #ifdef MGf_LOCAL
857             ,0
858             #endif
859             };
860              
861             // destructor for Tree::RB::XS::Iter
862 229           static int TreeRBXS_iter_magic_free(pTHX_ SV* sv, MAGIC *mg) {
863 229 50         if (mg->mg_ptr)
864 229           TreeRBXS_iter_free((struct TreeRBXS_iter*) mg->mg_ptr);
865 229           return 0;
866             }
867              
868             static MGVTBL TreeRBXS_iter_magic_vt= {
869             0, /* get */
870             0, /* write */
871             0, /* length */
872             0, /* clear */
873             TreeRBXS_iter_magic_free,
874             0, /* copy */
875             TreeRBXS_magic_dup
876             #ifdef MGf_LOCAL
877             ,0
878             #endif
879             };
880              
881             // Return the TreeRBXS struct attached to a Perl object via MAGIC.
882             // The 'obj' should be a reference to a blessed SV.
883             // Use AUTOCREATE to attach magic and allocate a struct if it wasn't present.
884             // Use OR_DIE for a built-in croak() if the return value would be NULL.
885 470896           static struct TreeRBXS* TreeRBXS_get_magic_tree(SV *obj, int flags) {
886             SV *sv;
887             MAGIC* magic;
888             struct TreeRBXS *tree;
889 470896 50         if (!sv_isobject(obj)) {
890 0 0         if (flags & OR_DIE)
891 0           croak("Not an object");
892 0           return NULL;
893             }
894 470896           sv= SvRV(obj);
895 470896 100         if (SvMAGICAL(sv)) {
896             /* Iterate magic attached to this scalar, looking for one with our vtable */
897 470851 50         for (magic= SvMAGIC(sv); magic; magic = magic->mg_moremagic)
898 470851 50         if (magic->mg_type == PERL_MAGIC_ext && magic->mg_virtual == &TreeRBXS_magic_vt)
    50          
899             /* If found, the mg_ptr points to the fields structure. */
900 470851           return (struct TreeRBXS*) magic->mg_ptr;
901             }
902 45 50         if (flags & AUTOCREATE) {
903 45           Newxz(tree, 1, struct TreeRBXS);
904 45           magic= sv_magicext(sv, NULL, PERL_MAGIC_ext, &TreeRBXS_magic_vt, (const char*) tree, 0);
905             #ifdef USE_ITHREADS
906             magic->mg_flags |= MGf_DUP;
907             #endif
908 45           rbtree_init_tree(&tree->root_sentinel, &tree->leaf_sentinel);
909 45           tree->owner= sv;
910 45           return tree;
911             }
912 0 0         else if (flags & OR_DIE)
913 0           croak("Object lacks 'struct TreeRBXS' magic");
914 0           return NULL;
915             }
916              
917             // Return the TreeRBXS_item that was attached to a perl object via MAGIC.
918             // The 'obj' should be a reference to a blessed magical SV.
919 409           static struct TreeRBXS_item* TreeRBXS_get_magic_item(SV *obj, int flags) {
920             SV *sv;
921             MAGIC* magic;
922              
923 409 100         if (!sv_isobject(obj)) {
924 19 50         if (flags & OR_DIE)
925 0           croak("Not an object");
926 19           return NULL;
927             }
928 390           sv= SvRV(obj);
929 390 50         if (SvMAGICAL(sv)) {
930             /* Iterate magic attached to this scalar, looking for one with our vtable */
931 604 100         for (magic= SvMAGIC(sv); magic; magic = magic->mg_moremagic)
932 390 50         if (magic->mg_type == PERL_MAGIC_ext && magic->mg_virtual == &TreeRBXS_item_magic_vt)
    100          
933             /* If found, the mg_ptr points to the fields structure. */
934 176           return (struct TreeRBXS_item*) magic->mg_ptr;
935             }
936 214 50         if (flags & OR_DIE)
937 0           croak("Object lacks 'struct TreeRBXS_item' magic");
938 214           return NULL;
939             }
940              
941             // Return existing Node object, or create a new one.
942             // Returned SV is a reference with active refcount, which is what the typemap
943             // wants for returning a "struct TreeRBXS_item*" to perl-land
944 128           static SV* TreeRBXS_wrap_item(struct TreeRBXS_item *item) {
945             SV *obj;
946             MAGIC *magic;
947             // Since this is used in typemap, handle NULL gracefully
948 128 100         if (!item)
949 30           return &PL_sv_undef;
950             // If there is already a node object, return a new reference to it.
951 98 100         if (item->owner)
952 8           return newRV_inc(item->owner);
953             // else create a node object
954 90           item->owner= newSV(0);
955 90           obj= newRV_noinc(item->owner);
956 90           sv_bless(obj, gv_stashpv("Tree::RB::XS::Node", GV_ADD));
957 90           magic= sv_magicext(item->owner, NULL, PERL_MAGIC_ext, &TreeRBXS_item_magic_vt, (const char*) item, 0);
958             #ifdef USE_ITHREADS
959             magic->mg_flags |= MGf_DUP;
960             #else
961             (void)magic; // suppress warning
962             #endif
963 90           return obj;
964             }
965              
966 113           static SV* TreeRBXS_item_wrap_key(struct TreeRBXS_item *item) {
967 113 100         if (!item)
968 7           return &PL_sv_undef;
969 106           switch (item->key_type) {
970             case KEY_TYPE_ANY:
971 83           case KEY_TYPE_CLAIM: return SvREFCNT_inc(item->keyunion.svkey);
972 19           case KEY_TYPE_INT: return newSViv(item->keyunion.ikey);
973 1           case KEY_TYPE_FLOAT: return newSVnv(item->keyunion.nkey);
974 1           case KEY_TYPE_USTR: return newSVpvn_flags(item->keyunion.ckey, item->ckeylen, SVf_UTF8);
975 2           case KEY_TYPE_BSTR: return newSVpvn(item->keyunion.ckey, item->ckeylen);
976 0           default: croak("BUG: un-handled key_type");
977             }
978             }
979              
980             // Can't figure out how to create new CV instances on the fly...
981             /*
982             static SV* TreeRBXS_wrap_iter(pTHX_ struct TreeRBXS_iter *iter) {
983             SV *obj;
984             CV *iter_next_cv;
985             MAGIC *magic;
986             // Since this is used in typemap, handle NULL gracefully
987             if (!iter)
988             return &PL_sv_undef;
989             // If there is already a node object, return a new reference to it.
990             if (iter->owner)
991             return newRV_inc(iter->owner);
992             // else create an iterator
993             iter_next_cv= get_cv("Tree::RB::XS::Iter::next", 0);
994             if (!iter_next_cv) croak("BUG: can't find Iter->next");
995             obj= newRV_noinc((SV*)cv_clone(iter_next_cv));
996             sv_bless(obj, gv_stashpv("Tree::RB::XS::Iter", GV_ADD));
997             magic= sv_magicext(SvRV(obj), NULL, PERL_MAGIC_ext, &TreeRBXS_iter_magic_vt, (const char*) iter, 0);
998             #ifdef USE_ITHREADS
999             magic->mg_flags |= MGf_DUP;
1000             #else
1001             (void)magic; // suppress warning
1002             #endif
1003             return obj;
1004             }
1005             */
1006              
1007             // Return the TreeRBXS_iter struct attached to a Perl object via MAGIC.
1008             // The 'obj' should be a reference to a blessed SV.
1009             // Use AUTOCREATE to attach magic and allocate a struct if it wasn't present.
1010             // Use OR_DIE for a built-in croak() if the return value would be NULL.
1011 2044           static struct TreeRBXS_iter* TreeRBXS_get_magic_iter(SV *obj, int flags) {
1012             SV *sv;
1013             MAGIC* magic;
1014             struct TreeRBXS_iter *iter;
1015 2044 50         if (!sv_isobject(obj)) {
1016 0 0         if (flags & OR_DIE)
1017 0           croak("Not an object");
1018 0           return NULL;
1019             }
1020 2044           sv= SvRV(obj);
1021 2044 50         if (SvMAGICAL(sv)) {
1022             /* Iterate magic attached to this scalar, looking for one with our vtable */
1023 2502 100         for (magic= SvMAGIC(sv); magic; magic = magic->mg_moremagic)
1024 2044 100         if (magic->mg_type == PERL_MAGIC_ext && magic->mg_virtual == &TreeRBXS_iter_magic_vt)
    100          
1025             /* If found, the mg_ptr points to the fields structure. */
1026 1586           return (struct TreeRBXS_iter*) magic->mg_ptr;
1027             }
1028 458 100         if (flags & AUTOCREATE) {
1029 229           Newxz(iter, 1, struct TreeRBXS_iter);
1030 229           magic= sv_magicext(sv, NULL, PERL_MAGIC_ext, &TreeRBXS_iter_magic_vt, (const char*) iter, 0);
1031             #ifdef USE_ITHREADS
1032             magic->mg_flags |= MGf_DUP;
1033             #endif
1034 229           iter->owner= sv;
1035 229           return iter;
1036             }
1037 229 50         else if (flags & OR_DIE)
1038 0           croak("Object lacks 'struct TreeRBXS_iter' magic");
1039 229           return NULL;
1040             }
1041              
1042             /*----------------------------------------------------------------------------
1043             * Tree Methods
1044             */
1045              
1046             MODULE = Tree::RB::XS PACKAGE = Tree::RB::XS
1047              
1048             void
1049             _init_tree(obj, key_type_sv, compare_fn)
1050             SV *obj
1051             SV *key_type_sv;
1052             SV *compare_fn;
1053             INIT:
1054             struct TreeRBXS *tree;
1055             int key_type;
1056 45           int cmp_id= 0;
1057             PPCODE:
1058             // Must be called on a blessed hashref
1059 45 50         if (!sv_isobject(obj) || SvTYPE(SvRV(obj)) != SVt_PVHV)
    50          
1060 0           croak("_init_tree called on non-object");
1061            
1062             // parse key type and compare_fn
1063 45 100         key_type= SvOK(key_type_sv)? parse_key_type(key_type_sv) : 0;
    50          
    50          
1064 45 50         if (key_type < 0)
1065 0 0         croak("invalid key_type %s", SvPV_nolen(key_type_sv));
1066            
1067 45 100         if (SvOK(compare_fn)) {
    50          
    50          
1068 7           cmp_id= parse_cmp_fn(compare_fn);
1069 7 50         if (cmp_id < 0)
1070 0 0         croak("invalid compare_fn %s", SvPV_nolen(compare_fn));
1071             } else {
1072 38           cmp_id= key_type == KEY_TYPE_INT? CMP_INT
1073 63 100         : key_type == KEY_TYPE_FLOAT? CMP_FLOAT
1074 45 100         : key_type == KEY_TYPE_BSTR? CMP_MEMCMP
1075 34 100         : key_type == KEY_TYPE_USTR? CMP_UTF8
1076 14 100         : key_type == KEY_TYPE_ANY? CMP_PERL /* use Perl's cmp operator */
1077             : key_type == KEY_TYPE_CLAIM? CMP_PERL
1078             : CMP_PERL;
1079             }
1080 45           tree= TreeRBXS_get_magic_tree(obj, AUTOCREATE|OR_DIE);
1081 45 50         if (tree->owner != SvRV(obj))
1082 0           croak("Tree is already initialized");
1083            
1084 45           tree->owner= SvRV(obj);
1085 45           tree->compare_fn_id= cmp_id;
1086 45           switch (cmp_id) {
1087             case CMP_SUB:
1088 4           tree->compare_callback= compare_fn;
1089 4           SvREFCNT_inc(tree->compare_callback);
1090 4 50         tree->key_type= key_type == KEY_TYPE_CLAIM? key_type : KEY_TYPE_ANY;
1091 4           tree->compare= TreeRBXS_cmp_perl_cb;
1092 4           break;
1093             case CMP_UTF8:
1094 3           tree->key_type= KEY_TYPE_USTR;
1095 3           tree->compare= TreeRBXS_cmp_memcmp;
1096 3           break;
1097             case CMP_PERL:
1098 11 100         tree->key_type= key_type == KEY_TYPE_CLAIM? key_type : KEY_TYPE_ANY;
1099 11           tree->compare= TreeRBXS_cmp_perl;
1100 11           break;
1101             case CMP_INT:
1102 13           tree->key_type= KEY_TYPE_INT;
1103 13           tree->compare= TreeRBXS_cmp_int;
1104 13           break;
1105             case CMP_FLOAT:
1106 5           tree->key_type= KEY_TYPE_FLOAT;
1107 5           tree->compare= TreeRBXS_cmp_float;
1108 5           break;
1109             case CMP_MEMCMP:
1110 6           tree->key_type= KEY_TYPE_BSTR;
1111 6           tree->compare= TreeRBXS_cmp_memcmp;
1112 6           break;
1113             case CMP_NUMSPLIT:
1114 2 100         tree->key_type= key_type == KEY_TYPE_BSTR || key_type == KEY_TYPE_USTR
1115 5 100         || key_type == KEY_TYPE_ANY || key_type == KEY_TYPE_CLAIM? key_type : KEY_TYPE_BSTR;
    50          
    0          
1116 3           tree->compare= TreeRBXS_cmp_numsplit;
1117 3           break;
1118             default:
1119 0           croak("BUG: unhandled cmp_id");
1120             }
1121 45           XSRETURN(1);
1122              
1123             void
1124             _assert_structure(tree)
1125             struct TreeRBXS *tree
1126             CODE:
1127 15           TreeRBXS_assert_structure(tree);
1128              
1129             void
1130             key_type(tree)
1131             struct TreeRBXS *tree
1132             INIT:
1133 16           int kt= tree->key_type;
1134             PPCODE:
1135 16           ST(0)= sv_2mortal(new_enum_dualvar(kt, newSVpv(get_key_type_name(kt), 0)));
1136 16           XSRETURN(1);
1137              
1138             void
1139             compare_fn(tree)
1140             struct TreeRBXS *tree
1141             INIT:
1142 9           int id= tree->compare_fn_id;
1143             PPCODE:
1144 18           ST(0)= id == CMP_SUB? tree->compare_callback
1145 9 100         : sv_2mortal(new_enum_dualvar(id, newSVpv(get_cmp_name(id), 0)));
1146 9           XSRETURN(1);
1147              
1148             void
1149             allow_duplicates(tree, allow= NULL)
1150             struct TreeRBXS *tree
1151             SV* allow
1152             PPCODE:
1153 11 100         if (items > 1) {
1154 5 50         tree->allow_duplicates= SvTRUE(allow);
    50          
    0          
    50          
    0          
    0          
    50          
    0          
    0          
    0          
    0          
    0          
    50          
    50          
    50          
    0          
    0          
    50          
    0          
1155             // ST(0) is $self, so let it be the return value
1156             } else {
1157 6           ST(0)= sv_2mortal(newSViv(tree->allow_duplicates? 1 : 0));
1158             }
1159 11           XSRETURN(1);
1160              
1161             void
1162             compat_list_get(tree, allow= NULL)
1163             struct TreeRBXS *tree
1164             SV* allow
1165             PPCODE:
1166 0 0         if (items > 1) {
1167 0 0         tree->compat_list_get= SvTRUE(allow);
    0          
    0          
    0          
    0          
    0          
    0          
    0          
    0          
    0          
    0          
    0          
    0          
    0          
    0          
    0          
    0          
    0          
    0          
1168             // ST(0) is $self, so let it be the return value
1169             } else {
1170 0           ST(0)= sv_2mortal(newSViv(tree->compat_list_get? 1 : 0));
1171             }
1172 0           XSRETURN(1);
1173              
1174             IV
1175             size(tree)
1176             struct TreeRBXS *tree
1177             CODE:
1178 35           RETVAL= TreeRBXS_get_count(tree);
1179             OUTPUT:
1180             RETVAL
1181              
1182             IV
1183             insert(tree, key, val)
1184             struct TreeRBXS *tree
1185             SV *key
1186             SV *val
1187             INIT:
1188             struct TreeRBXS_item stack_item, *item;
1189 70094           rbtree_node_t *hint= NULL;
1190 70094           int cmp= 0;
1191             CODE:
1192             //TreeRBXS_assert_structure(tree);
1193 70094 50         if (!SvOK(key))
    0          
    0          
1194 0           croak("Can't use undef as a key");
1195 70094           TreeRBXS_init_tmp_item(&stack_item, tree, key, val);
1196             /* check for duplicates, unless they are allowed */
1197             //warn("Insert %p into %p", item, tree);
1198 70094 100         if (!tree->allow_duplicates) {
1199 70000           hint= rbtree_find_nearest(
1200             &tree->root_sentinel,
1201             &stack_item, // The item *is* the key that gets passed to the compare function
1202 70000           (int(*)(void*,void*,void*)) tree->compare,
1203             tree, -OFS_TreeRBXS_item_FIELD_rbnode,
1204             &cmp);
1205             }
1206 70094 100         if (hint && cmp == 0) {
    50          
1207 0           RETVAL= -1;
1208             } else {
1209 70094           item= TreeRBXS_new_item_from_tmp_item(&stack_item);
1210 70094 100         if (!rbtree_node_insert(
    50          
1211             hint? hint : &tree->root_sentinel,
1212             &item->rbnode,
1213 70094           (int(*)(void*,void*,void*)) tree->compare,
1214             tree, -OFS_TreeRBXS_item_FIELD_rbnode
1215             )) {
1216 0           TreeRBXS_item_free(item);
1217 0           croak("BUG: insert failed");
1218             }
1219 70094           RETVAL= rbtree_node_index(&item->rbnode);
1220             }
1221             //TreeRBXS_assert_structure(tree);
1222             OUTPUT:
1223             RETVAL
1224              
1225             void
1226             put(tree, key, val)
1227             struct TreeRBXS *tree
1228             SV *key
1229             SV *val
1230             INIT:
1231             struct TreeRBXS_item stack_item, *item;
1232 400129           rbtree_node_t *first= NULL, *last= NULL;
1233             size_t count;
1234             PPCODE:
1235 400129 50         if (!SvOK(key))
    0          
    0          
1236 0           croak("Can't use undef as a key");
1237 400129           TreeRBXS_init_tmp_item(&stack_item, tree, key, val);
1238 400129           ST(0)= &PL_sv_undef;
1239 400129 100         if (rbtree_find_all(
1240             &tree->root_sentinel,
1241             &stack_item, // The item *is* the key that gets passed to the compare function
1242 400129           (int(*)(void*,void*,void*)) tree->compare,
1243             tree, -OFS_TreeRBXS_item_FIELD_rbnode,
1244             &first, &last, &count)
1245             ) {
1246             //warn("replacing %d matching keys with new value", (int)count);
1247             // prune every node that follows 'first'
1248 11 50         while (last != first) {
1249 0           item= GET_TreeRBXS_item_FROM_rbnode(last);
1250 0           last= rbtree_node_prev(last);
1251 0           rbtree_node_prune(&item->rbnode);
1252 0           TreeRBXS_item_detach_tree(item, tree);
1253             }
1254             /* overwrite the value of the node */
1255 11           item= GET_TreeRBXS_item_FROM_rbnode(first);
1256 11           val= newSVsv(val);
1257 11           ST(0)= sv_2mortal(item->value); // return the old value
1258 11           item->value= val; // sore new copy of supplied param
1259             }
1260             else {
1261 400118           item= TreeRBXS_new_item_from_tmp_item(&stack_item);
1262 400147 100         if (!rbtree_node_insert(
    50          
1263 29 100         first? first : last? last : &tree->root_sentinel,
1264             &item->rbnode,
1265 400118           (int(*)(void*,void*,void*)) tree->compare,
1266             tree, -OFS_TreeRBXS_item_FIELD_rbnode
1267             )) {
1268 0           TreeRBXS_item_free(item);
1269 0           croak("BUG: insert failed");
1270             }
1271             }
1272 400129           XSRETURN(1);
1273              
1274             void
1275             EXISTS(tree, key)
1276             struct TreeRBXS *tree
1277             SV *key
1278             INIT:
1279             struct TreeRBXS_item stack_item;
1280 0           rbtree_node_t *node= NULL;
1281             int cmp;
1282             PPCODE:
1283 0 0         if (!SvOK(key))
    0          
    0          
1284 0           croak("Can't use undef as a key");
1285             // create a fake item to act as a search key
1286 0           TreeRBXS_init_tmp_item(&stack_item, tree, key, &PL_sv_undef);
1287 0           node= rbtree_find_nearest(
1288             &tree->root_sentinel,
1289             &stack_item,
1290 0           (int(*)(void*,void*,void*)) tree->compare,
1291             tree, -OFS_TreeRBXS_item_FIELD_rbnode,
1292             &cmp);
1293 0 0         ST(0)= (node && cmp == 0)? &PL_sv_yes : &PL_sv_no;
    0          
1294 0           XSRETURN(1);
1295              
1296             void
1297             get(tree, key, mode_sv= NULL)
1298             struct TreeRBXS *tree
1299             SV *key
1300             SV *mode_sv
1301             ALIAS:
1302             Tree::RB::XS::lookup = 0
1303             Tree::RB::XS::get = 1
1304             Tree::RB::XS::get_node = 2
1305             Tree::RB::XS::get_node_last = 3
1306             Tree::RB::XS::get_node_le = 4
1307             Tree::RB::XS::get_node_le_last = 5
1308             Tree::RB::XS::get_node_lt = 6
1309             Tree::RB::XS::get_node_gt = 7
1310             Tree::RB::XS::get_node_ge = 8
1311             Tree::RB::XS::FETCH = 9
1312             INIT:
1313             struct TreeRBXS_item stack_item, *item;
1314 250           int mode= 0;
1315             PPCODE:
1316 250 50         if (!SvOK(key))
    0          
    0          
1317 0           croak("Can't use undef as a key");
1318 250           switch (ix) {
1319             // In "full compatibility mode", 'get' is identical to 'lookup'
1320             case 1:
1321 202 50         if (tree->compat_list_get) {
1322 0           ix= 0;
1323             // In scalar context, lookup is identical to 'get'
1324 21 50         case 0: if (GIMME_V == G_SCALAR) ix= 1;
    50          
1325             }
1326             case 2:
1327 237 100         mode= mode_sv? parse_lookup_mode(mode_sv) : GET_EQ;
1328 237 50         if (mode < 0)
1329 0 0         croak("Invalid lookup mode %s", SvPV_nolen(mode_sv));
1330 237           break;
1331 0           case 3: mode= GET_EQ_LAST; if (0)
1332 0           case 4: mode= GET_LE; if (0)
1333 0           case 5: mode= GET_LE_LAST; if (0)
1334 0           case 6: mode= GET_LT; if (0)
1335 0           case 7: mode= GET_GT; if (0)
1336 0           case 8: mode= GET_GE;
1337 0 0         if (mode_sv) croak("extra get-mode argument");
1338 0           ix= 2;
1339 0           break;
1340 13           case 9: ix= 1; break; // FETCH should always return a single value
1341             }
1342             // create a fake item to act as a search key
1343 250           TreeRBXS_init_tmp_item(&stack_item, tree, key, &PL_sv_undef);
1344 250           item= TreeRBXS_find_item(tree, &stack_item, mode);
1345 250 100         if (item) {
1346 245 50         if (ix == 0) { // lookup in list context
1347 0           ST(0)= item->value;
1348 0           ST(1)= sv_2mortal(TreeRBXS_wrap_item(item));
1349 0           XSRETURN(2);
1350 245 100         } else if (ix == 1) { // get, or lookup in scalar context
1351 231           ST(0)= item->value;
1352 231           XSRETURN(1);
1353             } else { // get_node
1354 14           ST(0)= sv_2mortal(TreeRBXS_wrap_item(item));
1355 14           XSRETURN(1);
1356             }
1357             } else {
1358 5 50         if (ix == 0) { // lookup in list context
1359 0           XSRETURN(0);
1360             }
1361             else {
1362 5           ST(0)= &PL_sv_undef;
1363 250           XSRETURN(1);
1364             }
1365             }
1366              
1367             void
1368             get_all(tree, key)
1369             struct TreeRBXS *tree
1370             SV *key
1371             INIT:
1372             struct TreeRBXS_item stack_item, *item;
1373             rbtree_node_t *first;
1374             size_t count, i;
1375             PPCODE:
1376 1 50         if (!SvOK(key))
    0          
    0          
1377 0           croak("Can't use undef as a key");
1378 1           TreeRBXS_init_tmp_item(&stack_item, tree, key, &PL_sv_undef);
1379 1 50         if (rbtree_find_all(
1380             &tree->root_sentinel,
1381             &stack_item,
1382 1           (int(*)(void*,void*,void*)) tree->compare,
1383             tree, -OFS_TreeRBXS_item_FIELD_rbnode,
1384             &first, NULL, &count)
1385             ) {
1386 1 50         EXTEND(SP, count);
1387 7 100         for (i= 0; i < count; i++) {
1388 6           item= GET_TreeRBXS_item_FROM_rbnode(first);
1389 6           ST(i)= item->value;
1390 6           first= rbtree_node_next(first);
1391             }
1392             } else
1393 0           count= 0;
1394 1           XSRETURN(count);
1395              
1396             IV
1397             delete(tree, key1, key2= NULL)
1398             struct TreeRBXS *tree
1399             SV *key1
1400             SV *key2
1401             INIT:
1402             struct TreeRBXS_item stack_item, *item;
1403             rbtree_node_t *first, *last, *node;
1404             size_t count, i;
1405             CODE:
1406 15 50         if (!SvOK(key1))
    0          
    0          
1407 0           croak("Can't use undef as a key");
1408 15           RETVAL= 0;
1409 15 50         if ((item= TreeRBXS_get_magic_item(key1, 0))) {
1410 0           first= &item->rbnode;
1411             // verify it comes from this tree
1412 0 0         for (node= first; rbtree_node_is_in_tree(node) && node->parent; node= node->parent);
    0          
1413 0 0         if (node != &tree->root_sentinel)
1414 0           croak("Node is not in tree");
1415             }
1416             else {
1417 15           TreeRBXS_init_tmp_item(&stack_item, tree, key1, &PL_sv_undef);
1418 15 100         if (rbtree_find_all(
1419             &tree->root_sentinel,
1420             &stack_item,
1421 15           (int(*)(void*,void*,void*)) tree->compare,
1422             tree, -OFS_TreeRBXS_item_FIELD_rbnode,
1423             &first, &last, &count)
1424             ) {
1425 12 100         if (key2)
1426 12           last= NULL;
1427             }
1428             else {
1429             // Didn't find any matches. But if range is given, then start deleting
1430             // from the node following the key
1431 3 100         if (key2) {
1432 2           first= last;
1433 2           last= NULL;
1434             }
1435             }
1436             }
1437             // If a range is given, and the first part of the range found a node,
1438             // look for the end of the range.
1439 15 100         if (key2 && first) {
    50          
1440 3 50         if ((item= TreeRBXS_get_magic_item(key2, 0))) {
1441 0           last= &item->rbnode;
1442             // verify it comes from this tree
1443 0 0         for (node= last; rbtree_node_is_in_tree(node) && node->parent; node= node->parent);
    0          
1444 0 0         if (node != &tree->root_sentinel)
1445 0           croak("Node is not in tree");
1446             }
1447             else {
1448 3           TreeRBXS_init_tmp_item(&stack_item, tree, key2, &PL_sv_undef);
1449 3 100         if (rbtree_find_all(
1450             &tree->root_sentinel,
1451             &stack_item,
1452 3           (int(*)(void*,void*,void*)) tree->compare,
1453             tree, -OFS_TreeRBXS_item_FIELD_rbnode,
1454             &node, &last, NULL)
1455             ) {
1456             // first..last is ready to be deleted
1457             } else {
1458             // didn't match, so 'node' holds the final element before the key
1459 2           last= node;
1460             }
1461             }
1462             // Ensure that first comes before last
1463 3 50         if (last && rbtree_node_index(first) > rbtree_node_index(last))
    100          
1464 1           last= NULL;
1465             }
1466             // Delete the nodes if constructed a successful range
1467 15           i= 0;
1468 15 50         if (first && last) {
    100          
1469             do {
1470 16           item= GET_TreeRBXS_item_FROM_rbnode(first);
1471 16 100         first= (first == last)? NULL : rbtree_node_next(first);
1472 16           TreeRBXS_item_detach_tree(item, tree);
1473 16           ++i;
1474 16 100         } while (first);
1475             }
1476 15           RETVAL= i;
1477             OUTPUT:
1478             RETVAL
1479              
1480             IV
1481             clear(tree)
1482             struct TreeRBXS *tree
1483             CODE:
1484 0           RETVAL= TreeRBXS_get_count(tree);
1485 0           rbtree_clear(&tree->root_sentinel, (void (*)(void *, void *)) &TreeRBXS_item_detach_tree,
1486             -OFS_TreeRBXS_item_FIELD_rbnode, tree);
1487             OUTPUT:
1488             RETVAL
1489              
1490             struct TreeRBXS_item *
1491             min_node(tree)
1492             struct TreeRBXS *tree
1493             INIT:
1494 17           rbtree_node_t *node= rbtree_node_left_leaf(TreeRBXS_get_root(tree));
1495             CODE:
1496 17 50         RETVAL= node? GET_TreeRBXS_item_FROM_rbnode(node) : NULL;
1497             OUTPUT:
1498             RETVAL
1499              
1500             struct TreeRBXS_item *
1501             max_node(tree)
1502             struct TreeRBXS *tree
1503             INIT:
1504 3           rbtree_node_t *node= rbtree_node_right_leaf(TreeRBXS_get_root(tree));
1505             CODE:
1506 3 50         RETVAL= node? GET_TreeRBXS_item_FROM_rbnode(node) : NULL;
1507             OUTPUT:
1508             RETVAL
1509              
1510             struct TreeRBXS_item *
1511             nth_node(tree, ofs)
1512             struct TreeRBXS *tree
1513             IV ofs
1514             INIT:
1515             rbtree_node_t *node;
1516             CODE:
1517 7 100         if (ofs < 0) ofs += TreeRBXS_get_count(tree);
1518 7           node= rbtree_node_child_at_index(TreeRBXS_get_root(tree), ofs);
1519 7 100         RETVAL= node? GET_TreeRBXS_item_FROM_rbnode(node) : NULL;
1520             OUTPUT:
1521             RETVAL
1522              
1523             struct TreeRBXS_item *
1524             root_node(tree)
1525             struct TreeRBXS *tree
1526             CODE:
1527 8           RETVAL= !TreeRBXS_get_count(tree)? NULL
1528 4 50         : GET_TreeRBXS_item_FROM_rbnode(TreeRBXS_get_root(tree));
1529             OUTPUT:
1530             RETVAL
1531              
1532             SV *
1533             FIRSTKEY(tree)
1534             struct TreeRBXS *tree
1535             INIT:
1536 6           struct TreeRBXS_iter *iter= TreeRBXS_get_hashiter(tree);
1537             rbtree_node_t *node;
1538             CODE:
1539 6 100         if (tree->hashiterset)
1540 1           tree->hashiterset= false; // iter has 'hseek' applied, don't change it
1541             else
1542 5           TreeRBXS_iter_rewind(iter);
1543 6           RETVAL= TreeRBXS_item_wrap_key(iter->item); // handles null by returning undef
1544             OUTPUT:
1545             RETVAL
1546              
1547             SV *
1548             NEXTKEY(tree, lastkey)
1549             struct TreeRBXS *tree
1550             SV *lastkey
1551             INIT:
1552 19           struct TreeRBXS_iter *iter= TreeRBXS_get_hashiter(tree);
1553             CODE:
1554 19 100         if (tree->hashiterset)
1555 2           tree->hashiterset= false; // iter has 'hseek' applied, don't change it
1556             else
1557 17           TreeRBXS_iter_advance(iter, 1);
1558 19           RETVAL= TreeRBXS_item_wrap_key(iter->item);
1559             (void)lastkey;
1560             OUTPUT:
1561             RETVAL
1562              
1563             void
1564             _set_hashiter(tree, item_sv, reverse)
1565             struct TreeRBXS *tree
1566             SV *item_sv
1567             bool reverse
1568             INIT:
1569 3           struct TreeRBXS_item *item= TreeRBXS_get_magic_item(item_sv, 0);
1570 3           struct TreeRBXS_iter *iter= TreeRBXS_get_hashiter(tree);
1571             PPCODE:
1572 3 100         if (item && (TreeRBXS_item_get_tree(item) != tree))
    50          
1573 0           croak("Node is not part of this tree");
1574 3           iter->reverse= reverse;
1575 3           TreeRBXS_iter_set_item(iter, item);
1576 3 100         if (!item) TreeRBXS_iter_rewind(iter);
1577 3           tree->hashiterset= true;
1578 3           XSRETURN(0);
1579              
1580             SV *
1581             SCALAR(tree)
1582             struct TreeRBXS *tree
1583             CODE:
1584 2           RETVAL= newSViv(TreeRBXS_get_count(tree));
1585             OUTPUT:
1586             RETVAL
1587              
1588             void
1589             DELETE(tree, key)
1590             struct TreeRBXS *tree
1591             SV *key
1592             INIT:
1593             struct TreeRBXS_item stack_item, *item;
1594             rbtree_node_t *first, *last;
1595             PPCODE:
1596 1 50         if (!SvOK(key))
    0          
    0          
1597 0           croak("Can't use undef as a key");
1598 1           TreeRBXS_init_tmp_item(&stack_item, tree, key, &PL_sv_undef);
1599 1 50         if (rbtree_find_all(
1600             &tree->root_sentinel,
1601             &stack_item,
1602 1           (int(*)(void*,void*,void*)) tree->compare,
1603             tree, -OFS_TreeRBXS_item_FIELD_rbnode,
1604             &first, &last, NULL)
1605             ) {
1606 1           ST(0)= sv_2mortal(SvREFCNT_inc(GET_TreeRBXS_item_FROM_rbnode(first)->value));
1607             do {
1608 1           item= GET_TreeRBXS_item_FROM_rbnode(first);
1609 1 50         first= (first == last)? NULL : rbtree_node_next(first);
1610 1           TreeRBXS_item_detach_tree(item, tree);
1611 1 50         } while (first);
1612             } else {
1613 0           ST(0)= &PL_sv_undef;
1614             }
1615 1           XSRETURN(1);
1616              
1617             #-----------------------------------------------------------------------------
1618             # Node Methods
1619             #
1620              
1621             MODULE = Tree::RB::XS PACKAGE = Tree::RB::XS::Node
1622              
1623             SV *
1624             key(item)
1625             struct TreeRBXS_item *item
1626             CODE:
1627 53           RETVAL= TreeRBXS_item_wrap_key(item);
1628             OUTPUT:
1629             RETVAL
1630              
1631             SV *
1632             value(item, newval=NULL)
1633             struct TreeRBXS_item *item
1634             SV *newval;
1635             CODE:
1636 19 50         if (newval)
1637 0           sv_setsv(item->value, newval);
1638 19           RETVAL= SvREFCNT_inc_simple_NN(item->value);
1639             OUTPUT:
1640             RETVAL
1641              
1642             IV
1643             index(item)
1644             struct TreeRBXS_item *item
1645             CODE:
1646 0           RETVAL= rbtree_node_index(&item->rbnode);
1647             OUTPUT:
1648             RETVAL
1649              
1650             struct TreeRBXS_item *
1651             prev(item)
1652             struct TreeRBXS_item *item
1653             INIT:
1654 4           rbtree_node_t *node= rbtree_node_prev(&item->rbnode);
1655             CODE:
1656 4 100         RETVAL= node? GET_TreeRBXS_item_FROM_rbnode(node) : NULL;
1657             OUTPUT:
1658             RETVAL
1659              
1660             struct TreeRBXS_item *
1661             next(item)
1662             struct TreeRBXS_item *item
1663             INIT:
1664 51           rbtree_node_t *node= rbtree_node_next(&item->rbnode);
1665             CODE:
1666 51 100         RETVAL= node? GET_TreeRBXS_item_FROM_rbnode(node) : NULL;
1667             OUTPUT:
1668             RETVAL
1669              
1670             struct TreeRBXS_item *
1671             parent(item)
1672             struct TreeRBXS_item *item
1673             CODE:
1674 1 50         RETVAL= rbtree_node_is_in_tree(&item->rbnode) && item->rbnode.parent->count?
1675 3 100         GET_TreeRBXS_item_FROM_rbnode(item->rbnode.parent) : NULL;
1676             OUTPUT:
1677             RETVAL
1678              
1679             void
1680             tree(item)
1681             struct TreeRBXS_item *item
1682             INIT:
1683 1           struct TreeRBXS *tree= TreeRBXS_item_get_tree(item);
1684             PPCODE:
1685 1 50         ST(0)= tree && tree->owner? sv_2mortal(newRV_inc(tree->owner)) : &PL_sv_undef;
    0          
1686 1           XSRETURN(1);
1687              
1688             struct TreeRBXS_item *
1689             left(item)
1690             struct TreeRBXS_item *item
1691             CODE:
1692 6 100         RETVAL= rbtree_node_is_in_tree(&item->rbnode) && item->rbnode.left->count?
1693 13 100         GET_TreeRBXS_item_FROM_rbnode(item->rbnode.left) : NULL;
1694             OUTPUT:
1695             RETVAL
1696              
1697             struct TreeRBXS_item *
1698             right(item)
1699             struct TreeRBXS_item *item
1700             CODE:
1701 6 100         RETVAL= rbtree_node_is_in_tree(&item->rbnode) && item->rbnode.right->count?
1702 13 100         GET_TreeRBXS_item_FROM_rbnode(item->rbnode.right) : NULL;
1703             OUTPUT:
1704             RETVAL
1705              
1706             struct TreeRBXS_item *
1707             left_leaf(item)
1708             struct TreeRBXS_item *item
1709             INIT:
1710 2           rbtree_node_t *node= rbtree_node_left_leaf(&item->rbnode);
1711             CODE:
1712 2 100         RETVAL= node? GET_TreeRBXS_item_FROM_rbnode(node) : NULL;
1713             OUTPUT:
1714             RETVAL
1715              
1716             struct TreeRBXS_item *
1717             right_leaf(item)
1718             struct TreeRBXS_item *item
1719             INIT:
1720 2           rbtree_node_t *node= rbtree_node_right_leaf(&item->rbnode);
1721             CODE:
1722 2 100         RETVAL= node? GET_TreeRBXS_item_FROM_rbnode(node) : NULL;
1723             OUTPUT:
1724             RETVAL
1725              
1726             IV
1727             color(item)
1728             struct TreeRBXS_item *item
1729             CODE:
1730 4           RETVAL= item->rbnode.color;
1731             OUTPUT:
1732             RETVAL
1733              
1734             IV
1735             count(item)
1736             struct TreeRBXS_item *item
1737             CODE:
1738 2           RETVAL= item->rbnode.count;
1739             OUTPUT:
1740             RETVAL
1741              
1742             IV
1743             prune(item)
1744             struct TreeRBXS_item *item
1745             INIT:
1746 5           struct TreeRBXS *tree= TreeRBXS_item_get_tree(item);
1747             CODE:
1748 5           RETVAL= 0;
1749 5 100         if (tree) {
1750 4           TreeRBXS_item_detach_tree(item, tree);
1751 4           RETVAL= 1;
1752             }
1753             OUTPUT:
1754             RETVAL
1755              
1756             #-----------------------------------------------------------------------------
1757             # Iterator methods
1758             #
1759              
1760             MODULE = Tree::RB::XS PACKAGE = Tree::RB::XS::Iter
1761              
1762             void
1763             _init(iter_sv, target, direction= 1)
1764             SV *iter_sv
1765             SV *target
1766             IV direction
1767             INIT:
1768 229           struct TreeRBXS_iter *iter2, *iter= TreeRBXS_get_magic_iter(iter_sv, AUTOCREATE|OR_DIE);
1769             struct TreeRBXS *tree;
1770 229           struct TreeRBXS_item *item= NULL;
1771 229           rbtree_node_t *node= NULL;
1772             PPCODE:
1773 229 50         if (iter->item || iter->tree)
    50          
1774 0           croak("Iterator is already initialized");
1775 229 100         if (!(direction == 1 || direction == -1))
    50          
1776 0           croak("Direction must be 1 or -1");
1777 229           iter->reverse= (direction == -1);
1778              
1779             // target can be a tree, a node, or another iterator
1780 229 50         if ((iter2= TreeRBXS_get_magic_iter(target, 0))) {
1781             // use this direction unless overridden
1782 0 0         if (items < 2) iter->reverse= iter2->reverse;
1783 0           tree= iter2->tree;
1784 0           item= iter2->item;
1785             }
1786 229 100         else if ((item= TreeRBXS_get_magic_item(target, 0))) {
1787 15           tree= TreeRBXS_item_get_tree(item);
1788             }
1789 214 50         else if ((tree= TreeRBXS_get_magic_tree(target, 0))) {
1790 428           node= !TreeRBXS_get_count(tree)? NULL
1791 428 50         : iter->reverse? rbtree_node_right_leaf(TreeRBXS_get_root(tree))
1792 214 100         : rbtree_node_left_leaf(TreeRBXS_get_root(tree));
1793 214 50         if (node)
1794 214           item= GET_TreeRBXS_item_FROM_rbnode(node);
1795             }
1796 229 50         if (!tree)
1797 0           croak("Can't iterate a node that isn't in the tree");
1798 229           iter->tree= tree;
1799 229 50         if (tree->owner)
1800 229           SvREFCNT_inc(tree->owner);
1801 229           TreeRBXS_iter_set_item(iter, item);
1802 229           ST(0)= iter_sv;
1803 229           XSRETURN(1);
1804              
1805             SV *
1806             key(iter)
1807             struct TreeRBXS_iter *iter
1808             CODE:
1809             // wrap_key handles NULL items
1810 16           RETVAL= TreeRBXS_item_wrap_key(iter->item);
1811             OUTPUT:
1812             RETVAL
1813              
1814             SV *
1815             value(iter)
1816             struct TreeRBXS_iter *iter
1817             CODE:
1818 25 100         RETVAL= iter->item? SvREFCNT_inc_simple_NN(iter->item->value) : &PL_sv_undef;
1819             OUTPUT:
1820             RETVAL
1821              
1822             SV *
1823             index(iter)
1824             struct TreeRBXS_iter *iter
1825             CODE:
1826 0 0         RETVAL= !iter->item || !rbtree_node_is_in_tree(&iter->item->rbnode)? &PL_sv_undef
1827 1 50         : newSViv(rbtree_node_index(&iter->item->rbnode));
1828             OUTPUT:
1829             RETVAL
1830              
1831             SV *
1832             tree(iter)
1833             struct TreeRBXS_iter *iter
1834             CODE:
1835 0 0         RETVAL= iter->tree && iter->tree->owner? newRV_inc(iter->tree->owner) : &PL_sv_undef;
    0          
1836             OUTPUT:
1837             RETVAL
1838              
1839             bool
1840             done(iter)
1841             struct TreeRBXS_iter *iter
1842             CODE:
1843 36           RETVAL= !iter->item;
1844             OUTPUT:
1845             RETVAL
1846              
1847             void
1848             next(iter, count_sv= NULL)
1849             struct TreeRBXS_iter *iter
1850             SV* count_sv
1851             ALIAS:
1852             Tree::RB::XS::Iter::next = 0
1853             Tree::RB::XS::Iter::next_keys = 1
1854             Tree::RB::XS::Iter::next_values = 2
1855             Tree::RB::XS::Iter::next_kv = 3
1856             INIT:
1857 19           size_t pos, n, nret, i, tree_count= TreeRBXS_get_count(iter->tree);
1858             IV request;
1859             rbtree_node_t *node;
1860 19 100         rbtree_node_t *(*step)(rbtree_node_t *)= iter->reverse? &rbtree_node_prev : rbtree_node_next;
1861             PPCODE:
1862 19 50         if (iter->item) {
1863 25 100         request= !count_sv? 1
    100          
    50          
1864 6 50         : SvPOK(count_sv) && *SvPV_nolen(count_sv) == '*'? tree_count
    50          
1865 14           : SvIV(count_sv);
1866 19 100         if (request < 1) {
1867 1           n= i= 0;
1868             }
1869             // A request for 1 is simpler because there is no need to count how many will be returned.
1870             // iter->item wasn't NULL so it is guaranteed to be 1.
1871 18 50         else if (GIMME_V == G_VOID) {
    50          
1872             // skip all the busywork if called in void context
1873             // (but still advance the iterator below)
1874 0           n= request;
1875 0           i= 0;
1876             }
1877 18 100         else if (request == 1) {
1878 7           n= i= 1;
1879 6           ST(0)= ix == 0? sv_2mortal(TreeRBXS_wrap_item(iter->item))
1880 14 100         : ix == 2? iter->item->value
1881 1 50         : sv_2mortal(TreeRBXS_item_wrap_key(iter->item));
1882 7 50         if (ix == 3) {
1883 0 0         EXTEND(SP, 2);
1884 7           ST(1)= iter->item->value;
1885             }
1886             }
1887             else {
1888 11           pos= rbtree_node_index(&iter->item->rbnode);
1889             // calculate how many nodes will be returned
1890 11 100         n= iter->reverse? 1 + pos : tree_count - pos;
1891 11 100         if (n > request) n= request;
1892 11           node= &iter->item->rbnode;
1893 11 100         nret= ix == 3? 2*n : n;
1894 11 50         EXTEND(SP, nret); // EXTEND macro declares a temp 'ix' internally - GitHub #2
1895 11 100         if (ix == 0) { // Return N node references
1896 3 100         for (i= 0; i < n && node; i++, node= step(node))
    50          
1897 2           ST(i)= sv_2mortal(TreeRBXS_wrap_item(GET_TreeRBXS_item_FROM_rbnode(node)));
1898             }
1899 10 100         else if (ix == 1) { // Return N keys
1900 20 100         for (i= 0; i < n && node; i++, node= step(node))
    50          
1901 16           ST(i)= sv_2mortal(TreeRBXS_item_wrap_key(GET_TreeRBXS_item_FROM_rbnode(node)));
1902             }
1903 6 100         else if (ix == 2) { // Return N values
1904 96 100         for (i= 0; i < n && node; i++, node= step(node))
    50          
1905 91           ST(i)= GET_TreeRBXS_item_FROM_rbnode(node)->value;
1906             }
1907             else { // return N (Key,Value) pairs
1908 3 100         for (i= 0; i < n && node; i++, node= step(node)) {
    50          
1909 2           ST(i*2)= sv_2mortal(TreeRBXS_item_wrap_key(GET_TreeRBXS_item_FROM_rbnode(node)));
1910 2           ST(i*2+1)= GET_TreeRBXS_item_FROM_rbnode(node)->value;
1911             }
1912             }
1913 11 50         if (i != n)
1914 0           croak("BUG: expected %ld nodes but found %ld", (long) n, (long) i);
1915             }
1916 19           TreeRBXS_iter_advance(iter, n);
1917 19 100         XSRETURN(ix == 3? 2*i : i);
1918             } else {
1919             // end of iteration, nothing to do
1920 0           ST(0)= &PL_sv_undef;
1921             // return the undef only if the user didn't specify a count
1922 0           XSRETURN(count_sv? 0 : 1);
1923             }
1924              
1925             bool
1926             step(iter, ofs= 1)
1927             struct TreeRBXS_iter *iter
1928             IV ofs
1929             CODE:
1930 1484           TreeRBXS_iter_advance(iter, ofs);
1931             // Return boolean whether the iterator points to an item
1932 1484           RETVAL= !!iter->item;
1933             OUTPUT:
1934             RETVAL
1935              
1936             void
1937             delete(iter)
1938             struct TreeRBXS_iter *iter
1939             PPCODE:
1940 5 50         if (iter->item) {
1941             // up the recnt temporarily to make sure it doesn't get lost when item gets freed
1942 5           ST(0)= sv_2mortal(SvREFCNT_inc(iter->item->value));
1943             // pruning the item automatically moves iterators to next, including this iterator.
1944 5           TreeRBXS_item_detach_tree(iter->item, iter->tree);
1945             }
1946             else
1947 0           ST(0)= &PL_sv_undef;
1948 5           XSRETURN(1);
1949              
1950             #-----------------------------------------------------------------------------
1951             # Constants
1952             #
1953              
1954             BOOT:
1955 10           HV* stash= gv_stashpvn("Tree::RB::XS", 12, 1);
1956 10           EXPORT_ENUM(KEY_TYPE_ANY);
1957 10           EXPORT_ENUM(KEY_TYPE_INT);
1958 10           EXPORT_ENUM(KEY_TYPE_FLOAT);
1959 10           EXPORT_ENUM(KEY_TYPE_USTR);
1960 10           EXPORT_ENUM(KEY_TYPE_BSTR);
1961 10           EXPORT_ENUM(KEY_TYPE_CLAIM);
1962 10           EXPORT_ENUM(CMP_PERL);
1963 10           EXPORT_ENUM(CMP_INT);
1964 10           EXPORT_ENUM(CMP_FLOAT);
1965 10           EXPORT_ENUM(CMP_UTF8);
1966 10           EXPORT_ENUM(CMP_MEMCMP);
1967 10           EXPORT_ENUM(CMP_NUMSPLIT);
1968 10           EXPORT_ENUM(GET_EQ);
1969 10           EXPORT_ENUM(GET_EQ_LAST);
1970 10           EXPORT_ENUM(GET_GE);
1971 10           EXPORT_ENUM(GET_LE);
1972 10           EXPORT_ENUM(GET_LE_LAST);
1973 10           EXPORT_ENUM(GET_GT);
1974 10           EXPORT_ENUM(GET_LT);
1975 10           EXPORT_ENUM(GET_NEXT);
1976 10           EXPORT_ENUM(GET_PREV);
1977              
1978             PROTOTYPES: DISABLE