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