1 /* SPDX-License-Identifier: Unlicense */ 2 // 3 // Based on Julienne Walker's <http://eternallyconfuzzled.com/> rb_tree 4 // implementation. 5 // 6 // Modified by Mirek Rusin <http://github.com/mirek/rb_tree>. 7 // 8 // This is free and unencumbered software released into the public domain. 9 // 10 // Anyone is free to copy, modify, publish, use, compile, sell, or 11 // distribute this software, either in source code form or as a compiled 12 // binary, for any purpose, commercial or non-commercial, and by any 13 // means. 14 // 15 // In jurisdictions that recognize copyright laws, the author or authors 16 // of this software dedicate any and all copyright interest in the 17 // software to the public domain. We make this dedication for the benefit 18 // of the public at large and to the detriment of our heirs and 19 // successors. We intend this dedication to be an overt act of 20 // relinquishment in perpetuity of all present and future rights to this 21 // software under copyright law. 22 // 23 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 24 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 25 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 26 // IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR 27 // OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, 28 // ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 29 // OTHER DEALINGS IN THE SOFTWARE. 30 // 31 // For more information, please refer to <http://unlicense.org/> 32 // 33 34 #ifndef __RB_TREE_H__ 35 #define __RB_TREE_H__ 1 36 37 #include <stdio.h> 38 #include <stdint.h> 39 #include <stddef.h> 40 #include <stdlib.h> 41 42 #ifndef RB_ITER_MAX_HEIGHT 43 #define RB_ITER_MAX_HEIGHT 64 // Tallest allowable tree to iterate 44 #endif 45 46 struct rb_node; 47 struct rb_tree; 48 49 typedef int (*rb_tree_node_cmp_f) (struct rb_tree *self, struct rb_node *a, struct rb_node *b); 50 typedef void (*rb_tree_node_f) (struct rb_tree *self, struct rb_node *node); 51 52 struct rb_node { 53 int red; // Color red (1), black (0) 54 struct rb_node *link[2]; // Link left [0] and right [1] 55 void *value; // User provided, used indirectly via rb_tree_node_cmp_f. 56 }; 57 58 struct rb_tree { 59 struct rb_node *root; 60 rb_tree_node_cmp_f cmp; 61 size_t size; 62 void *info; // User provided, not used by rb_tree. 63 }; 64 65 struct rb_iter { 66 struct rb_tree *tree; 67 struct rb_node *node; // Current node 68 struct rb_node *path[RB_ITER_MAX_HEIGHT]; // Traversal path 69 size_t top; // Top of stack 70 void *info; // User provided, not used by rb_iter. 71 }; 72 73 int rb_tree_node_cmp_ptr_cb (struct rb_tree *self, struct rb_node *a, struct rb_node *b); 74 void rb_tree_node_dealloc_cb (struct rb_tree *self, struct rb_node *node); 75 76 struct rb_node *rb_node_alloc (); 77 struct rb_node *rb_node_create (void *value); 78 struct rb_node *rb_node_init (struct rb_node *self, void *value); 79 void rb_node_dealloc (struct rb_node *self); 80 81 struct rb_tree *rb_tree_alloc (); 82 struct rb_tree *rb_tree_create (rb_tree_node_cmp_f cmp); 83 struct rb_tree *rb_tree_init (struct rb_tree *self, rb_tree_node_cmp_f cmp); 84 void rb_tree_dealloc (struct rb_tree *self, rb_tree_node_f node_cb); 85 void *rb_tree_find (struct rb_tree *self, void *value); 86 int rb_tree_insert (struct rb_tree *self, void *value); 87 int rb_tree_remove (struct rb_tree *self, void *value); 88 size_t rb_tree_size (struct rb_tree *self); 89 90 int rb_tree_insert_node (struct rb_tree *self, struct rb_node *node); 91 int rb_tree_remove_with_cb (struct rb_tree *self, void *value, rb_tree_node_f node_cb); 92 93 int rb_tree_test (struct rb_tree *self, struct rb_node *root); 94 95 struct rb_iter *rb_iter_alloc (); 96 struct rb_iter *rb_iter_init (struct rb_iter *self); 97 struct rb_iter *rb_iter_create (); 98 void rb_iter_dealloc (struct rb_iter *self); 99 void *rb_iter_first (struct rb_iter *self, struct rb_tree *tree); 100 void *rb_iter_last (struct rb_iter *self, struct rb_tree *tree); 101 void *rb_iter_next (struct rb_iter *self); 102 void *rb_iter_prev (struct rb_iter *self); 103 104 #endif 105