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 int
 233 bdb_idl_fetch_key(
 234         BackendDB       *be,
 235         DB                      *db,
 236         DB_TXN          *tid,
 237         DBT                     *key,
 238         ID                      *ids )
 239 {
 240         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
 241         int rc;
 242         DBT data;
 243
 244         assert( ids != NULL );
 245
 246         DBTzero( &data );
 247
 248 #ifdef BDB_IDL_MULTI
 249         {
 250                 DBC *cursor;
 251                 /* buf must be large enough to grab the entire IDL in one
 252                  * get(), otherwise BDB 4 will leak resources on subsequent
 253                  * get's. We can safely call get() twice - once for the data,
 254                  * and once to get the DB_NOTFOUND result meaning there's
 255                  * no more data. See ITS#2040 for details.
 256                  */
 257                 ID buf[BDB_IDL_DB_SIZE*5];
 258                 ID *i;
 259                 void *ptr;
 260                 size_t len;
 261                 int rc2;
 262                 int flags = bdb->bi_db_opflags | DB_MULTIPLE;
 263                 data.data = buf;
 264                 data.ulen = sizeof(buf);
 265                 data.flags = DB_DBT_USERMEM;
 266
 267                 if ( tid )
 268                         flags |= DB_RMW;
 269
 270                 rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
 271                 if( rc != 0 ) {
 272 #ifdef NEW_LOGGING
 273                         LDAP_LOG( INDEX, ERR,
 274                                 "bdb_idl_fetch_key: cursor failed: %s (%d)\n",
 275                                 db_strerror(rc), rc, 0 );
 276 #else
 277                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 278                                 "cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 );
 279 #endif
 280                         return rc;
 281                 }
 282                 rc = cursor->c_get( cursor, key, &data, flags | DB_SET );
 283                 if (rc == 0) {
 284                         i = ids;
 285                         while (rc == 0) {
 286                                 u_int8_t *j;
 287
 288                                 DB_MULTIPLE_INIT( ptr, &data );
 289                                 while (ptr) {
 290                                         DB_MULTIPLE_NEXT(ptr, &data, j, len);
 291                                         if (j) {
 292                                                 ++i;
 293                                                 AC_MEMCPY( i, j, sizeof(ID) );
 294                                         }
 295                                 }
 296                                 rc = cursor->c_get( cursor, key, &data, flags | DB_NEXT_DUP );
 297                         }
 298                         if ( rc == DB_NOTFOUND ) rc = 0;
 299                         ids[0] = i - ids;
 300                         /* On disk, a range is denoted by 0 in the first element */
 301                         if (ids[1] == 0) {
 302                                 if (ids[0] != BDB_IDL_RANGE_SIZE) {
 303 #ifdef NEW_LOGGING
 304                                         LDAP_LOG( INDEX, ERR,
 305                                                 "=> bdb_idl_fetch_key: range size mismatch: "
 306                                                 "expected %ld, got %ld\n",
 307                                                 BDB_IDL_RANGE_SIZE, ids[0], 0 );
 308 #else
 309                                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 310                                                 "range size mismatch: expected %d, got %ld\n",
 311                                                 BDB_IDL_RANGE_SIZE, ids[0], 0 );
 312 #endif
 313                                         cursor->c_close( cursor );
 314                                         return -1;
 315                                 }
 316                                 BDB_IDL_RANGE( ids, ids[2], ids[3] );
 317                         }
 318                         data.size = BDB_IDL_SIZEOF(ids);
 319                 }
 320                 rc2 = cursor->c_close( cursor );
 321                 if (rc2) {
 322 #ifdef NEW_LOGGING
 323                         LDAP_LOG( INDEX, ERR,
 324                                 "bdb_idl_fetch_key: close failed: %s (%d)\n",
 325                                 db_strerror(rc2), rc2, 0 );
 326 #else
 327                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 328                                 "close failed: %s (%d)\n", db_strerror(rc2), rc2, 0 );
 329 #endif
 330                         return rc2;
 331                 }
 332         }
 333 #else
 334         data.data = ids;
 335         data.ulen = BDB_IDL_UM_SIZEOF;
 336         data.flags = DB_DBT_USERMEM;
 337         /* fetch it */
 338         rc = db->get( db, tid, key, &data, bdb->bi_db_opflags );
 339 #endif
 340
 341         if( rc == DB_NOTFOUND ) {
 342                 return rc;
 343
 344         } else if( rc != 0 ) {
 345 #ifdef NEW_LOGGING
 346                 LDAP_LOG( INDEX, ERR,
 347                         "bdb_idl_fetch_key: get failed: %s (%d)\n",
 348                         db_strerror(rc), rc, 0 );
 349 #else
 350                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 351                         "get failed: %s (%d)\n",
 352                         db_strerror(rc), rc, 0 );
 353 #endif
 354                 return rc;
 355
 356         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 357                 /* size not multiple of ID size */
 358 #ifdef NEW_LOGGING
 359                 LDAP_LOG( INDEX, ERR,
 360                         "bdb_idl_fetch_key: odd size: expected %ld multiple, got %ld\n",
 361                         (long) sizeof( ID ), (long) data.size, 0 );
 362 #else
 363                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 364                         "odd size: expected %ld multiple, got %ld\n",
 365                         (long) sizeof( ID ), (long) data.size, 0 );
 366 #endif
 367                 return -1;
 368
 369         } else if ( data.size != BDB_IDL_SIZEOF(ids) ) {
 370                 /* size mismatch */
 371 #ifdef NEW_LOGGING
 372                 LDAP_LOG( INDEX, ERR,
 373                         "bdb_idl_fetch_key: get size mismatch: expected %ld, got %ld\n",
 374                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 375 #else
 376                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 377                         "get size mismatch: expected %ld, got %ld\n",
 378                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 379 #endif
 380                 return -1;
 381         }
 382
 383         return rc;
 384 }
 385
 386 int
 387 bdb_idl_insert_key(
 388         BackendDB       *be,
 389         DB                      *db,
 390         DB_TXN          *tid,
 391         DBT                     *key,
 392         ID                      id )
 393 {
 394         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
 395         int     rc;
 396         DBT data;
 397 #ifndef BDB_IDL_MULTI
 398         ID ids[BDB_IDL_DB_SIZE];
 399 #endif
 400
 401 #if 0
 402         /* for printable keys only */
 403 #ifdef NEW_LOGGING
 404         LDAP_LOG( INDEX, ARGS, "bdb_idl_insert_key: %s %ld\n",
 405                 (char *)key->data, (long) id, 0 );
 406 #else
 407         Debug( LDAP_DEBUG_ARGS,
 408                 "=> bdb_idl_insert_key: %s %ld\n",
 409                 (char *)key->data, (long) id, 0 );
 410 #endif
 411 #endif
 412
 413         assert( id != NOID );
 414
 415         DBTzero( &data );
 416 #ifdef BDB_IDL_MULTI
 417         {
 418                 DBC *cursor;
 419                 ID lo, hi, tmp;
 420                 char *err;
 421
 422                 data.size = sizeof( ID );
 423                 data.ulen = data.size;
 424                 data.flags = DB_DBT_USERMEM;
 425
 426                 rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
 427                 if ( rc != 0 ) {
 428 #ifdef NEW_LOGGING
 429                         LDAP_LOG( INDEX, ERR,
 430                                 "bdb_idl_insert_key: cursor failed: %s (%d)\n",
 431                                 db_strerror(rc), rc, 0 );
 432 #else
 433                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 434                                 "cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 );
 435 #endif
 436                         return rc;
 437                 }
 438                 data.data = &tmp;
 439                 /* Fetch the first data item for this key, to see if it
 440                  * exists and if it's a range.
 441                  */
 442                 rc = cursor->c_get( cursor, key, &data, DB_SET | DB_RMW );
 443                 err = "c_get";
 444                 if ( rc == 0 ) {
 445                         if ( tmp != 0 ) {
 446                                 /* not a range, count the number of items */
 447                                 db_recno_t count;
 448                                 rc = cursor->c_count( cursor, &count, 0 );
 449                                 if ( rc != 0 ) {
 450                                         err = "c_count";
 451                                         goto fail;
 452                                 }
 453                                 if ( count >= BDB_IDL_DB_MAX ) {
 454                                 /* No room, convert to a range */
 455                                         DBT key2 = *key;
 456
 457                                         key2.dlen = key2.ulen;
 458                                         key2.flags |= DB_DBT_PARTIAL;
 459
 460                                         lo = tmp;
 461                                         data.data = &hi;
 462                                         rc = cursor->c_get( cursor, &key2, &data, DB_NEXT_NODUP );
 463                                         if ( rc != 0 && rc != DB_NOTFOUND ) {
 464                                                 err = "c_get next_nodup";
 465                                                 goto fail;
 466                                         }
 467                                         if ( rc == DB_NOTFOUND ) {
 468                                                 rc = cursor->c_get( cursor, key, &data, DB_LAST );
 469                                                 if ( rc != 0 ) {
 470                                                         err = "c_get last";
 471                                                         goto fail;
 472                                                 }
 473                                         } else {
 474                                                 rc = cursor->c_get( cursor, key, &data, DB_PREV );
 475                                                 if ( rc != 0 ) {
 476                                                         err = "c_get prev";
 477                                                         goto fail;
 478                                                 }
 479                                         }
 480                                         if ( id < lo )
 481                                                 lo = id;
 482                                         else if ( id > hi )
 483                                                 hi = id;
 484                                         rc = db->del( db, tid, key, 0 );
 485                                         if ( rc != 0 ) {
 486                                                 err = "del";
 487                                                 goto fail;
 488                                         }
 489                                         data.data = &id;
 490                                         id = 0;
 491                                         rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST );
 492                                         if ( rc != 0 ) {
 493                                                 err = "c_put 0";
 494                                                 goto fail;
 495                                         }
 496                                         id = lo;
 497                                         rc = cursor->c_put( cursor, key, &data, DB_KEYLAST );
 498                                         if ( rc != 0 ) {
 499                                                 err = "c_put lo";
 500                                                 goto fail;
 501                                         }
 502                                         id = hi;
 503                                         rc = cursor->c_put( cursor, key, &data, DB_KEYLAST );
 504                                         if ( rc != 0 ) {
 505                                                 err = "c_put hi";
 506                                                 goto fail;
 507                                         }
 508                                 } else {
 509                                 /* There's room, just store it */
 510                                         goto put1;
 511                                 }
 512                         } else {
 513                                 /* It's a range, see if we need to rewrite
 514                                  * the boundaries
 515                                  */
 516                                 hi = id;
 517                                 data.data = &lo;
 518                                 rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
 519                                 if ( rc != 0 ) {
 520                                         err = "c_get lo";
 521                                         goto fail;
 522                                 }
 523                                 if ( id > lo ) {
 524                                         data.data = &hi;
 525                                         rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
 526                                         if ( rc != 0 ) {
 527                                                 err = "c_get hi";
 528                                                 goto fail;
 529                                         }
 530                                 }
 531                                 if ( id < lo || id > hi ) {
 532                                         /* Delete the current lo/hi */
 533                                         rc = cursor->c_del( cursor, 0 );
 534                                         if ( rc != 0 ) {
 535                                                 err = "c_del";
 536                                                 goto fail;
 537                                         }
 538                                         data.data = &id;
 539                                         rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST );
 540                                         if ( rc != 0 ) {
 541                                                 err = "c_put lo/hi";
 542                                                 goto fail;
 543                                         }
 544                                 }
 545                         }
 546                 } else if ( rc == DB_NOTFOUND ) {
 547 put1:                   data.data = &id;
 548                         rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST );
 549                         /* Don't worry if it's already there */
 550                         if ( rc != 0 && rc != DB_KEYEXIST ) {
 551                                 err = "c_put id";
 552                                 goto fail;
 553                         }
 554                 } else {
 555                         /* initial c_get failed, nothing was done */
 556 fail:
 557 #ifdef NEW_LOGGING
 558                         LDAP_LOG( INDEX, ERR,
 559                                 "bdb_idl_insert_key: %s failed: %s (%d)\n",
 560                                 err, db_strerror(rc), rc );
 561 #else
 562                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 563                                 "%s failed: %s (%d)\n", err, db_strerror(rc), rc );
 564 #endif
 565                         cursor->c_close( cursor );
 566                         return rc;
 567                 }
 568                 rc = cursor->c_close( cursor );
 569         }
 570 #else   /* !BDB_IDL_MULTI */
 571         data.data = ids;
 572         data.ulen = sizeof ids;
 573         data.flags = DB_DBT_USERMEM;
 574
 575         /* fetch the key for read/modify/write */
 576         rc = db->get( db, tid, key, &data, DB_RMW | bdb->bi_db_opflags );
 577
 578         if( rc == DB_NOTFOUND ) {
 579                 ids[0] = 1;
 580                 ids[1] = id;
 581                 data.size = 2 * sizeof( ID );
 582
 583         } else if ( rc != 0 ) {
 584 #ifdef NEW_LOGGING
 585                 LDAP_LOG( INDEX, ERR, "bdb_idl_insert_key: get failed: %s (%d)\n",
 586                         db_strerror(rc), rc, 0 );
 587 #else
 588                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 589                         "get failed: %s (%d)\n",
 590                         db_strerror(rc), rc, 0 );
 591 #endif
 592                 return rc;
 593
 594         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 595                 /* size not multiple of ID size */
 596 #ifdef NEW_LOGGING
 597                 LDAP_LOG( INDEX, ERR,
 598                         "bdb_idl_insert_key: odd size: expected %ld multiple, got %ld\n",
 599                         (long) sizeof( ID ), (long) data.size, 0 );
 600 #else
 601                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 602                         "odd size: expected %ld multiple, got %ld\n",
 603                         (long) sizeof( ID ), (long) data.size, 0 );
 604 #endif
 605                 return -1;
 606
 607         } else if ( data.size != BDB_IDL_SIZEOF(ids) ) {
 608                 /* size mismatch */
 609 #ifdef NEW_LOGGING
 610                 LDAP_LOG( INDEX, ERR,
 611                         "bdb_idl_insert_key: odd size: expected %ld multiple, got %ld\n",
 612                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 613 #else
 614                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 615                         "get size mismatch: expected %ld, got %ld\n",
 616                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 617 #endif
 618                 return -1;
 619
 620         } else if ( BDB_IDL_IS_RANGE(ids) ) {
 621                 if( id < ids[1] ) {
 622                         ids[1] = id;
 623                 } else if ( ids[2] > id ) {
 624                         ids[2] = id;
 625                 } else {
 626                         return 0;
 627                 }
 628
 629         } else {
 630                 rc = bdb_idl_insert( ids, id );
 631
 632                 if( rc == -1 ) {
 633 #ifdef NEW_LOGGING
 634                         LDAP_LOG( INDEX, DETAIL1, "bdb_idl_insert_key: dup\n", 0, 0, 0 );
 635 #else
 636                         Debug( LDAP_DEBUG_TRACE, "=> bdb_idl_insert_key: dup\n",
 637                                 0, 0, 0 );
 638 #endif
 639                         return 0;
 640                 }
 641                 if( rc != 0 ) {
 642 #ifdef NEW_LOGGING
 643                         LDAP_LOG( INDEX, ERR,
 644                                 "bdb_idl_insert_key: insert failed: (%d)\n", rc, 0, 0 );
 645 #else
 646                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 647                                 "bdb_idl_insert failed (%d)\n",
 648                                 rc, 0, 0 );
 649 #endif
 650
 651                         return rc;
 652                 }
 653
 654                 data.size = BDB_IDL_SIZEOF( ids );
 655         }
 656
 657         /* store the key */
 658         rc = db->put( db, tid, key, &data, 0 );
 659 #endif
 660         if( rc != 0 && rc != DB_KEYEXIST ) {
 661 #ifdef NEW_LOGGING
 662                 LDAP_LOG( INDEX, ERR,
 663                         "bdb_idl_insert_key: put failed: %s (%d)\n",
 664                         db_strerror(rc), rc, 0 );
 665 #else
 666                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 667                         "put failed: %s (%d)\n",
 668                         db_strerror(rc), rc, 0 );
 669 #endif
 670         }
 671         return rc;
 672 }
 673
 674 int
 675 bdb_idl_delete_key(
 676         BackendDB       *be,
 677         DB                      *db,
 678         DB_TXN          *tid,
 679         DBT                     *key,
 680         ID                      id )
 681 {
 682         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
 683         int     rc;
 684         DBT data;
 685 #ifndef BDB_IDL_MULTI
 686         ID ids[BDB_IDL_DB_SIZE];
 687 #endif
 688
 689 #if 0
 690         /* for printable keys only */
 691 #ifdef NEW_LOGGING
 692         LDAP_LOG( INDEX, ARGS, "bdb_idl_delete_key: %s %ld\n",
 693                 (char *)key->data, (long) id, 0 );
 694 #else
 695         Debug( LDAP_DEBUG_ARGS,
 696                 "=> bdb_idl_delete_key: %s %ld\n",
 697                 (char *)key->data, (long) id, 0 );
 698 #endif
 699 #endif
 700
 701         assert( id != NOID );
 702
 703         DBTzero( &data );
 704 #ifdef BDB_IDL_MULTI
 705         {
 706                 DBC *cursor;
 707                 ID lo, hi, tmp;
 708                 char *err;
 709
 710                 data.data = &tmp;
 711                 data.size = sizeof( id );
 712                 data.ulen = data.size;
 713                 data.flags = DB_DBT_USERMEM;
 714
 715                 rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
 716                 if ( rc != 0 ) {
 717 #ifdef NEW_LOGGING
 718                         LDAP_LOG( INDEX, ERR,
 719                                 "bdb_idl_delete_key: cursor failed: %s (%d)\n",
 720                                 db_strerror(rc), rc, 0 );
 721 #else
 722                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 723                                 "cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 );
 724 #endif
 725                         return rc;
 726                 }
 727                 /* Fetch the first data item for this key, to see if it
 728                  * exists and if it's a range.
 729                  */
 730                 rc = cursor->c_get( cursor, key, &data, DB_SET | DB_RMW );
 731                 err = "c_get";
 732                 if ( rc == 0 ) {
 733                         if ( tmp != 0 ) {
 734                                 /* Not a range, just delete it */
 735                                 if (tmp != id) {
 736                                         /* position to correct item */
 737                                         tmp = id;
 738                                         rc = cursor->c_get( cursor, key, &data,
 739                                                 DB_GET_BOTH | DB_RMW  );
 740                                 }
 741                                 if ( rc == 0 ) {
 742                                         rc = cursor->c_del( cursor, 0 );
 743                                         if ( rc != 0 ) {
 744                                                 err = "c_del id";
 745                                                 goto fail;
 746                                         }
 747                                 }
 748                         } else {
 749                                 /* It's a range, see if we need to rewrite
 750                                  * the boundaries
 751                                  */
 752                                 hi = 0;
 753                                 data.data = &lo;
 754                                 rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
 755                                 if ( rc != 0 ) {
 756                                         err = "c_get lo";
 757                                         goto fail;
 758                                 }
 759                                 if ( id > lo ) {
 760                                         data.data = &hi;
 761                                         rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
 762                                         if ( rc != 0 ) {
 763                                                 err = "c_get hi";
 764                                                 goto fail;
 765                                         }
 766                                 }
 767                                 if ( id == lo || id == hi ) {
 768                                         if ( id == lo ) {
 769                                                 id++;
 770                                                 lo = id;
 771                                         } else if ( id == hi ) {
 772                                                 id--;
 773                                                 hi = id;
 774                                         }
 775                                         if ( lo >= hi ) {
 776                                         /* The range has collapsed... */
 777                                                 rc = db->del( db, tid, key, 0 );
 778                                                 if ( rc != 0 ) {
 779                                                         err = "del";
 780                                                         goto fail;
 781                                                 }
 782                                         } else {
 783                                                 rc = cursor->c_del( cursor, 0 );
 784                                                 if ( rc != 0 ) {
 785                                                         err = "c_del";
 786                                                         goto fail;
 787                                                 }
 788                                         }
 789                                         if ( lo <= hi ) {
 790                                                 data.data = &id;
 791                                                 rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST );
 792                                                 if ( rc != 0 ) {
 793                                                         err = "c_put lo/hi";
 794                                                         goto fail;
 795                                                 }
 796                                         }
 797                                 }
 798                         }
 799                 } else {
 800                         /* initial c_get failed, nothing was done */
 801 fail:
 802 #ifdef NEW_LOGGING
 803                         LDAP_LOG( INDEX, ERR,
 804                                 "bdb_idl_delete_key: %s failed: %s (%d)\n",
 805                                 err, db_strerror(rc), rc );
 806 #else
 807                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 808                                 "%s failed: %s (%d)\n", err, db_strerror(rc), rc );
 809 #endif
 810                         cursor->c_close( cursor );
 811                         return rc;
 812                 }
 813                 rc = cursor->c_close( cursor );
 814         }
 815 #else
 816         data.data = ids;
 817         data.ulen = sizeof( ids );
 818         data.flags = DB_DBT_USERMEM;
 819
 820         /* fetch the key for read/modify/write */
 821         rc = db->get( db, tid, key, &data, DB_RMW | bdb->bi_db_opflags );
 822
 823         if ( rc != 0 ) {
 824 #ifdef NEW_LOGGING
 825                 LDAP_LOG( INDEX, ERR, "bdb_idl_delete_key: get failed: %s (%d)\n",
 826                         db_strerror(rc), rc, 0 );
 827 #else
 828                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 829                         "get failed: %s (%d)\n",
 830                         db_strerror(rc), rc, 0 );
 831 #endif
 832                 return rc;
 833
 834         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 835                 /* size not multiple of ID size */
 836 #ifdef NEW_LOGGING
 837                 LDAP_LOG( INDEX, ERR,
 838                         "bdb_idl_delete_key: odd size: expected: %ld multiple, got %ld\n",
 839                         (long) sizeof( ID ), (long) data.size, 0 );
 840 #else
 841                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 842                         "odd size: expected %ld multiple, got %ld\n",
 843                         (long) sizeof( ID ), (long) data.size, 0 );
 844 #endif
 845                 return -1;
 846
 847         } else if ( BDB_IDL_IS_RANGE(ids) ) {
 848                 return 0;
 849
 850         } else if ( data.size != (1 + ids[0]) * sizeof( ID ) ) {
 851                 /* size mismatch */
 852 #ifdef NEW_LOGGING
 853                 LDAP_LOG( INDEX, ERR,
 854                         "bdb_idl_delete_key: get size mismatch: expected: %ld, got %ld\n",
 855                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 856 #else
 857                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 858                         "get size mismatch: expected %ld, got %ld\n",
 859                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 860 #endif
 861                 return -1;
 862
 863         } else {
 864                 rc = idl_delete( ids, id );
 865
 866                 if( rc != 0 ) {
 867 #ifdef NEW_LOGGING
 868                         LDAP_LOG( INDEX, ERR,
 869                                 "bdb_idl_delete_key: delete failed: (%d)\n", rc, 0, 0 );
 870 #else
 871                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 872                                 "idl_delete failed (%d)\n",
 873                                 rc, 0, 0 );
 874 #endif
 875                         return rc;
 876                 }
 877
 878                 if( ids[0] == 0 ) {
 879                         /* delete the key */
 880                         rc = db->del( db, tid, key, 0 );
 881                         if( rc != 0 ) {
 882 #ifdef NEW_LOGGING
 883                                 LDAP_LOG( INDEX, ERR,
 884                                         "bdb_idl_delete_key: delete failed: %s (%d)\n",
 885                                         db_strerror(rc), rc, 0 );
 886 #else
 887                                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 888                                         "delete failed: %s (%d)\n",
 889                                         db_strerror(rc), rc, 0 );
 890 #endif
 891                         }
 892                         return rc;
 893                 }
 894
 895                 data.size = (ids[0]+1) * sizeof( ID );
 896         }
 897
 898         /* store the key */
 899         rc = db->put( db, tid, key, &data, 0 );
 900
 901 #endif /* BDB_IDL_MULTI */
 902
 903         if( rc != 0 ) {
 904 #ifdef NEW_LOGGING
 905                 LDAP_LOG( INDEX, ERR, "bdb_idl_delete_key: put failed: %s (%d)\n",
 906                         db_strerror(rc), rc, 0 );
 907 #else
 908                 Debug( LDAP_DEBUG_ANY,
 909                         "=> bdb_idl_delete_key: put failed: %s (%d)\n",
 910                         db_strerror(rc), rc, 0 );
 911 #endif
 912         }
 913
 914         return rc;
 915 }
 916
 917
 918 /*
 919  * idl_intersection - return a = a intersection b
 920  */
 921 int
 922 bdb_idl_intersection(
 923         ID *a,
 924         ID *b )
 925 {
 926         ID ida, idb;
 927         ID idmax, idmin;
 928         ID cursora = 0, cursorb = 0, cursorc;
 929         int swap = 0;
 930
 931         if ( BDB_IDL_IS_ZERO( a ) || BDB_IDL_IS_ZERO( b ) ) {
 932                 a[0] = 0;
 933                 return 0;
 934         }
 935
 936         idmin = IDL_MAX( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) );
 937         idmax = IDL_MIN( BDB_IDL_LAST(a), BDB_IDL_LAST(b) );
 938         if ( idmin > idmax ) {
 939                 a[0] = 0;
 940                 return 0;
 941         } else if ( idmin == idmax ) {
 942                 a[0] = 1;
 943                 a[1] = idmin;
 944                 return 0;
 945         }
 946
 947         if ( BDB_IDL_IS_RANGE( a ) && BDB_IDL_IS_RANGE(b) ) {
 948                 a[1] = idmin;
 949                 a[2] = idmax;
 950                 return 0;
 951         }
 952
 953         if ( BDB_IDL_IS_RANGE( a ) ) {
 954                 ID *tmp = a;
 955                 a = b;
 956                 b = tmp;
 957                 swap = 1;
 958         }
 959
 960         if ( BDB_IDL_IS_RANGE( b ) && BDB_IDL_FIRST( b ) <= idmin &&
 961                 BDB_IDL_LAST( b ) >= idmax) {
 962                 if (idmax - idmin + 1 == a[0])
 963                 {
 964                         a[0] = NOID;
 965                         a[1] = idmin;
 966                         a[2] = idmax;
 967                 }
 968                 goto done;
 969         }
 970
 971         ida = bdb_idl_first( a, &cursora );
 972         idb = bdb_idl_first( b, &cursorb );
 973         cursorc = 0;
 974
 975         while( ida < idmin )
 976                 ida = bdb_idl_next( a, &cursora );
 977         while( idb < idmin )
 978                 idb = bdb_idl_next( b, &cursorb );
 979
 980         while( ida <= idmax || idb <= idmax ) {
 981                 if( ida == idb ) {
 982                         a[++cursorc] = ida;
 983                         ida = bdb_idl_next( a, &cursora );
 984                         idb = bdb_idl_next( b, &cursorb );
 985                 } else if ( ida < idb ) {
 986                         ida = bdb_idl_next( a, &cursora );
 987                 } else {
 988                         idb = bdb_idl_next( b, &cursorb );
 989                 }
 990         }
 991         a[0] = cursorc;
 992 done:
 993         if (swap)
 994                 BDB_IDL_CPY( b, a );
 995
 996         return 0;
 997 }
 998
 999
1000 /*
1001  * idl_union - return a = a union b
1002  */
1003 int
1004 bdb_idl_union(
1005         ID      *a,
1006         ID      *b )
1007 {
1008         ID ida, idb;
1009         ID cursora = 0, cursorb = 0, cursorc;
1010
1011         if ( BDB_IDL_IS_ZERO( b ) ) {
1012                 return 0;
1013         }
1014
1015         if ( BDB_IDL_IS_ZERO( a ) ) {
1016                 BDB_IDL_CPY( a, b );
1017                 return 0;
1018         }
1019
1020         if ( BDB_IDL_IS_RANGE( a ) || BDB_IDL_IS_RANGE(b) ) {
1021 over:           ida = IDL_MIN( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) );
1022                 idb = IDL_MAX( BDB_IDL_LAST(a), BDB_IDL_LAST(b) );
1023                 a[0] = NOID;
1024                 a[1] = ida;
1025                 a[2] = idb;
1026                 return 0;
1027         }
1028
1029         ida = bdb_idl_first( a, &cursora );
1030         idb = bdb_idl_first( b, &cursorb );
1031
1032         cursorc = b[0];
1033
1034         /* The distinct elements of a are cat'd to b */
1035         while( ida != NOID || idb != NOID ) {
1036                 if ( ida < idb ) {
1037                         if( ++cursorc > BDB_IDL_UM_MAX ) {
1038                                 goto over;
1039                         }
1040                         b[cursorc] = ida;
1041                         ida = bdb_idl_next( a, &cursora );
1042
1043                 } else {
1044                         if ( ida == idb )
1045                                 ida = bdb_idl_next( a, &cursora );
1046                         idb = bdb_idl_next( b, &cursorb );
1047                 }
1048         }
1049
1050         /* b is copied back to a in sorted order */
1051         a[0] = cursorc;
1052         cursora = 1;
1053         cursorb = 1;
1054         cursorc = b[0]+1;
1055         while (cursorb <= b[0] || cursorc <= a[0]) {
1056                 if (cursorc > a[0])
1057                         idb = NOID;
1058                 else
1059                         idb = b[cursorc];
1060                 if (cursorb <= b[0] && b[cursorb] < idb)
1061                         a[cursora++] = b[cursorb++];
1062                 else {
1063                         a[cursora++] = idb;
1064                         cursorc++;
1065                 }
1066         }
1067
1068         return 0;
1069 }
1070
1071
1072 #if 0
1073 /*
1074  * bdb_idl_notin - return a intersection ~b (or a minus b)
1075  */
1076 int
1077 bdb_idl_notin(
1078         ID      *a,
1079         ID      *b,
1080         ID *ids )
1081 {
1082         ID ida, idb;
1083         ID cursora = 0, cursorb = 0;
1084
1085         if( BDB_IDL_IS_ZERO( a ) ||
1086                 BDB_IDL_IS_ZERO( b ) ||
1087                 BDB_IDL_IS_RANGE( b ) )
1088         {
1089                 BDB_IDL_CPY( ids, a );
1090                 return 0;
1091         }
1092
1093         if( BDB_IDL_IS_RANGE( a ) ) {
1094                 BDB_IDL_CPY( ids, a );
1095                 return 0;
1096         }
1097
1098         ida = bdb_idl_first( a, &cursora ),
1099         idb = bdb_idl_first( b, &cursorb );
1100
1101         ids[0] = 0;
1102
1103         while( ida != NOID ) {
1104                 if ( idb == NOID ) {
1105                         /* we could shortcut this */
1106                         ids[++ids[0]] = ida;
1107                         ida = bdb_idl_next( a, &cursora );
1108
1109                 } else if ( ida < idb ) {
1110                         ids[++ids[0]] = ida;
1111                         ida = bdb_idl_next( a, &cursora );
1112
1113                 } else if ( ida > idb ) {
1114                         idb = bdb_idl_next( b, &cursorb );
1115
1116                 } else {
1117                         ida = bdb_idl_next( a, &cursora );
1118                         idb = bdb_idl_next( b, &cursorb );
1119                 }
1120         }
1121
1122         return 0;
1123 }
1124 #endif
1125
1126 ID bdb_idl_first( ID *ids, ID *cursor )
1127 {
1128         ID pos;
1129
1130         if ( ids[0] == 0 ) {
1131                 *cursor = NOID;
1132                 return NOID;
1133         }
1134
1135         if ( BDB_IDL_IS_RANGE( ids ) ) {
1136                 if( *cursor < ids[1] ) {
1137                         *cursor = ids[1];
1138                 }
1139                 return *cursor;
1140         }
1141
1142         if ( *cursor == 0 )
1143                 pos = 1;
1144         else
1145                 pos = bdb_idl_search( ids, *cursor );
1146
1147         if( pos > ids[0] ) {
1148                 return NOID;
1149         }
1150
1151         *cursor = pos;
1152         return ids[pos];
1153 }
1154
1155 ID bdb_idl_next( ID *ids, ID *cursor )
1156 {
1157         if ( BDB_IDL_IS_RANGE( ids ) ) {
1158                 if( ids[2] < ++(*cursor) ) {
1159                         return NOID;
1160                 }
1161                 return *cursor;
1162         }
1163
1164         if ( ++(*cursor) <= ids[0] ) {
1165                 return ids[*cursor];
1166         }
1167
1168         return NOID;
1169 }