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 for (tok = s;;) {
67 c = *s++;
68 spanp = delim;
69 do {
70 if ((sc = *spanp++) == c) {
71 if (c == 0)
72 s = NULL;
73 else
74 s[-1] = 0;
75 *stringp = s;
76 return (tok);
77 }
78 } while (sc != 0);
79 }
80 /* NOTREACHED */
81 }
82
83 #endif /* !defined(HAVE_STRSEP) */
84
85
86 #ifndef HAVE_TDESTROY
87 /*
88 uClibc older than 0.9.19 is missing tdestroy() (don't know exactly when
89 it was added) I added a replacement to this, just to be able to compile
90 owfs for WRT54G without any patched uClibc.
91 */
92
93 #ifndef NODE_T_DEFINED
94 #define NODE_T_DEFINED
95 typedef struct node_t {
96 void *key;
97 struct node_t *left, *right;
98 } node;
99 #endif
100
tdestroy_recurse_(node * root,void (* freefct)(void *))101 static void tdestroy_recurse_(node * root, void (*freefct) (void *))
102 {
103 if (root->left != NULL)
104 tdestroy_recurse_(root->left, freefct);
105 if (root->right != NULL)
106 tdestroy_recurse_(root->right, freefct);
107 if (root->key) {
108 (*freefct) ((void *) root->key);
109 //free(root->key);
110 root->key = NULL;
111 }
112 /* Free the node itself. */
113 free(root);
114 }
115
tdestroy(void * vroot,void (* freefct)(void *))116 void tdestroy(void *vroot, void (*freefct) (void *))
117 {
118 node *root = (node *) vroot;
119 if (root != NULL) {
120 tdestroy_recurse_(root, freefct);
121 }
122 }
123 #endif /* HAVE_TDESTROY */
124
125 #ifndef HAVE_TSEARCH
126 #ifndef NODE_T_DEFINED
127 #define NODE_T_DEFINED
128 typedef struct node_t {
129 void *key;
130 struct node_t *left, *right;
131 } node;
132 #endif
133
134 /* find or insert datum into search tree.
135 char *key; key to be located
136 register node **rootp; address of tree root
137 int (*compar)(); ordering function
138 */
139
tsearch(__const void * key,void ** vrootp,__compar_fn_t compar)140 void *tsearch(__const void *key, void **vrootp, __compar_fn_t compar)
141 {
142 register node *q;
143 register node **rootp = (node **) vrootp;
144
145 if (rootp == (struct node_t **) 0)
146 return ((struct node_t *) 0);
147 while (*rootp != (struct node_t *) 0) { /* Knuth's T1: */
148 int r;
149
150 if ((r = (*compar) (key, (*rootp)->key)) == 0) /* T2: */
151 return (*rootp); /* we found it! */
152 rootp = (r < 0) ? &(*rootp)->left : /* T3: follow left branch */
153 &(*rootp)->right; /* T4: follow right branch */
154 }
155 q = (node *) malloc(sizeof(node)); /* T5: key not found */
156 if (q != (struct node_t *) 0) { /* make new node */
157 *rootp = q; /* link new node to old */
158 q->key = (void *) key; /* initialize new node */
159 q->left = q->right = (struct node_t *) 0;
160 }
161 return (q);
162 }
163 #endif
164
165 #ifndef HAVE_TFIND
166 #ifndef NODE_T_DEFINED
167 #define NODE_T_DEFINED
168 typedef struct node_t {
169 void *key;
170 struct node_t *left, *right;
171 } node;
172 #endif
173
tfind(__const void * key,void * __const * vrootp,__compar_fn_t compar)174 void *tfind(__const void *key, void *__const * vrootp, __compar_fn_t compar)
175 {
176 register node **rootp = (node **) vrootp;
177
178 if (rootp == (struct node_t **) 0)
179 return ((struct node_t *) 0);
180 while (*rootp != (struct node_t *) 0) { /* Knuth's T1: */
181 int r;
182
183 if ((r = (*compar) (key, (*rootp)->key)) == 0) /* T2: */
184 return (*rootp); /* we found it! */
185 rootp = (r < 0) ? &(*rootp)->left : /* T3: follow left branch */
186 &(*rootp)->right; /* T4: follow right branch */
187 }
188 return NULL;
189 }
190 #endif
191
192 #ifndef HAVE_TFIND
193 #ifndef NODE_T_DEFINED
194 #define NODE_T_DEFINED
195 typedef struct node_t {
196 void *key;
197 struct node_t *left, *right;
198 } node;
199 #endif
200 /* delete node with given key
201 char *key; key to be deleted
202 register node **rootp; address of the root of tree
203 int (*compar)(); comparison function
204 */
tdelete(__const void * key,void ** vrootp,__compar_fn_t compar)205 void *tdelete(__const void *key, void **vrootp, __compar_fn_t compar)
206 {
207 node *p;
208 register node *q;
209 register node *r;
210 int cmp;
211 register node **rootp = (node **) vrootp;
212
213 if (rootp == (struct node_t **) 0 || (p = *rootp) == (struct node_t *) 0)
214 return ((struct node_t *) 0);
215 while ((cmp = (*compar) (key, (*rootp)->key)) != 0) {
216 p = *rootp;
217 rootp = (cmp < 0) ? &(*rootp)->left : /* follow left branch */
218 &(*rootp)->right; /* follow right branch */
219 if (*rootp == (struct node_t *) 0)
220 return ((struct node_t *) 0); /* key not found */
221 }
222 r = (*rootp)->right; /* D1: */
223 if ((q = (*rootp)->left) == (struct node_t *) 0) /* Left (struct node_t *)0? */
224 q = r;
225 else if (r != (struct node_t *) 0) { /* Right link is null? */
226 if (r->left == (struct node_t *) 0) { /* D2: Find successor */
227 r->left = q;
228 q = r;
229 } else { /* D3: Find (struct node_t *)0 link */
230 for (q = r->left; q->left != (struct node_t *) 0; q = r->left)
231 r = q;
232 r->left = q->right;
233 q->left = (*rootp)->left;
234 q->right = (*rootp)->right;
235 }
236 }
237 free((struct node_t *) *rootp); /* D4: Free node */
238 *rootp = q; /* link parent to new node */
239 return (p);
240 }
241 #endif
242
243 #ifndef HAVE_TWALK
244 #ifndef NODE_T_DEFINED
245 #define NODE_T_DEFINED
246 typedef struct node_t {
247 void *key;
248 struct node_t *left, *right;
249 } node;
250 #endif
251 /* Walk the nodes of a tree
252 register node *root; Root of the tree to be walked
253 register void (*action)(); Function to be called at each node
254 register int level;
255 */
trecurse(__const void * vroot,__action_fn_t action,int level)256 static void trecurse(__const void *vroot, __action_fn_t action, int level)
257 {
258 register node *root = (node *) vroot;
259
260 if (root->left == (struct node_t *) 0 && root->right == (struct node_t *) 0)
261 (*action) (root, leaf, level);
262 else {
263 (*action) (root, preorder, level);
264 if (root->left != (struct node_t *) 0)
265 trecurse(root->left, action, level + 1);
266 (*action) (root, postorder, level);
267 if (root->right != (struct node_t *) 0)
268 trecurse(root->right, action, level + 1);
269 (*action) (root, endorder, level);
270 }
271 }
272
273 /* void twalk(root, action) Walk the nodes of a tree
274 node *root; Root of the tree to be walked
275 void (*action)(); Function to be called at each node
276 PTR
277 */
twalk(__const void * vroot,__action_fn_t action)278 void twalk(__const void *vroot, __action_fn_t action)
279 {
280 register __const node *root = (node *) vroot;
281
282 if (root != (node *) 0 && action != (__action_fn_t) 0)
283 trecurse(root, action, 0);
284 }
285 #endif
286