tree.h

   1 /*
   2  * Copyright (C) 2024 Mikulas Patocka
   3  *
   4  * This file is part of Ajla.
   5  *
   6  * Ajla is free software: you can redistribute it and/or modify it under the
   7  * terms of the GNU General Public License as published by the Free Software
   8  * Foundation, either version 3 of the License, or (at your option) any later
   9  * version.
  10  *
  11  * Ajla is distributed in the hope that it will be useful, but WITHOUT ANY
  12  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
  13  * A PARTICULAR PURPOSE. See the GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License along with
  16  * Ajla. If not, see <https://www.gnu.org/licenses/>.
  17  */
  18
  19 #ifndef AJLA_TREE_H
  20 #define AJLA_TREE_H
  21
  22 struct tree_entry {
  23         struct tree_entry *children[2];
  24         struct tree_entry **parent;
  25         uchar_efficient_t color;
  26         uchar_efficient_t idx;
  27 };
  28
  29 #define RB_BLACK        0
  30 #define RB_RED          1
  31
  32 #define RB_IDX_LEFT     0
  33 #define RB_IDX_RIGHT    1
  34 #define RB_IDX_ROOT     2
  35
  36 struct tree {
  37         struct tree_entry *root;
  38 };
  39
  40 static inline void tree_init(struct tree *root)
  41 {
  42         root->root = NULL;
  43 }
  44
  45 static inline bool tree_is_empty(struct tree *root)
  46 {
  47         return !root->root;
  48 }
  49
  50 #ifdef DEBUG_RBTREE
  51 void tree_verify_node(struct tree_entry *);
  52 #else
  53 #define tree_verify_node(n)     ((void)0)
  54 #endif
  55
  56 struct tree_insert_position {
  57         size_t idx;
  58         struct tree_entry **link;
  59 };
  60
  61 static inline struct tree_entry *tree_find_for_insert(
  62         struct tree *root,
  63         int (*compare)(const struct tree_entry *, uintptr_t),
  64         uintptr_t key,
  65         struct tree_insert_position *pos)
  66 {
  67         struct tree_entry *p = root->root;
  68         if (pos) {
  69                 pos->idx = RB_IDX_ROOT;
  70                 pos->link = &root->root;
  71         }
  72         while (p) {
  73                 int c;
  74                 size_t cc;
  75                 tree_verify_node(p);
  76                 c = compare(p, key);
  77                 if (!c)
  78                         return p;
  79                 cc = c < 0;
  80                 /*__asm__("" : "=r"(cc) : "0"(cc));*/
  81                 if (pos) {
  82                         pos->idx = cc;
  83                         pos->link = &p->children[cc];
  84                 }
  85                 p = p->children[cc];
  86         }
  87         return NULL;
  88 }
  89
  90 static inline struct tree_entry *tree_find(
  91         struct tree *root,
  92         int (*compare)(const struct tree_entry *, uintptr_t),
  93         uintptr_t key)
  94 {
  95         return tree_find_for_insert(root, compare, key, NULL);
  96 }
  97
  98 static inline struct tree_entry *tree_find_next(
  99         struct tree *root,
 100         int (*compare)(const struct tree_entry *, uintptr_t),
 101         uintptr_t key)
 102 {
 103         struct tree_entry *p = root->root;
 104         struct tree_entry *last_candidate = NULL;
 105         while (p) {
 106                 int c;
 107                 size_t cc;
 108                 tree_verify_node(p);
 109                 c = compare(p, key);
 110                 if (c > 0)
 111                         last_candidate = p;
 112                 cc = c <= 0;
 113                 p = p->children[cc];
 114         }
 115         return last_candidate;
 116 }
 117
 118 static inline struct tree_entry *tree_find_best(
 119         struct tree *root,
 120         int (*compare)(const struct tree_entry *, uintptr_t),
 121         uintptr_t key)
 122 {
 123         struct tree_entry *p = root->root;
 124         struct tree_entry *last_candidate = NULL;
 125         while (p) {
 126                 int c;
 127                 size_t cc;
 128                 tree_verify_node(p);
 129                 c = compare(p, key);
 130                 if (c >= 0)
 131                         last_candidate = p;
 132                 if (!c)
 133                         break;
 134                 cc = c < 0;
 135                 p = p->children[cc];
 136         }
 137         return last_candidate;
 138 }
 139
 140 void attr_fastcall tree_insert_after_find_impl(struct tree_entry *, uchar_efficient_t idx, struct tree_entry **link);
 141
 142 static inline void tree_insert_after_find(struct tree_entry *p, const struct tree_insert_position *pos)
 143 {
 144         tree_insert_after_find_impl(p, (uchar_efficient_t)pos->idx, pos->link);
 145 }
 146
 147 void attr_fastcall tree_delete(struct tree_entry *);
 148
 149 struct tree_entry * attr_fastcall tree_first(struct tree *);
 150 struct tree_entry * attr_fastcall tree_next(struct tree_entry *);
 151 struct tree_entry * attr_fastcall tree_last(struct tree *);
 152
 153 static inline struct tree_entry *tree_any(struct tree *root)
 154 {
 155         return root->root;
 156 }
 157
 158 #endif