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-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 */