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