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