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 */
+tsearch (const void *vkey,              /* key to be located */
-        void **vrootp,                  /* address of tree root */
+         void **vrootp,                 /* address of tree root */
-        int (*compar)(const void *, const void *))
+         int (*compar)(const void *, const void *))
 {
-        node_t *q;
+  node_t *q;
-        node_t **rootp = (node_t **)vrootp;
+  node_t **rootp = (node_t **)vrootp;
-        if (rootp == NULL)
+  if (NULL == rootp)
-                return NULL;
+    return NULL;
-        while (*rootp != NULL) {        /* Knuth's T1: */
+  while (*rootp != NULL)
-                int r;
+    {   /* Knuth's T1: */
+      int r;
-                if ((r = (*compar)(vkey, (*rootp)->key)) == 0)  /* T2: */
-                        return *rootp;          /* we found it! */
+      if ((r = (*compar)(vkey, (*rootp)->key)) == 0)    /* T2: */
+        return *rootp;          /* we found it! */
-                rootp = (r < 0) ?
-                    &(*rootp)->llink :          /* T3: follow left branch */
+      rootp = (r < 0) ?
-                    &(*rootp)->rlink;           /* T4: follow right branch */
+        &(*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 */
+  q = malloc (sizeof(node_t));          /* T5: key not found */
-                *rootp = q;                     /* link new node to old */
+  if (q)
-                q->key = vkey;          /* initialize new node */
+    {                           /* make new node */
-                q->llink = q->rlink = NULL;
+      *rootp = q;                       /* link new node to old */
-        }
+      q->key = vkey;            /* initialize new node */
-        return q;
+      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 */
+tfind (const void *vkey,         /* key to be found */
-      void * const *vrootp,     /* address of the tree root */
+       void * const *vrootp,     /* address of the tree root */
-      int (*compar)(const void *, const void *))
+       int (*compar)(const void *, const void *))
 {
-        node_t * const *rootp = (node_t * const*)vrootp;
+  node_t * const *rootp = (node_t * const*)vrootp;
-        if (rootp == NULL)
+  if (NULL == rootp)
-                return NULL;
+    return NULL;
-        while (*rootp != NULL) {                /* T1: */
+  while (*rootp != NULL)
-                int r;
+    {           /* T1: */
+      int r;
-                if ((r = (*compar)(vkey, (*rootp)->key)) == 0)  /* T2: */
-                        return *rootp;          /* key found */
+      if ((r = (*compar)(vkey, (*rootp)->key)) == 0)    /* T2: */
-                rootp = (r < 0) ?
+        return *rootp;          /* key found */
-                    &(*rootp)->llink :          /* T3: follow left branch */
+      rootp = (r < 0) ?
-                    &(*rootp)->rlink;           /* T4: follow right branch */
+        &(*rootp)->llink :              /* T3: follow left branch */
-        }
+        &(*rootp)->rlink;               /* T4: follow right branch */
-        return NULL;
+    }
+  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,
+tdelete (const void * __restrict vkey,
-    int (*compar)(const void *, const void *))
+         void ** __restrict vrootp,
+         int (*compar)(const void *, const void *))
 {
-        node_t **rootp = (node_t **)vrootp;
+  node_t **rootp = (node_t **)vrootp;
-        node_t *p, *q, *r;
+  node_t *p;
-        int cmp;
+  node_t *q;
+  node_t *r;
-        if (rootp == NULL || (p = *rootp) == NULL)
+  int cmp;
-                return NULL;
+  if (rootp == NULL || (p = *rootp) == NULL)
-        while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0) {
+    return NULL;
-                p = *rootp;
-                rootp = (cmp < 0) ?
+  while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0)
-                    &(*rootp)->llink :          /* follow llink branch */
+    {
-                    &(*rootp)->rlink;           /* follow rlink branch */
+      p = *rootp;
-                if (*rootp == NULL)
+      rootp = (cmp < 0) ?
-                        return NULL;            /* key not found */
+        &(*rootp)->llink :              /* follow llink branch */
-        }
+        &(*rootp)->rlink;               /* follow rlink branch */
-        r = (*rootp)->rlink;                    /* D1: */
+      if (*rootp == NULL)
-        if ((q = (*rootp)->llink) == NULL)      /* Left NULL? */
+        return NULL;            /* key not found */
-                q = r;
+    }
-        else if (r != NULL) {                   /* Right link is NULL? */
+  r = (*rootp)->rlink;                  /* D1: */
-                if (r->llink == NULL) {         /* D2: Find successor */
+  if ((q = (*rootp)->llink) == NULL)    /* Left NULL? */
-                        r->llink = q;
+    {
-                        q = r;
+      q = r;
-                } else {                        /* D3: Find NULL link */
+    }
-                        for (q = r->llink; q->llink != NULL; q = r->llink)
+  else if (r != NULL)
-                                r = q;
+    {                   /* Right link is NULL? */
-                        r->llink = q->rlink;
+      if (r->llink == NULL)
-                        q->llink = (*rootp)->llink;
+        {               /* D2: Find successor */
-                        q->rlink = (*rootp)->rlink;
+          r->llink = q;
-                }
+          q = r;
-        }
+        }
-        free(*rootp);                           /* D4: Free node */
+      else
-        *rootp = q;                             /* link parent to new node */
+        {                       /* D3: Find NULL link */
-        return p;
+          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 */

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 @@
12	#include "tsearch.h"	12	#include "tsearch.h"
13	#include <stdlib.h>	13	#include <stdlib.h>
14		14
15	typedef struct node {	15
		16	typedef struct node
		17	{
16	const void *key;	18	const void *key;
17	struct node llink, rlink;	19	struct node *llink;
		20	struct node *rlink;
18	} node_t;	21	} node_t;
19		22
		23
20	/* $NetBSD: tsearch.c,v 1.5 2005/11/29 03:12:00 christos Exp $ */	24	/* $NetBSD: tsearch.c,v 1.5 2005/11/29 03:12:00 christos Exp $ */
21	/* find or insert datum into search tree */	25	/* find or insert datum into search tree */
22	void *	26	void *
23	tsearch(const void vkey, / key to be located */	27	tsearch (const void vkey, / key to be located */
24	void *vrootp, / address of tree root */	28	void *vrootp, / address of tree root */
25	int (compar)(const void , const void *))	29	int (compar)(const void , const void *))
26	{	30	{
27	node_t *q;	31	node_t *q;
28	node_t rootp = (node_t )vrootp;	32	node_t rootp = (node_t )vrootp;
29		33
30	if (rootp == NULL)	34	if (NULL == rootp)
31	return NULL;	35	return NULL;
32		36
33	while (rootp != NULL) { / Knuth's T1: */	37	while (*rootp != NULL)
34	int r;	38	{ /* Knuth's T1: */
35		39	int r;
36	if ((r = (compar)(vkey, (rootp)->key)) == 0) /* T2: */	40
37	return rootp; / we found it! */	41	if ((r = (compar)(vkey, (rootp)->key)) == 0) /* T2: */
38		42	return rootp; / we found it! */
39	rootp = (r < 0) ?	43
40	&(rootp)->llink : / T3: follow left branch */	44	rootp = (r < 0) ?
41	&(rootp)->rlink; / T4: follow right branch */	45	&(rootp)->llink : / T3: follow left branch */
42	}	46	&(rootp)->rlink; / T4: follow right branch */
43		47	}
44	q = malloc(sizeof(node_t)); /* T5: key not found */	48
45	if (q) { /* make new node */	49	q = malloc (sizeof(node_t)); /* T5: key not found */
46	rootp = q; / link new node to old */	50	if (q)
47	q->key = vkey; /* initialize new node */	51	{ /* make new node */
48	q->llink = q->rlink = NULL;	52	rootp = q; / link new node to old */
49	}	53	q->key = vkey; /* initialize new node */
50	return q;	54	q->llink = q->rlink = NULL;
		55	}
		56	return q;
51	}	57	}
52		58
		59
53	/* $NetBSD: tfind.c,v 1.5 2005/03/23 08:16:53 kleink Exp $ */	60	/* $NetBSD: tfind.c,v 1.5 2005/03/23 08:16:53 kleink Exp $ */
54	/* find a node, or return NULL */	61	/* find a node, or return NULL */
55	void *	62	void *
56	tfind(const void vkey, / key to be found */	63	tfind (const void vkey, / key to be found */
57	void * const vrootp, / address of the tree root */	64	void * const vrootp, / address of the tree root */
58	int (compar)(const void , const void *))	65	int (compar)(const void , const void *))
59	{	66	{
60	node_t * const rootp = (node_t const*)vrootp;	67	node_t * const rootp = (node_t const*)vrootp;
61		68
62	if (rootp == NULL)	69	if (NULL == rootp)
63	return NULL;	70	return NULL;
64		71
65	while (rootp != NULL) { / T1: */	72	while (*rootp != NULL)
66	int r;	73	{ /* T1: */
67		74	int r;
68	if ((r = (compar)(vkey, (rootp)->key)) == 0) /* T2: */	75
69	return rootp; / key found */	76	if ((r = (compar)(vkey, (rootp)->key)) == 0) /* T2: */
70	rootp = (r < 0) ?	77	return rootp; / key found */
71	&(rootp)->llink : / T3: follow left branch */	78	rootp = (r < 0) ?
72	&(rootp)->rlink; / T4: follow right branch */	79	&(rootp)->llink : / T3: follow left branch */
73	}	80	&(rootp)->rlink; / T4: follow right branch */
74	return NULL;	81	}
		82	return NULL;
75	}	83	}
76		84
		85
77	/* $NetBSD: tdelete.c,v 1.2 1999/09/16 11:45:37 lukem Exp $ */	86	/* $NetBSD: tdelete.c,v 1.2 1999/09/16 11:45:37 lukem Exp $ */
78	/*	87	/*
79	* delete node with given key	88	* delete node with given key
@@ -83,42 +92,52 @@ tfind(const void vkey, / key to be found */
83	* compar: function to carry out node comparisons	92	* compar: function to carry out node comparisons
84	*/	93	*/
85	void *	94	void *
86	tdelete(const void * __restrict vkey, void ** __restrict vrootp,	95	tdelete (const void * __restrict vkey,
87	int (compar)(const void , const void *))	96	void ** __restrict vrootp,
		97	int (compar)(const void , const void *))
88	{	98	{
89	node_t rootp = (node_t )vrootp;	99	node_t rootp = (node_t )vrootp;
90	node_t p, q, *r;	100	node_t *p;
91	int cmp;	101	node_t *q;
92		102	node_t *r;
93	if (rootp == NULL \|\| (p = *rootp) == NULL)	103	int cmp;
94	return NULL;	104
95		105	if (rootp == NULL \|\| (p = *rootp) == NULL)
96	while ((cmp = (compar)(vkey, (rootp)->key)) != 0) {	106	return NULL;
97	p = *rootp;	107
98	rootp = (cmp < 0) ?	108	while ((cmp = (compar)(vkey, (rootp)->key)) != 0)
99	&(rootp)->llink : / follow llink branch */	109	{
100	&(rootp)->rlink; / follow rlink branch */	110	p = *rootp;
101	if (*rootp == NULL)	111	rootp = (cmp < 0) ?
102	return NULL; /* key not found */	112	&(rootp)->llink : / follow llink branch */
103	}	113	&(rootp)->rlink; / follow rlink branch */
104	r = (rootp)->rlink; / D1: */	114	if (*rootp == NULL)
105	if ((q = (rootp)->llink) == NULL) / Left NULL? */	115	return NULL; /* key not found */
106	q = r;	116	}
107	else if (r != NULL) { /* Right link is NULL? */	117	r = (rootp)->rlink; / D1: */
108	if (r->llink == NULL) { /* D2: Find successor */	118	if ((q = (rootp)->llink) == NULL) / Left NULL? */
109	r->llink = q;	119	{
110	q = r;	120	q = r;
111	} else { /* D3: Find NULL link */	121	}
112	for (q = r->llink; q->llink != NULL; q = r->llink)	122	else if (r != NULL)
113	r = q;	123	{ /* Right link is NULL? */
114	r->llink = q->rlink;	124	if (r->llink == NULL)
115	q->llink = (*rootp)->llink;	125	{ /* D2: Find successor */
116	q->rlink = (*rootp)->rlink;	126	r->llink = q;
117	}	127	q = r;
118	}	128	}
119	free(rootp); / D4: Free node */	129	else
120	rootp = q; / link parent to new node */	130	{ /* D3: Find NULL link */
121	return p;	131	for (q = r->llink; q->llink != NULL; q = r->llink)
		132	r = q;
		133	r->llink = q->rlink;
		134	q->llink = (*rootp)->llink;
		135	q->rlink = (*rootp)->rlink;
		136	}
		137	}
		138	free(rootp); / D4: Free node */
		139	rootp = q; / link parent to new node */
		140	return p;
122	}	141	}
123		142
124	/* end of tsearch.c */	143	/* end of tsearch.c */