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