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