summaryrefslogtreecommitdiff
path: root/src/search
AgeCommit message (Collapse)AuthorLines
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