Re: Completeness status of musl

[Szabolcs Nagy <nsz@port70.net>]

[-- Attachment #1: Type: text/plain, Size: 1771 bytes --]

* Rich Felker <dalias@aerifal.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/


[-- Attachment #2: search.h --]
[-- Type: text/x-chdr, Size: 1039 bytes --]

#ifndef	_SEARCH_H
#define	_SEARCH_H

// TODO: cplusplus, xopensource,..

#define __NEED_size_t
#include <bits/alltypes.h>

typedef enum { FIND, ENTER } ACTION;
typedef enum { preorder, postorder, endorder, leaf } VISIT;

typedef struct {
	char *key;
	void *data;
} ENTRY;

int hcreate(size_t nel);
void hdestroy(void);
ENTRY *hsearch(ENTRY item, ACTION action);

void insque(void *element, void *pred);
void remque(void *element);

void *lsearch(const void *key, void *base, size_t *nelp, size_t width,
	int (*compar)(const void *, const void *));
void *lfind(const void *key, const void *base, size_t *nelp,
	size_t width, int (*compar)(const void *, const void *));

void *tdelete(const void *restrict key, void **restrict rootp,
	int(*compar)(const void *, const void *));
void *tfind(const void *key, void *const *rootp,
	int(*compar)(const void *, const void *));
void *tsearch(const void *key, void **rootp,
	int (*compar)(const void *, const void *));
void twalk(const void *root, void (*action)(const void *, VISIT, int));

#endif

[-- Attachment #3: hsearch.c --]
[-- Type: text/x-csrc, Size: 1995 bytes --]

#include <stdlib.h>
#include <string.h>
#include <search.h>

/*
open addressing hash table with 2^n table size
quadratic probing is used in case of hash collision
tab indices and hash are size_t
after resize fails with ENOMEM the state of tab is still usable

with the posix api items cannot be iterated and length cannot be queried
*/

#define MINSIZE 8
#define MAXSIZE ((size_t)-1/2 + 1)

struct entry {
	ENTRY item;
	size_t hash;
};

static size_t mask;
static size_t used;
static struct entry *tab;

static size_t keyhash(char *k)
{
	unsigned char *p = (void *)k;
	size_t h = 0;

	while (*p)
		h = 31*h + *p++;
	return h;
}

static int resize(size_t nel)
{
	size_t newsize;
	size_t i, j;
	struct entry *e, *newe;
	struct entry *oldtab = tab;
	struct entry *oldend = tab + mask + 1;

	if (nel > MAXSIZE)
		nel = MAXSIZE;
	for (newsize = MINSIZE; newsize < nel; newsize *= 2);
	tab = calloc(newsize, sizeof *tab);
	if (!tab) {
		tab = oldtab;
		return 0;
	}
	mask = newsize - 1;
	if (!oldtab)
		return 1;
	for (e = oldtab; e < oldend; e++)
		if (e->item.key) {
			for (i=e->hash,j=1; ; i+=j++) {
				newe = tab + (i & mask);
				if (!newe->item.key)
					break;
			}
			*newe = *e;
		}
	free(oldtab);
	return 1;
}

int hcreate(size_t nel)
{
	mask = 0;
	used = 0;
	tab = 0;
	return resize(nel);
}

void hdestroy(void)
{
	free(tab);
	tab = 0;
	mask = 0;
	used = 0;
}

static struct entry *lookup(char *key, size_t hash)
{
	size_t i, j;
	struct entry *e;

	for (i=hash,j=1; ; i+=j++) {
		e = tab + (i & mask);
		if (!e->item.key ||
		    (e->hash==hash && strcmp(e->item.key, key)==0))
			break;
	}
	return e;
}

ENTRY *hsearch(ENTRY item, ACTION action)
{
	size_t hash = keyhash(item.key);
	struct entry *e = lookup(item.key, hash);

	if (e->item.key)
		return &e->item;
	if (action == FIND)
		return 0;
	e->item = item;
	e->hash = hash;
	if (++used > mask - mask/4) {
		if (!resize(2*used)) {
			used--;
			e->item.key = 0;
			return 0;
		}
		e = lookup(item.key, hash);
	}
	return &e->item;
}

[-- Attachment #4: insque.c --]
[-- Type: text/x-csrc, Size: 448 bytes --]

#include <search.h>

struct node {
	struct node *next;
	struct node *prev;
};

void insque(void *element, void *pred)
{
	struct node *e = element;
	struct node *p = pred;

	if (!p) {
		e->next = e->prev = 0;
		return;
	}
	e->next = p->next;
	e->prev = p;
	p->next = e;
	if (e->next)
		e->next->prev = e;
}

void remque(void *element)
{
	struct node *e = element;

	if (e->next)
		e->next->prev = e->prev;
	if (e->prev)
		e->prev->next = e->next;
}

[-- Attachment #5: lsearch.c --]
[-- Type: text/x-csrc, Size: 609 bytes --]

#include <search.h>
#include <string.h>

void *lsearch(const void *key, void *base, size_t *nelp, size_t width,
	int (*compar)(const void *, const void *))
{
	char (*p)[width] = base;
	size_t n = *nelp;
	size_t i;

	for (i = 0; i < n; i++)
		if (compar(p[i], key) == 0)
			return p[i];
	*nelp = n+1;
	return memcpy(p[n], key, width);
}

void *lfind(const void *key, const void *base, size_t *nelp,
	size_t width, int (*compar)(const void *, const void *))
{
	char (*p)[width] = (void *)base;
	size_t n = *nelp;
	size_t i;

	for (i = 0; i < n; i++)
		if (compar(p[i], key) == 0)
			return p[i];
	return 0;
}



[-- Attachment #6: tsearch_avl.c --]
[-- Type: text/x-csrc, Size: 3351 bytes --]

#include <stdlib.h>
#include <search.h>

struct node {
	const void *key;
	struct node *left;
	struct node *right;
	int height;
};

static int delta(struct node *n) {
	return (n->left ? n->left->height:0) - (n->right ? n->right->height:0);
}

static void updateheight(struct node *n) {
	n->height = 0;
	if (n->left && n->left->height > n->height)
		n->height = n->left->height;
	if (n->right && n->right->height > n->height)
		n->height = n->right->height;
	n->height++;
}

static struct node *rotl(struct node *n) {
	struct node *r = n->right;
	n->right = r->left;
	r->left = n;
	updateheight(n);
	updateheight(r);
	return r;
}

static struct node *rotr(struct node *n) {
	struct node *l = n->left;
	n->left = l->right;
	l->right = n;
	updateheight(n);
	updateheight(l);
	return l;
}

static struct node *balance(struct node *n) {
	int d = delta(n);

	if (d < -1) {
		if (delta(n->right) > 0)
			n->right = rotr(n->right);
		return rotl(n);
	} else if (d > 1) {
		if (delta(n->left) < 0)
			n->left = rotl(n->left);
		return rotr(n);
	}
	updateheight(n);
	return n;
}

static struct node *find(struct node *n, const void *k,
	int (*cmp)(const void *, const void *))
{
	int c;

	if (!n)
		return 0;
	c = cmp(k, n->key);
	if (c == 0)
		return n;
	if (c < 0)
		return find(n->left, k, cmp);
	else
		return find(n->right, k, cmp);
}

static struct node *insert(struct node **n, const void *k,
	int (*cmp)(const void *, const void *), int *new)
{
	struct node *r = *n;
	int c;

	if (!r) {
		*n = r = malloc(sizeof **n);
		if (r) {
			r->key = k;
			r->left = r->right = 0;
			r->height = 1;
		}
		*new = 1;
		return r;
	}
	c = cmp(k, r->key);
	if (c == 0)
		return r;
	if (c < 0)
		r = insert(&r->left, k, cmp, new);
	else
		r = insert(&r->right, k, cmp, new);
	if (*new)
		*n = balance(*n);
	return r;
}

static struct node *movr(struct node *n, struct node *r) {
	if (!n)
		return r;
	n->right = movr(n->right, r);
	return balance(n);
}

static struct node *remove(struct node **n, const void *k,
	int (*cmp)(const void *, const void *), struct node *parent)
{
	int c;

	if (!*n)
		return 0;
	c = cmp(k, (*n)->key);
	if (c == 0) {
		struct node *r = *n;
		*n = movr(r->left, r->right);
		free(r);
		return parent;
	}
	if (c < 0)
		parent = remove(&(*n)->left, k, cmp, *n);
	else
		parent = remove(&(*n)->right, k, cmp, *n);
	if (parent)
		*n = balance(*n);
	return parent;
}

void *tdelete(const void *restrict key, void **restrict rootp,
	int(*compar)(const void *, const void *))
{
	/* last argument is arbitrary non-null pointer
	   which is returned when the root node is deleted */
	return remove((void*)rootp, key, compar, *rootp);
}

void *tfind(const void *key, void *const *rootp,
	int(*compar)(const void *, const void *))
{
	return find(*rootp, key, compar);
}

void *tsearch(const void *key, void **rootp,
	int (*compar)(const void *, const void *))
{
	int new = 0;
	return insert((void*)rootp, key, compar, &new);
}

static void walk(const struct node *r, void (*action)(const void *, VISIT, int), int d)
{
	if (r == 0)
		return;
	if (r->left == 0 && r->right == 0)
		action(r, leaf, d);
	else {
		action(r, preorder, d);
		walk(r->left, action, d+1);
		action(r, postorder, d);
		walk(r->right, action, d+1);
		action(r, endorder, d);
	}
}

void twalk(const void *root, void (*action)(const void *, VISIT, int))
{
	walk(root, action, 0);
}

[-- Attachment #7: tsearch_simple.c --]
[-- Type: text/x-csrc, Size: 1780 bytes --]

#include <stdlib.h>
#include <search.h>

struct node {
	const void *key;
	struct node *left;
	struct node *right;
};

static struct node **lookup(const void *key, struct node **r,
	int (*compar)(const void *, const void *))
{
	while (*r) {
		int c = compar(key, (*r)->key);
		if (c < 0)
			r = &(*r)->left;
		else if (c > 0)
			r = &(*r)->right;
		else
			break;
	}
	return r;
}

void *tdelete(const void *restrict key, void **restrict rootp,
	int(*compar)(const void *, const void *))
{
	struct node **r = (void*)rootp;
	struct node *parent = *r; /* arbitrary non-null pointer */
	struct node *a;
	struct node *b;
	int c;

	for (;;) {
		if (!*r)
			return 0;
		c = compar(key, (*r)->key);
		if (c == 0)
			break;
		parent = *r;
		if (c < 0)
			r = &(*r)->left;
		else
			r = &(*r)->right;
	}
	a = (*r)->left;
	b = (*r)->right;
	free(*r);
	if (a) {
		*r = a;
		for (; a->right; a = a->right);
		a->right = b;
	} else
		*r = b;
	return parent;
}

void *tfind(const void *key, void *const *rootp,
	int(*compar)(const void *, const void *))
{
	return *lookup(key, (void*)rootp, compar);
}

void *tsearch(const void *key, void **rootp,
	int (*compar)(const void *, const void *))
{
	struct node **r = lookup(key, (void*)rootp, compar);
	if (*r)
		return *r;
	*r = malloc(sizeof **r);
	if (*r) {
		(*r)->left = (*r)->right = 0;
		(*r)->key = key;
	}
	return *r;
}

static void rec(const struct node *r, void (*action)(const void *, VISIT, int), int d) {
	if (r == 0)
		return;
	if (r->left == 0 && r->right == 0)
		action(r, leaf, d);
	else {
		action(r, preorder, d);
		rec(r->left, action, d+1);
		action(r, postorder, d);
		rec(r->right, action, d+1);
		action(r, endorder, d);
	}
}

void twalk(const void *root, void (*action)(const void *, VISIT, int))
{
	rec(root, action, 0);
}