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