source: vendor/current/source3/lib/adt_tree.c

Last change on this file was 988, checked in by Silvan Scherrer, 9 years ago

Samba Server: update vendor to version 4.4.3
File size: 10.2 KB
Line 
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
23struct 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
31struct sorted_tree {
32 struct tree_node *root;
33};
34
35/**************************************************************************
36 *************************************************************************/
37
38static bool trim_tree_keypath( char *path, char **base, char **new_path )
39{
40 char *p;
41
42 *new_path = *base = NULL;
43
44 if ( !path )
45 return False;
46
47 *base = path;
48
49 p = strchr( path, '\\' );
50
51 if ( p ) {
52 *p = '\0';
53 *new_path = p+1;
54 }
55
56 return True;
57}
58
59/**************************************************************************
60 Initialize the tree's root.
61 *************************************************************************/
62
63struct sorted_tree *pathtree_init(void *data_p)
64{
65 struct sorted_tree *tree = NULL;
66
67 tree = talloc_zero(NULL, struct sorted_tree);
68 if (tree == NULL) {
69 return NULL;
70 }
71
72 tree->root = talloc_zero(tree, struct tree_node);
73 if (tree->root == NULL) {
74 TALLOC_FREE( tree );
75 return NULL;
76 }
77
78 tree->root->data_p = data_p;
79
80 return tree;
81}
82
83
84/**************************************************************************
85 Find the next child given a key string
86 *************************************************************************/
87
88static struct tree_node *pathtree_birth_child(struct tree_node *node,
89 char* key )
90{
91 struct tree_node *infant = NULL;
92 struct tree_node **siblings;
93 int i;
94
95 infant = talloc_zero(node, struct tree_node);
96 if (infant == NULL) {
97 return NULL;
98 }
99
100 infant->key = talloc_strdup( infant, key );
101 infant->parent = node;
102
103 siblings = talloc_realloc(node, node->children, struct tree_node *,
104 node->num_children+1);
105
106 if ( siblings )
107 node->children = siblings;
108
109 node->num_children++;
110
111 /* first child */
112
113 if ( node->num_children == 1 ) {
114 DEBUG(11,("pathtree_birth_child: First child of node [%s]! [%s]\n",
115 node->key ? node->key : "NULL", infant->key ));
116 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 for ( i = node->num_children-1; i>=1; i-- )
130 {
131 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 if ( strcasecmp_m( infant->key, node->children[i-1]->key ) > 0 ) {
138 DEBUG(11,("pathtree_birth_child: storing infant in i == [%d]\n",
139 i));
140 node->children[i] = infant;
141 break;
142 }
143
144 /* bump everything towards the end on slot */
145
146 node->children[i] = node->children[i-1];
147 }
148
149 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 if ( i == 0 )
155 node->children[0] = infant;
156 }
157
158 return infant;
159}
160
161/**************************************************************************
162 Find the next child given a key string
163 *************************************************************************/
164
165static struct tree_node *pathtree_find_child(struct tree_node *node,
166 char *key )
167{
168 struct tree_node *next = NULL;
169 int i, result;
170
171 if ( !node ) {
172 DEBUG(0,("pathtree_find_child: NULL node passed into function!\n"));
173 return NULL;
174 }
175
176 if ( !key ) {
177 DEBUG(0,("pathtree_find_child: NULL key string passed into function!\n"));
178 return NULL;
179 }
180
181 for ( i=0; i<node->num_children; i++ )
182 {
183 DEBUG(11,("pathtree_find_child: child key => [%s]\n",
184 node->children[i]->key));
185
186 result = strcasecmp_m( node->children[i]->key, key );
187
188 if ( result == 0 )
189 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 if ( result > 0 )
196 break;
197 }
198
199 DEBUG(11,("pathtree_find_child: %s [%s]\n",
200 next ? "Found" : "Did not find", key ));
201
202 return next;
203}
204
205/**************************************************************************
206 Add a new node into the tree given a key path and a blob of data
207 *************************************************************************/
208
209bool 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 bool ret = true;
214
215 DEBUG(8,("pathtree_add: Enter\n"));
216
217 if ( !path || *path != '\\' ) {
218 DEBUG(0,("pathtree_add: Attempt to add a node with a bad path [%s]\n",
219 path ? path : "NULL" ));
220 return false;
221 }
222
223 if ( !tree ) {
224 DEBUG(0,("pathtree_add: Attempt to add a node to an uninitialized tree!\n"));
225 return false;
226 }
227
228 /* move past the first '\\' */
229
230 path++;
231 path2 = SMB_STRDUP( path );
232 if ( !path2 ) {
233 DEBUG(0,("pathtree_add: strdup() failed on string [%s]!?!?!\n", path));
234 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 base = path2;
245 str = path2;
246 current = tree->root;
247
248 do {
249 /* break off the remaining part of the path */
250
251 str = strchr( str, '\\' );
252 if ( str )
253 *str = '\0';
254
255 /* iterate to the next child--birth it if necessary */
256
257 next = pathtree_find_child( current, base );
258 if ( !next ) {
259 next = pathtree_birth_child( current, base );
260 if ( !next ) {
261 DEBUG(0,("pathtree_add: Failed to create new child!\n"));
262 ret = false;
263 goto done;
264 }
265 }
266 current = next;
267
268 /* setup the next part of the path */
269
270 base = str;
271 if ( base ) {
272 *base = '\\';
273 base++;
274 str = base;
275 }
276
277 } while ( base != NULL );
278
279 current->data_p = data_p;
280
281 DEBUG(10,("pathtree_add: Successfully added node [%s] to tree\n",
282 path ));
283
284 DEBUG(8,("pathtree_add: Exit\n"));
285
286done:
287 SAFE_FREE( path2 );
288 return ret;
289}
290
291
292/**************************************************************************
293 Recursive routine to print out all children of a struct tree_node
294 *************************************************************************/
295
296static 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 char *path2 = NULL;
304
305 if ( !node )
306 return;
307
308 if ( node->key )
309 DEBUG(debug,("%s: [%s] (%s)\n", path ? path : "NULL", node->key,
310 node->data_p ? "data" : "NULL" ));
311
312 if ( path ) {
313 path2 = talloc_strdup(ctx, path);
314 if (!path2) {
315 return;
316 }
317 }
318
319 path2 = talloc_asprintf(ctx,
320 "%s%s/",
321 path ? path : "",
322 node->key ? node->key : "NULL");
323 if (!path2) {
324 return;
325 }
326
327 num_children = node->num_children;
328 for ( i=0; i<num_children; i++ ) {
329 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
337void pathtree_print_keys(struct sorted_tree *tree, int debug )
338{
339 int i;
340 int num_children = tree->root->num_children;
341
342 if ( tree->root->key )
343 DEBUG(debug,("ROOT/: [%s] (%s)\n", tree->root->key,
344 tree->root->data_p ? "data" : "NULL" ));
345
346 for ( i=0; i<num_children; i++ ) {
347 TALLOC_CTX *ctx = talloc_stackframe();
348 pathtree_print_children(ctx, tree->root->children[i], debug,
349 tree->root->key ? tree->root->key : "ROOT/" );
350 TALLOC_FREE(ctx);
351 }
352
353}
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
361void* pathtree_find(struct sorted_tree *tree, char *key )
362{
363 char *keystr, *base = NULL, *str = NULL, *p;
364 struct tree_node *current;
365 void *result = NULL;
366
367 DEBUG(10,("pathtree_find: Enter [%s]\n", key ? key : "NULL" ));
368
369 /* sanity checks first */
370
371 if ( !key ) {
372 DEBUG(0,("pathtree_find: Attempt to search tree using NULL search string!\n"));
373 return NULL;
374 }
375
376 if ( !tree ) {
377 DEBUG(0,("pathtree_find: Attempt to search an uninitialized tree using string [%s]!\n",
378 key ? key : "NULL" ));
379 return NULL;
380 }
381
382 if ( !tree->root )
383 return NULL;
384
385 /* make a copy to play with */
386
387 if ( *key == '\\' )
388 keystr = SMB_STRDUP( key+1 );
389 else
390 keystr = SMB_STRDUP( key );
391
392 if ( !keystr ) {
393 DEBUG(0,("pathtree_find: strdup() failed on string [%s]!?!?!\n", key));
394 return NULL;
395 }
396
397 /* start breaking the path apart */
398
399 p = keystr;
400 current = tree->root;
401
402 if ( tree->root->data_p )
403 result = tree->root->data_p;
404
405 do
406 {
407 /* break off the remaining part of the path */
408
409 trim_tree_keypath( p, &base, &str );
410
411 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 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 if ( current && current->data_p )
426 result = current->data_p;
427
428 /* reset the path pointer 'p' to the remaining part of the key string */
429
430 p = str;
431
432 } while ( str && current );
433
434 /* result should be the data_p from the lowest match node in the tree */
435 if ( result )
436 DEBUG(11,("pathtree_find: Found data_p!\n"));
437
438 SAFE_FREE( keystr );
439
440 DEBUG(10,("pathtree_find: Exit\n"));
441
442 return result;
443}
444
445
Note: See TracBrowser for help on using the repository browser.