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