linsys: use vlc_strerror_c()
[vlc.git] / compat / tdestroy.c
1 /*****************************************************************************
2  * tdestroy.c : implement every t* fuctions
3  *****************************************************************************/
4
5 #ifdef HAVE_CONFIG_H
6 # include <config.h>
7 #endif
8
9 /** search.h is not present so every t* functions has to be implemented */
10 #ifndef HAVE_SEARCH_H
11
12 #include <assert.h>
13 #include <stdlib.h>
14
15 typedef struct node {
16     char         *key;
17     struct node  *llink, *rlink;
18 } node_t;
19
20 /*      $NetBSD: tdelete.c,v 1.4 2006/03/19 01:12:08 christos Exp $     */
21
22 /*
23  * Tree search generalized from Knuth (6.2.2) Algorithm T just like
24  * the AT&T man page says.
25  *
26  * The node_t structure is for internal use only, lint doesn't grok it.
27  *
28  * Written by reading the System V Interface Definition, not the code.
29  *
30  * Totally public domain.
31  */
32
33 /* delete node with given key */
34 void *
35 tdelete(vkey, vrootp, compar)
36         const void *vkey;       /* key to be deleted */
37         void      **vrootp;     /* address of the root of tree */
38         int       (*compar) (const void *, const void *);
39 {
40         node_t **rootp = (node_t **)vrootp;
41         node_t *p, *q, *r;
42         int  cmp;
43
44         assert(vkey != NULL);
45         assert(compar != NULL);
46
47         if (rootp == NULL || (p = *rootp) == NULL)
48                 return NULL;
49
50         while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0) {
51                 p = *rootp;
52                 rootp = (cmp < 0) ?
53                     &(*rootp)->llink :          /* follow llink branch */
54                     &(*rootp)->rlink;           /* follow rlink branch */
55                 if (*rootp == NULL)
56                         return NULL;            /* key not found */
57         }
58         r = (*rootp)->rlink;                    /* D1: */
59         if ((q = (*rootp)->llink) == NULL)      /* Left NULL? */
60                 q = r;
61         else if (r != NULL) {                   /* Right link is NULL? */
62                 if (r->llink == NULL) {         /* D2: Find successor */
63                         r->llink = q;
64                         q = r;
65                 } else {                        /* D3: Find NULL link */
66                         for (q = r->llink; q->llink != NULL; q = r->llink)
67                                 r = q;
68                         r->llink = q->rlink;
69                         q->llink = (*rootp)->llink;
70                         q->rlink = (*rootp)->rlink;
71                 }
72         }
73         if (p != *rootp)
74                 free(*rootp);                   /* D4: Free node */
75         *rootp = q;                             /* link parent to new node */
76         return p;
77 }
78
79
80 /*      $NetBSD: tdestroy.c,v 1.2 1999/09/16 11:45:37 lukem Exp $       */
81
82 /*
83  * Tree search generalized from Knuth (6.2.2) Algorithm T just like
84  * the AT&T man page says.
85  *
86  * The node_t structure is for internal use only, lint doesn't grok it.
87  *
88  * Written by reading the System V Interface Definition, not the code.
89  *
90  * Totally public domain.
91  */
92
93 /* Walk the nodes of a tree */
94 static void
95 tdestroy_recurse(node_t* root, void (*free_action)(void *))
96 {
97   if (root->llink != NULL)
98     tdestroy_recurse(root->llink, free_action);
99   if (root->rlink != NULL)
100     tdestroy_recurse(root->rlink, free_action);
101
102   (*free_action) ((void *) root->key);
103   free(root);
104 }
105
106 void
107 tdestroy(vrootp, freefct)
108        void *vrootp;
109        void (*freefct)(void *);
110 {
111   node_t *root = (node_t *) vrootp;
112
113   if (root != NULL)
114     tdestroy_recurse(root, freefct);
115 }
116
117
118 /*      $NetBSD: tfind.c,v 1.5 2005/03/23 08:16:53 kleink Exp $ */
119
120 /*
121  * Tree search generalized from Knuth (6.2.2) Algorithm T just like
122  * the AT&T man page says.
123  *
124  * The node_t structure is for internal use only, lint doesn't grok it.
125  *
126  * Written by reading the System V Interface Definition, not the code.
127  *
128  * Totally public domain.
129  */
130
131 /* find a node, or return 0 */
132 void *
133 tfind(vkey, vrootp, compar)
134         const void *vkey;               /* key to be found */
135         const void **vrootp;            /* address of the tree root */
136         int (*compar) (const void *, const void *);
137 {
138         node_t * const *rootp = (node_t * const*)vrootp;
139
140         assert(vkey != NULL);
141         assert(compar != NULL);
142
143         if (rootp == NULL)
144                 return NULL;
145
146         while (*rootp != NULL) {                /* T1: */
147                 int r;
148
149                 if ((r = (*compar)(vkey, (*rootp)->key)) == 0)  /* T2: */
150                         return *rootp;          /* key found */
151                 rootp = (r < 0) ?
152                     &(*rootp)->llink :          /* T3: follow left branch */
153                     &(*rootp)->rlink;           /* T4: follow right branch */
154         }
155         return NULL;
156 }
157
158
159 /*      $NetBSD: tsearch.c,v 1.5 2005/11/29 03:12:00 christos Exp $     */
160
161 /*
162  * Tree search generalized from Knuth (6.2.2) Algorithm T just like
163  * the AT&T man page says.
164  *
165  * The node_t structure is for internal use only, lint doesn't grok it.
166  *
167  * Written by reading the System V Interface Definition, not the code.
168  *
169  * Totally public domain.
170  */
171
172 /* find or insert datum into search tree */
173 void *
174 tsearch(vkey, vrootp, compar)
175         const void *vkey;               /* key to be located */
176         void **vrootp;                  /* address of tree root */
177         int (*compar) (const void *, const void *);
178 {
179         node_t *q;
180         node_t **rootp = (node_t **)vrootp;
181
182         assert(vkey != NULL);
183         assert(compar != NULL);
184
185         if (rootp == NULL)
186                 return NULL;
187
188         while (*rootp != NULL) {        /* Knuth's T1: */
189                 int r;
190
191                 if ((r = (*compar)(vkey, (*rootp)->key)) == 0)  /* T2: */
192                         return *rootp;          /* we found it! */
193
194                 rootp = (r < 0) ?
195                     &(*rootp)->llink :          /* T3: follow left branch */
196                     &(*rootp)->rlink;           /* T4: follow right branch */
197         }
198
199         q = malloc(sizeof(node_t));             /* T5: key not found */
200         if (q != 0) {                           /* make new node */
201                 *rootp = q;                     /* link new node to old */
202                 q->key = (void*)vkey;   /* initialize new node */
203                 q->llink = q->rlink = NULL;
204         }
205         return q;
206 }
207
208
209 /*      $NetBSD: twalk.c,v 1.2 1999/09/16 11:45:37 lukem Exp $  */
210
211 /*
212  * Tree search generalized from Knuth (6.2.2) Algorithm T just like
213  * the AT&T man page says.
214  *
215  * The node_t structure is for internal use only, lint doesn't grok it.
216  *
217  * Written by reading the System V Interface Definition, not the code.
218  *
219  * Totally public domain.
220  */
221
222 /* Walk the nodes of a tree */
223 static void
224 twalk_recurse(root, action, level)
225         const node_t *root;     /* Root of the tree to be walked */
226         void (*action) (const void *, VISIT, int);
227         int level;
228 {
229         assert(root != NULL);
230         assert(action != NULL);
231
232         if (root->llink == NULL && root->rlink == NULL)
233                 (*action)(root, leaf, level);
234         else {
235                 (*action)(root, preorder, level);
236                 if (root->llink != NULL)
237                         twalk_recurse(root->llink, action, level + 1);
238                 (*action)(root, postorder, level);
239                 if (root->rlink != NULL)
240                         twalk_recurse(root->rlink, action, level + 1);
241                 (*action)(root, endorder, level);
242         }
243 }
244
245 /* Walk the nodes of a tree */
246 void
247 twalk(vroot, action)
248         const void *vroot;      /* Root of the tree to be walked */
249         void (*action) (const void *, VISIT, int);
250 {
251         if (vroot != NULL && action != NULL)
252                 twalk_recurse(vroot, action, 0);
253 }
254
255 #endif // HAVE_SEARCH_H