Line data Source code
1 : /*
2 : * Unix SMB/CIFS implementation.
3 : * Generic Abstract Data Types
4 : * Copyright (C) Gerald Carter 2002.
5 : *
6 : * This program is free software; you can redistribute it and/or modify
7 : * it under the terms of the GNU General Public License as published by
8 : * the Free Software Foundation; either version 3 of the License, or
9 : * (at your option) any later version.
10 : *
11 : * This program is distributed in the hope that it will be useful,
12 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : * GNU General Public License for more details.
15 : *
16 : * You should have received a copy of the GNU General Public License
17 : * along with this program; if not, see <http://www.gnu.org/licenses/>.
18 : */
19 :
20 : #include "includes.h"
21 : #include "adt_tree.h"
22 :
23 : struct tree_node {
24 : struct tree_node *parent;
25 : struct tree_node **children;
26 : int num_children;
27 : char *key;
28 : void *data_p;
29 : };
30 :
31 : struct sorted_tree {
32 : struct tree_node *root;
33 : };
34 :
35 : /**************************************************************************
36 : *************************************************************************/
37 :
38 947397 : static bool trim_tree_keypath( char *path, char **base, char **new_path )
39 : {
40 : char *p;
41 :
42 947397 : *new_path = *base = NULL;
43 :
44 947397 : if ( !path )
45 0 : return False;
46 :
47 947397 : *base = path;
48 :
49 947397 : p = strchr( path, '\\' );
50 :
51 947397 : if ( p ) {
52 757591 : *p = '\0';
53 757591 : *new_path = p+1;
54 : }
55 :
56 947397 : return True;
57 : }
58 :
59 : /**************************************************************************
60 : Initialize the tree's root.
61 : *************************************************************************/
62 :
63 128 : struct sorted_tree *pathtree_init(void *data_p)
64 : {
65 128 : struct sorted_tree *tree = NULL;
66 :
67 128 : tree = talloc_zero(NULL, struct sorted_tree);
68 128 : if (tree == NULL) {
69 0 : return NULL;
70 : }
71 :
72 128 : tree->root = talloc_zero(tree, struct tree_node);
73 128 : if (tree->root == NULL) {
74 0 : TALLOC_FREE( tree );
75 0 : return NULL;
76 : }
77 :
78 128 : tree->root->data_p = data_p;
79 :
80 128 : return tree;
81 : }
82 :
83 :
84 : /**************************************************************************
85 : Find the next child given a key string
86 : *************************************************************************/
87 :
88 1942 : static struct tree_node *pathtree_birth_child(struct tree_node *node,
89 : char* key )
90 : {
91 1942 : struct tree_node *infant = NULL;
92 : struct tree_node **siblings;
93 : int i;
94 :
95 1942 : infant = talloc_zero(node, struct tree_node);
96 1942 : if (infant == NULL) {
97 0 : return NULL;
98 : }
99 :
100 1942 : infant->key = talloc_strdup( infant, key );
101 1942 : infant->parent = node;
102 :
103 1942 : siblings = talloc_realloc(node, node->children, struct tree_node *,
104 : node->num_children+1);
105 :
106 1942 : if ( siblings )
107 1942 : node->children = siblings;
108 :
109 1942 : node->num_children++;
110 :
111 : /* first child */
112 :
113 1942 : if ( node->num_children == 1 ) {
114 1292 : DEBUG(11,("pathtree_birth_child: First child of node [%s]! [%s]\n",
115 : node->key ? node->key : "NULL", infant->key ));
116 1292 : node->children[0] = infant;
117 : }
118 : else
119 : {
120 : /*
121 : * multiple siblings .... (at least 2 children)
122 : *
123 : * work from the end of the list forward
124 : * The last child is not set at this point
125 : * Insert the new infanct in ascending order
126 : * from left to right
127 : */
128 :
129 975 : for ( i = node->num_children-1; i>=1; i-- )
130 : {
131 715 : DEBUG(11,("pathtree_birth_child: Looking for crib; infant -> [%s], child -> [%s]\n",
132 : infant->key, node->children[i-1]->key));
133 :
134 : /* the strings should never match assuming that we
135 : have called pathtree_find_child() first */
136 :
137 715 : if ( strcasecmp_m( infant->key, node->children[i-1]->key ) > 0 ) {
138 390 : DEBUG(11,("pathtree_birth_child: storing infant in i == [%d]\n",
139 : i));
140 390 : node->children[i] = infant;
141 390 : break;
142 : }
143 :
144 : /* bump everything towards the end on slot */
145 :
146 325 : node->children[i] = node->children[i-1];
147 : }
148 :
149 650 : DEBUG(11,("pathtree_birth_child: Exiting loop (i == [%d])\n", i ));
150 :
151 : /* if we haven't found the correct slot yet, the child
152 : will be first in the list */
153 :
154 650 : if ( i == 0 )
155 260 : node->children[0] = infant;
156 : }
157 :
158 1942 : return infant;
159 : }
160 :
161 : /**************************************************************************
162 : Find the next child given a key string
163 : *************************************************************************/
164 :
165 952018 : static struct tree_node *pathtree_find_child(struct tree_node *node,
166 : char *key )
167 : {
168 952018 : struct tree_node *next = NULL;
169 : int i, result;
170 :
171 952018 : if ( !node ) {
172 0 : DEBUG(0,("pathtree_find_child: NULL node passed into function!\n"));
173 0 : return NULL;
174 : }
175 :
176 952018 : if ( !key ) {
177 0 : DEBUG(0,("pathtree_find_child: NULL key string passed into function!\n"));
178 0 : return NULL;
179 : }
180 :
181 1868472 : for ( i=0; i<node->num_children; i++ )
182 : {
183 1221000 : DEBUG(11,("pathtree_find_child: child key => [%s]\n",
184 : node->children[i]->key));
185 :
186 1221000 : result = strcasecmp_m( node->children[i]->key, key );
187 :
188 1221000 : if ( result == 0 )
189 761376 : next = node->children[i];
190 :
191 : /* if result > 0 then we've gone to far because
192 : the list of children is sorted by key name
193 : If result == 0, then we have a match */
194 :
195 1221000 : if ( result > 0 )
196 304546 : break;
197 : }
198 :
199 952018 : DEBUG(11,("pathtree_find_child: %s [%s]\n",
200 : next ? "Found" : "Did not find", key ));
201 :
202 952018 : return next;
203 : }
204 :
205 : /**************************************************************************
206 : Add a new node into the tree given a key path and a blob of data
207 : *************************************************************************/
208 :
209 879 : bool pathtree_add(struct sorted_tree *tree, const char *path, void *data_p)
210 : {
211 : char *str, *base, *path2;
212 : struct tree_node *current, *next;
213 879 : bool ret = true;
214 :
215 879 : DEBUG(8,("pathtree_add: Enter\n"));
216 :
217 879 : if ( !path || *path != '\\' ) {
218 0 : DEBUG(0,("pathtree_add: Attempt to add a node with a bad path [%s]\n",
219 : path ? path : "NULL" ));
220 0 : return false;
221 : }
222 :
223 879 : if ( !tree ) {
224 0 : DEBUG(0,("pathtree_add: Attempt to add a node to an uninitialized tree!\n"));
225 0 : return false;
226 : }
227 :
228 : /* move past the first '\\' */
229 :
230 879 : path++;
231 879 : path2 = SMB_STRDUP( path );
232 879 : if ( !path2 ) {
233 0 : DEBUG(0,("pathtree_add: strdup() failed on string [%s]!?!?!\n", path));
234 0 : return false;
235 : }
236 :
237 :
238 : /*
239 : * this works sort of like a 'mkdir -p' call, possibly
240 : * creating an entire path to the new node at once
241 : * The path should be of the form /<key1>/<key2>/...
242 : */
243 :
244 879 : base = path2;
245 879 : str = path2;
246 879 : current = tree->root;
247 :
248 : do {
249 : /* break off the remaining part of the path */
250 :
251 4621 : str = strchr( str, '\\' );
252 4621 : if ( str )
253 3742 : *str = '\0';
254 :
255 : /* iterate to the next child--birth it if necessary */
256 :
257 4621 : next = pathtree_find_child( current, base );
258 4621 : if ( !next ) {
259 1942 : next = pathtree_birth_child( current, base );
260 1942 : if ( !next ) {
261 0 : DEBUG(0,("pathtree_add: Failed to create new child!\n"));
262 0 : ret = false;
263 0 : goto done;
264 : }
265 : }
266 4621 : current = next;
267 :
268 : /* setup the next part of the path */
269 :
270 4621 : base = str;
271 4621 : if ( base ) {
272 3742 : *base = '\\';
273 3742 : base++;
274 3742 : str = base;
275 : }
276 :
277 4621 : } while ( base != NULL );
278 :
279 879 : current->data_p = data_p;
280 :
281 879 : DEBUG(10,("pathtree_add: Successfully added node [%s] to tree\n",
282 : path ));
283 :
284 879 : DEBUG(8,("pathtree_add: Exit\n"));
285 :
286 879 : done:
287 879 : SAFE_FREE( path2 );
288 879 : return ret;
289 : }
290 :
291 :
292 : /**************************************************************************
293 : Recursive routine to print out all children of a struct tree_node
294 : *************************************************************************/
295 :
296 0 : static void pathtree_print_children(TALLOC_CTX *ctx,
297 : struct tree_node *node,
298 : int debug,
299 : const char *path )
300 : {
301 : int i;
302 : int num_children;
303 0 : char *path2 = NULL;
304 :
305 0 : if ( !node )
306 0 : return;
307 :
308 0 : if ( node->key )
309 0 : DEBUG(debug,("%s: [%s] (%s)\n", path ? path : "NULL", node->key,
310 : node->data_p ? "data" : "NULL" ));
311 :
312 0 : if ( path ) {
313 0 : path2 = talloc_strdup(ctx, path);
314 0 : if (!path2) {
315 0 : return;
316 : }
317 : }
318 :
319 0 : path2 = talloc_asprintf(ctx,
320 : "%s%s/",
321 : path ? path : "",
322 0 : node->key ? node->key : "NULL");
323 0 : if (!path2) {
324 0 : return;
325 : }
326 :
327 0 : num_children = node->num_children;
328 0 : for ( i=0; i<num_children; i++ ) {
329 0 : pathtree_print_children(ctx, node->children[i], debug, path2 );
330 : }
331 : }
332 :
333 : /**************************************************************************
334 : Dump the kys for a tree to the log file
335 : *************************************************************************/
336 :
337 0 : void pathtree_print_keys(struct sorted_tree *tree, int debug )
338 : {
339 : int i;
340 0 : int num_children = tree->root->num_children;
341 :
342 0 : if ( tree->root->key )
343 0 : DEBUG(debug,("ROOT/: [%s] (%s)\n", tree->root->key,
344 : tree->root->data_p ? "data" : "NULL" ));
345 :
346 0 : for ( i=0; i<num_children; i++ ) {
347 0 : TALLOC_CTX *ctx = talloc_stackframe();
348 0 : pathtree_print_children(ctx, tree->root->children[i], debug,
349 0 : tree->root->key ? tree->root->key : "ROOT/" );
350 0 : TALLOC_FREE(ctx);
351 : }
352 :
353 0 : }
354 :
355 : /**************************************************************************
356 : return the data_p for for the node in tree matching the key string
357 : The key string is the full path. We must break it apart and walk
358 : the tree
359 : *************************************************************************/
360 :
361 190475 : void* pathtree_find(struct sorted_tree *tree, char *key )
362 : {
363 190475 : char *keystr, *base = NULL, *str = NULL, *p;
364 : struct tree_node *current;
365 190475 : void *result = NULL;
366 :
367 190475 : DEBUG(10,("pathtree_find: Enter [%s]\n", key ? key : "NULL" ));
368 :
369 : /* sanity checks first */
370 :
371 190475 : if ( !key ) {
372 0 : DEBUG(0,("pathtree_find: Attempt to search tree using NULL search string!\n"));
373 0 : return NULL;
374 : }
375 :
376 190475 : if ( !tree ) {
377 0 : DEBUG(0,("pathtree_find: Attempt to search an uninitialized tree using string [%s]!\n",
378 : key ? key : "NULL" ));
379 0 : return NULL;
380 : }
381 :
382 190475 : if ( !tree->root )
383 0 : return NULL;
384 :
385 : /* make a copy to play with */
386 :
387 190475 : if ( *key == '\\' )
388 190475 : keystr = SMB_STRDUP( key+1 );
389 : else
390 0 : keystr = SMB_STRDUP( key );
391 :
392 190475 : if ( !keystr ) {
393 0 : DEBUG(0,("pathtree_find: strdup() failed on string [%s]!?!?!\n", key));
394 0 : return NULL;
395 : }
396 :
397 : /* start breaking the path apart */
398 :
399 190475 : p = keystr;
400 190475 : current = tree->root;
401 :
402 190475 : if ( tree->root->data_p )
403 190475 : result = tree->root->data_p;
404 :
405 : do
406 : {
407 : /* break off the remaining part of the path */
408 :
409 947397 : trim_tree_keypath( p, &base, &str );
410 :
411 947397 : DEBUG(11,("pathtree_find: [loop] base => [%s], new_path => [%s]\n",
412 : base ? base : "",
413 : str ? str : ""));
414 :
415 : /* iterate to the next child */
416 :
417 947397 : current = pathtree_find_child( current, base );
418 :
419 : /*
420 : * the idea is that the data_p for a parent should
421 : * be inherited by all children, but allow it to be
422 : * overridden farther down
423 : */
424 :
425 947397 : if ( current && current->data_p )
426 187897 : result = current->data_p;
427 :
428 : /* reset the path pointer 'p' to the remaining part of the key string */
429 :
430 947397 : p = str;
431 :
432 947397 : } while ( str && current );
433 :
434 : /* result should be the data_p from the lowest match node in the tree */
435 190475 : if ( result )
436 190475 : DEBUG(11,("pathtree_find: Found data_p!\n"));
437 :
438 190475 : SAFE_FREE( keystr );
439 :
440 190475 : DEBUG(10,("pathtree_find: Exit\n"));
441 :
442 190475 : return result;
443 : }
444 :
445 :
|
