Mercurial > gnulib
annotate lib/gl_anytree_omap.h @ 40057:b06060465f09
maint: Run 'make update-copyright'
| author | Paul Eggert <eggert@cs.ucla.edu> |
|---|---|
| date | Tue, 01 Jan 2019 00:25:11 +0100 |
| parents | 975fc034aecf |
| children |
| rev | line source |
|---|---|
| 40006 | 1 /* Ordered map data type implemented by a binary tree. |
|
40057
b06060465f09
maint: Run 'make update-copyright'
Paul Eggert <eggert@cs.ucla.edu>
parents:
40012
diff
changeset
|
2 Copyright (C) 2006-2007, 2009-2019 Free Software Foundation, Inc. |
| 40006 | 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; | |
|
40012
975fc034aecf
array-omap, avltree-omap, rbtree-omap: Tweak style.
Bruno Haible <bruno@clisp.org>
parents:
40006
diff
changeset
|
132 return 1; |
| 40006 | 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; | |
|
40012
975fc034aecf
array-omap, avltree-omap, rbtree-omap: Tweak style.
Bruno Haible <bruno@clisp.org>
parents:
40006
diff
changeset
|
150 return 1; |
| 40006 | 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; | |
|
40012
975fc034aecf
array-omap, avltree-omap, rbtree-omap: Tweak style.
Bruno Haible <bruno@clisp.org>
parents:
40006
diff
changeset
|
160 return 1; |
| 40006 | 161 } |
| 162 node = node->left; | |
| 163 } | |
| 164 else /* cmp == 0 */ | |
| 165 { | |
| 166 *oldvaluep = node->value; | |
| 167 node->value = value; | |
|
40012
975fc034aecf
array-omap, avltree-omap, rbtree-omap: Tweak style.
Bruno Haible <bruno@clisp.org>
parents:
40006
diff
changeset
|
168 return 0; |
| 40006 | 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 } |