summaryrefslogtreecommitdiff
path: root/src/microhttpd/tsearch.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/microhttpd/tsearch.c')
-rw-r--r--src/microhttpd/tsearch.c183
1 files changed, 101 insertions, 82 deletions
diff --git a/src/microhttpd/tsearch.c b/src/microhttpd/tsearch.c
index 0c4d3e37..fe5fcd5b 100644
--- a/src/microhttpd/tsearch.c
+++ b/src/microhttpd/tsearch.c
@@ -12,68 +12,77 @@
#include "tsearch.h"
#include <stdlib.h>
-typedef struct node {
+
+typedef struct node
+{
const void *key;
- struct node *llink, *rlink;
+ struct node *llink;
+ struct node *rlink;
} node_t;
+
/* $NetBSD: tsearch.c,v 1.5 2005/11/29 03:12:00 christos Exp $ */
/* find or insert datum into search tree */
void *
-tsearch(const void *vkey, /* key to be located */
- void **vrootp, /* address of tree root */
- int (*compar)(const void *, const void *))
+tsearch (const void *vkey, /* key to be located */
+ void **vrootp, /* address of tree root */
+ int (*compar)(const void *, const void *))
{
- node_t *q;
- node_t **rootp = (node_t **)vrootp;
-
- if (rootp == NULL)
- return NULL;
-
- while (*rootp != NULL) { /* Knuth's T1: */
- int r;
-
- if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */
- return *rootp; /* we found it! */
-
- rootp = (r < 0) ?
- &(*rootp)->llink : /* T3: follow left branch */
- &(*rootp)->rlink; /* T4: follow right branch */
- }
-
- q = malloc(sizeof(node_t)); /* T5: key not found */
- if (q) { /* make new node */
- *rootp = q; /* link new node to old */
- q->key = vkey; /* initialize new node */
- q->llink = q->rlink = NULL;
- }
- return q;
+ node_t *q;
+ node_t **rootp = (node_t **)vrootp;
+
+ if (NULL == rootp)
+ return NULL;
+
+ while (*rootp != NULL)
+ { /* Knuth's T1: */
+ int r;
+
+ if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */
+ return *rootp; /* we found it! */
+
+ rootp = (r < 0) ?
+ &(*rootp)->llink : /* T3: follow left branch */
+ &(*rootp)->rlink; /* T4: follow right branch */
+ }
+
+ q = malloc (sizeof(node_t)); /* T5: key not found */
+ if (q)
+ { /* make new node */
+ *rootp = q; /* link new node to old */
+ q->key = vkey; /* initialize new node */
+ q->llink = q->rlink = NULL;
+ }
+ return q;
}
+
/* $NetBSD: tfind.c,v 1.5 2005/03/23 08:16:53 kleink Exp $ */
/* find a node, or return NULL */
void *
-tfind(const void *vkey, /* key to be found */
- void * const *vrootp, /* address of the tree root */
- int (*compar)(const void *, const void *))
+tfind (const void *vkey, /* key to be found */
+ void * const *vrootp, /* address of the tree root */
+ int (*compar)(const void *, const void *))
{
- node_t * const *rootp = (node_t * const*)vrootp;
-
- if (rootp == NULL)
- return NULL;
-
- while (*rootp != NULL) { /* T1: */
- int r;
-
- if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */
- return *rootp; /* key found */
- rootp = (r < 0) ?
- &(*rootp)->llink : /* T3: follow left branch */
- &(*rootp)->rlink; /* T4: follow right branch */
- }
- return NULL;
+ node_t * const *rootp = (node_t * const*)vrootp;
+
+ if (NULL == rootp)
+ return NULL;
+
+ while (*rootp != NULL)
+ { /* T1: */
+ int r;
+
+ if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */
+ return *rootp; /* key found */
+ rootp = (r < 0) ?
+ &(*rootp)->llink : /* T3: follow left branch */
+ &(*rootp)->rlink; /* T4: follow right branch */
+ }
+ return NULL;
}
+
/* $NetBSD: tdelete.c,v 1.2 1999/09/16 11:45:37 lukem Exp $ */
/*
* delete node with given key
@@ -83,42 +92,52 @@ tfind(const void *vkey, /* key to be found */
* compar: function to carry out node comparisons
*/
void *
-tdelete(const void * __restrict vkey, void ** __restrict vrootp,
- int (*compar)(const void *, const void *))
+tdelete (const void * __restrict vkey,
+ void ** __restrict vrootp,
+ int (*compar)(const void *, const void *))
{
- node_t **rootp = (node_t **)vrootp;
- node_t *p, *q, *r;
- int cmp;
-
- if (rootp == NULL || (p = *rootp) == NULL)
- return NULL;
-
- while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0) {
- p = *rootp;
- rootp = (cmp < 0) ?
- &(*rootp)->llink : /* follow llink branch */
- &(*rootp)->rlink; /* follow rlink branch */
- if (*rootp == NULL)
- return NULL; /* key not found */
- }
- r = (*rootp)->rlink; /* D1: */
- if ((q = (*rootp)->llink) == NULL) /* Left NULL? */
- q = r;
- else if (r != NULL) { /* Right link is NULL? */
- if (r->llink == NULL) { /* D2: Find successor */
- r->llink = q;
- q = r;
- } else { /* D3: Find NULL link */
- for (q = r->llink; q->llink != NULL; q = r->llink)
- r = q;
- r->llink = q->rlink;
- q->llink = (*rootp)->llink;
- q->rlink = (*rootp)->rlink;
- }
- }
- free(*rootp); /* D4: Free node */
- *rootp = q; /* link parent to new node */
- return p;
+ node_t **rootp = (node_t **)vrootp;
+ node_t *p;
+ node_t *q;
+ node_t *r;
+ int cmp;
+
+ if (rootp == NULL || (p = *rootp) == NULL)
+ return NULL;
+
+ while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0)
+ {
+ p = *rootp;
+ rootp = (cmp < 0) ?
+ &(*rootp)->llink : /* follow llink branch */
+ &(*rootp)->rlink; /* follow rlink branch */
+ if (*rootp == NULL)
+ return NULL; /* key not found */
+ }
+ r = (*rootp)->rlink; /* D1: */
+ if ((q = (*rootp)->llink) == NULL) /* Left NULL? */
+ {
+ q = r;
+ }
+ else if (r != NULL)
+ { /* Right link is NULL? */
+ if (r->llink == NULL)
+ { /* D2: Find successor */
+ r->llink = q;
+ q = r;
+ }
+ else
+ { /* D3: Find NULL link */
+ for (q = r->llink; q->llink != NULL; q = r->llink)
+ r = q;
+ r->llink = q->rlink;
+ q->llink = (*rootp)->llink;
+ q->rlink = (*rootp)->rlink;
+ }
+ }
+ free(*rootp); /* D4: Free node */
+ *rootp = q; /* link parent to new node */
+ return p;
}
/* end of tsearch.c */