1 /*
2 * Copyright (c) 2014 Dave Vasilevsky <dave@vasilevsky.ca>
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR
15 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
16 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
17 * IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT,
18 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
19 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
20 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
21 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25 #include "traverse.h"
26
27 #include "fs.h"
28
29 #include <stdlib.h>
30 #include <string.h>
31
32
33 #define TRAVERSE_PATH_SEPARATOR "/"
34
35 /* Default initial capacity of trv.path */
36 #define TRAVERSE_DEFAULT_PATH_CAP 32
37
38
39 enum {
40 /* These states may be set on entry to sqfs_traverse_next(), with real
41 work to do. */
42 TRAVERSE_DESCEND, /* Descend into the current entry (a dir) */
43 TRAVERSE_NAME_REMOVE, /* Remove the name from the end of the stored path */
44
45 /* End states */
46 TRAVERSE_ERROR,
47 TRAVERSE_FINISHED,
48
49 /* Internal */
50 TRAVERSE_ASCEND, /* Done with a directory, ascend a level */
51 TRAVERSE_NAME_ADD, /* Add a name to the end of the stored path */
52 TRAVERSE_GET_ENTRY /* Get the next entry at the same level */
53 } sqfs_traverse_state;
54
55 /* The struct stored in trv.stack */
56 typedef struct {
57 sqfs_dir dir;
58 size_t name_size;
59 } sqfs_traverse_level;
60
61
62 /* Make our structure safe */
63 static void sqfs_traverse_init(sqfs_traverse *trv);
64
65 /* Path manipulation functions */
66 static sqfs_err sqfs_traverse_path_init(sqfs_traverse *trv);
67 static sqfs_err sqfs_traverse_path_add(sqfs_traverse *trv,
68 const char *str, size_t size);
69 static sqfs_err sqfs_traverse_path_add_name(sqfs_traverse *trv);
70 static sqfs_err sqfs_traverse_path_add_sep(sqfs_traverse *trv);
71 static void sqfs_traverse_path_remove(sqfs_traverse *trv, size_t size);
72 static void sqfs_traverse_path_remove_name(sqfs_traverse *trv);
73 static void sqfs_traverse_path_remove_sep(sqfs_traverse *trv);
74 /* Set the size of the last path component */
75 static void sqfs_traverse_path_set_name_size(sqfs_traverse *trv, size_t size);
76 /* Add nul-terminator */
77 static void sqfs_traverse_path_terminate(sqfs_traverse *trv);
78
79 /* Descend into new directories, and ascend back */
80 static sqfs_err sqfs_traverse_descend_inode(sqfs_traverse *trv,
81 sqfs_inode *inode);
82 static sqfs_err sqfs_traverse_descend(sqfs_traverse *trv, sqfs_inode_id iid);
83 static sqfs_err sqfs_traverse_ascend(sqfs_traverse *trv);
84
85
sqfs_traverse_init(sqfs_traverse * trv)86 static void sqfs_traverse_init(sqfs_traverse *trv) {
87 sqfs_dentry_init(&trv->entry, trv->namebuf);
88 sqfs_stack_init(&trv->stack);
89 trv->state = TRAVERSE_ERROR;
90 trv->path = NULL;
91 }
92
sqfs_traverse_open_inode(sqfs_traverse * trv,sqfs * fs,sqfs_inode * inode)93 sqfs_err sqfs_traverse_open_inode(sqfs_traverse *trv, sqfs *fs,
94 sqfs_inode *inode) {
95 sqfs_err err;
96
97 sqfs_traverse_init(trv);
98 if ((err = sqfs_traverse_path_init(trv)))
99 goto error;
100 err = sqfs_stack_create(&trv->stack, sizeof(sqfs_traverse_level), 0, NULL);
101 if (err)
102 goto error;
103
104 trv->fs = fs;
105 if ((err = sqfs_traverse_descend_inode(trv, inode)))
106 goto error;
107
108 sqfs_traverse_path_set_name_size(trv, 0); /* The root has no name */
109 trv->state = TRAVERSE_NAME_REMOVE;
110 return SQFS_OK;
111
112 error:
113 sqfs_traverse_close(trv);
114 return err;
115 }
116
sqfs_traverse_open(sqfs_traverse * trv,sqfs * fs,sqfs_inode_id iid)117 sqfs_err sqfs_traverse_open(sqfs_traverse *trv, sqfs *fs, sqfs_inode_id iid) {
118 sqfs_err err;
119 sqfs_inode inode;
120
121 if ((err = sqfs_inode_get(fs, &inode, iid)))
122 return err;
123
124 return sqfs_traverse_open_inode(trv, fs, &inode);
125 }
126
sqfs_traverse_close(sqfs_traverse * trv)127 void sqfs_traverse_close(sqfs_traverse *trv) {
128 sqfs_stack_destroy(&trv->stack);
129 free(trv->path);
130 sqfs_traverse_init(trv);
131 }
132
133
sqfs_traverse_next(sqfs_traverse * trv,sqfs_err * err)134 bool sqfs_traverse_next(sqfs_traverse *trv, sqfs_err *err) {
135 sqfs_traverse_level *level;
136 bool found;
137
138 *err = SQFS_OK;
139 while (true) {
140 switch (trv->state) {
141 case TRAVERSE_GET_ENTRY:
142 if ((*err = sqfs_stack_top(&trv->stack, &level)))
143 goto error;
144
145 found = sqfs_dir_next(trv->fs, &level->dir, &trv->entry, err);
146 if (*err)
147 goto error;
148 if (found)
149 trv->state = TRAVERSE_NAME_ADD;
150 else
151 trv->state = TRAVERSE_ASCEND;
152 break;
153
154 case TRAVERSE_NAME_ADD:
155 if ((*err = sqfs_traverse_path_add_name(trv)))
156 goto error;
157 if (sqfs_dentry_is_dir(&trv->entry))
158 trv->state = TRAVERSE_DESCEND;
159 else
160 trv->state = TRAVERSE_NAME_REMOVE;
161 trv->dir_end = false;
162 return true;
163
164 case TRAVERSE_NAME_REMOVE:
165 sqfs_traverse_path_remove_name(trv);
166 trv->state = TRAVERSE_GET_ENTRY;
167 break;
168
169 case TRAVERSE_DESCEND:
170 *err = sqfs_traverse_descend(trv, sqfs_dentry_inode(&trv->entry));
171 if (*err)
172 goto error;
173 trv->state = TRAVERSE_GET_ENTRY;
174 break;
175
176 case TRAVERSE_ASCEND:
177 if ((*err = sqfs_traverse_ascend(trv)))
178 goto error;
179 if (sqfs_stack_size(&trv->stack) > 0) {
180 trv->dir_end = true;
181 trv->state = TRAVERSE_NAME_REMOVE;
182 return true;
183 }
184 trv->state = TRAVERSE_FINISHED;
185 break;
186
187 case TRAVERSE_FINISHED:
188 return false;
189
190 case TRAVERSE_ERROR:
191 *err = SQFS_ERR;
192 goto error;
193 }
194 }
195
196 error:
197 trv->state = TRAVERSE_ERROR;
198 return false;
199 }
200
sqfs_traverse_prune(sqfs_traverse * trv)201 sqfs_err sqfs_traverse_prune(sqfs_traverse *trv) {
202 trv->state = TRAVERSE_NAME_REMOVE;
203 return SQFS_OK;
204 }
205
206
sqfs_traverse_path_init(sqfs_traverse * trv)207 static sqfs_err sqfs_traverse_path_init(sqfs_traverse *trv) {
208 trv->path_cap = TRAVERSE_DEFAULT_PATH_CAP;
209 if (!(trv->path = malloc(trv->path_cap)))
210 return SQFS_ERR;
211 trv->path[0] = '\0';
212 trv->path_size = 1; /* includes nul-terminator */
213 return SQFS_OK;
214 }
215
sqfs_traverse_path_terminate(sqfs_traverse * trv)216 static void sqfs_traverse_path_terminate(sqfs_traverse *trv) {
217 trv->path[trv->path_size - 1] = '\0';
218 }
219
sqfs_traverse_path_add(sqfs_traverse * trv,const char * str,size_t size)220 static sqfs_err sqfs_traverse_path_add(sqfs_traverse *trv,
221 const char *str, size_t size) {
222 size_t need = trv->path_size + size;
223 if (need > trv->path_cap) {
224 char *next_path;
225 size_t next_cap = trv->path_cap;
226 while (need > next_cap)
227 next_cap *= 2;
228
229 if (!(next_path = realloc(trv->path, next_cap)))
230 return SQFS_ERR;
231
232 trv->path = next_path;
233 trv->path_cap = next_cap;
234 }
235
236 memcpy(trv->path + trv->path_size - 1, str, size);
237 trv->path_size = need;
238 sqfs_traverse_path_terminate(trv);
239 return SQFS_OK;
240 }
241
sqfs_traverse_path_remove(sqfs_traverse * trv,size_t size)242 static void sqfs_traverse_path_remove(sqfs_traverse *trv, size_t size) {
243 if (trv->path_size > size)
244 trv->path_size -= size;
245 else
246 trv->path_size = 1; /* only nul terminator left */
247
248 sqfs_traverse_path_terminate(trv);
249 }
250
sqfs_traverse_path_add_name(sqfs_traverse * trv)251 static sqfs_err sqfs_traverse_path_add_name(sqfs_traverse *trv) {
252 trv->path_last_size = sqfs_dentry_name_size(&trv->entry);
253 return sqfs_traverse_path_add(trv, sqfs_dentry_name(&trv->entry),
254 trv->path_last_size);
255 }
256
sqfs_traverse_path_add_sep(sqfs_traverse * trv)257 static sqfs_err sqfs_traverse_path_add_sep(sqfs_traverse *trv) {
258 return sqfs_traverse_path_add(trv, TRAVERSE_PATH_SEPARATOR,
259 strlen(TRAVERSE_PATH_SEPARATOR));
260 }
261
sqfs_traverse_path_remove_name(sqfs_traverse * trv)262 static void sqfs_traverse_path_remove_name(sqfs_traverse *trv) {
263 sqfs_traverse_path_remove(trv, trv->path_last_size);
264 }
265
sqfs_traverse_path_remove_sep(sqfs_traverse * trv)266 static void sqfs_traverse_path_remove_sep(sqfs_traverse *trv) {
267 sqfs_traverse_path_remove(trv, strlen(TRAVERSE_PATH_SEPARATOR));
268 }
269
sqfs_traverse_path_set_name_size(sqfs_traverse * trv,size_t size)270 static void sqfs_traverse_path_set_name_size(sqfs_traverse *trv, size_t size) {
271 trv->path_last_size = size;
272 }
273
274
sqfs_traverse_descend_inode(sqfs_traverse * trv,sqfs_inode * inode)275 static sqfs_err sqfs_traverse_descend_inode(sqfs_traverse *trv,
276 sqfs_inode *inode) {
277 sqfs_err err;
278 sqfs_traverse_level *level;
279 bool initial;
280
281 initial = (sqfs_stack_size(&trv->stack) == 0);
282
283 if ((err = sqfs_stack_push(&trv->stack, &level)))
284 return err;
285 if ((err = sqfs_dir_open(trv->fs, inode, &level->dir, 0)))
286 return err;
287
288 if (initial) {
289 /* Don't add the separator or store the size for the root directory */
290 level->name_size = 0;
291 } else {
292 level->name_size = sqfs_dentry_name_size(&trv->entry);
293 if ((err = sqfs_traverse_path_add_sep(trv)))
294 return err;
295 }
296
297 return err;
298 }
299
sqfs_traverse_descend(sqfs_traverse * trv,sqfs_inode_id iid)300 static sqfs_err sqfs_traverse_descend(sqfs_traverse *trv, sqfs_inode_id iid) {
301 sqfs_err err;
302 sqfs_inode inode;
303
304 if ((err = sqfs_inode_get(trv->fs, &inode, iid)))
305 return err;
306
307 return sqfs_traverse_descend_inode(trv, &inode);
308 }
309
sqfs_traverse_ascend(sqfs_traverse * trv)310 static sqfs_err sqfs_traverse_ascend(sqfs_traverse *trv) {
311 sqfs_err err;
312 sqfs_traverse_level *level;
313
314 if ((err = sqfs_stack_top(&trv->stack, &level)))
315 return err;
316
317 sqfs_traverse_path_remove_sep(trv); /* safe even if initial */
318 sqfs_traverse_path_set_name_size(trv, level->name_size);
319
320 sqfs_stack_pop(&trv->stack);
321 return SQFS_OK;
322 }
323