grovel/src/search, branch main Unnamed repository; edit this file 'description' to name the repository. http://euandre.org/git/grovel/atom?h=main 2024-01-05T08:47:09Z Setup stub unit test infrastructure 2024-01-05T08:47:09Z EuAndreh eu@euandre.org 2024-01-04T23:36:02Z urn:sha1:8492f115890d56c98c1da24b9fdf26bb1b714c05 hsearch: fix null pointer arithmetic UB 2023-02-12T22:41:23Z Szabolcs Nagy nsz@port70.net 2023-02-03T22:10:17Z urn:sha1:7e6da7ac98efdc8167ed2d109298ba232a9a7ba3 htab->__tab->entries pointer may be 0 so delay using it in arithmetics. this did not cause any known issue other than with ubsan instrumentation. new tsearch implementation 2018-09-20T21:57:47Z Szabolcs Nagy nsz@port70.net 2016-08-21T20:06:56Z urn:sha1:c50985d5c8e316c5c464f352e79eeebfed1121a9 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 reduce spurious inclusion of libc.h 2018-09-12T18:34:37Z Rich Felker dalias@aerifal.cx 2018-09-12T04:08:09Z urn:sha1:5ce3737931bb411a8d167356d4d0287b53b0cbdc libc.h was intended to be a header for access to global libc state and related interfaces, but ended up included all over the place because it was the way to get the weak_alias macro. most of the inclusions removed here are places where weak_alias was needed. a few were recently introduced for hidden. some go all the way back to when libc.h defined CANCELPT_BEGIN and _END, and all (wrongly implemented) cancellation points had to include it. remaining spurious users are mostly callers of the LOCK/UNLOCK macros and files that use the LFS64 macro to define the awful *64 aliases. in a few places, new inclusion of libc.h is added because several internal headers no longer implicitly include libc.h. declarations for __lockfile and __unlockfile are moved from libc.h to stdio_impl.h so that the latter does not need libc.h. putting them in libc.h made no sense at all, since the macros in stdio_impl.h are needed to use them correctly anyway. make inadvertently exposed __h{create,delete,search}_r functions static 2018-09-12T18:34:28Z Rich Felker dalias@aerifal.cx 2018-09-06T18:06:50Z urn:sha1:736a950b3d4f476018d2909302be6d150530df50 fix lsearch and lfind to pass key as first arg to the compar callback 2017-03-06T01:02:31Z Szabolcs Nagy nsz@port70.net 2017-03-05T22:03:35Z urn:sha1:827c4e6fbe46142049ef3d8bcb8f35951712797d this is not a conformance issue as posix does not specify the argument order, but the order is specified for bsearch and some systems document the order for lsearch consistently (openbsd). since there were two indpendent reports of this issue it's better to use the more widely expected argument order. fix tsearch, tfind, tdelete to handle null pointer input 2015-12-08T23:53:18Z Szabolcs Nagy nsz@port70.net 2015-12-05T20:53:59Z urn:sha1:3abb094d19ca4c7c4adcf373d971fb5aa05c5252 POSIX specifies the behaviour for null rootp input, but it was not implemented correctly. tsearch code cleanup 2015-12-08T23:53:02Z Szabolcs Nagy nsz@port70.net 2015-12-05T20:06:02Z urn:sha1:8994908b199a57097f420707b1fca75fc30236fa changed the insertion method to simplify the recursion logic and reduce code size a bit. fix tsearch to avoid crash on oom 2015-12-08T23:52:38Z Szabolcs Nagy nsz@port70.net 2015-12-05T20:04:18Z urn:sha1:bc9744763afe72d626e7b9f461001d425582fe9c malloc failure was not properly propagated in the insertion method which led to null pointer dereference. fix tdelete to properly balance the tree 2015-12-08T23:52:25Z Szabolcs Nagy nsz@port70.net 2015-12-05T20:02:34Z urn:sha1:e4f9d811684011d8a67e363827de39d5f2d3ae5a 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.