diff options
| author | Laurent Bercot <ska-skaware@skarnet.org> | 2025-07-30 13:37:50 +0000 |
|---|---|---|
| committer | Laurent Bercot <ska@appnovation.com> | 2025-07-30 13:37:50 +0000 |
| commit | 46f12f13e6667e7820bad71bb8c66ab9c564f58a (patch) | |
| tree | 9e11717a0087a8260588b4579c8a10bd03f8616e /src/libdatastruct | |
| parent | 2d96b5f87aecf9b3aa45761ee9d29138955bd554 (diff) | |
| download | skalibs-46f12f13e6667e7820bad71bb8c66ab9c564f58a.tar.gz | |
bugfix: avltree_delete needs to pass UINT32_MAX as sentinel
Signed-off-by: Laurent Bercot <ska@appnovation.com>
Diffstat (limited to 'src/libdatastruct')
| -rw-r--r-- | src/libdatastruct/avlnode_insertnode.c | 12 | ||||
| -rw-r--r-- | src/libdatastruct/avltree_delete.c | 5 | ||||
| -rw-r--r-- | src/libdatastruct/avltree_newnode.c | 1 |
3 files changed, 9 insertions, 9 deletions
diff --git a/src/libdatastruct/avlnode_insertnode.c b/src/libdatastruct/avlnode_insertnode.c index 294b109..5bb22d2 100644 --- a/src/libdatastruct/avlnode_insertnode.c +++ b/src/libdatastruct/avlnode_insertnode.c @@ -10,7 +10,6 @@ uint32_t avlnode_insertnode (avlnode *s, uint32_t max, uint32_t r, uint32_t i, d uint32_t stack[AVLNODE_MAXDEPTH] ; uint8_t spin[AVLNODE_MAXDEPTH] ; uint8_t sp = 0 ; - { void const *k = (*dtok)(s[i].data, p) ; for (; r < max ; sp++) @@ -31,13 +30,12 @@ uint32_t avlnode_insertnode (avlnode *s, uint32_t max, uint32_t r, uint32_t i, d return r ; lastfix: - if (avlnode_ufroms(s[r].balance) != spin[sp]) + if (avlnode_ufroms(s[r].balance) != spin[sp]) s[r].balance = 0 ; + else { - s[r].balance = 0 ; - return stack[0] ; + r = avlnode_rotate_maydouble(s, max, r, !spin[sp], spin[sp] != spin[sp+1]) ; + if (!sp--) return r ; + s[stack[sp]].child[spin[sp]] = r ; } - r = avlnode_rotate_maydouble(s, max, r, !spin[sp], spin[sp] != spin[sp+1]) ; - if (!sp--) return r ; - s[stack[sp]].child[spin[sp]] = r ; return stack[0] ; } diff --git a/src/libdatastruct/avltree_delete.c b/src/libdatastruct/avltree_delete.c index 04f6097..b0b63fc 100644 --- a/src/libdatastruct/avltree_delete.c +++ b/src/libdatastruct/avltree_delete.c @@ -2,6 +2,7 @@ #include <stdint.h> #include <errno.h> + #include <skalibs/gensetdyn.h> #include <skalibs/avlnode.h> #include <skalibs/avltree.h> @@ -9,8 +10,8 @@ int avltree_delete (avltree *t, void const *k) { uint32_t r = avltree_root(t) ; - uint32_t i = avlnode_delete(avltree_nodes(t), avltree_totalsize(t), &r, k, t->dtok, t->kcmp, t->external) ; - if (i >= avltree_totalsize(t)) return (errno = ESRCH, 0) ; + uint32_t i = avlnode_delete(avltree_nodes(t), UINT32_MAX, &r, k, t->dtok, t->kcmp, t->external) ; + if (i >= UINT32_MAX) return (errno = ESRCH, 0) ; avltree_setroot(t, r) ; if (!gensetdyn_delete(&t->x, i)) return 0 ; return 1 ; diff --git a/src/libdatastruct/avltree_newnode.c b/src/libdatastruct/avltree_newnode.c index 3d658c6..300f918 100644 --- a/src/libdatastruct/avltree_newnode.c +++ b/src/libdatastruct/avltree_newnode.c @@ -1,6 +1,7 @@ /* ISC license. */ #include <errno.h> + #include <skalibs/gensetdyn.h> #include <skalibs/avlnode.h> #include <skalibs/avltree.h> |