git.sur5r.net Git - openldap/blob - servers/slapd/back-ldbm/idl.c

   1 /* idl.c - ldap id list handling routines */
   2 /* $OpenLDAP$ */
   3 /*
   4  * Copyright 1998-2000 The OpenLDAP Foundation, All Rights Reserved.
   5  * COPYING RESTRICTIONS APPLY, see COPYRIGHT file
   6  */
   7
   8 #include "portable.h"
   9
  10 #include <stdio.h>
  11
  12 #include <ac/string.h>
  13 #include <ac/socket.h>
  14
  15 #include "slap.h"
  16 #include "back-ldbm.h"
  17
  18 static ID_BLOCK* idl_dup( ID_BLOCK *idl );
  19
  20 static void cont_alloc( Datum *cont, Datum *key )
  21 {
  22         ldbm_datum_init( *cont );
  23         cont->dsize = 1 + sizeof(ID) + key->dsize;
  24         cont->dptr = ch_malloc( cont->dsize );
  25
  26         * (unsigned char *) cont->dptr = SLAP_INDEX_CONT_PREFIX;
  27
  28         AC_MEMCPY( &((unsigned char *)cont->dptr)[1 + sizeof(ID)],
  29                 key->dptr, key->dsize );
  30 }
  31
  32 static void cont_id( Datum *cont, ID id )
  33 {
  34         int i;
  35
  36         for( i=1; i <= sizeof(id); i++) {
  37                 ((unsigned char *)cont->dptr)[i] = (unsigned char)(id & 0xFF);
  38                 id >>= 8;
  39         }
  40
  41 }
  42
  43 static void cont_free( Datum *cont )
  44 {
  45         ch_free( cont->dptr );
  46 }
  47
  48 /* Allocate an ID_BLOCK with room for nids ids */
  49 ID_BLOCK *
  50 idl_alloc( unsigned int nids )
  51 {
  52         ID_BLOCK        *new;
  53
  54         /* nmax + nids + space for the ids */
  55         new = (ID_BLOCK *) ch_calloc( (ID_BLOCK_IDS_OFFSET + nids), sizeof(ID) );
  56         ID_BLOCK_NMAX(new) = nids;
  57         ID_BLOCK_NIDS(new) = 0;
  58
  59         return( new );
  60 }
  61
  62
  63 /* Allocate an empty ALLIDS ID_BLOCK */
  64 ID_BLOCK        *
  65 idl_allids( Backend *be )
  66 {
  67         ID_BLOCK        *idl;
  68
  69         idl = idl_alloc( 0 );
  70         ID_BLOCK_NMAX(idl) = ID_BLOCK_ALLIDS_VALUE;
  71         ID_BLOCK_NIDS(idl) = next_id_get( be );
  72
  73         return( idl );
  74 }
  75
  76 /* Free an ID_BLOCK */
  77 void
  78 idl_free( ID_BLOCK *idl )
  79 {
  80         if ( idl == NULL ) {
  81 #ifdef NEW_LOGGING
  82                 LDAP_LOG(( "cache", LDAP_LEVEL_INFO,
  83                            "idl_freee: called with NULL pointer\n" ));
  84 #else
  85                 Debug( LDAP_DEBUG_TRACE,
  86                         "idl_free: called with NULL pointer\n",
  87                         0, 0, 0 );
  88 #endif
  89
  90                 return;
  91         }
  92
  93         free( (char *) idl );
  94 }
  95
  96
  97 /* Fetch an single ID_BLOCK from the cache */
  98 static ID_BLOCK *
  99 idl_fetch_one(
 100     Backend             *be,
 101     DBCache     *db,
 102     Datum               key
 103 )
 104 {
 105         Datum   data;
 106         ID_BLOCK        *idl;
 107
 108         /* Debug( LDAP_DEBUG_TRACE, "=> idl_fetch_one\n", 0, 0, 0 ); */
 109
 110         data = ldbm_cache_fetch( db, key );
 111
 112         if( data.dptr == NULL ) {
 113                 return NULL;
 114         }
 115
 116         idl = idl_dup((ID_BLOCK *) data.dptr);
 117
 118         ldbm_datum_free( db->dbc_db, data );
 119
 120         return idl;
 121 }
 122
 123
 124 /* Fetch a set of ID_BLOCKs from the cache
 125  *      if not INDIRECT
 126  *              if block return is an ALLIDS block,
 127  *                      return an new ALLIDS block
 128  *              otherwise
 129  *                      return block
 130  *      construct super block from all blocks referenced by INDIRECT block
 131  *      return super block
 132  */
 133 ID_BLOCK *
 134 idl_fetch(
 135     Backend             *be,
 136     DBCache     *db,
 137     Datum               key
 138 )
 139 {
 140         Datum   data;
 141         ID_BLOCK        *idl;
 142         ID_BLOCK        **tmp;
 143         int     i, nids;
 144
 145         idl = idl_fetch_one( be, db, key );
 146
 147         if ( idl == NULL ) {
 148                 return NULL;
 149         }
 150
 151         if ( ID_BLOCK_ALLIDS(idl) ) {
 152                 /* all ids block */
 153                 /* make sure we have the current value of highest id */
 154                 idl_free( idl );
 155                 idl = idl_allids( be );
 156
 157                 return( idl );
 158         }
 159
 160         if ( ! ID_BLOCK_INDIRECT( idl ) ) {
 161                 /* regular block */
 162                 return( idl );
 163         }
 164
 165         /*
 166          * this is an indirect block which points to other blocks.
 167          * we need to read in all the blocks it points to and construct
 168          * a big id list containing all the ids, which we will return.
 169          */
 170
 171         /* count the number of blocks & allocate space for pointers to them */
 172         for ( i = 0; !ID_BLOCK_NOID(idl, i); i++ )
 173                 ;       /* NULL */
 174         tmp = (ID_BLOCK **) ch_malloc( (i + 1) * sizeof(ID_BLOCK *) );
 175
 176         /* read in all the blocks */
 177         cont_alloc( &data, &key );
 178         nids = 0;
 179         for ( i = 0; !ID_BLOCK_NOID(idl, i); i++ ) {
 180                 cont_id( &data, ID_BLOCK_ID(idl, i) );
 181
 182                 if ( (tmp[i] = idl_fetch_one( be, db, data )) == NULL ) {
 183 #ifdef NEW_LOGGING
 184                         LDAP_LOG(( "cache", LDAP_LEVEL_INFO,
 185                                    "idl_fetch: idl_fetch_one returned NULL\n" ));
 186 #else
 187                         Debug( LDAP_DEBUG_ANY,
 188                             "idl_fetch: one returned NULL\n", 0, 0, 0 );
 189 #endif
 190
 191                         continue;
 192                 }
 193
 194                 nids += ID_BLOCK_NIDS(tmp[i]);
 195         }
 196         tmp[i] = NULL;
 197         cont_free( &data );
 198         idl_free( idl );
 199
 200         /* allocate space for the big block */
 201         idl = idl_alloc( nids );
 202         ID_BLOCK_NIDS(idl) = nids;
 203         nids = 0;
 204
 205         /* copy in all the ids from the component blocks */
 206         for ( i = 0; tmp[i] != NULL; i++ ) {
 207                 if ( tmp[i] == NULL ) {
 208                         continue;
 209                 }
 210
 211                 AC_MEMCPY(
 212                         (char *) &ID_BLOCK_ID(idl, nids),
 213                         (char *) &ID_BLOCK_ID(tmp[i], 0),
 214                         ID_BLOCK_NIDS(tmp[i]) * sizeof(ID) );
 215                 nids += ID_BLOCK_NIDS(tmp[i]);
 216
 217                 idl_free( tmp[i] );
 218         }
 219         free( (char *) tmp );
 220
 221 #ifdef NEW_LOGGING
 222         LDAP_LOG(( "cache", LDAP_LEVEL_ENTRY,
 223                    "idl_fetch: %ld ids (%ld max)\n",
 224                    ID_BLOCK_NIDS(idl), ID_BLOCK_NMAX(idl) ));
 225 #else
 226         Debug( LDAP_DEBUG_TRACE, "<= idl_fetch %ld ids (%ld max)\n",
 227                ID_BLOCK_NIDS(idl), ID_BLOCK_NMAX(idl), 0 );
 228 #endif
 229
 230         return( idl );
 231 }
 232
 233
 234 /* store a single block */
 235 static int
 236 idl_store(
 237     Backend             *be,
 238     DBCache     *db,
 239     Datum               key,
 240     ID_BLOCK            *idl
 241 )
 242 {
 243         int     rc, flags;
 244         Datum   data;
 245         struct ldbminfo *li = (struct ldbminfo *) be->be_private;
 246
 247         ldbm_datum_init( data );
 248
 249         /* Debug( LDAP_DEBUG_TRACE, "=> idl_store\n", 0, 0, 0 ); */
 250
 251         data.dptr = (char *) idl;
 252         data.dsize = (ID_BLOCK_IDS_OFFSET + ID_BLOCK_NMAX(idl)) * sizeof(ID);
 253
 254 #ifdef LDBM_DEBUG
 255         Statslog( LDAP_DEBUG_STATS, "<= idl_store(): rc=%d\n",
 256                 rc, 0, 0, 0, 0 );
 257 #endif
 258
 259         flags = LDBM_REPLACE;
 260         rc = ldbm_cache_store( db, key, data, flags );
 261
 262         /* Debug( LDAP_DEBUG_TRACE, "<= idl_store %d\n", rc, 0, 0 ); */
 263         return( rc );
 264 }
 265
 266 /* split the block at id
 267  *      locate ID greater than or equal to id.
 268  */
 269 static void
 270 idl_split_block(
 271     ID_BLOCK    *b,
 272     ID          id,
 273     ID_BLOCK    **right,
 274     ID_BLOCK    **left
 275 )
 276 {
 277         unsigned int    nr, nl;
 278
 279         /* find where to split the block *//* XXX linear search XXX */
 280         for ( nr = 0; nr < ID_BLOCK_NIDS(b) && id > ID_BLOCK_ID(b, nr); nr++ )
 281                 ;       /* NULL */
 282
 283         nl = ID_BLOCK_NIDS(b) - nr;
 284
 285         *right = idl_alloc( nr == 0 ? 1 : nr );
 286         *left = idl_alloc( nl + (nr == 0 ? 0 : 1));
 287
 288         /*
 289          * everything before the id being inserted in the first block
 290          * unless there is nothing, in which case the id being inserted
 291          * goes there.
 292          */
 293         if ( nr == 0 ) {
 294                 ID_BLOCK_NIDS(*right) = 1;
 295                 ID_BLOCK_ID(*right, 0) = id;
 296         } else {
 297                 AC_MEMCPY(
 298                         (char *) &ID_BLOCK_ID(*right, 0),
 299                         (char *) &ID_BLOCK_ID(b, 0),
 300                         nr * sizeof(ID) );
 301                 ID_BLOCK_NIDS(*right) = nr;
 302                 ID_BLOCK_ID(*left, 0) = id;
 303         }
 304
 305         /* the id being inserted & everything after in the second block */
 306         AC_MEMCPY(
 307                 (char *) &ID_BLOCK_ID(*left, (nr == 0 ? 0 : 1)),
 308             (char *) &ID_BLOCK_ID(b, nr),
 309                 nl * sizeof(ID) );
 310         ID_BLOCK_NIDS(*left) = nl + (nr == 0 ? 0 : 1);
 311 }
 312
 313
 314 /*
 315  * idl_change_first - called when an indirect block's first key has
 316  * changed, meaning it needs to be stored under a new key, and the
 317  * header block pointing to it needs updating.
 318  */
 319 static int
 320 idl_change_first(
 321     Backend             *be,
 322     DBCache     *db,
 323     Datum               hkey,           /* header block key     */
 324     ID_BLOCK            *h,             /* header block         */
 325     int                 pos,            /* pos in h to update   */
 326     Datum               bkey,           /* data block key       */
 327     ID_BLOCK            *b              /* data block           */
 328 )
 329 {
 330         int     rc;
 331
 332         /* Debug( LDAP_DEBUG_TRACE, "=> idl_change_first\n", 0, 0, 0 ); */
 333
 334         /* delete old key block */
 335         if ( (rc = ldbm_cache_delete( db, bkey )) != 0 ) {
 336 #ifdef NEW_LOGGING
 337                 LDAP_LOG(( "cache", LDAP_LEVEL_INFO,
 338                            "idl_change_first: ldbm_cache_delete returned %d\n", rc ));
 339 #else
 340                 Debug( LDAP_DEBUG_ANY,
 341                     "idl_change_first: ldbm_cache_delete returned %d\n",
 342                         rc, 0, 0 );
 343 #endif
 344
 345                 return( rc );
 346         }
 347
 348         /* write block with new key */
 349         cont_id( &bkey, ID_BLOCK_ID(b, 0) );
 350
 351         if ( (rc = idl_store( be, db, bkey, b )) != 0 ) {
 352 #ifdef NEW_LOGGING
 353                 LDAP_LOG(( "cache", LDAP_LEVEL_INFO,
 354                            "idl_change_first: idl_store returned %d\n", rc ));
 355 #else
 356                 Debug( LDAP_DEBUG_ANY,
 357                     "idl_change_first: idl_store returned %d\n", rc, 0, 0 );
 358 #endif
 359
 360                 return( rc );
 361         }
 362
 363         /* update + write indirect header block */
 364         ID_BLOCK_ID(h, pos) = ID_BLOCK_ID(b, 0);
 365         if ( (rc = idl_store( be, db, hkey, h )) != 0 ) {
 366 #ifdef NEW_LOGGING
 367                 LDAP_LOG(( "cache", LDAP_LEVEL_INFO,
 368                            "idl_change_first: idl_store returned %s\n", rc ));
 369 #else
 370                 Debug( LDAP_DEBUG_ANY,
 371                     "idl_change_first: idl_store returned %d\n", rc, 0, 0 );
 372 #endif
 373
 374                 return( rc );
 375         }
 376
 377         return( 0 );
 378 }
 379
 380
 381 int
 382 idl_insert_key(
 383     Backend             *be,
 384     DBCache     *db,
 385     Datum               key,
 386     ID                  id
 387 )
 388 {
 389         int     i, j, first, rc;
 390         ID_BLOCK        *idl, *tmp, *tmp2, *tmp3;
 391         Datum   k2;
 392
 393         if ( (idl = idl_fetch_one( be, db, key )) == NULL ) {
 394                 idl = idl_alloc( 1 );
 395                 ID_BLOCK_ID(idl, ID_BLOCK_NIDS(idl)++) = id;
 396                 rc = idl_store( be, db, key, idl );
 397
 398                 idl_free( idl );
 399                 return( rc );
 400         }
 401
 402         if ( ID_BLOCK_ALLIDS( idl ) ) {
 403                 /* ALLIDS */
 404                 idl_free( idl );
 405                 return 0;
 406         }
 407
 408         if ( ! ID_BLOCK_INDIRECT( idl ) ) {
 409                 /* regular block */
 410                 switch ( idl_insert( &idl, id, db->dbc_maxids ) ) {
 411                 case 0:         /* id inserted - store the updated block */
 412                 case 1:
 413                         rc = idl_store( be, db, key, idl );
 414                         break;
 415
 416                 case 2:         /* id already there - nothing to do */
 417                         rc = 0;
 418                         break;
 419
 420                 case 3:         /* id not inserted - block must be split */
 421                         /* check threshold for marking this an all-id block */
 422                         if ( db->dbc_maxindirect < 2 ) {
 423                                 idl_free( idl );
 424                                 idl = idl_allids( be );
 425                                 rc = idl_store( be, db, key, idl );
 426                                 break;
 427                         }
 428
 429                         idl_split_block( idl, id, &tmp, &tmp2 );
 430                         idl_free( idl );
 431
 432                         /* create the header indirect block */
 433                         idl = idl_alloc( 3 );
 434                         ID_BLOCK_NMAX(idl) = 3;
 435                         ID_BLOCK_NIDS(idl) = ID_BLOCK_INDIRECT_VALUE;
 436                         ID_BLOCK_ID(idl, 0) = ID_BLOCK_ID(tmp, 0);
 437                         ID_BLOCK_ID(idl, 1) = ID_BLOCK_ID(tmp2, 0);
 438                         ID_BLOCK_ID(idl, 2) = NOID;
 439
 440                         /* store it */
 441                         rc = idl_store( be, db, key, idl );
 442
 443                         cont_alloc( &k2, &key );
 444                         cont_id( &k2, ID_BLOCK_ID(tmp, 0) );
 445
 446                         rc = idl_store( be, db, k2, tmp );
 447
 448                         cont_id( &k2, ID_BLOCK_ID(tmp2, 0) );
 449                         rc = idl_store( be, db, k2, tmp2 );
 450
 451                         cont_free( &k2 );
 452
 453                         idl_free( tmp );
 454                         idl_free( tmp2 );
 455                         break;
 456                 }
 457
 458                 idl_free( idl );
 459                 return( rc );
 460         }
 461
 462         /*
 463          * this is an indirect block which points to other blocks.
 464          * we need to read in the block into which the id should be
 465          * inserted, then insert the id and store the block.  we might
 466          * have to split the block if it is full, which means we also
 467          * need to write a new "header" block.
 468          */
 469
 470         /* select the block to try inserting into *//* XXX linear search XXX */
 471         for ( i = 0; !ID_BLOCK_NOID(idl, i) && id > ID_BLOCK_ID(idl, i); i++ )
 472                 ;       /* NULL */
 473
 474         if ( i != 0 ) {
 475                 i--;
 476                 first = 0;
 477         } else {
 478                 first = 1;
 479         }
 480
 481         /* get the block */
 482         cont_alloc( &k2, &key );
 483         cont_id( &k2, ID_BLOCK_ID(idl, i) );
 484
 485         if ( (tmp = idl_fetch_one( be, db, k2 )) == NULL ) {
 486 #ifdef NEW_LOGGING
 487                 LDAP_LOG(( "cache", LDAP_LEVEL_ERR,
 488                            "idl_insert_key: nonexistent continuation block\n" ));
 489 #else
 490                 Debug( LDAP_DEBUG_ANY, "idl_insert_key: nonexistent continuation block\n",
 491                     0, 0, 0 );
 492 #endif
 493
 494                 cont_free( &k2 );
 495                 idl_free( idl );
 496                 return( -1 );
 497         }
 498
 499         /* insert the id */
 500         switch ( idl_insert( &tmp, id, db->dbc_maxids ) ) {
 501         case 0:         /* id inserted ok */
 502                 if ( (rc = idl_store( be, db, k2, tmp )) != 0 ) {
 503 #ifdef NEW_LOGGING
 504                         LDAP_LOG(( "cache", LDAP_LEVEL_ERR,
 505                                    "ids_insert_key: idl_store returned %d\n", rc ));
 506 #else
 507                         Debug( LDAP_DEBUG_ANY,
 508                             "idl_insert_key: idl_store returned %d\n", rc, 0, 0 );
 509 #endif
 510
 511                 }
 512                 break;
 513
 514         case 1:         /* id inserted - first id in block has changed */
 515                 /*
 516                  * key for this block has changed, so we have to
 517                  * write the block under the new key, delete the
 518                  * old key block + update and write the indirect
 519                  * header block.
 520                  */
 521
 522                 rc = idl_change_first( be, db, key, idl, i, k2, tmp );
 523                 break;
 524
 525         case 2:         /* id not inserted - already there, do nothing */
 526                 rc = 0;
 527                 break;
 528
 529         case 3:         /* id not inserted - block is full */
 530                 /*
 531                  * first, see if it will fit in the next block,
 532                  * without splitting, unless we're trying to insert
 533                  * into the beginning of the first block.
 534                  */
 535
 536                 /* is there a next block? */
 537                 if ( !first && !ID_BLOCK_NOID(idl, i + 1) ) {
 538                         /* read it in */
 539                         cont_alloc( &k2, &key );
 540                         cont_id( &k2, ID_BLOCK_ID(idl, i) );
 541                         if ( (tmp2 = idl_fetch_one( be, db, k2 )) == NULL ) {
 542 #ifdef NEW_LOGGING
 543                                 LDAP_LOG(( "cache", LDAP_LEVEL_ERR,
 544                                            "idl_insert_key: idl_fetch_one returned NULL\n"));
 545 #else
 546                                 Debug( LDAP_DEBUG_ANY,
 547                                     "idl_insert_key: idl_fetch_one returned NULL\n",
 548                                     0, 0, 0 );
 549 #endif
 550
 551                                 /* split the original block */
 552                                 cont_free( &k2 );
 553                                 goto split;
 554                         }
 555
 556                         /* If the new id is less than the last id in the
 557                          * current block, it must not be put into the next
 558                          * block. Push the last id of the current block
 559                          * into the next block instead.
 560                          */
 561                         if (id < ID_BLOCK_ID(tmp, ID_BLOCK_NIDS(tmp) - 1)) {
 562                             ID id2 = ID_BLOCK_ID(tmp, ID_BLOCK_NIDS(tmp) - 1);
 563                             Datum k3;
 564
 565                             ldbm_datum_init( k3 );
 566
 567                             --ID_BLOCK_NIDS(tmp);
 568                             /* This must succeed since we just popped one
 569                              * ID off the end of it.
 570                              */
 571                             rc = idl_insert( &tmp, id, db->dbc_maxids );
 572
 573                                 k3.dptr = ch_malloc(k2.dsize);
 574                                 k3.dsize = k2.dsize;
 575                                 AC_MEMCPY(k3.dptr, k2.dptr, k3.dsize);
 576                             if ( (rc = idl_store( be, db, k3, tmp )) != 0 ) {
 577 #ifdef NEW_LOGGING
 578                                 LDAP_LOG(( "cache", LDAP_LEVEL_ERR,
 579                                                "idl_insert_key: idl_store returned %d\n", rc ));
 580 #else
 581                                 Debug( LDAP_DEBUG_ANY,
 582                             "idl_insert_key: idl_store returned %d\n", rc, 0, 0 );
 583 #endif
 584
 585                             }
 586
 587                                 free( k3.dptr );
 588
 589                             id = id2;
 590                             /* This new id will necessarily be inserted
 591                              * as the first id of the next block by the
 592                              * following switch() statement.
 593                              */
 594                         }
 595
 596                         switch ( (rc = idl_insert( &tmp2, id,
 597                             db->dbc_maxids )) ) {
 598                         case 1:         /* id inserted first in block */
 599                                 rc = idl_change_first( be, db, key, idl,
 600                                     i + 1, k2, tmp2 );
 601                                 /* FALL */
 602
 603                         case 2:         /* id already there - how? */
 604                         case 0:         /* id inserted: this can never be
 605                                          * the result of idl_insert, because
 606                                          * we guaranteed that idl_change_first
 607                                          * will always be called.
 608                                          */
 609                                 if ( rc == 2 ) {
 610 #ifdef NEW_LOGGING
 611                                         LDAP_LOG(( "cache", LDAP_LEVEL_INFO,
 612                                                    "idl_insert_key: id %ld is already in next block\n",
 613                                                    id ));
 614 #else
 615                                         Debug( LDAP_DEBUG_ANY,
 616                                             "idl_insert_key: id %ld already in next block\n",
 617                                             id, 0, 0 );
 618 #endif
 619
 620                                 }
 621
 622                                 idl_free( tmp );
 623                                 idl_free( tmp2 );
 624                                 idl_free( idl );
 625                                 return( 0 );
 626
 627                         case 3:         /* split the original block */
 628                                 break;
 629                         }
 630
 631                         idl_free( tmp2 );
 632                 }
 633
 634 split:
 635                 /*
 636                  * must split the block, write both new blocks + update
 637                  * and write the indirect header block.
 638                  */
 639
 640                 rc = 0; /* optimistic */
 641
 642
 643                 /* count how many indirect blocks *//* XXX linear count XXX */
 644                 for ( j = 0; !ID_BLOCK_NOID(idl, j); j++ )
 645                         ;       /* NULL */
 646
 647                 /* check it against all-id thresholed */
 648                 if ( j + 1 > db->dbc_maxindirect ) {
 649                         /*
 650                          * we've passed the all-id threshold, meaning
 651                          * that this set of blocks should be replaced
 652                          * by a single "all-id" block.  our job: delete
 653                          * all the indirect blocks, and replace the header
 654                          * block by an all-id block.
 655                          */
 656
 657                         /* delete all indirect blocks */
 658                         for ( j = 0; !ID_BLOCK_NOID(idl, j); j++ ) {
 659                                 cont_id( &k2, ID_BLOCK_ID(idl, j) );
 660
 661                                 rc = ldbm_cache_delete( db, k2 );
 662                         }
 663
 664                         /* store allid block in place of header block */
 665                         idl_free( idl );
 666                         idl = idl_allids( be );
 667                         rc = idl_store( be, db, key, idl );
 668
 669                         cont_free( &k2 );
 670                         idl_free( idl );
 671                         idl_free( tmp );
 672                         return( rc );
 673                 }
 674
 675                 idl_split_block( tmp, id, &tmp2, &tmp3 );
 676                 idl_free( tmp );
 677
 678                 /* create a new updated indirect header block */
 679                 tmp = idl_alloc( ID_BLOCK_NMAX(idl) + 1 );
 680                 ID_BLOCK_NIDS(tmp) = ID_BLOCK_INDIRECT_VALUE;
 681                 /* everything up to the split block */
 682                 AC_MEMCPY(
 683                         (char *) &ID_BLOCK_ID(tmp, 0),
 684                         (char *) &ID_BLOCK_ID(idl, 0),
 685                     i * sizeof(ID) );
 686                 /* the two new blocks */
 687                 ID_BLOCK_ID(tmp, i) = ID_BLOCK_ID(tmp2, 0);
 688                 ID_BLOCK_ID(tmp, i + 1) = ID_BLOCK_ID(tmp3, 0);
 689                 /* everything after the split block */
 690                 AC_MEMCPY(
 691                         (char *) &ID_BLOCK_ID(tmp, i + 2),
 692                         (char *) &ID_BLOCK_ID(idl, i + 1),
 693                         (ID_BLOCK_NMAX(idl) - i - 1) * sizeof(ID) );
 694
 695                 /* store the header block */
 696                 rc = idl_store( be, db, key, tmp );
 697
 698                 /* store the first id block */
 699                 cont_id( &k2, ID_BLOCK_ID(tmp2, 0) );
 700                 rc = idl_store( be, db, k2, tmp2 );
 701
 702                 /* store the second id block */
 703                 cont_id( &k2, ID_BLOCK_ID(tmp3, 0) );
 704                 rc = idl_store( be, db, k2, tmp3 );
 705
 706                 idl_free( tmp2 );
 707                 idl_free( tmp3 );
 708                 break;
 709         }
 710
 711         cont_free( &k2 );
 712         idl_free( tmp );
 713         idl_free( idl );
 714         return( rc );
 715 }
 716
 717
 718 /*
 719  * idl_insert - insert an id into an id list.
 720  *
 721  *      returns
 722  *              0       id inserted
 723  *              1       id inserted, first id in block has changed
 724  *              2       id not inserted, already there
 725  *              3       id not inserted, block must be split
 726  */
 727 int
 728 idl_insert( ID_BLOCK **idl, ID id, unsigned int maxids )
 729 {
 730         unsigned int    i;
 731
 732         if ( ID_BLOCK_ALLIDS( *idl ) ) {
 733                 return( 2 );    /* already there */
 734         }
 735
 736         /* is it already there? *//* XXX linear search XXX */
 737         for ( i = 0; i < ID_BLOCK_NIDS(*idl) && id > ID_BLOCK_ID(*idl, i); i++ ) {
 738                 ;       /* NULL */
 739         }
 740         if ( i < ID_BLOCK_NIDS(*idl) && ID_BLOCK_ID(*idl, i) == id ) {
 741                 return( 2 );    /* already there */
 742         }
 743
 744         /* do we need to make room for it? */
 745         if ( ID_BLOCK_NIDS(*idl) == ID_BLOCK_NMAX(*idl) ) {
 746                 /* make room or indicate block needs splitting */
 747                 if ( ID_BLOCK_NMAX(*idl) >= maxids ) {
 748                         return( 3 );    /* block needs splitting */
 749                 }
 750
 751                 ID_BLOCK_NMAX(*idl) *= 2;
 752                 if ( ID_BLOCK_NMAX(*idl) > maxids ) {
 753                         ID_BLOCK_NMAX(*idl) = maxids;
 754                 }
 755                 *idl = (ID_BLOCK *) ch_realloc( (char *) *idl,
 756                     (ID_BLOCK_NMAX(*idl) + ID_BLOCK_IDS_OFFSET) * sizeof(ID) );
 757         }
 758
 759         /* make a slot for the new id */
 760         AC_MEMCPY( &ID_BLOCK_ID(*idl, i+1), &ID_BLOCK_ID(*idl, i),
 761                     (ID_BLOCK_NIDS(*idl) - i) * sizeof(ID) );
 762
 763         ID_BLOCK_ID(*idl, i) = id;
 764         ID_BLOCK_NIDS(*idl)++;
 765         (void) memset(
 766                 (char *) &ID_BLOCK_ID((*idl), ID_BLOCK_NIDS(*idl)),
 767                 '\0',
 768             (ID_BLOCK_NMAX(*idl) - ID_BLOCK_NIDS(*idl)) * sizeof(ID) );
 769
 770         return( i == 0 ? 1 : 0 );       /* inserted - first id changed or not */
 771 }
 772
 773
 774 int
 775 idl_delete_key (
 776         Backend         *be,
 777         DBCache  *db,
 778         Datum           key,
 779         ID              id
 780 )
 781 {
 782         Datum  data;
 783         ID_BLOCK *idl;
 784         unsigned i;
 785         int j, nids;
 786
 787         if ( (idl = idl_fetch_one( be, db, key ) ) == NULL )
 788         {
 789                 /* It wasn't found.  Hmm... */
 790                 return -1;
 791         }
 792
 793         if ( ID_BLOCK_ALLIDS( idl ) ) {
 794                 idl_free( idl );
 795                 return 0;
 796         }
 797
 798         if ( ! ID_BLOCK_INDIRECT( idl ) ) {
 799                 for ( i=0; i < ID_BLOCK_NIDS(idl); i++ ) {
 800                         if ( ID_BLOCK_ID(idl, i) == id ) {
 801                                 if( --ID_BLOCK_NIDS(idl) == 0 ) {
 802                                         ldbm_cache_delete( db, key );
 803
 804                                 } else {
 805                                         AC_MEMCPY(
 806                                                 &ID_BLOCK_ID(idl, i),
 807                                                 &ID_BLOCK_ID(idl, i+1),
 808                                                 (ID_BLOCK_NIDS(idl)-i) * sizeof(ID) );
 809
 810                                         ID_BLOCK_ID(idl, ID_BLOCK_NIDS(idl)) = NOID;
 811
 812                                         idl_store( be, db, key, idl );
 813                                 }
 814
 815                                 idl_free( idl );
 816                                 return 0;
 817                         }
 818                         /*  We didn't find the ID.  Hmmm... */
 819                 }
 820                 idl_free( idl );
 821                 return -1;
 822         }
 823
 824         /* We have to go through an indirect block and find the ID
 825            in the list of IDL's
 826            */
 827         for ( nids = 0; !ID_BLOCK_NOID(idl, nids); nids++ )
 828                 ;       /* NULL */
 829
 830         cont_alloc( &data, &key );
 831
 832         for ( j = 0; !ID_BLOCK_NOID(idl, j); j++ )
 833         {
 834                 ID_BLOCK *tmp;
 835                 cont_id( &data, ID_BLOCK_ID(idl, j) );
 836
 837                 if ( (tmp = idl_fetch_one( be, db, data )) == NULL ) {
 838 #ifdef NEW_LOGGING
 839                         LDAP_LOG(( "cache", LDAP_LEVEL_INFO,
 840                                    "idl_delete_key: idl_fetch_one returned NULL\n" ));
 841 #else
 842                         Debug( LDAP_DEBUG_ANY,
 843                             "idl_delete_key: idl_fetch of returned NULL\n", 0, 0, 0 );
 844 #endif
 845
 846                         continue;
 847                 }
 848                 /*
 849                    Now try to find the ID in tmp
 850                 */
 851                 for ( i=0; i < ID_BLOCK_NIDS(tmp); i++ )
 852                 {
 853                         if ( ID_BLOCK_ID(tmp, i) == id )
 854                         {
 855                                 AC_MEMCPY(
 856                                         &ID_BLOCK_ID(tmp, i),
 857                                         &ID_BLOCK_ID(tmp, i+1),
 858                                         (ID_BLOCK_NIDS(tmp)-(i+1)) * sizeof(ID));
 859                                 ID_BLOCK_ID(tmp, ID_BLOCK_NIDS(tmp)-1 ) = NOID;
 860                                 ID_BLOCK_NIDS(tmp)--;
 861
 862                                 if ( ID_BLOCK_NIDS(tmp) ) {
 863                                         idl_store ( be, db, data, tmp );
 864
 865                                 } else {
 866                                         ldbm_cache_delete( db, data );
 867                                         AC_MEMCPY(
 868                                                 &ID_BLOCK_ID(idl, j),
 869                                                 &ID_BLOCK_ID(idl, j+1),
 870                                                 (nids-(j+1)) * sizeof(ID));
 871                                         ID_BLOCK_ID(idl, nids-1) = NOID;
 872                                         nids--;
 873                                         if ( ! nids )
 874                                                 ldbm_cache_delete( db, key );
 875                                         else
 876                                                 idl_store( be, db, key, idl );
 877                                 }
 878                                 idl_free( tmp );
 879                                 cont_free( &data );
 880                                 idl_free( idl );
 881                                 return 0;
 882                         }
 883                 }
 884                 idl_free( tmp );
 885         }
 886
 887         cont_free( &data );
 888         idl_free( idl );
 889         return -1;
 890 }
 891
 892
 893 /* return a duplicate of a single ID_BLOCK */
 894 static ID_BLOCK *
 895 idl_dup( ID_BLOCK *idl )
 896 {
 897         ID_BLOCK        *new;
 898
 899         if ( idl == NULL ) {
 900                 return( NULL );
 901         }
 902
 903         new = idl_alloc( ID_BLOCK_NMAX(idl) );
 904
 905         AC_MEMCPY(
 906                 (char *) new,
 907                 (char *) idl,
 908                 (ID_BLOCK_NMAX(idl) + ID_BLOCK_IDS_OFFSET) * sizeof(ID) );
 909
 910         return( new );
 911 }
 912
 913
 914 /* return the smaller ID_BLOCK */
 915 static ID_BLOCK *
 916 idl_min( ID_BLOCK *a, ID_BLOCK *b )
 917 {
 918         return( ID_BLOCK_NIDS(a) > ID_BLOCK_NIDS(b) ? b : a );
 919 }
 920
 921
 922 /*
 923  * idl_intersection - return a intersection b
 924  */
 925 ID_BLOCK *
 926 idl_intersection(
 927     Backend     *be,
 928     ID_BLOCK    *a,
 929     ID_BLOCK    *b
 930 )
 931 {
 932         unsigned int    ai, bi, ni;
 933         ID_BLOCK                *n;
 934
 935         if ( a == NULL || b == NULL ) {
 936                 return( NULL );
 937         }
 938         if ( ID_BLOCK_ALLIDS( a ) ) {
 939                 return( idl_dup( b ) );
 940         }
 941         if ( ID_BLOCK_ALLIDS( b ) ) {
 942                 return( idl_dup( a ) );
 943         }
 944
 945         n = idl_dup( idl_min( a, b ) );
 946
 947         for ( ni = 0, ai = 0, bi = 0; ai < ID_BLOCK_NIDS(a); ai++ ) {
 948                 for ( ;
 949                         bi < ID_BLOCK_NIDS(b) && ID_BLOCK_ID(b, bi) < ID_BLOCK_ID(a, ai);
 950                         bi++ )
 951                 {
 952                         ;       /* NULL */
 953                 }
 954
 955                 if ( bi == ID_BLOCK_NIDS(b) ) {
 956                         break;
 957                 }
 958
 959                 if ( ID_BLOCK_ID(b, bi) == ID_BLOCK_ID(a, ai) ) {
 960                         ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(a, ai);
 961                 }
 962         }
 963
 964         if ( ni == 0 ) {
 965                 idl_free( n );
 966                 return( NULL );
 967         }
 968         ID_BLOCK_NIDS(n) = ni;
 969
 970         return( n );
 971 }
 972
 973
 974 /*
 975  * idl_union - return a union b
 976  */
 977 ID_BLOCK *
 978 idl_union(
 979     Backend     *be,
 980     ID_BLOCK    *a,
 981     ID_BLOCK    *b
 982 )
 983 {
 984         unsigned int    ai, bi, ni;
 985         ID_BLOCK                *n;
 986
 987         if ( a == NULL ) {
 988                 return( idl_dup( b ) );
 989         }
 990         if ( b == NULL ) {
 991                 return( idl_dup( a ) );
 992         }
 993         if ( ID_BLOCK_ALLIDS( a ) || ID_BLOCK_ALLIDS( b ) ) {
 994                 return( idl_allids( be ) );
 995         }
 996
 997         if ( ID_BLOCK_NIDS(b) < ID_BLOCK_NIDS(a) ) {
 998                 n = a;
 999                 a = b;
1000                 b = n;
1001         }
1002
1003         n = idl_alloc( ID_BLOCK_NIDS(a) + ID_BLOCK_NIDS(b) );
1004
1005         for ( ni = 0, ai = 0, bi = 0;
1006                 ai < ID_BLOCK_NIDS(a) && bi < ID_BLOCK_NIDS(b);
1007                 )
1008         {
1009                 if ( ID_BLOCK_ID(a, ai) < ID_BLOCK_ID(b, bi) ) {
1010                         ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(a, ai++);
1011
1012                 } else if ( ID_BLOCK_ID(b, bi) < ID_BLOCK_ID(a, ai) ) {
1013                         ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(b, bi++);
1014
1015                 } else {
1016                         ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(a, ai);
1017                         ai++, bi++;
1018                 }
1019         }
1020
1021         for ( ; ai < ID_BLOCK_NIDS(a); ai++ ) {
1022                 ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(a, ai);
1023         }
1024         for ( ; bi < ID_BLOCK_NIDS(b); bi++ ) {
1025                 ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(b, bi);
1026         }
1027         ID_BLOCK_NIDS(n) = ni;
1028
1029         return( n );
1030 }
1031
1032
1033 /*
1034  * idl_notin - return a intersection ~b (or a minus b)
1035  */
1036 ID_BLOCK *
1037 idl_notin(
1038     Backend     *be,
1039     ID_BLOCK    *a,
1040     ID_BLOCK    *b
1041 )
1042 {
1043         unsigned int    ni, ai, bi;
1044         ID_BLOCK                *n;
1045
1046         if ( a == NULL ) {
1047                 return( NULL );
1048         }
1049         if ( b == NULL || ID_BLOCK_ALLIDS( b )) {
1050                 return( idl_dup( a ) );
1051         }
1052
1053         if ( ID_BLOCK_ALLIDS( a ) ) {
1054                 n = idl_alloc( SLAPD_LDBM_MIN_MAXIDS );
1055                 ni = 0;
1056
1057                 for ( ai = 1, bi = 0;
1058                         ai < ID_BLOCK_NIDS(a) && ni < ID_BLOCK_NMAX(n) && bi < ID_BLOCK_NMAX(b);
1059                         ai++ )
1060                 {
1061                         if ( ID_BLOCK_ID(b, bi) == ai ) {
1062                                 bi++;
1063                         } else {
1064                                 ID_BLOCK_ID(n, ni++) = ai;
1065                         }
1066                 }
1067
1068                 for ( ; ai < ID_BLOCK_NIDS(a) && ni < ID_BLOCK_NMAX(n); ai++ ) {
1069                         ID_BLOCK_ID(n, ni++) = ai;
1070                 }
1071
1072                 if ( ni == ID_BLOCK_NMAX(n) ) {
1073                         idl_free( n );
1074                         return( idl_allids( be ) );
1075                 } else {
1076                         ID_BLOCK_NIDS(n) = ni;
1077                         return( n );
1078                 }
1079         }
1080
1081         n = idl_dup( a );
1082
1083         ni = 0;
1084         for ( ai = 0, bi = 0; ai < ID_BLOCK_NIDS(a); ai++ ) {
1085                 for ( ;
1086                         bi < ID_BLOCK_NIDS(b) && ID_BLOCK_ID(b, bi) < ID_BLOCK_ID(a, ai);
1087                     bi++ )
1088                 {
1089                         ;       /* NULL */
1090                 }
1091
1092                 if ( bi == ID_BLOCK_NIDS(b) ) {
1093                         break;
1094                 }
1095
1096                 if ( ID_BLOCK_ID(b, bi) != ID_BLOCK_ID(a, ai) ) {
1097                         ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(a, ai);
1098                 }
1099         }
1100
1101         for ( ; ai < ID_BLOCK_NIDS(a); ai++ ) {
1102                 ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(a, ai);
1103         }
1104         ID_BLOCK_NIDS(n) = ni;
1105
1106         return( n );
1107 }
1108
1109 /*      return the first ID in the block
1110  *      if ALLIDS block
1111  *              NIDS > 1 return 1
1112  *              otherwise return NOID
1113  *      otherwise return first ID
1114  *
1115  *      cursor is set to 1
1116  */
1117 ID
1118 idl_firstid( ID_BLOCK *idl, ID *cursor )
1119 {
1120         *cursor = 1;
1121
1122         if ( idl == NULL || ID_BLOCK_NIDS(idl) == 0 ) {
1123                 return( NOID );
1124         }
1125
1126         if ( ID_BLOCK_ALLIDS( idl ) ) {
1127                 return( ID_BLOCK_NIDS(idl) > 1 ? 1 : NOID );
1128         }
1129
1130         return( ID_BLOCK_ID(idl, 0) );
1131 }
1132
1133 /*      return next ID
1134  *      if ALLIDS block, cursor is id.
1135  *              increment id
1136  *              if id < NIDS return id
1137  *              otherwise NOID.
1138  *      otherwise cursor is index into block
1139  *              if index < nids
1140  *                      return id at index then increment
1141  */
1142 ID
1143 idl_nextid( ID_BLOCK *idl, ID *cursor )
1144 {
1145         if ( ID_BLOCK_ALLIDS( idl ) ) {
1146                 if( ++(*cursor) < ID_BLOCK_NIDS(idl) ) {
1147                         return *cursor;
1148                 } else {
1149                         return NOID;
1150                 }
1151         }
1152
1153         if ( *cursor < ID_BLOCK_NIDS(idl) ) {
1154                 return( ID_BLOCK_ID(idl, (*cursor)++) );
1155         }
1156
1157         return( NOID );
1158 }