summaryrefslogtreecommitdiff
path: root/src/search
AgeCommit message (Collapse)AuthorLines
2018-09-20new tsearch implementationSzabolcs Nagy-213/+200
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
2018-09-12reduce spurious inclusion of libc.hRich Felker-1/+0
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.
2018-09-12make inadvertently exposed __h{create,delete,search}_r functions staticRich Felker-6/+6
2017-03-05fix lsearch and lfind to pass key as first arg to the compar callbackSzabolcs Nagy-2/+2
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.
2015-12-08fix tsearch, tfind, tdelete to handle null pointer inputSzabolcs Nagy-0/+6
POSIX specifies the behaviour for null rootp input, but it was not implemented correctly.
2015-12-08tsearch code cleanupSzabolcs Nagy-24/+28
changed the insertion method to simplify the recursion logic and reduce code size a bit.
2015-12-08fix tsearch to avoid crash on oomSzabolcs Nagy-1/+1
malloc failure was not properly propagated in the insertion method which led to null pointer dereference.
2015-12-08fix tdelete to properly balance the treeSzabolcs Nagy-5/+14
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.
2014-04-02remove struct elem entirely from hsearch.csin-29/+22
There are two changes here, both of which make sense to be done in a single patch: - Remove hash from struct elem and compute it at runtime wherever necessary. - Eliminate struct elem and use ENTRY directly. As a result we cut down on the memory usage as each element in the hash table now contains only an ENTRY not an ENTRY + size_t for the hash. The downside is that the hash needs to be computed at runtime.
2014-04-02implement hcreate_r, hdestroy_r and hsearch_rsin-30/+73
the size and alignment of struct hsearch_data are matched to the glibc definition for binary compatibility. the members of the structure do not match, which should not be a problem as long as applications correctly treat the structure as opaque. unlike the glibc implementation, this version of hcreate_r does not require the caller to zero-fill the structure before use.
2013-10-29POSIX conformance fix: define struct entry in search.hSzabolcs Nagy-8/+8
2013-08-02make tdestroy allow null function pointer if no destructor is neededRich Felker-1/+1
this change is to align with a change in the glibc interface.
2013-08-02fix aliasing violations in tsearch functionsRich Felker-2/+10
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.
2012-05-13search: add comments to tsearch_avl.cnsz-0/+6
2012-05-13search: add tdestroy (gnu extension)nsz-0/+21
2011-06-25XSI search.h API implementation by Szabolcs NagyRich Felker-0/+352