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

   1 /* idl.c - ldap id list handling routines */
   2 /* $OpenLDAP$ */
   3 /*
   4  * Copyright 1998-2002 The OpenLDAP Foundation, All Rights Reserved.
   5  * COPYING RESTRICTIONS APPLY, see COPYRIGHT file
   6  */
   7
   8 #include "portable.h"
   9
  10 #include <stdio.h>
  11 #include <ac/string.h>
  12
  13 #include "back-bdb.h"
  14 #include "idl.h"
  15
  16 #define IDL_MAX(x,y)    ( x > y ? x : y )
  17 #define IDL_MIN(x,y)    ( x < y ? x : y )
  18
  19 #define IDL_CMP(x,y)    ( x < y ? -1 : ( x > y ? 1 : 0 ) )
  20
  21 #if IDL_DEBUG > 0
  22 static void idl_check( ID *ids )
  23 {
  24         if( BDB_IDL_IS_RANGE( ids ) ) {
  25                 assert( BDB_IDL_RANGE_FIRST(ids) <= BDB_IDL_RANGE_LAST(ids) );
  26         } else {
  27                 ID i;
  28                 for( i=1; i < ids[0]; i++ ) {
  29                         assert( ids[i+1] > ids[i] );
  30                 }
  31         }
  32 }
  33
  34 #if IDL_DEBUG > 1
  35 static void idl_dump( ID *ids )
  36 {
  37         if( BDB_IDL_IS_RANGE( ids ) ) {
  38 #ifdef NEW_LOGGING
  39                 LDAP_LOG( INDEX, INFO, "IDL: range (%ld - %ld)\n",
  40                         (long) BDB_IDL_RANGE_FIRST( ids ),
  41                         (long) BDB_IDL_RANGE_LAST( ids ), 0 );
  42 #else
  43                 Debug( LDAP_DEBUG_ANY,
  44                         "IDL: range ( %ld - %ld )\n",
  45                         (long) BDB_IDL_RANGE_FIRST( ids ),
  46                         (long) BDB_IDL_RANGE_LAST( ids ) );
  47 #endif
  48
  49         } else {
  50                 ID i;
  51 #ifdef NEW_LOGGING
  52                 LDAP_LOG( INDEX, INFO, "IDL: size %ld", (long) ids[0], 0, 0 );
  53 #else
  54                 Debug( LDAP_DEBUG_ANY, "IDL: size %ld", (long) ids[0], 0, 0 );
  55 #endif
  56
  57                 for( i=1; i<=ids[0]; i++ ) {
  58                         if( i % 16 == 1 ) {
  59                                 Debug( LDAP_DEBUG_ANY, "\n", 0, 0, 0 );
  60                         }
  61 #ifdef NEW_LOGGING
  62                         LDAP_LOG( INDEX, INFO, "%02lx",(long)ids[i], 0, 0 );
  63 #else
  64                         Debug( LDAP_DEBUG_ANY, "  %02lx", (long) ids[i], 0, 0 );
  65 #endif
  66                 }
  67
  68                 Debug( LDAP_DEBUG_ANY, "\n", 0, 0, 0 );
  69         }
  70
  71         idl_check( ids );
  72 }
  73 #endif /* IDL_DEBUG > 1 */
  74 #endif /* IDL_DEBUG > 0 */
  75
  76 unsigned bdb_idl_search( ID *ids, ID id )
  77 {
  78 #define IDL_BINARY_SEARCH 1
  79 #ifdef IDL_BINARY_SEARCH
  80         /*
  81          * binary search of id in ids
  82          * if found, returns position of id
  83          * if not found, returns first postion greater than id
  84          */
  85         unsigned base = 0;
  86         unsigned cursor = 0;
  87         int val = 0;
  88         unsigned n = ids[0];
  89
  90 #if IDL_DEBUG > 0
  91         idl_check( ids );
  92 #endif
  93
  94         while( 0 < n ) {
  95                 int pivot = n >> 1;
  96                 cursor = base + pivot;
  97                 val = IDL_CMP( id, ids[cursor + 1] );
  98
  99                 if( val < 0 ) {
 100                         n = pivot;
 101
 102                 } else if ( val > 0 ) {
 103                         base = cursor + 1;
 104                         n -= pivot + 1;
 105
 106                 } else {
 107                         return cursor + 1;
 108                 }
 109         }
 110
 111         if( val > 0 ) {
 112                 return cursor + 2;
 113         } else {
 114                 return cursor + 1;
 115         }
 116
 117 #else
 118         /* (reverse) linear search */
 119         int i;
 120
 121 #if IDL_DEBUG > 0
 122         idl_check( ids );
 123 #endif
 124
 125         for( i=ids[0]; i; i-- ) {
 126                 if( id > ids[i] ) {
 127                         break;
 128                 }
 129         }
 130
 131         return i+1;
 132 #endif
 133 }
 134
 135 int bdb_idl_insert( ID *ids, ID id )
 136 {
 137         unsigned x = bdb_idl_search( ids, id );
 138
 139 #if IDL_DEBUG > 1
 140 #ifdef NEW_LOGGING
 141         LDAP_LOG( INDEX, DETAIL1, "insert: %04lx at %d\n", (long) id, x, 0 );
 142 #else
 143         Debug( LDAP_DEBUG_ANY, "insert: %04lx at %d\n", (long) id, x, 0 );
 144         idl_dump( ids );
 145 #endif
 146 #elif IDL_DEBUG > 0
 147         idl_check( ids );
 148 #endif
 149
 150         assert( x > 0 );
 151
 152         if( x < 1 ) {
 153                 /* internal error */
 154                 return -2;
 155         }
 156
 157         if ( x <= ids[0] && ids[x] == id ) {
 158                 /* duplicate */
 159                 return -1;
 160         }
 161
 162         if ( ++ids[0] >= BDB_IDL_DB_MAX ) {
 163                 if( id < ids[1] ) {
 164                         ids[1] = id;
 165                         ids[2] = ids[ids[0]-1];
 166                 } else if ( ids[ids[0]-1] < id ) {
 167                         ids[2] = id;
 168                 } else {
 169                         ids[2] = ids[ids[0]-1];
 170                 }
 171                 ids[0] = NOID;
 172
 173         } else {
 174                 /* insert id */
 175                 AC_MEMCPY( &ids[x+1], &ids[x], (ids[0]-x) * sizeof(ID) );
 176                 ids[x] = id;
 177         }
 178
 179 #if IDL_DEBUG > 1
 180         idl_dump( ids );
 181 #elif IDL_DEBUG > 0
 182         idl_check( ids );
 183 #endif
 184
 185         return 0;
 186 }
 187
 188 static int idl_delete( ID *ids, ID id )
 189 {
 190         unsigned x = bdb_idl_search( ids, id );
 191
 192 #if IDL_DEBUG > 1
 193 #ifdef NEW_LOGGING
 194         LDAP_LOG( INDEX, DETAIL1, "delete: %04lx at %d\n", (long) id, x, 0 );
 195 #else
 196         Debug( LDAP_DEBUG_ANY, "delete: %04lx at %d\n", (long) id, x, 0 );
 197         idl_dump( ids );
 198 #endif
 199 #elif IDL_DEBUG > 0
 200         idl_check( ids );
 201 #endif
 202
 203         assert( x > 0 );
 204
 205         if( x <= 0 ) {
 206                 /* internal error */
 207                 return -2;
 208         }
 209
 210         if( x > ids[0] || ids[x] != id ) {
 211                 /* not found */
 212                 return -1;
 213
 214         } else if ( --ids[0] == 0 ) {
 215                 if( x != 1 ) {
 216                         return -3;
 217                 }
 218
 219         } else {
 220                 AC_MEMCPY( &ids[x], &ids[x+1], (1+ids[0]-x) * sizeof(ID) );
 221         }
 222
 223 #if IDL_DEBUG > 1
 224         idl_dump( ids );
 225 #elif IDL_DEBUG > 0
 226         idl_check( ids );
 227 #endif
 228
 229         return 0;
 230 }
 231
 232 static char *
 233 bdb_show_key(
 234         DBT             *key,
 235         char            *buf )
 236 {
 237         if ( key->size == sizeof( ID ) ) {
 238                 unsigned char *c = key->data;
 239                 sprintf( buf, "[%02x%02x%02x%02x]", c[0], c[1], c[2], c[3] );
 240                 return buf;
 241         } else {
 242                 return key->data;
 243         }
 244 }
 245
 246 int
 247 bdb_idl_fetch_key(
 248         BackendDB       *be,
 249         DB                      *db,
 250         DB_TXN          *tid,
 251         DBT                     *key,
 252         ID                      *ids )
 253 {
 254         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
 255         int rc;
 256         DBT data;
 257 #ifdef BDB_IDL_MULTI
 258         /* buf must be large enough to grab the entire IDL in one
 259          * get(), otherwise BDB 4 will leak resources on subsequent
 260          * get's. We can safely call get() twice - once for the data,
 261          * and once to get the DB_NOTFOUND result meaning there's
 262          * no more data. See ITS#2040 for details.
 263          */
 264         ID buf[BDB_IDL_DB_SIZE*5];
 265         DBC *cursor;
 266         ID *i;
 267         void *ptr;
 268         size_t len;
 269         int rc2;
 270         int flags = bdb->bi_db_opflags | DB_MULTIPLE;
 271 #endif
 272
 273         {
 274                 char buf[16];
 275 #ifdef NEW_LOGGING
 276                 LDAP_LOG( INDEX, ARGS,
 277                         "bdb_idl_fetch_key: %s\n",
 278                         bdb_show_key( key, buf ), 0, 0 );
 279 #else
 280                 Debug( LDAP_DEBUG_ARGS,
 281                         "bdb_idl_fetch_key: %s\n",
 282                         bdb_show_key( key, buf ), 0, 0 );
 283 #endif
 284         }
 285         assert( ids != NULL );
 286
 287         DBTzero( &data );
 288
 289 #ifdef BDB_IDL_MULTI
 290         data.data = buf;
 291         data.ulen = sizeof(buf);
 292         data.flags = DB_DBT_USERMEM;
 293
 294         if ( tid )
 295                 flags |= DB_RMW;
 296
 297         rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
 298         if( rc != 0 ) {
 299 #ifdef NEW_LOGGING
 300                 LDAP_LOG( INDEX, ERR,
 301                         "bdb_idl_fetch_key: cursor failed: %s (%d)\n",
 302                         db_strerror(rc), rc, 0 );
 303 #else
 304                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 305                         "cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 );
 306 #endif
 307                 return rc;
 308         }
 309         rc = cursor->c_get( cursor, key, &data, flags | DB_SET );
 310         if (rc == 0) {
 311                 i = ids;
 312                 while (rc == 0) {
 313                         u_int8_t *j;
 314
 315                         DB_MULTIPLE_INIT( ptr, &data );
 316                         while (ptr) {
 317                                 DB_MULTIPLE_NEXT(ptr, &data, j, len);
 318                                 if (j) {
 319                                         ++i;
 320                                         AC_MEMCPY( i, j, sizeof(ID) );
 321                                 }
 322                         }
 323                         rc = cursor->c_get( cursor, key, &data, flags | DB_NEXT_DUP );
 324                 }
 325                 if ( rc == DB_NOTFOUND ) rc = 0;
 326                 ids[0] = i - ids;
 327                 /* On disk, a range is denoted by 0 in the first element */
 328                 if (ids[1] == 0) {
 329                         if (ids[0] != BDB_IDL_RANGE_SIZE) {
 330 #ifdef NEW_LOGGING
 331                                 LDAP_LOG( INDEX, ERR,
 332                                         "=> bdb_idl_fetch_key: range size mismatch: "
 333                                         "expected %ld, got %ld\n",
 334                                         BDB_IDL_RANGE_SIZE, ids[0], 0 );
 335 #else
 336                                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 337                                         "range size mismatch: expected %d, got %ld\n",
 338                                         BDB_IDL_RANGE_SIZE, ids[0], 0 );
 339 #endif
 340                                 cursor->c_close( cursor );
 341                                 return -1;
 342                         }
 343                         BDB_IDL_RANGE( ids, ids[2], ids[3] );
 344                 }
 345                 data.size = BDB_IDL_SIZEOF(ids);
 346         }
 347         rc2 = cursor->c_close( cursor );
 348         if (rc2) {
 349 #ifdef NEW_LOGGING
 350                 LDAP_LOG( INDEX, ERR,
 351                         "bdb_idl_fetch_key: close failed: %s (%d)\n",
 352                         db_strerror(rc2), rc2, 0 );
 353 #else
 354                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 355                         "close failed: %s (%d)\n", db_strerror(rc2), rc2, 0 );
 356 #endif
 357                 return rc2;
 358         }
 359 #else /* BDB_IDL_MULTI */
 360         data.data = ids;
 361         data.ulen = BDB_IDL_UM_SIZEOF;
 362         data.flags = DB_DBT_USERMEM;
 363         /* fetch it */
 364         rc = db->get( db, tid, key, &data, bdb->bi_db_opflags );
 365 #endif /* BDB_IDL_MULTI */
 366
 367         if( rc == DB_NOTFOUND ) {
 368                 return rc;
 369
 370         } else if( rc != 0 ) {
 371 #ifdef NEW_LOGGING
 372                 LDAP_LOG( INDEX, ERR,
 373                         "bdb_idl_fetch_key: get failed: %s (%d)\n",
 374                         db_strerror(rc), rc, 0 );
 375 #else
 376                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 377                         "get failed: %s (%d)\n",
 378                         db_strerror(rc), rc, 0 );
 379 #endif
 380                 return rc;
 381
 382         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 383                 /* size not multiple of ID size */
 384 #ifdef NEW_LOGGING
 385                 LDAP_LOG( INDEX, ERR,
 386                         "bdb_idl_fetch_key: odd size: expected %ld multiple, got %ld\n",
 387                         (long) sizeof( ID ), (long) data.size, 0 );
 388 #else
 389                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 390                         "odd size: expected %ld multiple, got %ld\n",
 391                         (long) sizeof( ID ), (long) data.size, 0 );
 392 #endif
 393                 return -1;
 394
 395         } else if ( data.size != BDB_IDL_SIZEOF(ids) ) {
 396                 /* size mismatch */
 397 #ifdef NEW_LOGGING
 398                 LDAP_LOG( INDEX, ERR,
 399                         "bdb_idl_fetch_key: get size mismatch: expected %ld, got %ld\n",
 400                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 401 #else
 402                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 403                         "get size mismatch: expected %ld, got %ld\n",
 404                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 405 #endif
 406                 return -1;
 407         }
 408
 409         return rc;
 410 }
 411
 412
 413 int
 414 bdb_idl_insert_key(
 415         BackendDB       *be,
 416         DB                      *db,
 417         DB_TXN          *tid,
 418         DBT                     *key,
 419         ID                      id )
 420 {
 421         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
 422         int     rc;
 423         DBT data;
 424 #ifdef BDB_IDL_MULTI
 425         DBC *cursor;
 426         ID lo, hi, tmp;
 427         char *err;
 428 #else
 429         ID ids[BDB_IDL_DB_SIZE];
 430 #endif
 431
 432         {
 433                 char buf[16];
 434 #ifdef NEW_LOGGING
 435                 LDAP_LOG( INDEX, ARGS,
 436                         "bdb_idl_insert_key: %lx %s\n",
 437                         (long) id, bdb_show_key( key, buf ), 0 );
 438 #else
 439                 Debug( LDAP_DEBUG_ARGS,
 440                         "bdb_idl_insert_key: %lx %s\n",
 441                         (long) id, bdb_show_key( key, buf ), 0 );
 442 #endif
 443         }
 444
 445         assert( id != NOID );
 446
 447         DBTzero( &data );
 448 #ifdef BDB_IDL_MULTI
 449         data.size = sizeof( ID );
 450         data.ulen = data.size;
 451         data.flags = DB_DBT_USERMEM;
 452
 453         rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
 454         if ( rc != 0 ) {
 455 #ifdef NEW_LOGGING
 456                 LDAP_LOG( INDEX, ERR,
 457                         "bdb_idl_insert_key: cursor failed: %s (%d)\n",
 458                         db_strerror(rc), rc, 0 );
 459 #else
 460                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 461                         "cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 );
 462 #endif
 463                 return rc;
 464         }
 465         data.data = &tmp;
 466         /* Fetch the first data item for this key, to see if it
 467          * exists and if it's a range.
 468          */
 469         rc = cursor->c_get( cursor, key, &data, DB_SET | DB_RMW );
 470         err = "c_get";
 471         if ( rc == 0 ) {
 472                 if ( tmp != 0 ) {
 473                         /* not a range, count the number of items */
 474                         db_recno_t count;
 475                         rc = cursor->c_count( cursor, &count, 0 );
 476                         if ( rc != 0 ) {
 477                                 err = "c_count";
 478                                 goto fail;
 479                         }
 480                         if ( count >= BDB_IDL_DB_MAX ) {
 481                         /* No room, convert to a range */
 482                                 DBT key2 = *key;
 483
 484                                 key2.dlen = key2.ulen;
 485                                 key2.flags |= DB_DBT_PARTIAL;
 486
 487                                 lo = tmp;
 488                                 data.data = &hi;
 489                                 rc = cursor->c_get( cursor, &key2, &data, DB_NEXT_NODUP );
 490                                 if ( rc != 0 && rc != DB_NOTFOUND ) {
 491                                         err = "c_get next_nodup";
 492                                         goto fail;
 493                                 }
 494                                 if ( rc == DB_NOTFOUND ) {
 495                                         rc = cursor->c_get( cursor, key, &data, DB_LAST );
 496                                         if ( rc != 0 ) {
 497                                                 err = "c_get last";
 498                                                 goto fail;
 499                                         }
 500                                 } else {
 501                                         rc = cursor->c_get( cursor, key, &data, DB_PREV );
 502                                         if ( rc != 0 ) {
 503                                                 err = "c_get prev";
 504                                                 goto fail;
 505                                         }
 506                                 }
 507                                 if ( id < lo )
 508                                         lo = id;
 509                                 else if ( id > hi )
 510                                         hi = id;
 511                                 rc = db->del( db, tid, key, 0 );
 512                                 if ( rc != 0 ) {
 513                                         err = "del";
 514                                         goto fail;
 515                                 }
 516                                 data.data = &id;
 517                                 id = 0;
 518                                 rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST );
 519                                 if ( rc != 0 ) {
 520                                         err = "c_put 0";
 521                                         goto fail;
 522                                 }
 523                                 id = lo;
 524                                 rc = cursor->c_put( cursor, key, &data, DB_KEYLAST );
 525                                 if ( rc != 0 ) {
 526                                         err = "c_put lo";
 527                                         goto fail;
 528                                 }
 529                                 id = hi;
 530                                 rc = cursor->c_put( cursor, key, &data, DB_KEYLAST );
 531                                 if ( rc != 0 ) {
 532                                         err = "c_put hi";
 533                                         goto fail;
 534                                 }
 535                         } else {
 536                         /* There's room, just store it */
 537                                 goto put1;
 538                         }
 539                 } else {
 540                         /* It's a range, see if we need to rewrite
 541                          * the boundaries
 542                          */
 543                         hi = id;
 544                         data.data = &lo;
 545                         rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
 546                         if ( rc != 0 ) {
 547                                 err = "c_get lo";
 548                                 goto fail;
 549                         }
 550                         if ( id > lo ) {
 551                                 data.data = &hi;
 552                                 rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
 553                                 if ( rc != 0 ) {
 554                                         err = "c_get hi";
 555                                         goto fail;
 556                                 }
 557                         }
 558                         if ( id < lo || id > hi ) {
 559                                 /* Delete the current lo/hi */
 560                                 rc = cursor->c_del( cursor, 0 );
 561                                 if ( rc != 0 ) {
 562                                         err = "c_del";
 563                                         goto fail;
 564                                 }
 565                                 data.data = &id;
 566                                 rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST );
 567                                 if ( rc != 0 ) {
 568                                         err = "c_put lo/hi";
 569                                         goto fail;
 570                                 }
 571                         }
 572                 }
 573         } else if ( rc == DB_NOTFOUND ) {
 574 put1:           data.data = &id;
 575                 rc = cursor->c_put( cursor, key, &data, DB_NODUPDATA );
 576                 /* Don't worry if it's already there */
 577                 if ( rc != 0 && rc != DB_KEYEXIST ) {
 578                         err = "c_put id";
 579                         goto fail;
 580                 }
 581         } else {
 582                 /* initial c_get failed, nothing was done */
 583 fail:
 584 #ifdef NEW_LOGGING
 585                 LDAP_LOG( INDEX, ERR,
 586                         "bdb_idl_insert_key: %s failed: %s (%d)\n",
 587                         err, db_strerror(rc), rc );
 588 #else
 589                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 590                         "%s failed: %s (%d)\n", err, db_strerror(rc), rc );
 591 #endif
 592                 cursor->c_close( cursor );
 593                 return rc;
 594         }
 595         rc = cursor->c_close( cursor );
 596 #else   /* !BDB_IDL_MULTI */
 597         data.data = ids;
 598         data.ulen = sizeof ids;
 599         data.flags = DB_DBT_USERMEM;
 600
 601         /* fetch the key for read/modify/write */
 602         rc = db->get( db, tid, key, &data, DB_RMW | bdb->bi_db_opflags );
 603
 604         if( rc == DB_NOTFOUND ) {
 605                 ids[0] = 1;
 606                 ids[1] = id;
 607                 data.size = 2 * sizeof( ID );
 608
 609         } else if ( rc != 0 ) {
 610 #ifdef NEW_LOGGING
 611                 LDAP_LOG( INDEX, ERR, "bdb_idl_insert_key: get failed: %s (%d)\n",
 612                         db_strerror(rc), rc, 0 );
 613 #else
 614                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 615                         "get failed: %s (%d)\n",
 616                         db_strerror(rc), rc, 0 );
 617 #endif
 618                 return rc;
 619
 620         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 621                 /* size not multiple of ID size */
 622 #ifdef NEW_LOGGING
 623                 LDAP_LOG( INDEX, ERR,
 624                         "bdb_idl_insert_key: odd size: expected %ld multiple, got %ld\n",
 625                         (long) sizeof( ID ), (long) data.size, 0 );
 626 #else
 627                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 628                         "odd size: expected %ld multiple, got %ld\n",
 629                         (long) sizeof( ID ), (long) data.size, 0 );
 630 #endif
 631                 return -1;
 632
 633         } else if ( data.size != BDB_IDL_SIZEOF(ids) ) {
 634                 /* size mismatch */
 635 #ifdef NEW_LOGGING
 636                 LDAP_LOG( INDEX, ERR,
 637                         "bdb_idl_insert_key: odd size: expected %ld multiple, got %ld\n",
 638                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 639 #else
 640                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 641                         "get size mismatch: expected %ld, got %ld\n",
 642                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 643 #endif
 644                 return -1;
 645
 646         } else if ( BDB_IDL_IS_RANGE(ids) ) {
 647                 if( id < ids[1] ) {
 648                         ids[1] = id;
 649                 } else if ( ids[2] > id ) {
 650                         ids[2] = id;
 651                 } else {
 652                         return 0;
 653                 }
 654
 655         } else {
 656                 rc = bdb_idl_insert( ids, id );
 657
 658                 if( rc == -1 ) {
 659 #ifdef NEW_LOGGING
 660                         LDAP_LOG( INDEX, DETAIL1, "bdb_idl_insert_key: dup\n", 0, 0, 0 );
 661 #else
 662                         Debug( LDAP_DEBUG_TRACE, "=> bdb_idl_insert_key: dup\n",
 663                                 0, 0, 0 );
 664 #endif
 665                         return 0;
 666                 }
 667                 if( rc != 0 ) {
 668 #ifdef NEW_LOGGING
 669                         LDAP_LOG( INDEX, ERR,
 670                                 "bdb_idl_insert_key: insert failed: (%d)\n", rc, 0, 0 );
 671 #else
 672                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 673                                 "bdb_idl_insert failed (%d)\n",
 674                                 rc, 0, 0 );
 675 #endif
 676
 677                         return rc;
 678                 }
 679
 680                 data.size = BDB_IDL_SIZEOF( ids );
 681         }
 682
 683         /* store the key */
 684         rc = db->put( db, tid, key, &data, 0 );
 685 #endif
 686         if( rc != 0 && rc != DB_KEYEXIST ) {
 687 #ifdef NEW_LOGGING
 688                 LDAP_LOG( INDEX, ERR,
 689                         "bdb_idl_insert_key: put failed: %s (%d)\n",
 690                         db_strerror(rc), rc, 0 );
 691 #else
 692                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 693                         "put failed: %s (%d)\n",
 694                         db_strerror(rc), rc, 0 );
 695 #endif
 696         }
 697         return rc;
 698 }
 699
 700 int
 701 bdb_idl_delete_key(
 702         BackendDB       *be,
 703         DB                      *db,
 704         DB_TXN          *tid,
 705         DBT                     *key,
 706         ID                      id )
 707 {
 708         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
 709         int     rc;
 710         DBT data;
 711 #ifdef BDB_IDL_MULTI
 712         DBC *cursor;
 713         ID lo, hi, tmp;
 714         char *err;
 715 #else
 716         ID ids[BDB_IDL_DB_SIZE];
 717 #endif
 718
 719         {
 720                 char buf[16];
 721 #ifdef NEW_LOGGING
 722                 LDAP_LOG( INDEX, ARGS,
 723                         "bdb_idl_delete_key: %lx %s\n",
 724                         (long) id, bdb_show_key( key, buf ), 0 );
 725 #else
 726                 Debug( LDAP_DEBUG_ARGS,
 727                         "bdb_idl_delete_key: %lx %s\n",
 728                         (long) id, bdb_show_key( key, buf ), 0 );
 729 #endif
 730         }
 731         assert( id != NOID );
 732
 733         DBTzero( &data );
 734
 735 #ifdef BDB_IDL_MULTI
 736         data.data = &tmp;
 737         data.size = sizeof( id );
 738         data.ulen = data.size;
 739         data.flags = DB_DBT_USERMEM;
 740
 741         rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
 742         if ( rc != 0 ) {
 743 #ifdef NEW_LOGGING
 744                 LDAP_LOG( INDEX, ERR,
 745                         "bdb_idl_delete_key: cursor failed: %s (%d)\n",
 746                         db_strerror(rc), rc, 0 );
 747 #else
 748                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 749                         "cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 );
 750 #endif
 751                 return rc;
 752         }
 753         /* Fetch the first data item for this key, to see if it
 754          * exists and if it's a range.
 755          */
 756         rc = cursor->c_get( cursor, key, &data, DB_SET | DB_RMW );
 757         err = "c_get";
 758         if ( rc == 0 ) {
 759                 if ( tmp != 0 ) {
 760                         /* Not a range, just delete it */
 761                         if (tmp != id) {
 762                                 /* position to correct item */
 763                                 tmp = id;
 764                                 rc = cursor->c_get( cursor, key, &data,
 765                                         DB_GET_BOTH | DB_RMW  );
 766                                 if ( rc != 0 ) {
 767                                         err = "c_get id";
 768                                         goto fail;
 769                                 }
 770                         }
 771                         rc = cursor->c_del( cursor, 0 );
 772                         if ( rc != 0 ) {
 773                                 err = "c_del id";
 774                                 goto fail;
 775                         }
 776                 } else {
 777                         /* It's a range, see if we need to rewrite
 778                          * the boundaries
 779                          */
 780                         hi = 0;
 781                         data.data = &lo;
 782                         rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
 783                         if ( rc != 0 ) {
 784                                 err = "c_get lo";
 785                                 goto fail;
 786                         }
 787                         if ( id > lo ) {
 788                                 data.data = &hi;
 789                                 rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
 790                                 if ( rc != 0 ) {
 791                                         err = "c_get hi";
 792                                         goto fail;
 793                                 }
 794                         }
 795                         if ( id == lo || id == hi ) {
 796                                 if ( id == lo ) {
 797                                         id++;
 798                                         lo = id;
 799                                 } else if ( id == hi ) {
 800                                         id--;
 801                                         hi = id;
 802                                 }
 803                                 if ( lo >= hi ) {
 804                                 /* The range has collapsed... */
 805                                         rc = db->del( db, tid, key, 0 );
 806                                         if ( rc != 0 ) {
 807                                                 err = "del";
 808                                                 goto fail;
 809                                         }
 810                                 } else {
 811                                         rc = cursor->c_del( cursor, 0 );
 812                                         if ( rc != 0 ) {
 813                                                 err = "c_del";
 814                                                 goto fail;
 815                                         }
 816                                 }
 817                                 if ( lo <= hi ) {
 818                                         data.data = &id;
 819                                         rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST );
 820                                         if ( rc != 0 ) {
 821                                                 err = "c_put lo/hi";
 822                                                 goto fail;
 823                                         }
 824                                 }
 825                         }
 826                 }
 827         } else {
 828                 /* initial c_get failed, nothing was done */
 829 fail:
 830                 if ( rc != DB_NOTFOUND ) {
 831 #ifdef NEW_LOGGING
 832                 LDAP_LOG( INDEX, ERR,
 833                         "bdb_idl_delete_key: %s failed: %s (%d)\n",
 834                         err, db_strerror(rc), rc );
 835 #else
 836                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 837                         "%s failed: %s (%d)\n", err, db_strerror(rc), rc );
 838 #endif
 839                 }
 840                 cursor->c_close( cursor );
 841                 return rc;
 842         }
 843         rc = cursor->c_close( cursor );
 844
 845 #else   /* BDB_IDL_MULTI */
 846
 847         data.data = ids;
 848         data.ulen = sizeof( ids );
 849         data.flags = DB_DBT_USERMEM;
 850
 851         /* fetch the key for read/modify/write */
 852         rc = db->get( db, tid, key, &data, DB_RMW | bdb->bi_db_opflags );
 853
 854         if ( rc != 0 ) {
 855 #ifdef NEW_LOGGING
 856                 LDAP_LOG( INDEX, ERR, "bdb_idl_delete_key: get failed: %s (%d)\n",
 857                         db_strerror(rc), rc, 0 );
 858 #else
 859                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 860                         "get failed: %s (%d)\n",
 861                         db_strerror(rc), rc, 0 );
 862 #endif
 863                 return rc;
 864
 865         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 866                 /* size not multiple of ID size */
 867 #ifdef NEW_LOGGING
 868                 LDAP_LOG( INDEX, ERR,
 869                         "bdb_idl_delete_key: odd size: expected: %ld multiple, got %ld\n",
 870                         (long) sizeof( ID ), (long) data.size, 0 );
 871 #else
 872                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 873                         "odd size: expected %ld multiple, got %ld\n",
 874                         (long) sizeof( ID ), (long) data.size, 0 );
 875 #endif
 876                 return -1;
 877
 878         } else if ( BDB_IDL_IS_RANGE(ids) ) {
 879                 return 0;
 880
 881         } else if ( data.size != (1 + ids[0]) * sizeof( ID ) ) {
 882                 /* size mismatch */
 883 #ifdef NEW_LOGGING
 884                 LDAP_LOG( INDEX, ERR,
 885                         "bdb_idl_delete_key: get size mismatch: expected: %ld, got %ld\n",
 886                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 887 #else
 888                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 889                         "get size mismatch: expected %ld, got %ld\n",
 890                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 891 #endif
 892                 return -1;
 893
 894         } else {
 895                 rc = idl_delete( ids, id );
 896
 897                 if( rc != 0 ) {
 898 #ifdef NEW_LOGGING
 899                         LDAP_LOG( INDEX, ERR,
 900                                 "bdb_idl_delete_key: delete failed: (%d)\n", rc, 0, 0 );
 901 #else
 902                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 903                                 "idl_delete failed (%d)\n",
 904                                 rc, 0, 0 );
 905 #endif
 906                         return rc;
 907                 }
 908
 909                 if( ids[0] == 0 ) {
 910                         /* delete the key */
 911                         rc = db->del( db, tid, key, 0 );
 912                         if( rc != 0 ) {
 913 #ifdef NEW_LOGGING
 914                                 LDAP_LOG( INDEX, ERR,
 915                                         "bdb_idl_delete_key: delete failed: %s (%d)\n",
 916                                         db_strerror(rc), rc, 0 );
 917 #else
 918                                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 919                                         "delete failed: %s (%d)\n",
 920                                         db_strerror(rc), rc, 0 );
 921 #endif
 922                         }
 923                         return rc;
 924                 }
 925
 926                 data.size = (ids[0]+1) * sizeof( ID );
 927         }
 928
 929         /* store the key */
 930         rc = db->put( db, tid, key, &data, 0 );
 931
 932 #endif /* BDB_IDL_MULTI */
 933
 934         if( rc != 0 ) {
 935 #ifdef NEW_LOGGING
 936                 LDAP_LOG( INDEX, ERR, "bdb_idl_delete_key: put failed: %s (%d)\n",
 937                         db_strerror(rc), rc, 0 );
 938 #else
 939                 Debug( LDAP_DEBUG_ANY,
 940                         "=> bdb_idl_delete_key: put failed: %s (%d)\n",
 941                         db_strerror(rc), rc, 0 );
 942 #endif
 943         }
 944
 945         return rc;
 946 }
 947
 948
 949 /*
 950  * idl_intersection - return a = a intersection b
 951  */
 952 int
 953 bdb_idl_intersection(
 954         ID *a,
 955         ID *b )
 956 {
 957         ID ida, idb;
 958         ID idmax, idmin;
 959         ID cursora = 0, cursorb = 0, cursorc;
 960         int swap = 0;
 961
 962         if ( BDB_IDL_IS_ZERO( a ) || BDB_IDL_IS_ZERO( b ) ) {
 963                 a[0] = 0;
 964                 return 0;
 965         }
 966
 967         idmin = IDL_MAX( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) );
 968         idmax = IDL_MIN( BDB_IDL_LAST(a), BDB_IDL_LAST(b) );
 969         if ( idmin > idmax ) {
 970                 a[0] = 0;
 971                 return 0;
 972         } else if ( idmin == idmax ) {
 973                 a[0] = 1;
 974                 a[1] = idmin;
 975                 return 0;
 976         }
 977
 978         if ( BDB_IDL_IS_RANGE( a ) && BDB_IDL_IS_RANGE(b) ) {
 979                 a[1] = idmin;
 980                 a[2] = idmax;
 981                 return 0;
 982         }
 983
 984         if ( BDB_IDL_IS_RANGE( a ) ) {
 985                 ID *tmp = a;
 986                 a = b;
 987                 b = tmp;
 988                 swap = 1;
 989         }
 990
 991         if ( BDB_IDL_IS_RANGE( b ) && BDB_IDL_FIRST( b ) <= idmin &&
 992                 BDB_IDL_LAST( b ) >= idmax) {
 993                 if (idmax - idmin + 1 == a[0])
 994                 {
 995                         a[0] = NOID;
 996                         a[1] = idmin;
 997                         a[2] = idmax;
 998                 }
 999                 goto done;
1000         }
1001
1002         ida = bdb_idl_first( a, &cursora );
1003         idb = bdb_idl_first( b, &cursorb );
1004         cursorc = 0;
1005
1006         while( ida < idmin )
1007                 ida = bdb_idl_next( a, &cursora );
1008         while( idb < idmin )
1009                 idb = bdb_idl_next( b, &cursorb );
1010
1011         while( ida <= idmax || idb <= idmax ) {
1012                 if( ida == idb ) {
1013                         a[++cursorc] = ida;
1014                         ida = bdb_idl_next( a, &cursora );
1015                         idb = bdb_idl_next( b, &cursorb );
1016                 } else if ( ida < idb ) {
1017                         ida = bdb_idl_next( a, &cursora );
1018                 } else {
1019                         idb = bdb_idl_next( b, &cursorb );
1020                 }
1021         }
1022         a[0] = cursorc;
1023 done:
1024         if (swap)
1025                 BDB_IDL_CPY( b, a );
1026
1027         return 0;
1028 }
1029
1030
1031 /*
1032  * idl_union - return a = a union b
1033  */
1034 int
1035 bdb_idl_union(
1036         ID      *a,
1037         ID      *b )
1038 {
1039         ID ida, idb;
1040         ID cursora = 0, cursorb = 0, cursorc;
1041
1042         if ( BDB_IDL_IS_ZERO( b ) ) {
1043                 return 0;
1044         }
1045
1046         if ( BDB_IDL_IS_ZERO( a ) ) {
1047                 BDB_IDL_CPY( a, b );
1048                 return 0;
1049         }
1050
1051         if ( BDB_IDL_IS_RANGE( a ) || BDB_IDL_IS_RANGE(b) ) {
1052 over:           ida = IDL_MIN( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) );
1053                 idb = IDL_MAX( BDB_IDL_LAST(a), BDB_IDL_LAST(b) );
1054                 a[0] = NOID;
1055                 a[1] = ida;
1056                 a[2] = idb;
1057                 return 0;
1058         }
1059
1060         ida = bdb_idl_first( a, &cursora );
1061         idb = bdb_idl_first( b, &cursorb );
1062
1063         cursorc = b[0];
1064
1065         /* The distinct elements of a are cat'd to b */
1066         while( ida != NOID || idb != NOID ) {
1067                 if ( ida < idb ) {
1068                         if( ++cursorc > BDB_IDL_UM_MAX ) {
1069                                 goto over;
1070                         }
1071                         b[cursorc] = ida;
1072                         ida = bdb_idl_next( a, &cursora );
1073
1074                 } else {
1075                         if ( ida == idb )
1076                                 ida = bdb_idl_next( a, &cursora );
1077                         idb = bdb_idl_next( b, &cursorb );
1078                 }
1079         }
1080
1081         /* b is copied back to a in sorted order */
1082         a[0] = cursorc;
1083         cursora = 1;
1084         cursorb = 1;
1085         cursorc = b[0]+1;
1086         while (cursorb <= b[0] || cursorc <= a[0]) {
1087                 if (cursorc > a[0])
1088                         idb = NOID;
1089                 else
1090                         idb = b[cursorc];
1091                 if (cursorb <= b[0] && b[cursorb] < idb)
1092                         a[cursora++] = b[cursorb++];
1093                 else {
1094                         a[cursora++] = idb;
1095                         cursorc++;
1096                 }
1097         }
1098
1099         return 0;
1100 }
1101
1102
1103 #if 0
1104 /*
1105  * bdb_idl_notin - return a intersection ~b (or a minus b)
1106  */
1107 int
1108 bdb_idl_notin(
1109         ID      *a,
1110         ID      *b,
1111         ID *ids )
1112 {
1113         ID ida, idb;
1114         ID cursora = 0, cursorb = 0;
1115
1116         if( BDB_IDL_IS_ZERO( a ) ||
1117                 BDB_IDL_IS_ZERO( b ) ||
1118                 BDB_IDL_IS_RANGE( b ) )
1119         {
1120                 BDB_IDL_CPY( ids, a );
1121                 return 0;
1122         }
1123
1124         if( BDB_IDL_IS_RANGE( a ) ) {
1125                 BDB_IDL_CPY( ids, a );
1126                 return 0;
1127         }
1128
1129         ida = bdb_idl_first( a, &cursora ),
1130         idb = bdb_idl_first( b, &cursorb );
1131
1132         ids[0] = 0;
1133
1134         while( ida != NOID ) {
1135                 if ( idb == NOID ) {
1136                         /* we could shortcut this */
1137                         ids[++ids[0]] = ida;
1138                         ida = bdb_idl_next( a, &cursora );
1139
1140                 } else if ( ida < idb ) {
1141                         ids[++ids[0]] = ida;
1142                         ida = bdb_idl_next( a, &cursora );
1143
1144                 } else if ( ida > idb ) {
1145                         idb = bdb_idl_next( b, &cursorb );
1146
1147                 } else {
1148                         ida = bdb_idl_next( a, &cursora );
1149                         idb = bdb_idl_next( b, &cursorb );
1150                 }
1151         }
1152
1153         return 0;
1154 }
1155 #endif
1156
1157 ID bdb_idl_first( ID *ids, ID *cursor )
1158 {
1159         ID pos;
1160
1161         if ( ids[0] == 0 ) {
1162                 *cursor = NOID;
1163                 return NOID;
1164         }
1165
1166         if ( BDB_IDL_IS_RANGE( ids ) ) {
1167                 if( *cursor < ids[1] ) {
1168                         *cursor = ids[1];
1169                 }
1170                 return *cursor;
1171         }
1172
1173         if ( *cursor == 0 )
1174                 pos = 1;
1175         else
1176                 pos = bdb_idl_search( ids, *cursor );
1177
1178         if( pos > ids[0] ) {
1179                 return NOID;
1180         }
1181
1182         *cursor = pos;
1183         return ids[pos];
1184 }
1185
1186 ID bdb_idl_next( ID *ids, ID *cursor )
1187 {
1188         if ( BDB_IDL_IS_RANGE( ids ) ) {
1189                 if( ids[2] < ++(*cursor) ) {
1190                         return NOID;
1191                 }
1192                 return *cursor;
1193         }
1194
1195         if ( ++(*cursor) <= ids[0] ) {
1196                 return ids[*cursor];
1197         }
1198
1199         return NOID;
1200 }