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