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         if ( i != 0 ) {
 564                 i--;
 565                 first = 0;
 566         } else {
 567                 first = 1;
 568         }
 569
 570         /* At this point, the following condition must be true:
 571          * ID_BLOCK_ID(idl, i) <= id && id < ID_BLOCK_ID(idl, i+1)
 572          * except when i is the first or the last block.
 573          */
 574
 575         /* get the block */
 576         cont_alloc( &k2, &key );
 577         cont_id( &k2, ID_BLOCK_ID(idl, i) );
 578
 579         if ( (tmp = idl_fetch_one( be, db, k2 )) == NULL ) {
 580 #ifdef NEW_LOGGING
 581                 LDAP_LOG( INDEX, ERR,
 582                            "idl_insert_key: nonexistent continuation block\n", 0, 0, 0 );
 583 #else
 584                 Debug( LDAP_DEBUG_ANY, "idl_insert_key: nonexistent continuation block\n",
 585                     0, 0, 0 );
 586 #endif
 587
 588                 cont_free( &k2 );
 589                 idl_free( idl );
 590                 return( -1 );
 591         }
 592
 593         /* insert the id */
 594         switch ( idl_insert( &tmp, id, db->dbc_maxids ) ) {
 595         case 0:         /* id inserted ok */
 596                 if ( (rc = idl_store( be, db, k2, tmp )) != 0 ) {
 597 #ifdef NEW_LOGGING
 598                         LDAP_LOG( INDEX, ERR,
 599                                    "ids_insert_key: idl_store returned %d\n", rc, 0, 0 );
 600 #else
 601                         Debug( LDAP_DEBUG_ANY,
 602                             "idl_insert_key: idl_store returned %d\n", rc, 0, 0 );
 603 #endif
 604
 605                 }
 606                 break;
 607
 608         case 1:         /* id inserted - first id in block has changed */
 609                 /*
 610                  * key for this block has changed, so we have to
 611                  * write the block under the new key, delete the
 612                  * old key block + update and write the indirect
 613                  * header block.
 614                  */
 615
 616                 rc = idl_change_first( be, db, key, idl, i, k2, tmp );
 617                 break;
 618
 619         case 2:         /* id not inserted - already there, do nothing */
 620                 rc = 0;
 621                 break;
 622
 623         case 3:         /* id not inserted - block is full */
 624                 /*
 625                  * first, see if it will fit in the next block,
 626                  * without splitting, unless we're trying to insert
 627                  * into the beginning of the first block.
 628                  */
 629
 630 #ifndef USE_INDIRECT_NIDS
 631                 /* is there a next block? */
 632                 if ( !first && !ID_BLOCK_NOID(idl, i + 1) ) {
 633 #else
 634                 if ( !first && (unsigned long)(i + 1) < ID_BLOCK_NIDS(idl) ) {
 635 #endif
 636                         Datum k3;
 637                         /* read it in */
 638                         cont_alloc( &k3, &key );
 639                         cont_id( &k3, ID_BLOCK_ID(idl, i + 1) );
 640                         if ( (tmp2 = idl_fetch_one( be, db, k3 )) == NULL ) {
 641 #ifdef NEW_LOGGING
 642                                 LDAP_LOG( INDEX, ERR,
 643                                            "idl_insert_key: idl_fetch_one returned NULL\n", 0, 0, 0);
 644 #else
 645                                 Debug( LDAP_DEBUG_ANY,
 646                                     "idl_insert_key: idl_fetch_one returned NULL\n",
 647                                     0, 0, 0 );
 648 #endif
 649
 650                                 /* split the original block */
 651                                 cont_free( &k3 );
 652                                 goto split;
 653                         }
 654
 655                         /* If the new id is less than the last id in the
 656                          * current block, it must not be put into the next
 657                          * block. Push the last id of the current block
 658                          * into the next block instead.
 659                          */
 660                         if (id < ID_BLOCK_ID(tmp, ID_BLOCK_NIDS(tmp) - 1)) {
 661                             ID id2 = ID_BLOCK_ID(tmp, ID_BLOCK_NIDS(tmp) - 1);
 662
 663                             --ID_BLOCK_NIDS(tmp);
 664                             /* This must succeed since we just popped one
 665                              * ID off the end of it.
 666                              */
 667                             rc = idl_insert( &tmp, id, db->dbc_maxids );
 668
 669                             if ( (rc = idl_store( be, db, k2, tmp )) != 0 ) {
 670 #ifdef NEW_LOGGING
 671                                 LDAP_LOG( INDEX, ERR,
 672                                         "idl_insert_key: idl_store returned %d\n", rc, 0, 0 );
 673 #else
 674                                 Debug( LDAP_DEBUG_ANY,
 675                             "idl_insert_key: idl_store returned %d\n", rc, 0, 0 );
 676 #endif
 677
 678                             }
 679
 680                             id = id2;
 681                             /* This new id will necessarily be inserted
 682                              * as the first id of the next block by the
 683                              * following switch() statement.
 684                              */
 685                         }
 686
 687                         switch ( (rc = idl_insert( &tmp2, id,
 688                             db->dbc_maxids )) ) {
 689                         case 1:         /* id inserted first in block */
 690                                 rc = idl_change_first( be, db, key, idl,
 691                                     i + 1, k3, tmp2 );
 692                                 /* FALL */
 693
 694                         case 2:         /* id already there - how? */
 695                         case 0:         /* id inserted: this can never be
 696                                          * the result of idl_insert, because
 697                                          * we guaranteed that idl_change_first
 698                                          * will always be called.
 699                                          */
 700                                 if ( rc == 2 ) {
 701 #ifdef NEW_LOGGING
 702                                         LDAP_LOG( INDEX, INFO,
 703                                                    "idl_insert_key: id %ld is already in next block\n",
 704                                                    id, 0, 0 );
 705 #else
 706                                         Debug( LDAP_DEBUG_ANY,
 707                                             "idl_insert_key: id %ld already in next block\n",
 708                                             id, 0, 0 );
 709 #endif
 710
 711                                 }
 712
 713                                 idl_free( tmp );
 714                                 idl_free( tmp2 );
 715                                 cont_free( &k3 );
 716                                 cont_free( &k2 );
 717                                 idl_free( idl );
 718                                 return( 0 );
 719
 720                         case 3:         /* split the original block */
 721                                 break;
 722                         }
 723
 724                         idl_free( tmp2 );
 725                         cont_free( &k3 );
 726                 }
 727
 728 split:
 729                 /*
 730                  * must split the block, write both new blocks + update
 731                  * and write the indirect header block.
 732                  */
 733
 734                 rc = 0; /* optimistic */
 735
 736
 737 #ifndef USE_INDIRECT_NIDS
 738                 /* count how many indirect blocks *//* XXX linear count XXX */
 739                 for ( j = 0; !ID_BLOCK_NOID(idl, j); j++ )
 740                         ;       /* NULL */
 741 #else
 742                 j = ID_BLOCK_NIDS(idl);
 743 #endif
 744
 745                 /* check it against all-id thresholed */
 746                 if ( j + 1 > db->dbc_maxindirect ) {
 747                         /*
 748                          * we've passed the all-id threshold, meaning
 749                          * that this set of blocks should be replaced
 750                          * by a single "all-id" block.  our job: delete
 751                          * all the indirect blocks, and replace the header
 752                          * block by an all-id block.
 753                          */
 754
 755                         /* delete all indirect blocks */
 756 #ifndef USE_INDIRECT_NIDS
 757                         for ( j = 0; !ID_BLOCK_NOID(idl, j); j++ ) {
 758 #else
 759                         for ( j = 0; (unsigned long) j < ID_BLOCK_NIDS(idl); j++ ) {
 760 #endif
 761                                 cont_id( &k2, ID_BLOCK_ID(idl, j) );
 762
 763                                 rc = ldbm_cache_delete( db, k2 );
 764                         }
 765
 766                         /* store allid block in place of header block */
 767                         idl_free( idl );
 768                         idl = idl_allids( be );
 769                         rc = idl_store( be, db, key, idl );
 770
 771                         cont_free( &k2 );
 772                         idl_free( idl );
 773                         idl_free( tmp );
 774                         return( rc );
 775                 }
 776
 777                 idl_split_block( tmp, id, &tmp2, &tmp3 );
 778                 idl_free( tmp );
 779
 780                 /* create a new updated indirect header block */
 781                 tmp = idl_alloc( ID_BLOCK_NMAXN(idl) + 1 );
 782 #ifndef USE_INDIRECT_NIDS
 783                 ID_BLOCK_NIDS(tmp) = ID_BLOCK_INDIRECT_VALUE;
 784 #else
 785                 ID_BLOCK_NMAX(tmp) |= ID_BLOCK_INDIRECT_VALUE;
 786 #endif
 787                 /* everything up to the split block */
 788                 AC_MEMCPY(
 789                         (char *) &ID_BLOCK_ID(tmp, 0),
 790                         (char *) &ID_BLOCK_ID(idl, 0),
 791                     i * sizeof(ID) );
 792                 /* the two new blocks */
 793                 ID_BLOCK_ID(tmp, i) = ID_BLOCK_ID(tmp2, 0);
 794                 ID_BLOCK_ID(tmp, i + 1) = ID_BLOCK_ID(tmp3, 0);
 795                 /* everything after the split block */
 796 #ifndef USE_INDIRECT_NIDS
 797                 AC_MEMCPY(
 798                         (char *) &ID_BLOCK_ID(tmp, i + 2),
 799                         (char *) &ID_BLOCK_ID(idl, i + 1),
 800                         (ID_BLOCK_NMAXN(idl) - i - 1) * sizeof(ID) );
 801 #else
 802                 AC_MEMCPY(
 803                         (char *) &ID_BLOCK_ID(tmp, i + 2),
 804                         (char *) &ID_BLOCK_ID(idl, i + 1),
 805                         (ID_BLOCK_NIDS(idl) - i - 1) * sizeof(ID) );
 806                 ID_BLOCK_NIDS(tmp) = ID_BLOCK_NIDS(idl) + 1;
 807 #endif
 808
 809                 /* store the header block */
 810                 rc = idl_store( be, db, key, tmp );
 811
 812                 /* store the first id block */
 813                 cont_id( &k2, ID_BLOCK_ID(tmp2, 0) );
 814                 rc = idl_store( be, db, k2, tmp2 );
 815
 816                 /* store the second id block */
 817                 cont_id( &k2, ID_BLOCK_ID(tmp3, 0) );
 818                 rc = idl_store( be, db, k2, tmp3 );
 819
 820                 idl_free( tmp2 );
 821                 idl_free( tmp3 );
 822                 break;
 823         }
 824
 825         cont_free( &k2 );
 826         idl_free( tmp );
 827         idl_free( idl );
 828         return( rc );
 829 }
 830
 831
 832 /*
 833  * idl_insert - insert an id into an id list.
 834  *
 835  *      returns
 836  *              0       id inserted
 837  *              1       id inserted, first id in block has changed
 838  *              2       id not inserted, already there
 839  *              3       id not inserted, block must be split
 840  */
 841 int
 842 idl_insert( ID_BLOCK **idl, ID id, unsigned int maxids )
 843 {
 844         unsigned int    i;
 845
 846         if ( ID_BLOCK_ALLIDS( *idl ) ) {
 847                 return( 2 );    /* already there */
 848         }
 849
 850         /* is it already there? */
 851         i = idl_find(*idl, id);
 852         if ( ID_BLOCK_ID(*idl, i) == id ) {
 853                 return( 2 );    /* already there */
 854         }
 855         if ( ID_BLOCK_NIDS(*idl) && ID_BLOCK_ID(*idl, i) < id )
 856                 i++;
 857
 858         /* do we need to make room for it? */
 859         if ( ID_BLOCK_NIDS(*idl) == ID_BLOCK_NMAXN(*idl) ) {
 860                 /* make room or indicate block needs splitting */
 861                 if ( ID_BLOCK_NMAXN(*idl) >= maxids ) {
 862                         return( 3 );    /* block needs splitting */
 863                 }
 864
 865                 ID_BLOCK_NMAX(*idl) *= 2;
 866                 if ( ID_BLOCK_NMAXN(*idl) > maxids ) {
 867                         ID_BLOCK_NMAX(*idl) = maxids;
 868                 }
 869                 *idl = (ID_BLOCK *) ch_realloc( (char *) *idl,
 870                     (ID_BLOCK_NMAXN(*idl) + ID_BLOCK_IDS_OFFSET) * sizeof(ID) );
 871         }
 872
 873         /* make a slot for the new id */
 874         AC_MEMCPY( &ID_BLOCK_ID(*idl, i+1), &ID_BLOCK_ID(*idl, i),
 875                     (ID_BLOCK_NIDS(*idl) - i) * sizeof(ID) );
 876
 877         ID_BLOCK_ID(*idl, i) = id;
 878         ID_BLOCK_NIDS(*idl)++;
 879         (void) memset(
 880                 (char *) &ID_BLOCK_ID((*idl), ID_BLOCK_NIDS(*idl)),
 881                 '\0',
 882             (ID_BLOCK_NMAXN(*idl) - ID_BLOCK_NIDS(*idl)) * sizeof(ID) );
 883
 884 #ifdef LDBM_DEBUG_IDL
 885         idl_check(*idl);
 886 #endif
 887
 888         return( i == 0 ? 1 : 0 );       /* inserted - first id changed or not */
 889 }
 890
 891
 892 int
 893 idl_delete_key (
 894         Backend         *be,
 895         DBCache  *db,
 896         Datum           key,
 897         ID              id
 898 )
 899 {
 900         Datum  data;
 901         ID_BLOCK *idl;
 902         unsigned i;
 903         int j, nids;
 904
 905         if ( (idl = idl_fetch_one( be, db, key ) ) == NULL )
 906         {
 907                 /* It wasn't found.  Hmm... */
 908                 return -1;
 909         }
 910
 911         if ( ID_BLOCK_ALLIDS( idl ) ) {
 912                 idl_free( idl );
 913                 return 0;
 914         }
 915
 916         if ( ! ID_BLOCK_INDIRECT( idl ) ) {
 917                 i = idl_find(idl, id);
 918                 if ( ID_BLOCK_ID(idl, i) == id ) {
 919                         if( --ID_BLOCK_NIDS(idl) == 0 ) {
 920                                 ldbm_cache_delete( db, key );
 921
 922                         } else {
 923                                 AC_MEMCPY(
 924                                         &ID_BLOCK_ID(idl, i),
 925                                         &ID_BLOCK_ID(idl, i+1),
 926                                         (ID_BLOCK_NIDS(idl)-i) * sizeof(ID) );
 927
 928                                 ID_BLOCK_ID(idl, ID_BLOCK_NIDS(idl)) = NOID;
 929
 930                                 idl_store( be, db, key, idl );
 931                         }
 932
 933                         idl_free( idl );
 934                         return 0;
 935                 }
 936                 /*  We didn't find the ID.  Hmmm... */
 937                 idl_free( idl );
 938                 return -1;
 939         }
 940
 941         /* We have to go through an indirect block and find the ID
 942            in the list of IDL's
 943            */
 944         cont_alloc( &data, &key );
 945 #ifndef USE_INDIRECT_NIDS
 946         for ( nids = 0; !ID_BLOCK_NOID(idl, nids); nids++ )
 947                 ;       /* NULL */
 948
 949         for ( j = 0; j<nids; j++ )
 950 #else
 951         nids = ID_BLOCK_NIDS(idl);
 952         for ( j = idl_find(idl, id); j >= 0; j = -1)    /* execute once */
 953 #endif
 954         {
 955                 ID_BLOCK *tmp;
 956                 cont_id( &data, ID_BLOCK_ID(idl, j) );
 957
 958                 if ( (tmp = idl_fetch_one( be, db, data )) == NULL ) {
 959 #ifdef NEW_LOGGING
 960                         LDAP_LOG( INDEX, INFO,
 961                                    "idl_delete_key: idl_fetch_one returned NULL\n", 0, 0, 0 );
 962 #else
 963                         Debug( LDAP_DEBUG_ANY,
 964                             "idl_delete_key: idl_fetch of returned NULL\n", 0, 0, 0 );
 965 #endif
 966
 967                         continue;
 968                 }
 969                 /*
 970                    Now try to find the ID in tmp
 971                 */
 972
 973                 i = idl_find(tmp, id);
 974                 if ( ID_BLOCK_ID(tmp, i) == id )
 975                 {
 976                         AC_MEMCPY(
 977                                 &ID_BLOCK_ID(tmp, i),
 978                                 &ID_BLOCK_ID(tmp, i+1),
 979                                 (ID_BLOCK_NIDS(tmp)-(i+1)) * sizeof(ID));
 980                         ID_BLOCK_ID(tmp, ID_BLOCK_NIDS(tmp)-1 ) = NOID;
 981                         ID_BLOCK_NIDS(tmp)--;
 982
 983                         if ( ID_BLOCK_NIDS(tmp) ) {
 984                                 idl_store ( be, db, data, tmp );
 985
 986                         } else {
 987                                 ldbm_cache_delete( db, data );
 988                                 AC_MEMCPY(
 989                                         &ID_BLOCK_ID(idl, j),
 990                                         &ID_BLOCK_ID(idl, j+1),
 991                                         (nids-(j+1)) * sizeof(ID));
 992                                 ID_BLOCK_ID(idl, nids-1) = NOID;
 993                                 nids--;
 994 #ifdef USE_INDIRECT_NIDS
 995                                 ID_BLOCK_NIDS(idl)--;
 996 #endif
 997                                 if ( ! nids )
 998                                         ldbm_cache_delete( db, key );
 999                                 else
1000                                         idl_store( be, db, key, idl );
1001                         }
1002                         idl_free( tmp );
1003                         cont_free( &data );
1004                         idl_free( idl );
1005                         return 0;
1006                 }
1007                 idl_free( tmp );
1008         }
1009
1010         cont_free( &data );
1011         idl_free( idl );
1012         return -1;
1013 }
1014
1015
1016 /* return a duplicate of a single ID_BLOCK */
1017 static ID_BLOCK *
1018 idl_dup( ID_BLOCK *idl )
1019 {
1020         ID_BLOCK        *new;
1021
1022         if ( idl == NULL ) {
1023                 return( NULL );
1024         }
1025
1026         new = idl_alloc( ID_BLOCK_NMAXN(idl) );
1027
1028         AC_MEMCPY(
1029                 (char *) new,
1030                 (char *) idl,
1031                 (ID_BLOCK_NMAXN(idl) + ID_BLOCK_IDS_OFFSET) * sizeof(ID) );
1032
1033 #ifdef LDBM_DEBUG_IDL
1034         idl_check(new);
1035 #endif
1036
1037         return( new );
1038 }
1039
1040
1041 /* return the smaller ID_BLOCK */
1042 static ID_BLOCK *
1043 idl_min( ID_BLOCK *a, ID_BLOCK *b )
1044 {
1045         return( ID_BLOCK_NIDS(a) > ID_BLOCK_NIDS(b) ? b : a );
1046 }
1047
1048
1049 /*
1050  * idl_intersection - return a intersection b
1051  */
1052 ID_BLOCK *
1053 idl_intersection(
1054     Backend     *be,
1055     ID_BLOCK    *a,
1056     ID_BLOCK    *b
1057 )
1058 {
1059         unsigned int    ai, bi, ni;
1060         ID_BLOCK                *n;
1061
1062         if ( a == NULL || b == NULL ) {
1063                 return( NULL );
1064         }
1065         if ( ID_BLOCK_ALLIDS( a ) ) {
1066                 return( idl_dup( b ) );
1067         }
1068         if ( ID_BLOCK_ALLIDS( b ) ) {
1069                 return( idl_dup( a ) );
1070         }
1071         if ( ID_BLOCK_NIDS(a) == 0 || ID_BLOCK_NIDS(b) == 0 ) {
1072                 return( NULL );
1073         }
1074
1075         n = idl_dup( idl_min( a, b ) );
1076
1077 #ifdef LDBM_DEBUG_IDL
1078         idl_check(a);
1079         idl_check(b);
1080 #endif
1081
1082         for ( ni = 0, ai = 0, bi = 0; ; ) {
1083                 if ( ID_BLOCK_ID(b, bi) == ID_BLOCK_ID(a, ai) ) {
1084                         ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(a, ai);
1085                         ai++;
1086                         bi++;
1087                         if ( ai >= ID_BLOCK_NIDS(a) || bi >= ID_BLOCK_NIDS(b) )
1088                                 break;
1089                 } else if ( ID_BLOCK_ID(a, ai) < ID_BLOCK_ID(b, bi) ) {
1090                         ai++;
1091                         if ( ai >= ID_BLOCK_NIDS(a) )
1092                                 break;
1093                 } else {
1094                         bi++;
1095                         if ( bi >= ID_BLOCK_NIDS(b) )
1096                                 break;
1097                 }
1098         }
1099
1100         if ( ni == 0 ) {
1101                 idl_free( n );
1102                 return( NULL );
1103         }
1104         ID_BLOCK_NIDS(n) = ni;
1105
1106 #ifdef LDBM_DEBUG_IDL
1107         idl_check(n);
1108 #endif
1109
1110         return( n );
1111 }
1112
1113
1114 /*
1115  * idl_union - return a union b
1116  */
1117 ID_BLOCK *
1118 idl_union(
1119     Backend     *be,
1120     ID_BLOCK    *a,
1121     ID_BLOCK    *b
1122 )
1123 {
1124         unsigned int    ai, bi, ni;
1125         ID_BLOCK                *n;
1126
1127         if ( a == NULL ) {
1128                 return( idl_dup( b ) );
1129         }
1130         if ( b == NULL ) {
1131                 return( idl_dup( a ) );
1132         }
1133         if ( ID_BLOCK_ALLIDS( a ) || ID_BLOCK_ALLIDS( b ) ) {
1134                 return( idl_allids( be ) );
1135         }
1136
1137 #ifdef LDBM_DEBUG_IDL
1138         idl_check(a);
1139         idl_check(b);
1140 #endif
1141
1142         if ( ID_BLOCK_NIDS(b) < ID_BLOCK_NIDS(a) ) {
1143                 n = a;
1144                 a = b;
1145                 b = n;
1146         }
1147
1148         n = idl_alloc( ID_BLOCK_NIDS(a) + ID_BLOCK_NIDS(b) );
1149
1150         for ( ni = 0, ai = 0, bi = 0;
1151                 ai < ID_BLOCK_NIDS(a) && bi < ID_BLOCK_NIDS(b);
1152                 )
1153         {
1154                 if ( ID_BLOCK_ID(a, ai) < ID_BLOCK_ID(b, bi) ) {
1155                         ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(a, ai++);
1156
1157                 } else if ( ID_BLOCK_ID(b, bi) < ID_BLOCK_ID(a, ai) ) {
1158                         ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(b, bi++);
1159
1160                 } else {
1161                         ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(a, ai);
1162                         ai++, bi++;
1163                 }
1164         }
1165
1166         for ( ; ai < ID_BLOCK_NIDS(a); ai++ ) {
1167                 ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(a, ai);
1168         }
1169         for ( ; bi < ID_BLOCK_NIDS(b); bi++ ) {
1170                 ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(b, bi);
1171         }
1172         ID_BLOCK_NIDS(n) = ni;
1173
1174 #ifdef LDBM_DEBUG_IDL
1175         idl_check(n);
1176 #endif
1177
1178         return( n );
1179 }
1180
1181
1182 /*
1183  * idl_notin - return a intersection ~b (or a minus b)
1184  */
1185 ID_BLOCK *
1186 idl_notin(
1187     Backend     *be,
1188     ID_BLOCK    *a,
1189     ID_BLOCK    *b
1190 )
1191 {
1192         unsigned int    ni, ai, bi;
1193         ID_BLOCK                *n;
1194
1195         if ( a == NULL ) {
1196                 return( NULL );
1197         }
1198         if ( b == NULL || ID_BLOCK_ALLIDS( b )) {
1199                 return( idl_dup( a ) );
1200         }
1201
1202         if ( ID_BLOCK_ALLIDS( a ) ) {
1203                 n = idl_alloc( SLAPD_LDBM_MIN_MAXIDS );
1204                 ni = 0;
1205
1206                 for ( ai = 1, bi = 0;
1207                         ai < ID_BLOCK_NIDS(a) && ni < ID_BLOCK_NMAXN(n) && bi < ID_BLOCK_NMAXN(b);
1208                         ai++ )
1209                 {
1210                         if ( ID_BLOCK_ID(b, bi) == ai ) {
1211                                 bi++;
1212                         } else {
1213                                 ID_BLOCK_ID(n, ni++) = ai;
1214                         }
1215                 }
1216
1217                 for ( ; ai < ID_BLOCK_NIDS(a) && ni < ID_BLOCK_NMAXN(n); ai++ ) {
1218                         ID_BLOCK_ID(n, ni++) = ai;
1219                 }
1220
1221                 if ( ni == ID_BLOCK_NMAXN(n) ) {
1222                         idl_free( n );
1223                         return( idl_allids( be ) );
1224                 } else {
1225                         ID_BLOCK_NIDS(n) = ni;
1226                         return( n );
1227                 }
1228         }
1229
1230         n = idl_dup( a );
1231
1232         ni = 0;
1233         for ( ai = 0, bi = 0; ai < ID_BLOCK_NIDS(a); ai++ ) {
1234                 for ( ;
1235                         bi < ID_BLOCK_NIDS(b) && ID_BLOCK_ID(b, bi) < ID_BLOCK_ID(a, ai);
1236                     bi++ )
1237                 {
1238                         ;       /* NULL */
1239                 }
1240
1241                 if ( bi == ID_BLOCK_NIDS(b) ) {
1242                         break;
1243                 }
1244
1245                 if ( ID_BLOCK_ID(b, bi) != ID_BLOCK_ID(a, ai) ) {
1246                         ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(a, ai);
1247                 }
1248         }
1249
1250         for ( ; ai < ID_BLOCK_NIDS(a); ai++ ) {
1251                 ID_BLOCK_ID(n, ni++) = ID_BLOCK_ID(a, ai);
1252         }
1253         ID_BLOCK_NIDS(n) = ni;
1254
1255 #ifdef LDBM_DEBUG_IDL
1256         idl_check(n);
1257 #endif
1258
1259         return( n );
1260 }
1261
1262 /*      return the first ID in the block
1263  *      if ALLIDS block
1264  *              NIDS > 1 return 1
1265  *              otherwise return NOID
1266  *      otherwise return first ID
1267  *
1268  *      cursor is set to 1
1269  */
1270 ID
1271 idl_firstid( ID_BLOCK *idl, ID *cursor )
1272 {
1273         *cursor = 1;
1274
1275         if ( idl == NULL || ID_BLOCK_NIDS(idl) == 0 ) {
1276                 return( NOID );
1277         }
1278
1279         if ( ID_BLOCK_ALLIDS( idl ) ) {
1280                 return( ID_BLOCK_NIDS(idl) > 1 ? 1 : NOID );
1281         }
1282
1283         return( ID_BLOCK_ID(idl, 0) );
1284 }
1285
1286 /*      return next ID
1287  *      if ALLIDS block, cursor is id.
1288  *              increment id
1289  *              if id < NIDS return id
1290  *              otherwise NOID.
1291  *      otherwise cursor is index into block
1292  *              if index < nids
1293  *                      return id at index then increment
1294  */
1295 ID
1296 idl_nextid( ID_BLOCK *idl, ID *cursor )
1297 {
1298         if ( ID_BLOCK_ALLIDS( idl ) ) {
1299                 if( ++(*cursor) < ID_BLOCK_NIDS(idl) ) {
1300                         return *cursor;
1301                 } else {
1302                         return NOID;
1303                 }
1304         }
1305
1306         if ( *cursor < ID_BLOCK_NIDS(idl) ) {
1307                 return( ID_BLOCK_ID(idl, (*cursor)++) );
1308         }
1309
1310         return( NOID );
1311 }