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