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

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