source: branches/samba-3.0/source/lib/adt_tree.c

Last change on this file was 1, checked in by Paul Smedley, 18 years ago

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