lib/gl_anytree_omap.h

   1 /* Ordered map data type implemented by a binary tree.
   2    Copyright (C) 2006-2007, 2009-2019 Free Software Foundation, Inc.
   3    Written by Bruno Haible <bruno@clisp.org>, 2018.
   4
   5    This program is free software: you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation; either version 3 of the License, or
   8    (at your option) any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  17
  18 /* Common code of gl_avltree_omap.c and gl_rbtree_omap.c.  */
  19
  20 /* An item on the stack used for iterating across the elements.  */
  21 typedef struct
  22 {
  23   gl_omap_node_t node;
  24   bool rightp;
  25 } iterstack_item_t;
  26
  27 /* A stack used for iterating across the elements.  */
  28 typedef iterstack_item_t iterstack_t[MAXHEIGHT];
  29
  30 static gl_omap_t
  31 gl_tree_nx_create_empty (gl_omap_implementation_t implementation,
  32                          gl_mapkey_compar_fn compar_fn,
  33                          gl_mapkey_dispose_fn kdispose_fn,
  34                          gl_mapvalue_dispose_fn vdispose_fn)
  35 {
  36   struct gl_omap_impl *map =
  37     (struct gl_omap_impl *) malloc (sizeof (struct gl_omap_impl));
  38
  39   if (map == NULL)
  40     return NULL;
  41
  42   map->base.vtable = implementation;
  43   map->base.compar_fn = compar_fn;
  44   map->base.kdispose_fn = kdispose_fn;
  45   map->base.vdispose_fn = vdispose_fn;
  46   map->root = NULL;
  47   map->count = 0;
  48
  49   return map;
  50 }
  51
  52 static size_t
  53 gl_tree_size (gl_omap_t map)
  54 {
  55   return map->count;
  56 }
  57
  58 static bool
  59 gl_tree_search (gl_omap_t map, const void *key, const void **valuep)
  60 {
  61   gl_mapkey_compar_fn compar = map->base.compar_fn;
  62   gl_omap_node_t node;
  63
  64   for (node = map->root; node != NULL; )
  65     {
  66       int cmp = (compar != NULL
  67                  ? compar (node->key, key)
  68                  : (node->key > key ? 1 :
  69                     node->key < key ? -1 : 0));
  70
  71       if (cmp < 0)
  72         node = node->right;
  73       else if (cmp > 0)
  74         node = node->left;
  75       else /* cmp == 0 */
  76         {
  77           /* We have a key equal to KEY.  */
  78           *valuep = node->value;
  79           return true;
  80         }
  81     }
  82   return false;
  83 }
  84
  85 static bool
  86 gl_tree_search_atleast (gl_omap_t map,
  87                         gl_mapkey_threshold_fn threshold_fn,
  88                         const void *threshold,
  89                         const void **keyp, const void **valuep)
  90 {
  91   gl_omap_node_t node;
  92
  93   for (node = map->root; node != NULL; )
  94     {
  95       if (! threshold_fn (node->key, threshold))
  96         node = node->right;
  97       else
  98         {
  99           /* We have a key >= THRESHOLD.  But we need the leftmost such
 100              element.  */
 101           gl_omap_node_t found = node;
 102           node = node->left;
 103           for (; node != NULL; )
 104             {
 105               if (! threshold_fn (node->key, threshold))
 106                 node = node->right;
 107               else
 108                 {
 109                   found = node;
 110                   node = node->left;
 111                 }
 112             }
 113           *keyp = found->key;
 114           *valuep = found->value;
 115           return true;
 116         }
 117     }
 118   return false;
 119 }
 120
 121 static int
 122 gl_tree_nx_getput (gl_omap_t map, const void *key, const void *value,
 123                    const void **oldvaluep)
 124 {
 125   gl_mapkey_compar_fn compar;
 126   gl_omap_node_t node = map->root;
 127
 128   if (node == NULL)
 129     {
 130       if (gl_tree_nx_add_first (map, key, value) == NULL)
 131         return -1;
 132       return 1;
 133     }
 134
 135   compar = map->base.compar_fn;
 136
 137   for (;;)
 138     {
 139       int cmp = (compar != NULL
 140                  ? compar (node->key, key)
 141                  : (node->key > key ? 1 :
 142                     node->key < key ? -1 : 0));
 143
 144       if (cmp < 0)
 145         {
 146           if (node->right == NULL)
 147             {
 148               if (gl_tree_nx_add_after (map, node, key, value) == NULL)
 149                 return -1;
 150               return 1;
 151             }
 152           node = node->right;
 153         }
 154       else if (cmp > 0)
 155         {
 156           if (node->left == NULL)
 157             {
 158               if (gl_tree_nx_add_before (map, node, key, value) == NULL)
 159                 return -1;
 160               return 1;
 161             }
 162           node = node->left;
 163         }
 164       else /* cmp == 0 */
 165         {
 166           *oldvaluep = node->value;
 167           node->value = value;
 168           return 0;
 169         }
 170     }
 171 }
 172
 173 static bool
 174 gl_tree_getremove (gl_omap_t map, const void *key, const void **oldvaluep)
 175 {
 176   gl_mapkey_compar_fn compar = map->base.compar_fn;
 177   gl_omap_node_t node;
 178
 179   for (node = map->root; node != NULL; )
 180     {
 181       int cmp = (compar != NULL
 182                  ? compar (node->key, key)
 183                  : (node->key > key ? 1 :
 184                     node->key < key ? -1 : 0));
 185
 186       if (cmp < 0)
 187         node = node->right;
 188       else if (cmp > 0)
 189         node = node->left;
 190       else /* cmp == 0 */
 191         {
 192           /* We have a key equal to KEY.  */
 193           *oldvaluep = node->value;
 194           gl_tree_remove_node (map, node);
 195           return true;
 196         }
 197     }
 198   return false;
 199 }
 200
 201 static void
 202 gl_tree_omap_free (gl_omap_t map)
 203 {
 204   /* Iterate across all elements in post-order.  */
 205   gl_omap_node_t node = map->root;
 206   iterstack_t stack;
 207   iterstack_item_t *stack_ptr = &stack[0];
 208
 209   for (;;)
 210     {
 211       /* Descend on left branch.  */
 212       for (;;)
 213         {
 214           if (node == NULL)
 215             break;
 216           stack_ptr->node = node;
 217           stack_ptr->rightp = false;
 218           node = node->left;
 219           stack_ptr++;
 220         }
 221       /* Climb up again.  */
 222       for (;;)
 223         {
 224           if (stack_ptr == &stack[0])
 225             goto done_iterate;
 226           stack_ptr--;
 227           node = stack_ptr->node;
 228           if (!stack_ptr->rightp)
 229             break;
 230           /* Free the current node.  */
 231           if (map->base.vdispose_fn != NULL)
 232             map->base.vdispose_fn (node->value);
 233           if (map->base.kdispose_fn != NULL)
 234             map->base.kdispose_fn (node->key);
 235           free (node);
 236         }
 237       /* Descend on right branch.  */
 238       stack_ptr->rightp = true;
 239       node = node->right;
 240       stack_ptr++;
 241     }
 242  done_iterate:
 243   free (map);
 244 }
 245
 246 /* --------------------- gl_omap_iterator_t Data Type --------------------- */
 247
 248 static gl_omap_iterator_t
 249 gl_tree_iterator (gl_omap_t map)
 250 {
 251   gl_omap_iterator_t result;
 252   gl_omap_node_t node;
 253
 254   result.vtable = map->base.vtable;
 255   result.map = map;
 256   /* Start node is the leftmost node.  */
 257   node = map->root;
 258   if (node != NULL)
 259     while (node->left != NULL)
 260       node = node->left;
 261   result.p = node;
 262   /* End point is past the rightmost node.  */
 263   result.q = NULL;
 264 #if defined GCC_LINT || defined lint
 265   result.i = 0;
 266   result.j = 0;
 267   result.count = 0;
 268 #endif
 269
 270   return result;
 271 }
 272
 273 static bool
 274 gl_tree_iterator_next (gl_omap_iterator_t *iterator,
 275                        const void **keyp, const void **valuep)
 276 {
 277   if (iterator->p != iterator->q)
 278     {
 279       gl_omap_node_t node = (gl_omap_node_t) iterator->p;
 280       *keyp = node->key;
 281       *valuep = node->value;
 282       /* Advance to the next node.  */
 283       if (node->right != NULL)
 284         {
 285           node = node->right;
 286           while (node->left != NULL)
 287             node = node->left;
 288         }
 289       else
 290         {
 291           while (node->parent != NULL && node->parent->right == node)
 292             node = node->parent;
 293           node = node->parent;
 294         }
 295       iterator->p = node;
 296       return true;
 297     }
 298   else
 299     return false;
 300 }
 301
 302 static void
 303 gl_tree_iterator_free (gl_omap_iterator_t *iterator)
 304 {
 305 }