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