]> git.sur5r.net Git - openldap/blob - servers/slapd/back-bdb/dn2id.c
ITS#2449, broken NOT filters
[openldap] / servers / slapd / back-bdb / dn2id.c
1 /* dn2id.c - routines to deal with the dn2id index */
2 /* $OpenLDAP$ */
3 /*
4  * Copyright 1998-2003 The OpenLDAP Foundation, All Rights Reserved.
5  * COPYING RESTRICTIONS APPLY, see COPYRIGHT file
6  */
7
8 #include "portable.h"
9
10 #include <stdio.h>
11 #include <ac/string.h>
12
13 #include "back-bdb.h"
14 #include "idl.h"
15 #include "lutil.h"
16
17 #ifndef BDB_HIER
18 int
19 bdb_dn2id_add(
20         BackendDB       *be,
21         DB_TXN *txn,
22         struct berval   *pbv,
23         Entry           *e )
24 {
25         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
26         DB *db = bdb->bi_dn2id->bdi_db;
27         int             rc;
28         DBT             key, data;
29         char            *buf;
30         struct berval   ptr, pdn;
31
32 #ifdef NEW_LOGGING
33         LDAP_LOG ( INDEX, ARGS, "bdb_dn2id_add( \"%s\", 0x%08lx )\n",
34                 e->e_ndn, (long) e->e_id, 0 );
35 #else
36         Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id_add( \"%s\", 0x%08lx )\n",
37                 e->e_ndn, (long) e->e_id, 0 );
38 #endif
39         assert( e->e_id != NOID );
40
41         DBTzero( &key );
42         key.size = e->e_nname.bv_len + 2;
43         key.ulen = key.size;
44         key.flags = DB_DBT_USERMEM;
45         buf = ch_malloc( key.size );
46         key.data = buf;
47         buf[0] = DN_BASE_PREFIX;
48         ptr.bv_val = buf + 1;
49         ptr.bv_len = e->e_nname.bv_len;
50         AC_MEMCPY( ptr.bv_val, e->e_nname.bv_val, e->e_nname.bv_len );
51         ptr.bv_val[ptr.bv_len] = '\0';
52
53         DBTzero( &data );
54         data.data = (char *) &e->e_id;
55         data.size = sizeof( e->e_id );
56
57         /* store it -- don't override */
58         rc = db->put( db, txn, &key, &data, DB_NOOVERWRITE );
59         if( rc != 0 ) {
60 #ifdef NEW_LOGGING
61                 LDAP_LOG ( INDEX, ERR, "bdb_dn2id_add: put failed: %s %d\n",
62                         db_strerror(rc), rc, 0 );
63 #else
64                 Debug( LDAP_DEBUG_ANY, "=> bdb_dn2id_add: put failed: %s %d\n",
65                         db_strerror(rc), rc, 0 );
66 #endif
67                 goto done;
68         }
69
70 #ifndef BDB_MULTIPLE_SUFFIXES
71         if( !be_issuffix( be, &ptr )) {
72 #endif
73                 buf[0] = DN_SUBTREE_PREFIX;
74                 rc = db->put( db, txn, &key, &data, DB_NOOVERWRITE );
75                 if( rc != 0 ) {
76 #ifdef NEW_LOGGING
77                         LDAP_LOG ( INDEX, ERR, 
78                                 "=> bdb_dn2id_add: subtree (%s) put failed: %d\n",
79                                 ptr.bv_val, rc, 0 );
80 #else
81                         Debug( LDAP_DEBUG_ANY,
82                         "=> bdb_dn2id_add: subtree (%s) put failed: %d\n",
83                         ptr.bv_val, rc, 0 );
84 #endif
85                         goto done;
86                 }
87                 
88 #ifdef BDB_MULTIPLE_SUFFIXES
89         if( !be_issuffix( be, &ptr )) {
90 #endif
91                 dnParent( &ptr, &pdn );
92         
93                 key.size = pdn.bv_len + 2;
94                 key.ulen = key.size;
95                 pdn.bv_val[-1] = DN_ONE_PREFIX;
96                 key.data = pdn.bv_val-1;
97                 ptr = pdn;
98
99                 rc = bdb_idl_insert_key( be, db, txn, &key, e->e_id );
100
101                 if( rc != 0 ) {
102 #ifdef NEW_LOGGING
103                         LDAP_LOG ( INDEX, ERR, 
104                                 "=> bdb_dn2id_add: parent (%s) insert failed: %d\n",
105                                 ptr.bv_val, rc, 0 );
106 #else
107                         Debug( LDAP_DEBUG_ANY,
108                                 "=> bdb_dn2id_add: parent (%s) insert failed: %d\n",
109                                         ptr.bv_val, rc, 0 );
110 #endif
111                         goto done;
112                 }
113 #ifndef BDB_MULTIPLE_SUFFIXES
114         }
115
116         while( !be_issuffix( be, &ptr )) {
117 #else
118         for (;;) {
119 #endif
120                 ptr.bv_val[-1] = DN_SUBTREE_PREFIX;
121
122                 rc = bdb_idl_insert_key( be, db, txn, &key, e->e_id );
123
124                 if( rc != 0 ) {
125 #ifdef NEW_LOGGING
126                         LDAP_LOG ( INDEX, ERR, 
127                                 "=> bdb_dn2id_add: subtree (%s) insert failed: %d\n",
128                                 ptr.bv_val, rc, 0 );
129 #else
130                         Debug( LDAP_DEBUG_ANY,
131                                 "=> bdb_dn2id_add: subtree (%s) insert failed: %d\n",
132                                         ptr.bv_val, rc, 0 );
133 #endif
134                         break;
135                 }
136 #ifdef BDB_MULTIPLE_SUFFIXES
137                 if( be_issuffix( be, &ptr )) break;
138 #endif
139                 dnParent( &ptr, &pdn );
140
141                 key.size = pdn.bv_len + 2;
142                 key.ulen = key.size;
143                 key.data = pdn.bv_val - 1;
144                 ptr = pdn;
145         }
146 #ifdef BDB_MULTIPLE_SUFFIXES
147         }
148 #endif
149
150 done:
151         ch_free( buf );
152 #ifdef NEW_LOGGING
153         LDAP_LOG ( INDEX, RESULTS, "<= bdb_dn2id_add: %d\n", rc, 0, 0 );
154 #else
155         Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id_add: %d\n", rc, 0, 0 );
156 #endif
157         return rc;
158 }
159
160 int
161 bdb_dn2id_delete(
162         BackendDB       *be,
163         DB_TXN *txn,
164         char    *pdnc,
165         Entry           *e )
166 {
167         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
168         DB *db = bdb->bi_dn2id->bdi_db;
169         int             rc;
170         DBT             key;
171         char            *buf;
172         struct berval   pdn, ptr;
173
174 #ifdef NEW_LOGGING
175         LDAP_LOG ( INDEX, ARGS, 
176                 "=> bdb_dn2id_delete ( \"%s\", 0x%08lx )\n", e->e_ndn, e->e_id, 0);
177 #else
178         Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id_delete( \"%s\", 0x%08lx )\n",
179                 e->e_ndn, e->e_id, 0 );
180 #endif
181
182         DBTzero( &key );
183         key.size = e->e_nname.bv_len + 2;
184         buf = ch_malloc( key.size );
185         key.data = buf;
186         key.flags = DB_DBT_USERMEM;
187         buf[0] = DN_BASE_PREFIX;
188         ptr.bv_val = buf+1;
189         ptr.bv_len = e->e_nname.bv_len;
190         AC_MEMCPY( ptr.bv_val, e->e_nname.bv_val, e->e_nname.bv_len );
191         ptr.bv_val[ptr.bv_len] = '\0';
192
193         /* delete it */
194         rc = db->del( db, txn, &key, 0 );
195         if( rc != 0 ) {
196 #ifdef NEW_LOGGING
197                 LDAP_LOG ( INDEX, ERR, 
198                         "=> bdb_dn2id_delete: delete failed: %s %d\n", 
199                         db_strerror(rc), rc, 0 );
200 #else
201                 Debug( LDAP_DEBUG_ANY, "=> bdb_dn2id_delete: delete failed: %s %d\n",
202                         db_strerror(rc), rc, 0 );
203 #endif
204                 goto done;
205         }
206
207 #ifndef BDB_MULTIPLE_SUFFIXES
208         if( !be_issuffix( be, &ptr )) {
209 #endif
210                 buf[0] = DN_SUBTREE_PREFIX;
211                 rc = db->del( db, txn, &key, 0 );
212                 if( rc != 0 ) {
213 #ifdef NEW_LOGGING
214                         LDAP_LOG ( INDEX, ERR, 
215                                 "=> bdb_dn2id_delete: subtree (%s) delete failed: %d\n", 
216                                 ptr.bv_val, rc, 0 );
217 #else
218                         Debug( LDAP_DEBUG_ANY,
219                         "=> bdb_dn2id_delete: subtree (%s) delete failed: %d\n",
220                         ptr.bv_val, rc, 0 );
221 #endif
222                         goto done;
223                 }
224
225 #ifdef BDB_MULTIPLE_SUFFIXES
226         if( !be_issuffix( be, &ptr )) {
227 #endif
228                 dnParent( &ptr, &pdn );
229
230                 key.size = pdn.bv_len + 2;
231                 key.ulen = key.size;
232                 pdn.bv_val[-1] = DN_ONE_PREFIX;
233                 key.data = pdn.bv_val - 1;
234                 ptr = pdn;
235
236                 rc = bdb_idl_delete_key( be, db, txn, &key, e->e_id );
237
238                 if( rc != 0 ) {
239 #ifdef NEW_LOGGING
240                         LDAP_LOG ( INDEX, ERR, 
241                                 "=> bdb_dn2id_delete: parent (%s) delete failed: %d\n", 
242                                 ptr.bv_val, rc, 0 );
243 #else
244                         Debug( LDAP_DEBUG_ANY,
245                                 "=> bdb_dn2id_delete: parent (%s) delete failed: %d\n",
246                                 ptr.bv_val, rc, 0 );
247 #endif
248                         goto done;
249                 }
250 #ifndef BDB_MULTIPLE_SUFFIXES
251         }
252
253         while( !be_issuffix( be, &ptr )) {
254 #else
255         for (;;) {
256 #endif
257                 ptr.bv_val[-1] = DN_SUBTREE_PREFIX;
258
259                 rc = bdb_idl_delete_key( be, db, txn, &key, e->e_id );
260                 if( rc != 0 ) {
261 #ifdef NEW_LOGGING
262                         LDAP_LOG ( INDEX, ERR, 
263                                 "=> bdb_dn2id_delete: subtree (%s) delete failed: %d\n", 
264                                 ptr.bv_val, rc, 0 );
265 #else
266                         Debug( LDAP_DEBUG_ANY,
267                                 "=> bdb_dn2id_delete: subtree (%s) delete failed: %d\n",
268                                 ptr.bv_val, rc, 0 );
269 #endif
270                         goto done;
271                 }
272 #ifdef BDB_MULTIPLE_SUFFIXES
273                 if( be_issuffix( be, &ptr )) break;
274 #endif
275                 dnParent( &ptr, &pdn );
276
277                 key.size = pdn.bv_len + 2;
278                 key.ulen = key.size;
279                 key.data = pdn.bv_val - 1;
280                 ptr = pdn;
281         }
282 #ifdef BDB_MULTIPLE_SUFFIXES
283         }
284 #endif
285
286 done:
287         ch_free( buf );
288 #ifdef NEW_LOGGING
289         LDAP_LOG ( INDEX, RESULTS, "<= bdb_dn2id_delete %d\n", rc, 0, 0 );
290 #else
291         Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id_delete %d\n", rc, 0, 0 );
292 #endif
293         return rc;
294 }
295
296 int
297 bdb_dn2id(
298         BackendDB       *be,
299         DB_TXN *txn,
300         struct berval   *dn,
301         ID *id,
302         void *ctx )
303 {
304         int             rc;
305         DBT             key, data;
306         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
307         DB *db = bdb->bi_dn2id->bdi_db;
308
309 #ifdef NEW_LOGGING
310         LDAP_LOG ( INDEX, ARGS, "=> bdb_dn2id( \"%s\" )\n", dn->bv_val, 0, 0 );
311 #else
312         Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id( \"%s\" )\n", dn->bv_val, 0, 0 );
313 #endif
314
315         assert (id);
316  
317         DBTzero( &key );
318         key.size = dn->bv_len + 2;
319         key.data = sl_malloc( key.size, ctx );
320         ((char *)key.data)[0] = DN_BASE_PREFIX;
321         AC_MEMCPY( &((char *)key.data)[1], dn->bv_val, key.size - 1 );
322
323         /* store the ID */
324         DBTzero( &data );
325         data.data = id;
326         data.ulen = sizeof(ID);
327         data.flags = DB_DBT_USERMEM;
328
329         /* fetch it */
330         rc = db->get( db, txn, &key, &data, bdb->bi_db_opflags );
331
332         if( rc != 0 ) {
333 #ifdef NEW_LOGGING
334                 LDAP_LOG ( INDEX, ERR, "<= bdb_dn2id: get failed %s (%d)\n", 
335                         db_strerror(rc), rc, 0 );
336 #else
337                 Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id: get failed: %s (%d)\n",
338                         db_strerror( rc ), rc, 0 );
339 #endif
340         } else {
341 #ifdef NEW_LOGGING
342                 LDAP_LOG ( INDEX, RESULTS, 
343                         "<= bdb_dn2id: got id=0x%08lx\n", *id, 0, 0 );
344 #else
345                 Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id: got id=0x%08lx\n",
346                         *id, 0, 0 );
347 #endif
348         }
349
350         sl_free( key.data, ctx );
351         return rc;
352 }
353
354 int
355 bdb_dn2id_children(
356         Operation *op,
357         DB_TXN *txn,
358         Entry *e )
359 {
360         int             rc;
361
362 #ifdef NEW_LOGGING
363         LDAP_LOG ( INDEX, ARGS, 
364                 "=> bdb_dn2id_children( %s )\n", e->e_nname.bv_val, 0, 0 );
365 #else
366         Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id_children( %s )\n",
367                 e->e_nname.bv_val, 0, 0 );
368 #endif
369
370         if ( BEI(e)->bei_kids ) {
371                 rc = 0;
372         }
373         if ( BEI(e)->bei_state & CACHE_ENTRY_NO_KIDS ) {
374                 rc = DB_NOTFOUND;
375         } else {
376
377         DBT             key, data;
378         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
379         DB *db = bdb->bi_dn2id->bdi_db;
380         ID              id;
381
382         DBTzero( &key );
383         key.size = e->e_nname.bv_len + 2;
384         key.data = sl_malloc( key.size, op->o_tmpmemctx );
385         ((char *)key.data)[0] = DN_ONE_PREFIX;
386         AC_MEMCPY( &((char *)key.data)[1], e->e_nname.bv_val, key.size - 1 );
387
388         /* we actually could do a empty get... */
389         DBTzero( &data );
390         data.data = &id;
391         data.ulen = sizeof(id);
392         data.flags = DB_DBT_USERMEM;
393         data.doff = 0;
394         data.dlen = sizeof(id);
395
396         rc = db->get( db, txn, &key, &data, bdb->bi_db_opflags );
397         sl_free( key.data, op->o_tmpmemctx );
398
399         if ( rc == DB_NOTFOUND ) {
400                 BEI(e)->bei_state |= CACHE_ENTRY_NO_KIDS;
401         }
402
403         }
404
405 #ifdef NEW_LOGGING
406         LDAP_LOG ( INDEX, DETAIL1, 
407                 "<= bdb_dn2id_children( %s ): %s (%d)\n", 
408                 e->e_nname.bv_val, rc == 0 ? "" : ( rc == DB_NOTFOUND ? "no " :
409                 db_strerror(rc)), rc );
410 #else
411         Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id_children( %s ): %s (%d)\n",
412                 e->e_nname.bv_val,
413                 rc == 0 ? "" : ( rc == DB_NOTFOUND ? "no " :
414                         db_strerror(rc) ), rc );
415 #endif
416
417         return rc;
418 }
419
420 int
421 bdb_dn2idl(
422         BackendDB       *be,
423         struct berval   *dn,
424         int prefix,
425         ID *ids )
426 {
427         int             rc;
428         DBT             key;
429         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
430         DB *db = bdb->bi_dn2id->bdi_db;
431
432 #ifdef NEW_LOGGING
433         LDAP_LOG ( INDEX, ARGS, 
434                 "=> bdb_dn2ididl( \"%s\" )\n", dn->bv_val, 0, 0 );
435 #else
436         Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2idl( \"%s\" )\n", dn->bv_val, 0, 0 );
437 #endif
438
439 #ifndef BDB_MULTIPLE_SUFFIXES
440         if (prefix == DN_SUBTREE_PREFIX && be_issuffix(be, dn))
441         {
442                 BDB_IDL_ALL(bdb, ids);
443                 return 0;
444         }
445 #endif
446
447         DBTzero( &key );
448         key.size = dn->bv_len + 2;
449         key.ulen = key.size;
450         key.flags = DB_DBT_USERMEM;
451         key.data = ch_malloc( key.size );
452         ((char *)key.data)[0] = prefix;
453         AC_MEMCPY( &((char *)key.data)[1], dn->bv_val, key.size - 1 );
454
455         rc = bdb_idl_fetch_key( be, db, NULL, &key, ids );
456
457         if( rc != 0 ) {
458 #ifdef NEW_LOGGING
459                 LDAP_LOG ( INDEX, ERR, 
460                         "<= bdb_dn2ididl: get failed: %s (%d)\n", db_strerror(rc), rc, 0 );
461 #else
462                 Debug( LDAP_DEBUG_TRACE,
463                         "<= bdb_dn2idl: get failed: %s (%d)\n",
464                         db_strerror( rc ), rc, 0 );
465 #endif
466
467         } else {
468 #ifdef NEW_LOGGING
469                 LDAP_LOG ( INDEX, RESULTS, 
470                         "<= bdb_dn2ididl: id=%ld first=%ld last=%ld\n", 
471                         (long) ids[0], (long) BDB_IDL_FIRST( ids ), 
472                         (long) BDB_IDL_LAST( ids ) );
473 #else
474                 Debug( LDAP_DEBUG_TRACE,
475                         "<= bdb_dn2idl: id=%ld first=%ld last=%ld\n",
476                         (long) ids[0],
477                         (long) BDB_IDL_FIRST( ids ), (long) BDB_IDL_LAST( ids ) );
478 #endif
479         }
480
481         ch_free( key.data );
482         return rc;
483 }
484 #else   /* BDB_HIER */
485
486 /* Experimental management routines for a hierarchically structured backend.
487  *
488  * Unsupported! Use at your own risk!
489  *
490  * Instead of a dn2id database, we use an id2parent database. Each entry in
491  * this database is a struct diskNode, containing the ID of the node's parent
492  * and the RDN of the node.
493  */
494 typedef struct diskNode {
495         ID parent;
496         struct berval rdn;
497         struct berval nrdn;
498 } diskNode;
499
500 /* In bdb_db_open() we call bdb_build_tree() which reads the entire id2parent
501  * database into memory (into an AVL tree). Next we iterate through each node
502  * of this tree, connecting each child to its parent. The nodes in this AVL
503  * tree are a struct idNode. The immediate (Onelevel) children of a node are
504  * referenced in the i_kids AVL tree. With this arrangement, there is no need
505  * to maintain the DN_ONE_PREFIX or DN_SUBTREE_PREFIX database keys. Note that
506  * the DN of an entry is constructed by walking up the list of i_parent
507  * pointers, so no full DN is stored on disk anywhere. This makes modrdn
508  * extremely efficient, even when operating on a populated subtree.
509  *
510  * The idNode tree is searched directly from the root when performing id to
511  * entry lookups. The tree is traversed using the i_kids subtrees when
512  * performing dn to id lookups.
513  */
514 typedef struct idNode {
515         ID i_id;
516         struct idNode *i_parent;
517         diskNode *i_rdn;
518         Avlnode *i_kids;
519         ldap_pvt_thread_rdwr_t i_kids_rdwr;
520 } idNode;
521
522
523 /* The main AVL tree is sorted in ID order. The i_kids AVL trees are
524  * sorted in lexical order. These are the various helper routines used
525  * for the searches and sorts.
526  */
527 static int
528 node_find_cmp(
529         const void *id,
530         const void *node
531 )
532 {
533         return *(const ID *)id - ((const idNode *)node)->i_id;
534 }
535
536 static int
537 node_frdn_cmp(
538         const void *v_nrdn,
539         const void *v_n
540 )
541 {
542         const struct berval *nrdn = v_nrdn;
543         const idNode *n = v_n;
544         return ber_bvcmp(nrdn, &n->i_rdn->nrdn);
545 }
546
547 static int
548 node_add_cmp(
549         const void *v_a,
550         const void *v_b
551 )
552 {
553         const idNode *a = v_a, *b = v_b;
554         return a->i_id - b->i_id;
555 }
556
557 static int
558 node_rdn_cmp(
559         const void *v_a,
560         const void *v_b
561 )
562 {
563         const idNode *a = v_a, *b = v_b;
564         /* should be slightly better without ordering drawbacks */
565         return ber_bvcmp(&a->i_rdn->nrdn, &b->i_rdn->nrdn);
566 }
567
568 idNode * bdb_find_id_node(
569         ID id,
570         Avlnode *tree
571 )
572 {
573         return avl_find(tree, &id, node_find_cmp);
574 }
575
576 idNode * bdb_find_rdn_node(
577         struct berval *nrdn,
578         Avlnode *tree
579 )
580 {
581         return avl_find(tree, nrdn, node_frdn_cmp);
582 }
583
584 /* This function links a node into its parent's i_kids tree. */
585 static int bdb_insert_kid(
586         void *v_a,
587         void *v_tree
588 )
589 {
590         idNode *a = v_a;
591         Avlnode *tree = v_tree;
592         int rc;
593
594         if (a->i_rdn->parent == 0)
595                 return 0;
596         a->i_parent = bdb_find_id_node(a->i_rdn->parent, tree);
597         if (!a->i_parent)
598                 return -1;
599         ldap_pvt_thread_rdwr_wlock(&a->i_parent->i_kids_rdwr);
600         rc = avl_insert( &a->i_parent->i_kids, (caddr_t) a,
601                          node_rdn_cmp, avl_dup_error );
602         ldap_pvt_thread_rdwr_wunlock(&a->i_parent->i_kids_rdwr);
603         return rc;
604 }
605
606 /* This function adds a node into the main AVL tree */
607 idNode *bdb_add_node(
608         ID id,
609         char *d,
610         struct bdb_info *bdb
611 )
612 {
613         idNode *node;
614
615         node = (idNode *)ch_malloc(sizeof(idNode));
616         node->i_id = id;
617         node->i_parent = NULL;
618         node->i_kids = NULL;
619         node->i_rdn = (diskNode *)d;
620         node->i_rdn->rdn.bv_val += (long)d;
621         node->i_rdn->nrdn.bv_val += (long)d;
622         ldap_pvt_thread_rdwr_init(&node->i_kids_rdwr);
623         avl_insert( &bdb->bi_tree, (caddr_t) node, node_add_cmp, avl_dup_error );
624         if (id == 1)
625                 bdb->bi_troot = node;
626         return node;
627 }
628
629 /* This function initializes the trees at startup time. */
630 int bdb_build_tree(
631         Backend *be
632 )
633 {
634         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
635         int rc;
636         DBC *cursor;
637         DBT key, data;
638         ID id;
639         idNode *node;
640
641         bdb->bi_tree = NULL;
642
643         rc = bdb->bi_id2parent->bdi_db->cursor(
644                 bdb->bi_id2parent->bdi_db, NULL, &cursor,
645                 bdb->bi_db_opflags );
646         if( rc != 0 ) {
647                 return NOID;
648         }
649
650         DBTzero( &key );
651         DBTzero( &data );
652         key.data = (char *)&id;
653         key.ulen = sizeof( id );
654         key.flags = DB_DBT_USERMEM;
655         data.flags = DB_DBT_MALLOC;
656
657         while (cursor->c_get( cursor, &key, &data, DB_NEXT ) == 0) {
658                 bdb_add_node( id, data.data, bdb );
659         }
660         cursor->c_close( cursor );
661
662         rc = avl_apply(bdb->bi_tree, bdb_insert_kid, bdb->bi_tree,
663                 -1, AVL_INORDER );
664
665         return rc;
666 }
667
668 /* This function constructs a full DN for a given id. We really should
669  * be passing idNodes directly, to save some effort...
670  */
671 int bdb_fix_dn(
672         BackendDB *be,
673         ID id,
674         Entry *e
675 )
676 {
677         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
678         idNode *n, *o;
679         int rlen, nrlen;
680         char *ptr, *nptr;
681         
682         ldap_pvt_thread_rdwr_rlock(&bdb->bi_tree_rdwr);
683         o = bdb_find_id_node(id, bdb->bi_tree);
684         rlen = be->be_suffix[0].bv_len + 1;
685         nrlen = be->be_nsuffix[0].bv_len + 1;
686         for (n = o; n && n->i_parent; n=n->i_parent) {
687                 rlen += n->i_rdn->rdn.bv_len + 1;
688                 nrlen += n->i_rdn->nrdn.bv_len + 1;
689         }
690         e->e_name.bv_len = rlen - 1;
691         e->e_nname.bv_len = nrlen - 1;
692         e->e_name.bv_val = ch_malloc(rlen + nrlen);
693         e->e_nname.bv_val = e->e_name.bv_val + rlen;
694         ptr = e->e_name.bv_val;
695         nptr = e->e_nname.bv_val;
696         for (n = o; n && n->i_parent; n=n->i_parent) {
697                 ptr = lutil_strcopy(ptr, n->i_rdn->rdn.bv_val);
698                 *ptr++ = ',';
699                 nptr = lutil_strcopy(nptr, n->i_rdn->nrdn.bv_val);
700                 *nptr++ = ',';
701         }
702         ldap_pvt_thread_rdwr_runlock(&bdb->bi_tree_rdwr);
703
704         strcpy(ptr, be->be_suffix[0].bv_val);
705         strcpy(nptr, be->be_nsuffix[0].bv_val);
706
707         return 0;
708 }
709
710 int
711 bdb_dn2id_add(
712         BackendDB       *be,
713         DB_TXN *txn,
714         struct berval   *pdn,
715         Entry           *e )
716 {
717         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
718         int             rc, rlen, nrlen;
719         DBT             key, data;
720         DB *db = bdb->bi_id2parent->bdi_db;
721         diskNode *d;
722         idNode *n;
723
724         nrlen = dn_rdnlen( be, &e->e_nname );
725         if (nrlen) {
726                 rlen = dn_rdnlen( be, &e->e_name );
727         } else {
728                 rlen = 0;
729         }
730
731         d = ch_malloc(sizeof(diskNode) + rlen + nrlen + 2);
732         d->rdn.bv_len = rlen;
733         d->nrdn.bv_len = nrlen;
734         d->rdn.bv_val = (char *)(d+1);
735         d->nrdn.bv_val = d->rdn.bv_val + rlen + 1;
736         strncpy(d->rdn.bv_val, e->e_dn, rlen);
737         d->rdn.bv_val[rlen] = '\0';
738         strncpy(d->nrdn.bv_val, e->e_ndn, nrlen);
739         d->nrdn.bv_val[nrlen] = '\0';
740         d->rdn.bv_val -= (long)d;
741         d->nrdn.bv_val -= (long)d;
742
743         if (pdn->bv_len) {
744                 bdb_dn2id(be, txn, pdn, &d->parent, 0);
745         } else {
746                 d->parent = 0;
747         }
748
749         DBTzero(&key);
750         DBTzero(&data);
751         key.data = &e->e_id;
752         key.size = sizeof(ID);
753         key.flags = DB_DBT_USERMEM;
754
755         data.data = d;
756         data.size = sizeof(diskNode) + rlen + nrlen + 2;
757         data.flags = DB_DBT_USERMEM;
758
759         rc = db->put( db, txn, &key, &data, DB_NOOVERWRITE );
760
761         if (rc == 0) {
762                 ldap_pvt_thread_rdwr_wlock(&bdb->bi_tree_rdwr);
763                 n = bdb_add_node( e->e_id, data.data, bdb);
764                 ldap_pvt_thread_rdwr_wunlock(&bdb->bi_tree_rdwr);
765
766                 if (d->parent) {
767                         ldap_pvt_thread_rdwr_rlock(&bdb->bi_tree_rdwr);
768                         bdb_insert_kid(n, bdb->bi_tree);
769                         ldap_pvt_thread_rdwr_runlock(&bdb->bi_tree_rdwr);
770                 }
771         } else {
772                 free(d);
773         }
774         return rc;
775 }
776
777 int
778 bdb_dn2id_delete(
779         BackendDB       *be,
780         DB_TXN *txn,
781         char    *pdn,
782         Entry   *e )
783 {
784         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
785         int rc;
786         DBT             key;
787         DB *db = bdb->bi_id2parent->bdi_db;
788         idNode *n;
789
790         DBTzero(&key);
791         key.size = sizeof(e->e_id);
792         key.data = &e->e_id;
793
794         rc = db->del( db, txn, &key, 0);
795
796         ldap_pvt_thread_rdwr_wlock(&bdb->bi_tree_rdwr);
797         n = avl_delete(&bdb->bi_tree, &e->e_id, node_find_cmp);
798         if (n) {
799                 if (n->i_parent) {
800                         ldap_pvt_thread_rdwr_wlock(&n->i_parent->i_kids_rdwr);
801                         avl_delete(&n->i_parent->i_kids, &n->i_rdn->nrdn, node_frdn_cmp);
802                         ldap_pvt_thread_rdwr_wunlock(&n->i_parent->i_kids_rdwr);
803                 }
804                 free(n->i_rdn);
805                 ldap_pvt_thread_rdwr_destroy(&n->i_kids_rdwr);
806                 free(n);
807         }
808         if (e->e_id == 1)
809                 bdb->bi_troot = NULL;
810         ldap_pvt_thread_rdwr_wunlock(&bdb->bi_tree_rdwr);
811
812         return rc;
813 }
814
815 int
816 bdb_dn2id_matched(
817         BackendDB       *be,
818         DB_TXN *txn,
819         struct berval   *in,
820         ID *id,
821         ID *id2,
822         int flags )
823 {
824         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
825         struct berval   rdn;
826         char            *p1, *p2;
827         idNode *n, *p;
828         int             rc = 0;
829
830         if (!bdb->bi_troot)
831                 return DB_NOTFOUND;
832
833         p = bdb->bi_troot;
834         if (be_issuffix(be, in)) {
835                 *id = p->i_id;
836                 return 0;
837         }
838
839         p1 = in->bv_val + in->bv_len - be->be_nsuffix[0].bv_len - 1;
840
841         n = p;
842         ldap_pvt_thread_rdwr_rlock(&bdb->bi_tree_rdwr);
843         for (;;) {
844                 for (p2 = p1-1; (p2 >= in->bv_val) && !DN_SEPARATOR(*p2); p2--);
845                 rdn.bv_val = p2+1;
846                 rdn.bv_len = p1-rdn.bv_val;
847                 p1 = p2;
848
849                 ldap_pvt_thread_rdwr_rlock(&p->i_kids_rdwr);
850                 n = bdb_find_rdn_node(&rdn, p->i_kids);
851                 ldap_pvt_thread_rdwr_runlock(&p->i_kids_rdwr);
852                 if (!n || p2 < in->bv_val) break;
853                 p = n;
854         }
855         ldap_pvt_thread_rdwr_runlock(&bdb->bi_tree_rdwr);
856
857         if (n) {
858                 *id = n->i_id;
859         } else if (id2) {
860                 *id2 = p->i_id;
861         } else {
862                 rc = DB_NOTFOUND;
863         }
864
865         return rc;
866 }
867
868 int
869 bdb_dn2id(
870         BackendDB       *be,
871         DB_TXN *txn,
872         struct berval   *dn,
873         ID *id,
874         int flags )
875 {
876         return bdb_dn2id_matched(be, txn, dn, id, NULL, flags);
877 }
878
879 int
880 bdb_dn2id_children(
881         BackendDB       *be,
882         DB_TXN *txn,
883         struct berval   *dn,
884         int flags )
885 {
886         int             rc;
887         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
888         ID              id;
889         idNode *n;
890
891         rc = bdb_dn2id(be, txn, dn, &id, flags);
892         if (rc != 0)
893                 return rc;
894
895         ldap_pvt_thread_rdwr_rlock(&bdb->bi_tree_rdwr);
896         n = bdb_find_id_node(id, bdb->bi_tree);
897         ldap_pvt_thread_rdwr_runlock(&bdb->bi_tree_rdwr);
898
899         if (!n->i_kids)
900                 return DB_NOTFOUND;
901         else
902                 return 0;
903 }
904
905 /* Since we don't store IDLs for onelevel or subtree, we have to construct
906  * them on the fly... Perhaps the i_kids tree ought to just be an IDL?
907  */
908 static int
909 insert_one(
910         void *v_n,
911         void *v_ids
912 )
913 {
914         idNode *n = v_n;
915         ID *ids = v_ids;
916         return bdb_idl_insert(ids, n->i_id);
917 }
918
919 static int
920 insert_sub(
921         void *v_n,
922         void *v_ids
923 )
924 {
925         idNode *n = v_n;
926         ID *ids = v_ids;
927         int rc;
928
929         rc = bdb_idl_insert(ids, n->i_id);
930         if (rc == 0) {
931                 ldap_pvt_thread_rdwr_rlock(&n->i_kids_rdwr);
932                 rc = avl_apply(n->i_kids, insert_sub, ids, -1, AVL_INORDER);
933                 ldap_pvt_thread_rdwr_runlock(&n->i_kids_rdwr);
934         }
935         return rc;
936 }
937
938 int
939 bdb_dn2idl(
940         BackendDB       *be,
941         struct berval   *dn,
942         int prefix,
943         ID *ids )
944 {
945         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
946         int             rc;
947         ID              id;
948         idNode          *n;
949
950         if (prefix == DN_SUBTREE_PREFIX && be_issuffix(be, dn)) {
951                 BDB_IDL_ALL(bdb, ids);
952                 return 0;
953         }
954
955         rc = bdb_dn2id(be, NULL, dn, &id, 0);
956         if (rc) return rc;
957
958         ldap_pvt_thread_rdwr_rlock(&bdb->bi_tree_rdwr);
959         n = bdb_find_id_node(id, bdb->bi_tree);
960         ldap_pvt_thread_rdwr_runlock(&bdb->bi_tree_rdwr);
961
962         ids[0] = 0;
963         ldap_pvt_thread_rdwr_rlock(&n->i_kids_rdwr);
964         if (prefix == DN_ONE_PREFIX) {
965                 rc = avl_apply(n->i_kids, insert_one, ids, -1, AVL_INORDER);
966         } else {
967                 ids[0] = 1;
968                 ids[1] = id;
969                 if (n->i_kids)
970                         rc = avl_apply(n->i_kids, insert_sub, ids, -1, AVL_INORDER);
971         }
972         ldap_pvt_thread_rdwr_runlock(&n->i_kids_rdwr);
973         return rc;
974 }
975 #endif  /* BDB_HIER */