source: branches/samba-3.2.x/source/lib/adt_tree.c

Last change on this file was 133, checked in by Paul Smedley, 17 years ago

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