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