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