musl - Re: Completeness status of musl

Follow @Openwall on Twitter for new release announcements and other news

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20110625183106.GV27421@port70.net>
Date: Sat, 25 Jun 2011 20:31:06 +0200
From: Szabolcs Nagy <nsz@...t70.net>
To: musl@...ts.openwall.com
Subject: Re: Completeness status of musl

* Rich Felker <dalias@...ifal.cx> [2011-06-08 19:58:10 -0400]:
> Moderate-effort new code:
> - XSI search.h functionality

i did this as it seems fairly simple/harmless
unfortunately this api is quite useless in practice
but i tried to write a simple and conformant implementation

hsearch:
    i used open addressing hashtable (with doubling)
    (it is probably a bit bigger than a chained hash)

    i used a simple hash function (its output must be
    size_t so clever 32bit hash functions are not ok)

    standard is not clear if item.key==NULL is allowed
    to be put into the table (i assumed NULL is not allowed
    as it says strcmp is used on the key, so i mark empty
    entries with NULL key)

    standard is not clear if after an out of memory event
    should there be a usable state, so i made it to work
    (if an insert fails the table can still be searched)

    this api does not provide iterator, number of items
    cannot queried and only string keys with strcmp can
    be used

insque,remque:
    doubly linked list management without type safety..

lsearch,lfind:
    complicated api that can be replaced by a for loop

tsearch:
    i provided two different implementations: plain binary
    tree (as used in bsd) and a self balancing avl tree
    (glibc seems to use rb-tree)

    the first one is simple, but walking the tree may use
    large amount of memory (stack memory, as i used
    recursion there)

    the avl tree implementation uses recursive functions
    (max depth of an avl tree with 2^42 nodes is 60)

    implementing (and using) this api is a bit painful
    the functions return node pointers that the user
    cannot really use..

attached code is also available here temporarily:
http://port70.net/~nsz/musl/search/


View attachment "search.h" of type "text/x-chdr" (1039 bytes)

View attachment "hsearch.c" of type "text/x-csrc" (1995 bytes)

View attachment "insque.c" of type "text/x-csrc" (448 bytes)

View attachment "lsearch.c" of type "text/x-csrc" (609 bytes)

View attachment "tsearch_avl.c" of type "text/x-csrc" (3351 bytes)

View attachment "tsearch_simple.c" of type "text/x-csrc" (1781 bytes)

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.