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