tommytree.h
Go to the documentation of this file.
1// SPDX-License-Identifier: BSD-2-Clause
2// Copyright (C) 2015 Andrea Mazzoleni
3
125#ifndef TOMMY_TREE_H
126#define TOMMY_TREE_H
127
128#include "tommytypes.h"
129#include "tommylist.h"
130
131/******************************************************************************/
132/* tree */
133
141
146typedef struct tommy_tree_struct {
151
157tommy_inline void tommy_tree_init(tommy_tree* tree, tommy_compare_func* cmp)
158{
159 tree->root = 0;
160 tree->count = 0;
161 tree->cmp = cmp;
162}
163
173tommy_inline void tommy_tree_swap(tommy_tree* first, tommy_tree* second)
174{
175 tommy_tree tmp = *first;
176 *first = *second;
177 *second = tmp;
178}
179
189tommy_inline void tommy_tree_clear(tommy_tree* tree)
190{
191 tree->root = 0;
192 tree->count = 0;
193}
194
204TOMMY_API void tommy_tree_insert(tommy_tree* tree, tommy_tree_node* node, void* data);
205
216TOMMY_API void* tommy_tree_insert_unique(tommy_tree* tree, tommy_tree_node* node, void* data);
217
229TOMMY_API void tommy_tree_to_list(tommy_tree* tree, tommy_list* list);
230
239
246{
247 return (tommy_tree_node*)(tommy_uintptr_t)(node->index & ~(tommy_size_t)3);
248}
249
258{
259 if (node->next) {
260 node = node->next;
261 while (node->prev)
262 node = node->prev;
263 return node;
264 }
265
266 tommy_tree_node* parent = tommy_tree_parent(node);
267 while (parent && node == parent->next) {
268 node = parent;
269 parent = tommy_tree_parent(parent);
270 }
271
272 return parent;
273}
274
283{
284 if (node->prev) {
285 node = node->prev;
286 while (node->next)
287 node = node->next;
288 return node;
289 }
290
291 tommy_tree_node* parent = tommy_tree_parent(node);
292 while (parent && node == parent->prev) {
293 node = parent;
294 parent = tommy_tree_parent(parent);
295 }
296
297 return parent;
298}
299
307{
308 tommy_tree_node* node = tree->root;
309
310 if (!node)
311 return 0;
312
313 while (node->prev)
314 node = node->prev;
315
316 return node;
317}
318
326{
327 tommy_tree_node* node = tree->root;
328
329 if (!node)
330 return 0;
331
332 while (node->next)
333 node = node->next;
334
335 return node;
336}
337
344tommy_inline void* tommy_tree_remove_head(tommy_tree* tree)
345{
346 tommy_tree_node* node = tommy_tree_head(tree);
347
348 if (!node)
349 return 0;
350
351 return tommy_tree_remove_existing(tree, node);
352}
353
360tommy_inline void* tommy_tree_remove_tail(tommy_tree* tree)
361{
362 tommy_tree_node* node = tommy_tree_tail(tree);
363
364 if (!node)
365 return 0;
366
367 return tommy_tree_remove_existing(tree, node);
368}
369
384tommy_inline tommy_tree_node* tommy_tree_find_compare(tommy_tree* tree, tommy_compare_func* cmp, const void* cmp_arg)
385{
386 tommy_tree_node* node = tree->root;
387 tommy_tree_node* candidate = 0;
388
389 while (node) {
390 /* comparators must not change the tree, so retain the data across the call */
391 void* data = node->data;
392 int c = cmp(cmp_arg, data);
393
394 if (c < 0)
395 node = node->prev;
396 else if (c > 0)
397 node = node->next;
398 else {
399 candidate = node;
400 node = node->prev;
401 }
402 }
403
404 return candidate;
405}
406
414tommy_inline tommy_tree_node* tommy_tree_find(tommy_tree* tree, const void* data)
415{
416 return tommy_tree_find_compare(tree, tree->cmp, data);
417}
418
433tommy_inline void* tommy_tree_search_compare(tommy_tree* tree, tommy_compare_func* cmp, const void* cmp_arg)
434{
435 tommy_tree_node* node = tommy_tree_find_compare(tree, cmp, cmp_arg);
436
437 return node ? node->data : 0;
438}
439
447tommy_inline void* tommy_tree_search(tommy_tree* tree, const void* data)
448{
449 tommy_tree_node* node = tommy_tree_find(tree, data);
450
451 return node ? node->data : 0;
452}
453
469{
470 tommy_tree_node* node = tree->root;
471 tommy_tree_node* candidate = 0;
472
473 while (node) {
474 /* comparators must not change the tree, so retain the data across the call */
475 void* data = node->data;
476 int c = cmp(cmp_arg, data);
477
478 if (c <= 0) {
479 candidate = node;
480 node = node->prev;
481 } else {
482 node = node->next;
483 }
484 }
485
486 return candidate;
487}
488
496tommy_inline tommy_tree_node* tommy_tree_find_greater_equal(tommy_tree* tree, const void* data)
497{
498 return tommy_tree_find_greater_equal_compare(tree, tree->cmp, data);
499}
500
515tommy_inline void* tommy_tree_search_greater_equal_compare(tommy_tree* tree, tommy_compare_func* cmp, const void* cmp_arg)
516{
517 tommy_tree_node* node = tommy_tree_find_greater_equal_compare(tree, cmp, cmp_arg);
518
519 return node ? node->data : 0;
520}
521
529tommy_inline void* tommy_tree_search_greater_equal(tommy_tree* tree, const void* data)
530{
532
533 return node ? node->data : 0;
534}
535
546{
547 tommy_tree_node* node = tree->root;
548 tommy_tree_node* candidate = 0;
549
550 while (node) {
551 /* comparators must not change the tree, so retain the data across the call */
552 void* data = node->data;
553 int c = cmp(cmp_arg, data);
554
555 if (c < 0) {
556 candidate = node;
557 node = node->prev;
558 } else {
559 node = node->next;
560 }
561 }
562
563 return candidate;
564}
565
573tommy_inline tommy_tree_node* tommy_tree_find_greater(tommy_tree* tree, const void* data)
574{
575 return tommy_tree_find_greater_compare(tree, tree->cmp, data);
576}
577
587tommy_inline void* tommy_tree_search_greater_compare(tommy_tree* tree, tommy_compare_func* cmp, const void* cmp_arg)
588{
589 tommy_tree_node* node = tommy_tree_find_greater_compare(tree, cmp, cmp_arg);
590
591 return node ? node->data : 0;
592}
593
601tommy_inline void* tommy_tree_search_greater(tommy_tree* tree, const void* data)
602{
603 tommy_tree_node* node = tommy_tree_find_greater(tree, data);
604
605 return node ? node->data : 0;
606}
607
623{
624 tommy_tree_node* node = tree->root;
625 tommy_tree_node* candidate = 0;
626
627 while (node) {
628 /* comparators must not change the tree, so retain the data across the call */
629 void* data = node->data;
630 int c = cmp(cmp_arg, data);
631
632 if (c < 0) {
633 node = node->prev;
634 } else {
635 candidate = node;
636 node = node->next;
637 }
638 }
639
640 return candidate;
641}
642
650tommy_inline tommy_tree_node* tommy_tree_find_less_equal(tommy_tree* tree, const void* data)
651{
652 return tommy_tree_find_less_equal_compare(tree, tree->cmp, data);
653}
654
669tommy_inline void* tommy_tree_search_less_equal_compare(tommy_tree* tree, tommy_compare_func* cmp, const void* cmp_arg)
670{
671 tommy_tree_node* node = tommy_tree_find_less_equal_compare(tree, cmp, cmp_arg);
672
673 return node ? node->data : 0;
674}
675
683tommy_inline void* tommy_tree_search_less_equal(tommy_tree* tree, const void* data)
684{
686
687 return node ? node->data : 0;
688}
689
699tommy_inline tommy_tree_node* tommy_tree_find_less_compare(tommy_tree* tree, tommy_compare_func* cmp, const void* cmp_arg)
700{
701 tommy_tree_node* node = tree->root;
702 tommy_tree_node* candidate = 0;
703
704 while (node) {
705 /* comparators must not change the tree, so retain the data across the call */
706 void* data = node->data;
707 int c = cmp(cmp_arg, data);
708
709 if (c > 0) {
710 candidate = node;
711 node = node->next;
712 } else {
713 node = node->prev;
714 }
715 }
716
717 return candidate;
718}
719
727tommy_inline tommy_tree_node* tommy_tree_find_less(tommy_tree* tree, const void* data)
728{
729 return tommy_tree_find_less_compare(tree, tree->cmp, data);
730}
731
741tommy_inline void* tommy_tree_search_less_compare(tommy_tree* tree, tommy_compare_func* cmp, const void* cmp_arg)
742{
743 tommy_tree_node* node = tommy_tree_find_less_compare(tree, cmp, cmp_arg);
744
745 return node ? node->data : 0;
746}
747
755tommy_inline void* tommy_tree_search_less(tommy_tree* tree, const void* data)
756{
757 tommy_tree_node* node = tommy_tree_find_less(tree, data);
758
759 return node ? node->data : 0;
760}
761
772tommy_inline void* tommy_tree_remove_compare(tommy_tree* tree, tommy_compare_func* cmp, const void* cmp_arg)
773{
774 tommy_tree_node* candidate = tommy_tree_find_compare(tree, cmp, cmp_arg);
775
776 if (!candidate)
777 return 0;
778
779 return tommy_tree_remove_existing(tree, candidate);
780}
781
789tommy_inline void* tommy_tree_remove(tommy_tree* tree, const void* data)
790{
791 return tommy_tree_remove_compare(tree, tree->cmp, data);
792}
793
832
842TOMMY_API void tommy_tree_foreach_arg(tommy_tree* tree, tommy_foreach_arg_func* func, void* arg);
843
850tommy_inline tommy_bool_t tommy_tree_empty(const tommy_tree* tree)
851{
852 return tree->root == 0;
853}
854
861tommy_inline tommy_size_t tommy_tree_count(const tommy_tree* tree)
862{
863 return tree->count;
864}
865
873
874#endif
875
Data structure node.
Definition: tommytypes.h:242
tommy_size_t index
Index of the node.
Definition: tommytypes.h:269
struct tommy_node_struct * next
Next node.
Definition: tommytypes.h:247
struct tommy_node_struct * prev
Previous node.
Definition: tommytypes.h:253
void * data
Pointer to the element containing the node.
Definition: tommytypes.h:260
Tree container type.
Definition: tommytree.h:146
tommy_tree_node * root
Root node.
Definition: tommytree.h:147
tommy_size_t count
Number of elements.
Definition: tommytree.h:149
tommy_compare_func * cmp
Comparison function.
Definition: tommytree.h:148
Doubly linked list for collisions into hashtables.
TOMMY_API void tommy_tree_foreach(tommy_tree *tree, tommy_foreach_func *func)
Calls the specified function for each element in the tree.
void * tommy_tree_search_compare(tommy_tree *tree, tommy_compare_func *cmp, const void *cmp_arg)
Searches an element in the tree with a specific comparison function.
Definition: tommytree.h:433
void * tommy_tree_remove(tommy_tree *tree, const void *data)
Searches and removes an element from the tree.
Definition: tommytree.h:789
TOMMY_API void tommy_tree_insert(tommy_tree *tree, tommy_tree_node *node, void *data)
Inserts an element in the tree, allowing duplicate keys.
tommy_node tommy_tree_node
Tree node.
Definition: tommytree.h:140
void tommy_tree_init(tommy_tree *tree, tommy_compare_func *cmp)
Initializes the tree.
Definition: tommytree.h:157
TOMMY_API void * tommy_tree_remove_existing(tommy_tree *tree, tommy_tree_node *node)
Removes an element from the tree.
tommy_tree_node * tommy_tree_prev(tommy_tree_node *node)
Gets the node preceding the specified one in tree order.
Definition: tommytree.h:282
tommy_tree_node * tommy_tree_head(tommy_tree *tree)
Gets the head (smallest) node in the tree.
Definition: tommytree.h:306
void * tommy_tree_remove_head(tommy_tree *tree)
Removes and returns the head (smallest) element.
Definition: tommytree.h:344
tommy_tree_node * tommy_tree_find_greater(tommy_tree *tree, const void *data)
Finds the first node in tree order with key strictly greater than the specified one.
Definition: tommytree.h:573
void * tommy_tree_search_greater_equal(tommy_tree *tree, const void *data)
Searches an element in the tree with key greater or equal than the specified one.
Definition: tommytree.h:529
void * tommy_tree_remove_compare(tommy_tree *tree, tommy_compare_func *cmp, const void *cmp_arg)
Searches and removes an element from the tree with a specific comparison function.
Definition: tommytree.h:772
void * tommy_tree_remove_tail(tommy_tree *tree)
Removes and returns the tail (greatest) element.
Definition: tommytree.h:360
tommy_tree_node * tommy_tree_find_compare(tommy_tree *tree, tommy_compare_func *cmp, const void *cmp_arg)
Finds the first equal node in the tree with a specific comparison function.
Definition: tommytree.h:384
void * tommy_tree_search_greater(tommy_tree *tree, const void *data)
Searches the first element in tree order with key strictly greater than the specified one.
Definition: tommytree.h:601
tommy_tree_node * tommy_tree_find(tommy_tree *tree, const void *data)
Finds the first equal node in the tree.
Definition: tommytree.h:414
tommy_tree_node * tommy_tree_next(tommy_tree_node *node)
Gets the node following the specified one in tree order.
Definition: tommytree.h:257
tommy_tree_node * tommy_tree_find_less_compare(tommy_tree *tree, tommy_compare_func *cmp, const void *cmp_arg)
Finds the last node in tree order with key strictly less than the specified one using a specific comp...
Definition: tommytree.h:699
struct tommy_tree_struct tommy_tree
Tree container type.
TOMMY_API void tommy_tree_to_list(tommy_tree *tree, tommy_list *list)
Transfers all elements from the tree to the tail of a list in tree order.
void tommy_tree_clear(tommy_tree *tree)
Removes all elements, preserving the comparison function.
Definition: tommytree.h:189
TOMMY_API void * tommy_tree_insert_unique(tommy_tree *tree, tommy_tree_node *node, void *data)
Inserts an element only if no equal element is already contained.
void tommy_tree_swap(tommy_tree *first, tommy_tree *second)
Exchanges the contents of two initialized trees, including their comparison functions.
Definition: tommytree.h:173
TOMMY_API tommy_size_t tommy_tree_memory_usage(const tommy_tree *tree)
Gets the size of allocated memory.
tommy_tree_node * tommy_tree_parent(tommy_tree_node *node)
Gets the parent of the specified node.
Definition: tommytree.h:245
tommy_tree_node * tommy_tree_find_greater_equal(tommy_tree *tree, const void *data)
Finds a node in the tree with key greater or equal than the specified one.
Definition: tommytree.h:496
tommy_tree_node * tommy_tree_find_greater_equal_compare(tommy_tree *tree, tommy_compare_func *cmp, const void *cmp_arg)
Finds a node in the tree with key greater or equal than the specified one with a specific comparison ...
Definition: tommytree.h:468
tommy_size_t tommy_tree_count(const tommy_tree *tree)
Gets the number of elements.
Definition: tommytree.h:861
tommy_tree_node * tommy_tree_find_less_equal(tommy_tree *tree, const void *data)
Finds a node in the tree with key less or equal than the specified one.
Definition: tommytree.h:650
void * tommy_tree_search_less_compare(tommy_tree *tree, tommy_compare_func *cmp, const void *cmp_arg)
Searches the last element in tree order with key strictly less than the specified one using a specifi...
Definition: tommytree.h:741
tommy_tree_node * tommy_tree_tail(tommy_tree *tree)
Gets the tail (greatest) node in the tree.
Definition: tommytree.h:325
void * tommy_tree_search_less_equal_compare(tommy_tree *tree, tommy_compare_func *cmp, const void *cmp_arg)
Searches an element in the tree with key less or equal than the specified one with a specific compari...
Definition: tommytree.h:669
void * tommy_tree_search_greater_compare(tommy_tree *tree, tommy_compare_func *cmp, const void *cmp_arg)
Searches the first element in tree order with key strictly greater than the specified one using a spe...
Definition: tommytree.h:587
void * tommy_tree_search(tommy_tree *tree, const void *data)
Searches an element in the tree.
Definition: tommytree.h:447
tommy_tree_node * tommy_tree_find_less(tommy_tree *tree, const void *data)
Finds the last node in tree order with key strictly less than the specified one.
Definition: tommytree.h:727
void * tommy_tree_search_less_equal(tommy_tree *tree, const void *data)
Searches an element in the tree with key less or equal than the specified one.
Definition: tommytree.h:683
tommy_tree_node * tommy_tree_find_greater_compare(tommy_tree *tree, tommy_compare_func *cmp, const void *cmp_arg)
Finds the first node in tree order with key strictly greater than the specified one using a specific ...
Definition: tommytree.h:545
tommy_tree_node * tommy_tree_find_less_equal_compare(tommy_tree *tree, tommy_compare_func *cmp, const void *cmp_arg)
Finds a node in the tree with key less or equal than the specified one with a specific comparison fun...
Definition: tommytree.h:622
void * tommy_tree_search_less(tommy_tree *tree, const void *data)
Searches the last element in tree order with key strictly less than the specified one.
Definition: tommytree.h:755
tommy_bool_t tommy_tree_empty(const tommy_tree *tree)
Checks whether the tree is empty.
Definition: tommytree.h:850
void * tommy_tree_search_greater_equal_compare(tommy_tree *tree, tommy_compare_func *cmp, const void *cmp_arg)
Searches an element in the tree with key greater or equal than the specified one with a specific comp...
Definition: tommytree.h:515
TOMMY_API void tommy_tree_foreach_arg(tommy_tree *tree, tommy_foreach_arg_func *func, void *arg)
Calls the specified function with an argument for each element in the tree.
Generic types.
void tommy_foreach_func(void *elem)
Foreach function.
Definition: tommytypes.h:346
int tommy_compare_func(const void *elem_a, const void *elem_b)
Compare function for elements.
Definition: tommytypes.h:302
uint64_t tommy_size_t
Generic size_t type.
Definition: tommytypes.h:40
void tommy_foreach_arg_func(void *arg, void *elem)
Foreach function with an argument.
Definition: tommytypes.h:353
uintptr_t tommy_uintptr_t
Generic uintptr_t type.
Definition: tommytypes.h:36
int tommy_bool_t
Generic boolean type.
Definition: tommytypes.h:53