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