git.sur5r.net Git - openldap/blob - servers/slapd/back-bdb/dn2id.c

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