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

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