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 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
   4  *
   5  * Copyright 2000-2007 The OpenLDAP Foundation.
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted only as authorized by the OpenLDAP
  10  * Public License.
  11  *
  12  * A copy of this license is available in the file LICENSE in the
  13  * top-level directory of the distribution or, alternatively, at
  14  * <http://www.OpenLDAP.org/license.html>.
  15  */
  16
  17 #include "portable.h"
  18
  19 #include <stdio.h>
  20 #include <ac/string.h>
  21
  22 #include "back-bdb.h"
  23 #include "idl.h"
  24 #include "lutil.h"
  25
  26 #define bdb_dn2id_lock                                  BDB_SYMBOL(dn2id_lock)
  27
  28 static int
  29 bdb_dn2id_lock( struct bdb_info *bdb, struct berval *dn,
  30         int rw, u_int32_t locker, DB_LOCK *lock )
  31 {
  32         int       rc;
  33         DBT       lockobj;
  34         int       db_rw;
  35
  36         if (rw)
  37                 db_rw = DB_LOCK_WRITE;
  38         else
  39                 db_rw = DB_LOCK_READ;
  40
  41         lockobj.data = dn->bv_val;
  42         lockobj.size = dn->bv_len;
  43
  44         rc = LOCK_GET(bdb->bi_dbenv, locker, DB_LOCK_NOWAIT,
  45                                         &lockobj, db_rw, lock);
  46         return rc;
  47 }
  48
  49 #ifndef BDB_HIER
  50 int
  51 bdb_dn2id_add(
  52         Operation *op,
  53         DB_TXN *txn,
  54         EntryInfo *eip,
  55         Entry           *e )
  56 {
  57         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
  58         DB *db = bdb->bi_dn2id->bdi_db;
  59         int             rc;
  60         DBT             key, data;
  61         ID              nid;
  62         char            *buf;
  63         struct berval   ptr, pdn;
  64
  65         Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id_add 0x%lx: \"%s\"\n",
  66                 e->e_id, e->e_ndn, 0 );
  67         assert( e->e_id != NOID );
  68
  69         DBTzero( &key );
  70         key.size = e->e_nname.bv_len + 2;
  71         key.ulen = key.size;
  72         key.flags = DB_DBT_USERMEM;
  73         buf = op->o_tmpalloc( key.size, op->o_tmpmemctx );
  74         key.data = buf;
  75         buf[0] = DN_BASE_PREFIX;
  76         ptr.bv_val = buf + 1;
  77         ptr.bv_len = e->e_nname.bv_len;
  78         AC_MEMCPY( ptr.bv_val, e->e_nname.bv_val, e->e_nname.bv_len );
  79         ptr.bv_val[ptr.bv_len] = '\0';
  80
  81         DBTzero( &data );
  82         data.data = &nid;
  83         data.size = sizeof( nid );
  84         BDB_ID2DISK( e->e_id, &nid );
  85
  86         /* store it -- don't override */
  87         rc = db->put( db, txn, &key, &data, DB_NOOVERWRITE );
  88         if( rc != 0 ) {
  89                 Debug( LDAP_DEBUG_ANY, "=> bdb_dn2id_add 0x%lx: put failed: %s %d\n",
  90                         e->e_id, db_strerror(rc), rc );
  91                 goto done;
  92         }
  93
  94 #ifndef BDB_MULTIPLE_SUFFIXES
  95         if( !be_issuffix( op->o_bd, &ptr ))
  96 #endif
  97         {
  98                 buf[0] = DN_SUBTREE_PREFIX;
  99                 rc = db->put( db, txn, &key, &data, DB_NOOVERWRITE );
 100                 if( rc != 0 ) {
 101                         Debug( LDAP_DEBUG_ANY,
 102                         "=> bdb_dn2id_add 0x%lx: subtree (%s) put failed: %d\n",
 103                         e->e_id, ptr.bv_val, rc );
 104                         goto done;
 105                 }
 106
 107 #ifdef BDB_MULTIPLE_SUFFIXES
 108         if( !be_issuffix( op->o_bd, &ptr ))
 109 #endif
 110         {
 111                 dnParent( &ptr, &pdn );
 112
 113                 key.size = pdn.bv_len + 2;
 114                 key.ulen = key.size;
 115                 pdn.bv_val[-1] = DN_ONE_PREFIX;
 116                 key.data = pdn.bv_val-1;
 117                 ptr = pdn;
 118
 119                 rc = bdb_idl_insert_key( op->o_bd, db, txn, &key, e->e_id );
 120
 121                 if( rc != 0 ) {
 122                         Debug( LDAP_DEBUG_ANY,
 123                                 "=> bdb_dn2id_add 0x%lx: parent (%s) insert failed: %d\n",
 124                                         e->e_id, ptr.bv_val, rc );
 125                         goto done;
 126                 }
 127         }
 128
 129 #ifndef BDB_MULTIPLE_SUFFIXES
 130         while( !be_issuffix( op->o_bd, &ptr ))
 131 #else
 132         for (;;)
 133 #endif
 134         {
 135                 ptr.bv_val[-1] = DN_SUBTREE_PREFIX;
 136
 137                 rc = bdb_idl_insert_key( op->o_bd, db, txn, &key, e->e_id );
 138
 139                 if( rc != 0 ) {
 140                         Debug( LDAP_DEBUG_ANY,
 141                                 "=> bdb_dn2id_add 0x%lx: subtree (%s) insert failed: %d\n",
 142                                         e->e_id, ptr.bv_val, rc );
 143                         break;
 144                 }
 145 #ifdef BDB_MULTIPLE_SUFFIXES
 146                 if( be_issuffix( op->o_bd, &ptr )) break;
 147 #endif
 148                 dnParent( &ptr, &pdn );
 149
 150                 key.size = pdn.bv_len + 2;
 151                 key.ulen = key.size;
 152                 key.data = pdn.bv_val - 1;
 153                 ptr = pdn;
 154         }
 155         }
 156
 157 done:
 158         op->o_tmpfree( buf, op->o_tmpmemctx );
 159         Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id_add 0x%lx: %d\n", e->e_id, rc, 0 );
 160         return rc;
 161 }
 162
 163 int
 164 bdb_dn2id_delete(
 165         Operation *op,
 166         DB_TXN *txn,
 167         EntryInfo       *eip,
 168         Entry           *e )
 169 {
 170         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 171         DB *db = bdb->bi_dn2id->bdi_db;
 172         char            *buf;
 173         DBT             key;
 174         DB_LOCK lock;
 175         struct berval   pdn, ptr;
 176         int             rc;
 177
 178         Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id_delete 0x%lx: \"%s\"\n",
 179                 e->e_id, e->e_ndn, 0 );
 180
 181         DBTzero( &key );
 182         key.size = e->e_nname.bv_len + 2;
 183         buf = op->o_tmpalloc( key.size, op->o_tmpmemctx );
 184         key.data = buf;
 185         key.flags = DB_DBT_USERMEM;
 186         buf[0] = DN_BASE_PREFIX;
 187         ptr.bv_val = buf+1;
 188         ptr.bv_len = e->e_nname.bv_len;
 189         AC_MEMCPY( ptr.bv_val, e->e_nname.bv_val, e->e_nname.bv_len );
 190         ptr.bv_val[ptr.bv_len] = '\0';
 191
 192         /* We hold this lock until the TXN completes */
 193         rc = bdb_dn2id_lock( bdb, &e->e_nname, 1, TXN_ID( txn ), &lock );
 194         if ( rc ) goto done;
 195
 196         /* delete it */
 197         rc = db->del( db, txn, &key, 0 );
 198         if( rc != 0 ) {
 199                 Debug( LDAP_DEBUG_ANY, "=> bdb_dn2id_delete 0x%lx: delete failed: %s %d\n",
 200                         e->e_id, db_strerror(rc), rc );
 201                 goto done;
 202         }
 203
 204 #ifndef BDB_MULTIPLE_SUFFIXES
 205         if( !be_issuffix( op->o_bd, &ptr ))
 206 #endif
 207         {
 208                 buf[0] = DN_SUBTREE_PREFIX;
 209                 rc = bdb_idl_delete_key( op->o_bd, db, txn, &key, e->e_id );
 210                 if( rc != 0 ) {
 211                         Debug( LDAP_DEBUG_ANY,
 212                         "=> bdb_dn2id_delete 0x%lx: subtree (%s) delete failed: %d\n",
 213                         e->e_id, ptr.bv_val, rc );
 214                         goto done;
 215                 }
 216
 217 #ifdef BDB_MULTIPLE_SUFFIXES
 218         if( !be_issuffix( op->o_bd, &ptr ))
 219 #endif
 220         {
 221                 dnParent( &ptr, &pdn );
 222
 223                 key.size = pdn.bv_len + 2;
 224                 key.ulen = key.size;
 225                 pdn.bv_val[-1] = DN_ONE_PREFIX;
 226                 key.data = pdn.bv_val - 1;
 227                 ptr = pdn;
 228
 229                 rc = bdb_idl_delete_key( op->o_bd, db, txn, &key, e->e_id );
 230
 231                 if( rc != 0 ) {
 232                         Debug( LDAP_DEBUG_ANY,
 233                                 "=> bdb_dn2id_delete 0x%lx: parent (%s) delete failed: %d\n",
 234                                 e->e_id, ptr.bv_val, rc );
 235                         goto done;
 236                 }
 237         }
 238
 239 #ifndef BDB_MULTIPLE_SUFFIXES
 240         while( !be_issuffix( op->o_bd, &ptr ))
 241 #else
 242         for (;;)
 243 #endif
 244         {
 245                 ptr.bv_val[-1] = DN_SUBTREE_PREFIX;
 246
 247                 rc = bdb_idl_delete_key( op->o_bd, db, txn, &key, e->e_id );
 248                 if( rc != 0 ) {
 249                         Debug( LDAP_DEBUG_ANY,
 250                                 "=> bdb_dn2id_delete 0x%lx: subtree (%s) delete failed: %d\n",
 251                                 e->e_id, ptr.bv_val, rc );
 252                         goto done;
 253                 }
 254 #ifdef BDB_MULTIPLE_SUFFIXES
 255                 if( be_issuffix( op->o_bd, &ptr )) break;
 256 #endif
 257                 dnParent( &ptr, &pdn );
 258
 259                 key.size = pdn.bv_len + 2;
 260                 key.ulen = key.size;
 261                 key.data = pdn.bv_val - 1;
 262                 ptr = pdn;
 263         }
 264         }
 265
 266 done:
 267         op->o_tmpfree( buf, op->o_tmpmemctx );
 268         Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id_delete 0x%lx: %d\n", e->e_id, rc, 0 );
 269         return rc;
 270 }
 271
 272 int
 273 bdb_dn2id(
 274         Operation *op,
 275         struct berval   *dn,
 276         EntryInfo *ei,
 277         u_int32_t locker,
 278         DB_LOCK *lock )
 279 {
 280         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 281         DB *db = bdb->bi_dn2id->bdi_db;
 282         DBC     *cursor;
 283         int             rc;
 284         DBT             key, data;
 285         ID              nid;
 286
 287         Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id(\"%s\")\n", dn->bv_val, 0, 0 );
 288
 289         DBTzero( &key );
 290         key.size = dn->bv_len + 2;
 291         key.data = op->o_tmpalloc( key.size, op->o_tmpmemctx );
 292         ((char *)key.data)[0] = DN_BASE_PREFIX;
 293         AC_MEMCPY( &((char *)key.data)[1], dn->bv_val, key.size - 1 );
 294
 295         /* store the ID */
 296         DBTzero( &data );
 297         data.data = &nid;
 298         data.ulen = sizeof(ID);
 299         data.flags = DB_DBT_USERMEM;
 300
 301         rc = db->cursor( db, NULL, &cursor, bdb->bi_db_opflags );
 302         if ( rc ) goto leave;
 303
 304         rc = bdb_dn2id_lock( bdb, dn, 0, locker, lock );
 305         if ( rc ) goto nolock;
 306
 307         if ( locker ) {
 308                 cursor->locker = locker;
 309         }
 310
 311         /* fetch it */
 312         rc = cursor->c_get( cursor, &key, &data, DB_SET );
 313
 314 nolock:
 315         cursor->c_close( cursor );
 316 leave:
 317
 318         if( rc != 0 ) {
 319                 Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id: get failed: %s (%d)\n",
 320                         db_strerror( rc ), rc, 0 );
 321         } else {
 322                 BDB_DISK2ID( &nid, &ei->bei_id );
 323                 Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id: got id=0x%lx\n",
 324                         ei->bei_id, 0, 0 );
 325         }
 326         op->o_tmpfree( key.data, op->o_tmpmemctx );
 327         return rc;
 328 }
 329
 330 int
 331 bdb_dn2id_children(
 332         Operation *op,
 333         DB_TXN *txn,
 334         Entry *e )
 335 {
 336         DBT             key, data;
 337         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 338         DB *db = bdb->bi_dn2id->bdi_db;
 339         ID              id;
 340         int             rc;
 341
 342         Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id_children(\"%s\")\n",
 343                 e->e_nname.bv_val, 0, 0 );
 344         DBTzero( &key );
 345         key.size = e->e_nname.bv_len + 2;
 346         key.data = op->o_tmpalloc( key.size, op->o_tmpmemctx );
 347         ((char *)key.data)[0] = DN_ONE_PREFIX;
 348         AC_MEMCPY( &((char *)key.data)[1], e->e_nname.bv_val, key.size - 1 );
 349
 350         if ( bdb->bi_idl_cache_size ) {
 351                 rc = bdb_idl_cache_get( bdb, db, &key, NULL );
 352                 if ( rc != LDAP_NO_SUCH_OBJECT ) {
 353                         op->o_tmpfree( key.data, op->o_tmpmemctx );
 354                         return rc;
 355                 }
 356         }
 357         /* we actually could do a empty get... */
 358         DBTzero( &data );
 359         data.data = &id;
 360         data.ulen = sizeof(id);
 361         data.flags = DB_DBT_USERMEM;
 362         data.doff = 0;
 363         data.dlen = sizeof(id);
 364
 365         rc = db->get( db, txn, &key, &data, bdb->bi_db_opflags );
 366         op->o_tmpfree( key.data, op->o_tmpmemctx );
 367
 368         Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id_children(\"%s\"): %s (%d)\n",
 369                 e->e_nname.bv_val,
 370                 rc == 0 ? "" : ( rc == DB_NOTFOUND ? "no " :
 371                         db_strerror(rc) ), rc );
 372
 373         return rc;
 374 }
 375
 376 int
 377 bdb_dn2idl(
 378         Operation *op,
 379         Entry *e,
 380         ID *ids,
 381         ID *stack )
 382 {
 383         int             rc;
 384         DBT             key;
 385         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 386         DB *db = bdb->bi_dn2id->bdi_db;
 387         int prefix = ( op->ors_scope == LDAP_SCOPE_ONELEVEL )
 388                 ? DN_ONE_PREFIX : DN_SUBTREE_PREFIX;
 389
 390         Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2idl(\"%s\")\n",
 391                 e->e_nname.bv_val, 0, 0 );
 392
 393 #ifndef BDB_MULTIPLE_SUFFIXES
 394         if ( prefix == DN_SUBTREE_PREFIX && BEI(e)->bei_parent->bei_id == 0 ) {
 395                 BDB_IDL_ALL(bdb, ids);
 396                 return 0;
 397         }
 398 #endif
 399
 400         DBTzero( &key );
 401         key.size = e->e_nname.bv_len + 2;
 402         key.ulen = key.size;
 403         key.flags = DB_DBT_USERMEM;
 404         key.data = op->o_tmpalloc( key.size, op->o_tmpmemctx );
 405         ((char *)key.data)[0] = prefix;
 406         AC_MEMCPY( &((char *)key.data)[1], e->e_nname.bv_val, key.size - 1 );
 407
 408         BDB_IDL_ZERO( ids );
 409         rc = bdb_idl_fetch_key( op->o_bd, db, NULL, &key, ids, NULL, 0 );
 410
 411         if( rc != 0 ) {
 412                 Debug( LDAP_DEBUG_TRACE,
 413                         "<= bdb_dn2idl: get failed: %s (%d)\n",
 414                         db_strerror( rc ), rc, 0 );
 415
 416         } else {
 417                 Debug( LDAP_DEBUG_TRACE,
 418                         "<= bdb_dn2idl: id=%ld first=%ld last=%ld\n",
 419                         (long) ids[0],
 420                         (long) BDB_IDL_FIRST( ids ), (long) BDB_IDL_LAST( ids ) );
 421         }
 422
 423         op->o_tmpfree( key.data, op->o_tmpmemctx );
 424         return rc;
 425 }
 426
 427 #else   /* BDB_HIER */
 428 /* Management routines for a hierarchically structured database.
 429  *
 430  * Instead of a ldbm-style dn2id database, we use a hierarchical one. Each
 431  * entry in this database is a struct diskNode, keyed by entryID and with
 432  * the data containing the RDN and entryID of the node's children. We use
 433  * a B-Tree with sorted duplicates to store all the children of a node under
 434  * the same key. Also, the first item under the key contains the entry's own
 435  * rdn and the ID of the node's parent, to allow bottom-up tree traversal as
 436  * well as top-down. To keep this info first in the list, the high bit of all
 437  * subsequent nrdnlen's is always set. This means we can only accomodate
 438  * RDNs up to length 32767, but that's fine since full DNs are already
 439  * restricted to 8192.
 440  *
 441  * The diskNode is a variable length structure. This definition is not
 442  * directly usable for in-memory manipulation.
 443  */
 444 typedef struct diskNode {
 445         unsigned char nrdnlen[2];
 446         char nrdn[1];
 447         char rdn[1];                        /* variable placement */
 448         unsigned char entryID[sizeof(ID)];  /* variable placement */
 449 } diskNode;
 450
 451 /* Sort function for the sorted duplicate data items of a dn2id key.
 452  * Sorts based on normalized RDN, in length order.
 453  */
 454 int
 455 hdb_dup_compare(
 456         DB *db,
 457         const DBT *usrkey,
 458         const DBT *curkey
 459 )
 460 {
 461         diskNode *un, *cn;
 462         int rc, ul, cl;
 463
 464         un = (diskNode *)usrkey->data;
 465         cn = (diskNode *)curkey->data;
 466
 467         /* data is not aligned, cannot compare directly */
 468         rc = un->nrdnlen[0] - cn->nrdnlen[0];
 469         if ( rc ) return rc;
 470         rc = un->nrdnlen[1] - cn->nrdnlen[1];
 471         if ( rc ) return rc;
 472
 473         return strcmp( un->nrdn, cn->nrdn );
 474 }
 475
 476 /* This function constructs a full DN for a given entry.
 477  */
 478 int hdb_fix_dn(
 479         Entry *e,
 480         int checkit )
 481 {
 482         EntryInfo *ei;
 483         int rlen = 0, nrlen = 0;
 484         char *ptr, *nptr;
 485         int max = 0;
 486
 487         if ( !e->e_id )
 488                 return 0;
 489
 490         /* count length of all DN components */
 491         for ( ei = BEI(e); ei && ei->bei_id; ei=ei->bei_parent ) {
 492                 rlen += ei->bei_rdn.bv_len + 1;
 493                 nrlen += ei->bei_nrdn.bv_len + 1;
 494                 if (ei->bei_modrdns > max) max = ei->bei_modrdns;
 495         }
 496
 497         /* See if the entry DN was invalidated by a subtree rename */
 498         if ( checkit ) {
 499                 if ( BEI(e)->bei_modrdns >= max ) {
 500                         return 0;
 501                 }
 502                 /* We found a mismatch, tell the caller to lock it */
 503                 if ( checkit == 1 ) {
 504                         return 1;
 505                 }
 506                 /* checkit == 2. do the fix. */
 507                 free( e->e_name.bv_val );
 508                 free( e->e_nname.bv_val );
 509         }
 510
 511         e->e_name.bv_len = rlen - 1;
 512         e->e_nname.bv_len = nrlen - 1;
 513         e->e_name.bv_val = ch_malloc(rlen);
 514         e->e_nname.bv_val = ch_malloc(nrlen);
 515         ptr = e->e_name.bv_val;
 516         nptr = e->e_nname.bv_val;
 517         for ( ei = BEI(e); ei && ei->bei_id; ei=ei->bei_parent ) {
 518                 ptr = lutil_strcopy(ptr, ei->bei_rdn.bv_val);
 519                 nptr = lutil_strcopy(nptr, ei->bei_nrdn.bv_val);
 520                 if ( ei->bei_parent ) {
 521                         *ptr++ = ',';
 522                         *nptr++ = ',';
 523                 }
 524         }
 525         BEI(e)->bei_modrdns = max;
 526         ptr[-1] = '\0';
 527         nptr[-1] = '\0';
 528
 529         return 0;
 530 }
 531
 532 /* We add two elements to the DN2ID database - a data item under the parent's
 533  * entryID containing the child's RDN and entryID, and an item under the
 534  * child's entryID containing the parent's entryID.
 535  */
 536 int
 537 hdb_dn2id_add(
 538         Operation       *op,
 539         DB_TXN *txn,
 540         EntryInfo       *eip,
 541         Entry           *e )
 542 {
 543         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 544         DB *db = bdb->bi_dn2id->bdi_db;
 545         DBT             key, data;
 546         ID              nid;
 547         int             rc, rlen, nrlen;
 548         diskNode *d;
 549         char *ptr;
 550
 551         Debug( LDAP_DEBUG_TRACE, "=> hdb_dn2id_add 0x%lx: \"%s\"\n",
 552                 e->e_id, e->e_ndn, 0 );
 553
 554         nrlen = dn_rdnlen( op->o_bd, &e->e_nname );
 555         if (nrlen) {
 556                 rlen = dn_rdnlen( op->o_bd, &e->e_name );
 557         } else {
 558                 nrlen = e->e_nname.bv_len;
 559                 rlen = e->e_name.bv_len;
 560         }
 561
 562         d = op->o_tmpalloc(sizeof(diskNode) + rlen + nrlen, op->o_tmpmemctx);
 563         d->nrdnlen[1] = nrlen & 0xff;
 564         d->nrdnlen[0] = (nrlen >> 8) | 0x80;
 565         ptr = lutil_strncopy( d->nrdn, e->e_nname.bv_val, nrlen );
 566         *ptr++ = '\0';
 567         ptr = lutil_strncopy( ptr, e->e_name.bv_val, rlen );
 568         *ptr++ = '\0';
 569         BDB_ID2DISK( e->e_id, ptr );
 570
 571         DBTzero(&key);
 572         DBTzero(&data);
 573         key.size = sizeof(ID);
 574         key.flags = DB_DBT_USERMEM;
 575         BDB_ID2DISK( eip->bei_id, &nid );
 576
 577         key.data = &nid;
 578
 579         /* Need to make dummy root node once. Subsequent attempts
 580          * will fail harmlessly.
 581          */
 582         if ( eip->bei_id == 0 ) {
 583                 diskNode dummy = {{0, 0}, "", "", ""};
 584                 data.data = &dummy;
 585                 data.size = sizeof(diskNode);
 586                 data.flags = DB_DBT_USERMEM;
 587
 588                 db->put( db, txn, &key, &data, DB_NODUPDATA );
 589         }
 590
 591         data.data = d;
 592         data.size = sizeof(diskNode) + rlen + nrlen;
 593         data.flags = DB_DBT_USERMEM;
 594
 595         rc = db->put( db, txn, &key, &data, DB_NODUPDATA );
 596
 597         if (rc == 0) {
 598                 BDB_ID2DISK( e->e_id, &nid );
 599                 BDB_ID2DISK( eip->bei_id, ptr );
 600                 d->nrdnlen[0] ^= 0x80;
 601
 602                 rc = db->put( db, txn, &key, &data, DB_NODUPDATA );
 603         }
 604
 605         /* Update all parents' IDL cache entries */
 606         if ( rc == 0 && bdb->bi_idl_cache_size ) {
 607                 ID tmp[2];
 608                 char *ptr = ((char *)&tmp[1])-1;
 609                 key.data = ptr;
 610                 key.size = sizeof(ID)+1;
 611                 tmp[1] = eip->bei_id;
 612                 *ptr = DN_ONE_PREFIX;
 613                 bdb_idl_cache_add_id( bdb, db, &key, e->e_id );
 614                 *ptr = DN_SUBTREE_PREFIX;
 615                 for (; eip && eip->bei_parent->bei_id; eip = eip->bei_parent) {
 616                         tmp[1] = eip->bei_id;
 617                         bdb_idl_cache_add_id( bdb, db, &key, e->e_id );
 618                 }
 619         }
 620
 621 leave:
 622         op->o_tmpfree( d, op->o_tmpmemctx );
 623         Debug( LDAP_DEBUG_TRACE, "<= hdb_dn2id_add 0x%lx: %d\n", e->e_id, rc, 0 );
 624
 625         return rc;
 626 }
 627
 628 int
 629 hdb_dn2id_delete(
 630         Operation       *op,
 631         DB_TXN *txn,
 632         EntryInfo       *eip,
 633         Entry   *e )
 634 {
 635         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 636         DB *db = bdb->bi_dn2id->bdi_db;
 637         DBT             key, data;
 638         DBC     *cursor;
 639         diskNode *d;
 640         int rc;
 641         ID      nid;
 642         unsigned char dlen[2];
 643         DB_LOCK lock;
 644
 645         Debug( LDAP_DEBUG_TRACE, "=> hdb_dn2id_delete 0x%lx: \"%s\"\n",
 646                 e->e_id, e->e_ndn, 0 );
 647
 648         DBTzero(&key);
 649         key.size = sizeof(ID);
 650         key.ulen = key.size;
 651         key.flags = DB_DBT_USERMEM;
 652         BDB_ID2DISK( eip->bei_id, &nid );
 653
 654         DBTzero(&data);
 655         data.size = sizeof(diskNode) + BEI(e)->bei_nrdn.bv_len - sizeof(ID) - 1;
 656         data.ulen = data.size;
 657         data.dlen = data.size;
 658         data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL;
 659
 660         key.data = &nid;
 661
 662         d = op->o_tmpalloc( data.size, op->o_tmpmemctx );
 663         d->nrdnlen[1] = BEI(e)->bei_nrdn.bv_len & 0xff;
 664         d->nrdnlen[0] = (BEI(e)->bei_nrdn.bv_len >> 8) | 0x80;
 665         dlen[0] = d->nrdnlen[0];
 666         dlen[1] = d->nrdnlen[1];
 667         strcpy( d->nrdn, BEI(e)->bei_nrdn.bv_val );
 668         data.data = d;
 669
 670         rc = db->cursor( db, txn, &cursor, bdb->bi_db_opflags );
 671         if ( rc ) goto leave;
 672
 673         /* We hold this lock until the TXN completes */
 674         rc = bdb_dn2id_lock( bdb, &e->e_nname, 1, TXN_ID( txn ), &lock );
 675         if ( rc ) goto nolock;
 676
 677         /* Delete our ID from the parent's list */
 678         rc = cursor->c_get( cursor, &key, &data, DB_GET_BOTH_RANGE );
 679         if ( rc == 0 ) {
 680                 if ( dlen[1] == d->nrdnlen[1] && dlen[0] == d->nrdnlen[0] &&
 681                         !strcmp( d->nrdn, BEI(e)->bei_nrdn.bv_val ))
 682                         rc = cursor->c_del( cursor, 0 );
 683                 else
 684                         rc = DB_NOTFOUND;
 685         }
 686
 687         /* Delete our ID from the tree. With sorted duplicates, this
 688          * will leave any child nodes still hanging around. This is OK
 689          * for modrdn, which will add our info back in later.
 690          */
 691         if ( rc == 0 ) {
 692                 BDB_ID2DISK( e->e_id, &nid );
 693                 rc = cursor->c_get( cursor, &key, &data, DB_SET );
 694                 if ( rc == 0 )
 695                         rc = cursor->c_del( cursor, 0 );
 696         }
 697
 698 nolock:
 699         cursor->c_close( cursor );
 700 leave:
 701         op->o_tmpfree( d, op->o_tmpmemctx );
 702
 703         /* Delete IDL cache entries */
 704         if ( rc == 0 && bdb->bi_idl_cache_size ) {
 705                 ID tmp[2];
 706                 char *ptr = ((char *)&tmp[1])-1;
 707                 key.data = ptr;
 708                 key.size = sizeof(ID)+1;
 709                 tmp[1] = eip->bei_id;
 710                 *ptr = DN_ONE_PREFIX;
 711                 bdb_idl_cache_del_id( bdb, db, &key, e->e_id );
 712                 *ptr = DN_SUBTREE_PREFIX;
 713                 for (; eip && eip->bei_parent->bei_id; eip = eip->bei_parent) {
 714                         tmp[1] = eip->bei_id;
 715                         bdb_idl_cache_del_id( bdb, db, &key, e->e_id );
 716                 }
 717         }
 718         Debug( LDAP_DEBUG_TRACE, "<= hdb_dn2id_delete 0x%lx: %d\n", e->e_id, rc, 0 );
 719         return rc;
 720 }
 721
 722
 723 int
 724 hdb_dn2id(
 725         Operation       *op,
 726         struct berval   *in,
 727         EntryInfo       *ei,
 728         u_int32_t locker,
 729         DB_LOCK *lock )
 730 {
 731         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 732         DB *db = bdb->bi_dn2id->bdi_db;
 733         DBT             key, data;
 734         DBC     *cursor;
 735         int             rc = 0, nrlen;
 736         diskNode *d;
 737         char    *ptr;
 738         unsigned char dlen[2];
 739         ID idp, parentID;
 740
 741         Debug( LDAP_DEBUG_TRACE, "=> hdb_dn2id(\"%s\")\n", in->bv_val, 0, 0 );
 742
 743         nrlen = dn_rdnlen( op->o_bd, in );
 744         if (!nrlen) nrlen = in->bv_len;
 745
 746         DBTzero(&key);
 747         key.size = sizeof(ID);
 748         key.data = &idp;
 749         key.ulen = sizeof(ID);
 750         key.flags = DB_DBT_USERMEM;
 751         parentID = ( ei->bei_parent != NULL ) ? ei->bei_parent->bei_id : 0;
 752         BDB_ID2DISK( parentID, &idp );
 753
 754         DBTzero(&data);
 755         data.size = sizeof(diskNode) + nrlen - sizeof(ID) - 1;
 756         data.ulen = data.size * 3;
 757         data.dlen = data.ulen;
 758         data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL;
 759
 760         rc = db->cursor( db, NULL, &cursor, bdb->bi_db_opflags );
 761         if ( rc ) return rc;
 762         if ( locker ) {
 763                 cursor->locker = locker;
 764         }
 765
 766         d = op->o_tmpalloc( data.size * 3, op->o_tmpmemctx );
 767         d->nrdnlen[1] = nrlen & 0xff;
 768         d->nrdnlen[0] = (nrlen >> 8) | 0x80;
 769         dlen[0] = d->nrdnlen[0];
 770         dlen[1] = d->nrdnlen[1];
 771         ptr = lutil_strncopy( d->nrdn, in->bv_val, nrlen );
 772         *ptr = '\0';
 773         data.data = d;
 774
 775         rc = bdb_dn2id_lock( bdb, in, 0, locker, lock );
 776         if ( rc ) goto leave;
 777
 778         rc = cursor->c_get( cursor, &key, &data, DB_GET_BOTH_RANGE );
 779         if ( rc == 0 && (dlen[1] != d->nrdnlen[1] || dlen[0] != d->nrdnlen[0] ||
 780                 strncmp( d->nrdn, in->bv_val, nrlen ))) {
 781                 rc = DB_NOTFOUND;
 782         }
 783         if ( rc == 0 ) {
 784                 ptr = (char *) data.data + data.size - sizeof(ID);
 785                 BDB_DISK2ID( ptr, &ei->bei_id );
 786                 ei->bei_rdn.bv_len = data.size - sizeof(diskNode) - nrlen;
 787                 ptr = d->nrdn + nrlen + 1;
 788                 ber_str2bv( ptr, ei->bei_rdn.bv_len, 1, &ei->bei_rdn );
 789                 if ( ei->bei_parent != NULL && !ei->bei_parent->bei_dkids ) {
 790                         db_recno_t dkids;
 791                         /* How many children does the parent have? */
 792                         /* FIXME: do we need to lock the parent
 793                          * entryinfo? Seems safe...
 794                          */
 795                         cursor->c_count( cursor, &dkids, 0 );
 796                         ei->bei_parent->bei_dkids = dkids;
 797                 }
 798         }
 799
 800 leave:
 801         cursor->c_close( cursor );
 802         op->o_tmpfree( d, op->o_tmpmemctx );
 803         if( rc != 0 ) {
 804                 Debug( LDAP_DEBUG_TRACE, "<= hdb_dn2id: get failed: %s (%d)\n",
 805                         db_strerror( rc ), rc, 0 );
 806         } else {
 807                 Debug( LDAP_DEBUG_TRACE, "<= hdb_dn2id: got id=0x%lx\n",
 808                         ei->bei_id, 0, 0 );
 809         }
 810
 811         return rc;
 812 }
 813
 814 int
 815 hdb_dn2id_parent(
 816         Operation *op,
 817         u_int32_t       locker,
 818         EntryInfo *ei,
 819         ID *idp )
 820 {
 821         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 822         DB *db = bdb->bi_dn2id->bdi_db;
 823         DBT             key, data;
 824         DBC     *cursor;
 825         int             rc = 0;
 826         diskNode *d;
 827         char    *ptr;
 828         ID      nid;
 829
 830         DBTzero(&key);
 831         key.size = sizeof(ID);
 832         key.data = &nid;
 833         key.ulen = sizeof(ID);
 834         key.flags = DB_DBT_USERMEM;
 835         BDB_ID2DISK( ei->bei_id, &nid );
 836
 837         DBTzero(&data);
 838         data.flags = DB_DBT_USERMEM;
 839
 840         rc = db->cursor( db, NULL, &cursor, bdb->bi_db_opflags );
 841         if ( rc ) return rc;
 842         if ( locker ) {
 843                 cursor->locker = locker;
 844         }
 845
 846         data.ulen = sizeof(diskNode) + (SLAP_LDAPDN_MAXLEN * 2);
 847         d = op->o_tmpalloc( data.ulen, op->o_tmpmemctx );
 848         data.data = d;
 849
 850         rc = cursor->c_get( cursor, &key, &data, DB_SET );
 851         if ( rc == 0 ) {
 852                 if (d->nrdnlen[0] & 0x80) {
 853                         rc = LDAP_OTHER;
 854                 } else {
 855                         db_recno_t dkids;
 856                         ptr = (char *) data.data + data.size - sizeof(ID);
 857                         BDB_DISK2ID( ptr, idp );
 858                         ei->bei_nrdn.bv_len = (d->nrdnlen[0] << 8) | d->nrdnlen[1];
 859                         ber_str2bv( d->nrdn, ei->bei_nrdn.bv_len, 1, &ei->bei_nrdn );
 860                         ei->bei_rdn.bv_len = data.size - sizeof(diskNode) -
 861                                 ei->bei_nrdn.bv_len;
 862                         ptr = d->nrdn + ei->bei_nrdn.bv_len + 1;
 863                         ber_str2bv( ptr, ei->bei_rdn.bv_len, 1, &ei->bei_rdn );
 864                         /* How many children does this node have? */
 865                         cursor->c_count( cursor, &dkids, 0 );
 866                         ei->bei_dkids = dkids;
 867                 }
 868         }
 869         cursor->c_close( cursor );
 870         op->o_tmpfree( d, op->o_tmpmemctx );
 871         return rc;
 872 }
 873
 874 int
 875 hdb_dn2id_children(
 876         Operation *op,
 877         DB_TXN *txn,
 878         Entry *e )
 879 {
 880         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 881         DB *db = bdb->bi_dn2id->bdi_db;
 882         DBT             key, data;
 883         DBC             *cursor;
 884         int             rc;
 885         ID              id;
 886         diskNode d;
 887
 888         DBTzero(&key);
 889         key.size = sizeof(ID);
 890         key.data = &e->e_id;
 891         key.flags = DB_DBT_USERMEM;
 892         BDB_ID2DISK( e->e_id, &id );
 893
 894         /* IDL cache is in host byte order */
 895         if ( bdb->bi_idl_cache_size ) {
 896                 rc = bdb_idl_cache_get( bdb, db, &key, NULL );
 897                 if ( rc != LDAP_NO_SUCH_OBJECT ) {
 898                         return rc;
 899                 }
 900         }
 901
 902         key.data = &id;
 903         DBTzero(&data);
 904         data.data = &d;
 905         data.ulen = sizeof(d);
 906         data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL;
 907         data.dlen = sizeof(d);
 908
 909         rc = db->cursor( db, txn, &cursor, bdb->bi_db_opflags );
 910         if ( rc ) return rc;
 911
 912         rc = cursor->c_get( cursor, &key, &data, DB_SET );
 913         if ( rc == 0 ) {
 914                 db_recno_t dkids;
 915                 rc = cursor->c_count( cursor, &dkids, 0 );
 916                 if ( rc == 0 ) {
 917                         BEI(e)->bei_dkids = dkids;
 918                         if ( dkids < 2 ) rc = DB_NOTFOUND;
 919                 }
 920         }
 921         cursor->c_close( cursor );
 922         return rc;
 923 }
 924
 925 /* bdb_dn2idl:
 926  * We can't just use bdb_idl_fetch_key because
 927  * 1 - our data items are longer than just an entry ID
 928  * 2 - our data items are sorted alphabetically by nrdn, not by ID.
 929  *
 930  * We descend the tree recursively, so we define this cookie
 931  * to hold our necessary state information. The bdb_dn2idl_internal
 932  * function uses this cookie when calling itself.
 933  */
 934
 935 struct dn2id_cookie {
 936         struct bdb_info *bdb;
 937         Operation *op;
 938         EntryInfo *ei;
 939         ID *ids;
 940         ID *tmp;
 941         ID *buf;
 942         DB *db;
 943         DBC *dbc;
 944         DBT key;
 945         DBT data;
 946         ID dbuf;
 947         ID id;
 948         ID nid;
 949         int rc;
 950         int depth;
 951         char need_sort;
 952         char prefix;
 953 };
 954
 955 static int
 956 apply_func(
 957         void *data,
 958         void *arg )
 959 {
 960         EntryInfo *ei = data;
 961         ID *idl = arg;
 962
 963         bdb_idl_append_one( idl, ei->bei_id );
 964         return 0;
 965 }
 966
 967 static int
 968 hdb_dn2idl_internal(
 969         struct dn2id_cookie *cx
 970 )
 971 {
 972         BDB_IDL_ZERO( cx->tmp );
 973
 974         if ( cx->bdb->bi_idl_cache_size ) {
 975                 char *ptr = ((char *)&cx->id)-1;
 976
 977                 cx->key.data = ptr;
 978                 cx->key.size = sizeof(ID)+1;
 979                 if ( cx->prefix == DN_SUBTREE_PREFIX ) {
 980                         ID *ids = cx->depth ? cx->tmp : cx->ids;
 981                         *ptr = cx->prefix;
 982                         cx->rc = bdb_idl_cache_get(cx->bdb, cx->db, &cx->key, ids);
 983                         if ( cx->rc == LDAP_SUCCESS ) {
 984                                 if ( cx->depth ) {
 985                                         bdb_idl_append( cx->ids, cx->tmp );
 986                                         cx->need_sort = 1;
 987                                 }
 988                                 return cx->rc;
 989                         }
 990                 }
 991                 *ptr = DN_ONE_PREFIX;
 992                 cx->rc = bdb_idl_cache_get(cx->bdb, cx->db, &cx->key, cx->tmp);
 993                 if ( cx->rc == LDAP_SUCCESS ) {
 994                         goto gotit;
 995                 }
 996                 if ( cx->rc == DB_NOTFOUND ) {
 997                         return cx->rc;
 998                 }
 999         }
1000
1001         bdb_cache_entryinfo_lock( cx->ei );
1002
1003         /* If number of kids in the cache differs from on-disk, load
1004          * up all the kids from the database
1005          */
1006         if ( cx->ei->bei_ckids+1 != cx->ei->bei_dkids ) {
1007                 EntryInfo ei;
1008                 db_recno_t dkids = cx->ei->bei_dkids;
1009                 ei.bei_parent = cx->ei;
1010
1011                 /* Only one thread should load the cache */
1012                 while ( cx->ei->bei_state & CACHE_ENTRY_ONELEVEL ) {
1013                         bdb_cache_entryinfo_unlock( cx->ei );
1014                         ldap_pvt_thread_yield();
1015                         bdb_cache_entryinfo_lock( cx->ei );
1016                         if ( cx->ei->bei_ckids+1 == cx->ei->bei_dkids ) {
1017                                 goto synced;
1018                         }
1019                 }
1020
1021                 cx->ei->bei_state |= CACHE_ENTRY_ONELEVEL;
1022
1023                 bdb_cache_entryinfo_unlock( cx->ei );
1024
1025                 cx->rc = cx->db->cursor( cx->db, NULL, &cx->dbc,
1026                         cx->bdb->bi_db_opflags );
1027                 if ( cx->rc )
1028                         goto done_one;
1029
1030                 cx->data.data = &cx->dbuf;
1031                 cx->data.ulen = sizeof(ID);
1032                 cx->data.dlen = sizeof(ID);
1033                 cx->data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL;
1034
1035                 /* The first item holds the parent ID. Ignore it. */
1036                 cx->key.data = &cx->nid;
1037                 cx->key.size = sizeof(ID);
1038                 cx->rc = cx->dbc->c_get( cx->dbc, &cx->key, &cx->data, DB_SET );
1039                 if ( cx->rc ) {
1040                         cx->dbc->c_close( cx->dbc );
1041                         goto done_one;
1042                 }
1043
1044                 /* If the on-disk count is zero we've never checked it.
1045                  * Count it now.
1046                  */
1047                 if ( !dkids ) {
1048                         cx->dbc->c_count( cx->dbc, &dkids, 0 );
1049                         cx->ei->bei_dkids = dkids;
1050                 }
1051
1052                 cx->data.data = cx->buf;
1053                 cx->data.ulen = BDB_IDL_UM_SIZE * sizeof(ID);
1054                 cx->data.flags = DB_DBT_USERMEM;
1055
1056                 if ( dkids > 1 ) {
1057                         /* Fetch the rest of the IDs in a loop... */
1058                         while ( (cx->rc = cx->dbc->c_get( cx->dbc, &cx->key, &cx->data,
1059                                 DB_MULTIPLE | DB_NEXT_DUP )) == 0 ) {
1060                                 u_int8_t *j;
1061                                 size_t len;
1062                                 void *ptr;
1063                                 DB_MULTIPLE_INIT( ptr, &cx->data );
1064                                 while (ptr) {
1065                                         DB_MULTIPLE_NEXT( ptr, &cx->data, j, len );
1066                                         if (j) {
1067                                                 EntryInfo *ei2;
1068                                                 diskNode *d = (diskNode *)j;
1069                                                 short nrlen;
1070
1071                                                 BDB_DISK2ID( j + len - sizeof(ID), &ei.bei_id );
1072                                                 nrlen = ((d->nrdnlen[0] ^ 0x80) << 8) | d->nrdnlen[1];
1073                                                 ei.bei_nrdn.bv_len = nrlen;
1074                                                 /* nrdn/rdn are set in-place.
1075                                                  * hdb_cache_load will copy them as needed
1076                                                  */
1077                                                 ei.bei_nrdn.bv_val = d->nrdn;
1078                                                 ei.bei_rdn.bv_len = len - sizeof(diskNode)
1079                                                         - ei.bei_nrdn.bv_len;
1080                                                 ei.bei_rdn.bv_val = d->nrdn + ei.bei_nrdn.bv_len + 1;
1081                                                 bdb_idl_append_one( cx->tmp, ei.bei_id );
1082                                                 hdb_cache_load( cx->bdb, &ei, &ei2 );
1083                                         }
1084                                 }
1085                         }
1086                 }
1087
1088                 cx->rc = cx->dbc->c_close( cx->dbc );
1089 done_one:
1090                 bdb_cache_entryinfo_lock( cx->ei );
1091                 cx->ei->bei_state ^= CACHE_ENTRY_ONELEVEL;
1092                 bdb_cache_entryinfo_unlock( cx->ei );
1093                 if ( cx->rc )
1094                         return cx->rc;
1095
1096         } else {
1097                 /* The in-memory cache is in sync with the on-disk data.
1098                  * do we have any kids?
1099                  */
1100 synced:
1101                 cx->rc = 0;
1102                 if ( cx->ei->bei_ckids > 0 ) {
1103                         /* Walk the kids tree; order is irrelevant since bdb_idl_sort
1104                          * will sort it later.
1105                          */
1106                         avl_apply( cx->ei->bei_kids, apply_func,
1107                                 cx->tmp, -1, AVL_POSTORDER );
1108                 }
1109                 bdb_cache_entryinfo_unlock( cx->ei );
1110         }
1111
1112         if ( !BDB_IDL_IS_RANGE( cx->tmp ) && cx->tmp[0] > 3 )
1113                 bdb_idl_sort( cx->tmp, cx->buf );
1114         if ( cx->bdb->bi_idl_cache_max_size && !BDB_IDL_IS_ZERO( cx->tmp )) {
1115                 char *ptr = ((char *)&cx->id)-1;
1116                 cx->key.data = ptr;
1117                 cx->key.size = sizeof(ID)+1;
1118                 *ptr = DN_ONE_PREFIX;
1119                 bdb_idl_cache_put( cx->bdb, cx->db, &cx->key, cx->tmp, cx->rc );
1120         }
1121
1122 gotit:
1123         if ( !BDB_IDL_IS_ZERO( cx->tmp )) {
1124                 if ( cx->prefix == DN_SUBTREE_PREFIX ) {
1125                         bdb_idl_append( cx->ids, cx->tmp );
1126                         cx->need_sort = 1;
1127                         if ( !(cx->ei->bei_state & CACHE_ENTRY_NO_GRANDKIDS)) {
1128                                 ID *save, idcurs;
1129                                 EntryInfo *ei = cx->ei;
1130                                 int nokids = 1;
1131                                 save = cx->op->o_tmpalloc( BDB_IDL_SIZEOF( cx->tmp ),
1132                                         cx->op->o_tmpmemctx );
1133                                 BDB_IDL_CPY( save, cx->tmp );
1134
1135                                 idcurs = 0;
1136                                 cx->depth++;
1137                                 for ( cx->id = bdb_idl_first( save, &idcurs );
1138                                         cx->id != NOID;
1139                                         cx->id = bdb_idl_next( save, &idcurs )) {
1140                                         cx->ei = bdb_cache_find_info( cx->bdb, cx->id );
1141                                         if ( !cx->ei ||
1142                                                 ( cx->ei->bei_state & CACHE_ENTRY_NO_KIDS ))
1143                                                 continue;
1144
1145                                         BDB_ID2DISK( cx->id, &cx->nid );
1146                                         hdb_dn2idl_internal( cx );
1147                                         if ( !BDB_IDL_IS_ZERO( cx->tmp ))
1148                                                 nokids = 0;
1149                                 }
1150                                 cx->depth--;
1151                                 cx->op->o_tmpfree( save, cx->op->o_tmpmemctx );
1152                                 if ( nokids ) ei->bei_state |= CACHE_ENTRY_NO_GRANDKIDS;
1153                         }
1154                         /* Make sure caller knows it had kids! */
1155                         cx->tmp[0]=1;
1156
1157                         cx->rc = 0;
1158                 } else {
1159                         BDB_IDL_CPY( cx->ids, cx->tmp );
1160                 }
1161         }
1162         return cx->rc;
1163 }
1164
1165 int
1166 hdb_dn2idl(
1167         Operation       *op,
1168         Entry           *e,
1169         ID *ids,
1170         ID *stack )
1171 {
1172         struct bdb_info *bdb = (struct bdb_info *)op->o_bd->be_private;
1173         struct dn2id_cookie cx;
1174
1175         Debug( LDAP_DEBUG_TRACE, "=> hdb_dn2idl(\"%s\")\n",
1176                 e->e_nname.bv_val, 0, 0 );
1177
1178 #ifndef BDB_MULTIPLE_SUFFIXES
1179         if ( op->ors_scope != LDAP_SCOPE_ONELEVEL &&
1180                 BEI(e)->bei_parent->bei_id == 0 )
1181         {
1182                 BDB_IDL_ALL( bdb, ids );
1183                 return 0;
1184         }
1185 #endif
1186
1187         cx.id = e->e_id;
1188         BDB_ID2DISK( cx.id, &cx.nid );
1189         cx.ei = e->e_id ? BEI(e) : &bdb->bi_cache.c_dntree;
1190         cx.bdb = bdb;
1191         cx.db = cx.bdb->bi_dn2id->bdi_db;
1192         cx.prefix = (op->ors_scope == LDAP_SCOPE_ONELEVEL) ?
1193                 DN_ONE_PREFIX : DN_SUBTREE_PREFIX;
1194         cx.ids = ids;
1195         cx.tmp = stack;
1196         cx.buf = stack + BDB_IDL_UM_SIZE;
1197         cx.op = op;
1198         cx.need_sort = 0;
1199         cx.depth = 0;
1200
1201         if ( cx.prefix == DN_SUBTREE_PREFIX ) {
1202                 ids[0] = 1;
1203                 ids[1] = cx.id;
1204         } else {
1205                 BDB_IDL_ZERO( ids );
1206         }
1207         if ( cx.ei->bei_state & CACHE_ENTRY_NO_KIDS )
1208                 return LDAP_SUCCESS;
1209
1210         DBTzero(&cx.key);
1211         cx.key.ulen = sizeof(ID);
1212         cx.key.size = sizeof(ID);
1213         cx.key.flags = DB_DBT_USERMEM;
1214
1215         DBTzero(&cx.data);
1216
1217         hdb_dn2idl_internal(&cx);
1218         if ( cx.need_sort ) {
1219                 char *ptr = ((char *)&cx.id)-1;
1220                 if ( !BDB_IDL_IS_RANGE( cx.ids ) && cx.ids[0] > 3 )
1221                         bdb_idl_sort( cx.ids, cx.tmp );
1222                 cx.key.data = ptr;
1223                 cx.key.size = sizeof(ID)+1;
1224                 *ptr = cx.prefix;
1225                 cx.id = e->e_id;
1226                 bdb_idl_cache_put( cx.bdb, cx.db, &cx.key, cx.ids, cx.rc );
1227         }
1228
1229         if ( cx.rc == DB_NOTFOUND )
1230                 cx.rc = LDAP_SUCCESS;
1231
1232         return cx.rc;
1233 }
1234 #endif  /* BDB_HIER */