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