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