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

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