1 /*
2 OWFS -- One-Wire filesystem
3 OWHTTPD -- One-Wire Web Server
4 Written 2003 Paul H Alfille
5 email: paul.alfille@gmail.com
6 Released under the GPL
7 See the header file: ow.h for full attribution
8 1wire/iButton system from Dallas Semiconductor
9 */
10
11 #include <config.h>
12 #include "owfs_config.h"
13 #include "ow.h"
14
15
16 #ifndef HAVE_STRSEP
17 /*-
18 * Copyright (c) 1990, 1993
19 * The Regents of the University of California. All rights reserved.
20 *
21 * Redistribution and use in source and binary forms, with or without
22 * modification, are permitted provided that the following conditions
23 * are met:
24 * 1. Redistributions of source code must retain the above copyright
25 * notice, this list of conditions and the following disclaimer.
26 * 2. Redistributions in binary form must reproduce the above copyright
27 * notice, this list of conditions and the following disclaimer in the
28 * documentation and/or other materials provided with the distribution.
29 * 3. Neither the name of the University nor the names of its contributors
30 * may be used to endorse or promote products derived from this software
31 * without specific prior written permission.
32 *
33 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
34 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
35 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
36 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
37 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
38 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
39 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
40 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
41 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
42 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
43 * SUCH DAMAGE.
44 */
45
46 /*
47 * Get next token from string *stringp, where tokens are possibly-empty
48 * strings separated by characters from delim.
49 *
50 * Writes NULs into the string at *stringp to end tokens.
51 * delim need not remain constant from call to call.
52 * On return, *stringp points past the last NUL written (if there might
53 * be further tokens), or is NULL (if there are definitely no more tokens).
54 *
55 * If *stringp is NULL, strsep returns NULL.
56 */
strsep(char ** stringp,const char * delim)57 char *strsep(char **stringp, const char *delim)
58 {
59 char *s;
60 const char *spanp;
61 int c, sc;
62 char *tok;
63
64 if ((s = *stringp) == NULL) {
65 return (NULL);
66 }
67 for (tok = s;;) {
68 c = *s++;
69 spanp = delim;
70 do {
71 if ((sc = *spanp++) == c) {
72 if (c == 0) {
73 s = NULL;
74 } else {
75 s[-1] = 0;
76 }
77 *stringp = s;
78 return (tok);
79 }
80 } while (sc != 0);
81 }
82 /* NOTREACHED */
83 }
84
85 #endif /* !defined(HAVE_STRSEP) */
86
87
88 #ifndef HAVE_TDESTROY
89 /*
90 uClibc older than 0.9.19 is missing tdestroy() (don't know exactly when
91 it was added) I added a replacement to this, just to be able to compile
92 owfs for WRT54G without any patched uClibc.
93 */
94
95 #ifndef NODE_T_DEFINED
96 #define NODE_T_DEFINED
97 typedef struct node_t {
98 void *key;
99 struct node_t *left, *right;
100 } node;
101 #endif
102
tdestroy_recurse_(node * root,void (* freefct)(void *))103 static void tdestroy_recurse_(node * root, void (*freefct) (void *))
104 {
105 if (root->left != NULL) {
106 tdestroy_recurse_(root->left, freefct);
107 }
108 if (root->right != NULL) {
109 tdestroy_recurse_(root->right, freefct);
110 }
111 if (root->key) {
112 (*freefct) ((void *) root->key);
113 //free(root->key);
114 root->key = NULL;
115 }
116 /* Free the node itself. */
117 owfree(root);
118 }
119
tdestroy(void * vroot,void (* freefct)(void *))120 void tdestroy(void *vroot, void (*freefct) (void *))
121 {
122 node *root = (node *) vroot;
123 if (root != NULL) {
124 tdestroy_recurse_(root, freefct);
125 }
126 }
127 #endif /* HAVE_TDESTROY */
128
129 #ifndef HAVE_TSEARCH
130 #ifndef NODE_T_DEFINED
131 #define NODE_T_DEFINED
132 typedef struct node_t {
133 void *key;
134 struct node_t *left, *right;
135 } node;
136 #endif
137
138 /* find or insert datum into search tree.
139 char *key; key to be located
140 register node **rootp; address of tree root
141 int (*compar)(); ordering function
142 */
143
tsearch(__const void * key,void ** vrootp,__compar_fn_t compar)144 void *tsearch(__const void *key, void **vrootp, __compar_fn_t compar)
145 {
146 register node *q;
147 register node **rootp = (node **) vrootp;
148
149 if (rootp == (struct node_t **) 0) {
150 return ((struct node_t *) 0);
151 }
152 while (*rootp != (struct node_t *) 0) { /* Knuth's T1: */
153 int r;
154
155 if ((r = (*compar) (key, (*rootp)->key)) == 0) { /* T2: */
156 return (*rootp); /* we found it! */
157 }
158 rootp = (r < 0) ? &(*rootp)->left : /* T3: follow left tree branch */
159 &(*rootp)->right; /* T4: follow right tree branch */
160 }
161 q = (node *) owmalloc(sizeof(node)); /* T5: key not found */
162 if (q != (struct node_t *) 0) { /* make new node */
163 *rootp = q; /* link new node to old */
164 q->key = (void *) key; /* initialize new node */
165 q->left = q->right = (struct node_t *) 0;
166 }
167 return (q);
168 }
169 #endif
170
171 #ifndef HAVE_TFIND
172 #ifndef NODE_T_DEFINED
173 #define NODE_T_DEFINED
174 typedef struct node_t {
175 void *key;
176 struct node_t *left, *right;
177 } node;
178 #endif
179
tfind(__const void * key,void * __const * vrootp,__compar_fn_t compar)180 void *tfind(__const void *key, void *__const * vrootp, __compar_fn_t compar)
181 {
182 register node **rootp = (node **) vrootp;
183
184 if (rootp == (struct node_t **) 0) {
185 return ((struct node_t *) 0);
186 }
187 while (*rootp != (struct node_t *) 0) { /* Knuth's T1: */
188 int r;
189
190 if ((r = (*compar) (key, (*rootp)->key)) == 0) { /* T2: */
191 return (*rootp); /* we found it! */
192 }
193 rootp = (r < 0) ? &(*rootp)->left : /* T3: follow left tree branch */
194 &(*rootp)->right; /* T4: follow right tree branch */
195 }
196 return NULL;
197 }
198 #endif
199
200 #ifndef HAVE_TFIND
201 #ifndef NODE_T_DEFINED
202 #define NODE_T_DEFINED
203 typedef struct node_t {
204 void *key;
205 struct node_t *left, *right;
206 } node;
207 #endif
208 /* delete node with given key
209 char *key; key to be deleted
210 register node **rootp; address of the root of tree
211 int (*compar)(); comparison function
212 */
tdelete(__const void * key,void ** vrootp,__compar_fn_t compar)213 void *tdelete(__const void *key, void **vrootp, __compar_fn_t compar)
214 {
215 node *p;
216 register node *q;
217 register node *r;
218 int cmp;
219 register node **rootp = (node **) vrootp;
220
221 if (rootp == (struct node_t **) 0 || (p = *rootp) == (struct node_t *) 0) {
222 return ((struct node_t *) 0);
223 }
224 while ((cmp = (*compar) (key, (*rootp)->key)) != 0) {
225 p = *rootp;
226 rootp = (cmp < 0) ? &(*rootp)->left : /* follow left tree branch */
227 &(*rootp)->right; /* follow right tree branch */
228 if (*rootp == (struct node_t *) 0) {
229 return ((struct node_t *) 0); /* key not found */
230 }
231 }
232 r = (*rootp)->right; /* D1: */
233 if ((q = (*rootp)->left) == (struct node_t *) 0) { /* Left (struct node_t *)0? */
234 q = r;
235 } else if (r != (struct node_t *) 0) { /* Right link is null? */
236 if (r->left == (struct node_t *) 0) { /* D2: Find successor */
237 r->left = q;
238 q = r;
239 } else { /* D3: Find (struct node_t *)0 link */
240 for (q = r->left; q->left != (struct node_t *) 0; q = r->left)
241 r = q;
242 r->left = q->right;
243 q->left = (*rootp)->left;
244 q->right = (*rootp)->right;
245 }
246 }
247 owfree((struct node_t *) *rootp); /* D4: Free node */
248 *rootp = q; /* link parent to new node */
249 return (p);
250 }
251 #endif
252
253 #ifndef HAVE_TWALK
254 #ifndef NODE_T_DEFINED
255 #define NODE_T_DEFINED
256 typedef struct node_t {
257 void *key;
258 struct node_t *left, *right;
259 } node;
260 #endif
261 /* Walk the nodes of a tree
262 register node *root; Root of the tree to be walked
263 register void (*action)(); Function to be called at each node
264 register int level;
265 */
trecurse(__const void * vroot,__action_fn_t action,int level)266 static void trecurse(__const void *vroot, __action_fn_t action, int level)
267 {
268 register node *root = (node *) vroot;
269
270 if (root->left == (struct node_t *) 0 && root->right == (struct node_t *) 0) {
271 (*action) (root, leaf, level);
272 } else {
273 (*action) (root, preorder, level);
274 if (root->left != (struct node_t *) 0) {
275 trecurse(root->left, action, level + 1);
276 }
277 (*action) (root, postorder, level);
278 if (root->right != (struct node_t *) 0) {
279 trecurse(root->right, action, level + 1);
280 }
281 (*action) (root, endorder, level);
282 }
283 }
284
285 /* void twalk(root, action) Walk the nodes of a tree
286 node *root; Root of the tree to be walked
287 void (*action)(); Function to be called at each node
288 PTR
289 */
twalk(__const void * vroot,__action_fn_t action)290 void twalk(__const void *vroot, __action_fn_t action)
291 {
292 register __const node *root = (node *) vroot;
293
294 if (root != (node *) 0 && action != (__action_fn_t) 0) {
295 trecurse(root, action, 0);
296 }
297 }
298 #endif
299