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

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