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