| Age | Commit message (Collapse) | Author | Lines |
|---|
|
Rewrote the AVL tree implementation:
- It is now non-recursive with fixed stack usage (large enough for
worst case tree height). twalk and tdestroy are still recursive as
that's smaller/simpler.
- Moved unrelated interfaces into separate translation units.
- The node structure is changed to use indexed children instead of
left/right pointers, this simplifies the balancing logic.
- Using void * pointers instead of struct node * in various places,
because this better fits the api (node address is passed in a void**
argument, so it is tempting to incorrectly cast it to struct node **).
- As a further performance improvement the rebalancing now stops
when it is not needed (subtree height is unchanged). Otherwise
the behaviour should be the same as before (checked over generated
random inputs that the resulting tree shape is equivalent).
- Removed the old copyright notice (including prng related one: it
should be licensed under the same terms as the rest of the project).
.text size of pic tsearch + tfind + tdelete + twalk:
x86_64 i386 aarch64 arm mips powerpc ppc64le sh4 m68k s390x
old 941 899 1220 1068 1852 1400 1600 1008 1008 1488
new 857 881 1040 976 1564 1192 1360 736 820 1408
|
|
POSIX specifies the behaviour for null rootp input, but it
was not implemented correctly.
|
|
changed the insertion method to simplify the recursion logic and
reduce code size a bit.
|
|
malloc failure was not properly propagated in the insertion method
which led to null pointer dereference.
|
|
the tsearch data structure is an avl tree, but it did not implement
the deletion operation correctly so the tree could become unbalanced.
reported by Ed Schouten.
|
|
patch by nsz. the actual object the caller has storing the tree root
has type void *, so accessing it as struct node * is not valid.
instead, simply access the value, move it to a temporary of the
appropriate type and work from there, then move the result back.
|
|
|
|
|
