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_IDL_DB_SIZE];
 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 %ld, 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                 ID buf[BDB_IDL_DB_SIZE];
 402                 DBC *cursor;
 403                 ID lo, hi;
 404                 char *err;
 405
 406                 data.size = sizeof( ID );
 407                 data.ulen = data.size;
 408                 data.flags = DB_DBT_USERMEM;
 409
 410                 rc = bdb_idl_fetch_key( be, db, tid, key, buf );
 411                 if ( rc && rc != DB_NOTFOUND )
 412                         return rc;
 413
 414                 /* If it never existed, or there's room in the current key,
 415                  * just store it.
 416                  */
 417                 if ( rc == DB_NOTFOUND || ( !BDB_IDL_IS_RANGE(buf) &&
 418                         BDB_IDL_N(buf) < BDB_IDL_DB_MAX ) ) {
 419                         data.data = &id;
 420                         rc = db->put( db, tid, key, &data, DB_NODUPDATA );
 421                 } else if ( BDB_IDL_IS_RANGE(buf) ) {
 422                         /* If it's a range and we're outside the boundaries,
 423                          * rewrite the range boundaries.
 424                          */
 425                         if ( id < BDB_IDL_RANGE_FIRST(buf) ||
 426                                 id > BDB_IDL_RANGE_LAST(buf) ) {
 427                                 rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
 428                                 if ( rc != 0 ) {
 429 #ifdef NEW_LOGGING
 430                                         LDAP_LOG(( "idl", LDAP_LEVEL_ERR, "bdb_idl_insert_key: cursor failed: %s (%d)\n", db_strerror(rc), rc ));
 431 #else
 432                                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 433                                                 "cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 );
 434 #endif
 435                                         return rc;
 436                                 }
 437                                 if ( id < BDB_IDL_RANGE_FIRST(buf) ) {
 438                                         data.data = buf+1;
 439                                 } else {
 440                                         data.data = buf+2;
 441                                 }
 442                                 rc = cursor->c_get( cursor, key, &data, DB_GET_BOTH | DB_RMW );
 443                                 if ( rc != 0 ) {
 444                                         err = "c_get";
 445 fail:
 446 #ifdef NEW_LOGGING
 447                                 LDAP_LOG(( "idl", LDAP_LEVEL_ERR, "bdb_idl_insert_key: %s failed: %s (%d)\n", err, db_strerror(rc), rc ));
 448 #else
 449                                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 450                                                 "%s failed: %s (%d)\n", err, db_strerror(rc), rc );
 451 #endif
 452                                         if ( cursor ) cursor->c_close( cursor );
 453                                         return rc;
 454                                 }
 455                                 data.data = &id;
 456                                 /* We should have been able to just overwrite the old
 457                                  * value with the new, but apparently we have to delete
 458                                  * it first.
 459                                  */
 460                                 rc = cursor->c_del( cursor, 0 );
 461                                 if ( rc ) {
 462                                         err = "c_del";
 463                                         goto fail;
 464                                 }
 465                                 rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST );
 466                                 if ( rc ) {
 467                                         err = "c_put";
 468                                         goto fail;
 469                                 }
 470                                 rc = cursor->c_close( cursor );
 471                                 if ( rc ) {
 472                                         cursor = NULL;
 473                                         err = "c_close";
 474                                         goto fail;
 475                                 }
 476                         }
 477                 } else {                /* convert to a range */
 478                         lo = BDB_IDL_FIRST(buf);
 479                         hi = BDB_IDL_LAST(buf);
 480
 481                         if (id < lo)
 482                                 lo = id;
 483                         else if (id > hi)
 484                                 hi = id;
 485
 486                         cursor = NULL;
 487
 488                         /* Delete all of the old IDL so we can replace with a range */
 489                         rc = db->del( db, tid, key, 0 );
 490                         if ( rc ) {
 491                                 err = "del";
 492                                 goto fail;
 493                         }
 494
 495                         /* Write the range */
 496                         data.data = &id;
 497                         id = 0;
 498                         rc = db->put( db, tid, key, &data, 0 );
 499                         if ( rc ) {
 500                                 err = "put #1";
 501                                 goto fail;
 502                         }
 503                         id = lo;
 504                         rc = db->put( db, tid, key, &data, 0 );
 505                         if ( rc ) {
 506                                 err = "put #2";
 507                                 goto fail;
 508                         }
 509                         id = hi;
 510                         rc = db->put( db, tid, key, &data, 0 );
 511                         if ( rc ) {
 512                                 err = "put #3";
 513                                 goto fail;
 514                         }
 515                 }
 516         }
 517 #else
 518         data.data = ids;
 519         data.ulen = sizeof ids;
 520         data.flags = DB_DBT_USERMEM;
 521
 522         /* fetch the key for read/modify/write */
 523         rc = db->get( db, tid, key, &data, DB_RMW | bdb->bi_db_opflags );
 524
 525         if( rc == DB_NOTFOUND ) {
 526                 ids[0] = 1;
 527                 ids[1] = id;
 528                 data.size = 2 * sizeof( ID );
 529
 530         } else if ( rc != 0 ) {
 531 #ifdef NEW_LOGGING
 532                 LDAP_LOG(( "idl", LDAP_LEVEL_ERR, "bdb_idl_insert_key: get failed: %s (%d)\n", db_strerror(rc), rc ));
 533 #else
 534                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 535                         "get failed: %s (%d)\n",
 536                         db_strerror(rc), rc, 0 );
 537 #endif
 538                 return rc;
 539
 540         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 541                 /* size not multiple of ID size */
 542 #ifdef NEW_LOGGING
 543                 LDAP_LOG(( "idl", LDAP_LEVEL_ERR, "bdb_idl_insert_key: odd size: expected %ld multiple, got %ld\n", (long) sizeof( ID ), (long) data.size ));
 544 #else
 545                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 546                         "odd size: expected %ld multiple, got %ld\n",
 547                         (long) sizeof( ID ), (long) data.size, 0 );
 548 #endif
 549                 return -1;
 550
 551         } else if ( data.size != BDB_IDL_SIZEOF(ids) ) {
 552                 /* size mismatch */
 553 #ifdef NEW_LOGGING
 554                 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 ));
 555 #else
 556                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 557                         "get size mismatch: expected %ld, got %ld\n",
 558                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 559 #endif
 560                 return -1;
 561
 562         } else if ( BDB_IDL_IS_RANGE(ids) ) {
 563                 if( id < ids[1] ) {
 564                         ids[1] = id;
 565                 } else if ( ids[2] > id ) {
 566                         ids[2] = id;
 567                 } else {
 568                         return 0;
 569                 }
 570
 571         } else {
 572                 rc = bdb_idl_insert( ids, id );
 573
 574                 if( rc == -1 ) {
 575 #ifdef NEW_LOGGING
 576                         LDAP_LOG(( "idl", LDAP_LEVEL_DETAIL1, "bdb_idl_insert_key: dup\n" ));
 577 #else
 578                         Debug( LDAP_DEBUG_TRACE, "=> bdb_idl_insert_key: dup\n",
 579                                 0, 0, 0 );
 580 #endif
 581                         return 0;
 582                 }
 583                 if( rc != 0 ) {
 584 #ifdef NEW_LOGGING
 585                         LDAP_LOG(( "idl", LDAP_LEVEL_ERR, "bdb_idl_insert_key: insert failed: (%d)\n", rc ));
 586 #else
 587                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 588                                 "bdb_idl_insert failed (%d)\n",
 589                                 rc, 0, 0 );
 590 #endif
 591
 592                         return rc;
 593                 }
 594
 595                 data.size = BDB_IDL_SIZEOF( ids );
 596         }
 597
 598         /* store the key */
 599         rc = db->put( db, tid, key, &data, 0 );
 600 #endif
 601         if( rc == DB_KEYEXIST ) rc = 0;
 602
 603         if( rc != 0 ) {
 604 #ifdef NEW_LOGGING
 605                 LDAP_LOG(( "idl", LDAP_LEVEL_ERR, "bdb_idl_insert_key: put failed: (%d)\n", db_strerror(rc), rc ));
 606 #else
 607                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 608                         "put failed: %s (%d)\n",
 609                         db_strerror(rc), rc, 0 );
 610 #endif
 611         }
 612         return rc;
 613 }
 614
 615 int
 616 bdb_idl_delete_key(
 617         BackendDB       *be,
 618         DB                      *db,
 619         DB_TXN          *tid,
 620         DBT                     *key,
 621         ID                      id )
 622 {
 623         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
 624         int     rc;
 625         DBT data;
 626 #ifndef BDB_IDL_MULTI
 627         ID ids[BDB_IDL_DB_SIZE];
 628 #endif
 629
 630 #if 0
 631         /* for printable keys only */
 632 #ifdef NEW_LOGGING
 633         LDAP_LOG(( "idl", LDAP_LEVEL_ARGS, "bdb_idl_delete_key: %s %ld\n", (char *)key->data, (long) id ));
 634 #else
 635         Debug( LDAP_DEBUG_ARGS,
 636                 "=> bdb_idl_delete_key: %s %ld\n",
 637                 (char *)key->data, (long) id, 0 );
 638 #endif
 639 #endif
 640
 641         assert( id != NOID );
 642
 643         DBTzero( &data );
 644 #ifdef BDB_IDL_MULTI
 645         {
 646                 DBC *cursor;
 647
 648                 data.data = &id;
 649                 data.size = sizeof( id );
 650                 data.ulen = data.size;
 651                 data.flags = DB_DBT_USERMEM;
 652
 653                 rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
 654                 rc = cursor->c_get( cursor, key, &data, bdb->bi_db_opflags |
 655                         DB_GET_BOTH | DB_RMW  );
 656                 if (rc == 0)
 657                         rc = cursor->c_del( cursor, 0 );
 658                 rc = cursor->c_close( cursor );
 659         }
 660 #else
 661         data.data = ids;
 662         data.ulen = sizeof( ids );
 663         data.flags = DB_DBT_USERMEM;
 664
 665         /* fetch the key for read/modify/write */
 666         rc = db->get( db, tid, key, &data, DB_RMW | bdb->bi_db_opflags );
 667
 668         if ( rc != 0 ) {
 669 #ifdef NEW_LOGGING
 670                 LDAP_LOG(( "idl", LDAP_LEVEL_ERR, "bdb_idl_delete_key: get failed: %s (%d)\n", db_strerror(rc), rc ));
 671 #else
 672                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 673                         "get failed: %s (%d)\n",
 674                         db_strerror(rc), rc, 0 );
 675 #endif
 676                 return rc;
 677
 678         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 679                 /* size not multiple of ID size */
 680 #ifdef NEW_LOGGING
 681                 LDAP_LOG(( "idl", LDAP_LEVEL_ERR, "bdb_idl_delete_key: odd size: expected: %ld multiple, got %ld\n", (long) sizeof( ID ), (long) data.size ));
 682 #else
 683                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 684                         "odd size: expected %ld multiple, got %ld\n",
 685                         (long) sizeof( ID ), (long) data.size, 0 );
 686 #endif
 687                 return -1;
 688
 689         } else if ( BDB_IDL_IS_RANGE(ids) ) {
 690                 return 0;
 691
 692         } else if ( data.size != (1 + ids[0]) * sizeof( ID ) ) {
 693                 /* size mismatch */
 694 #ifdef NEW_LOGGING
 695                 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 ));
 696 #else
 697                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 698                         "get size mismatch: expected %ld, got %ld\n",
 699                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 700 #endif
 701                 return -1;
 702
 703         } else {
 704                 rc = idl_delete( ids, id );
 705
 706                 if( rc != 0 ) {
 707 #ifdef NEW_LOGGING
 708                         LDAP_LOG(( "idl", LDAP_LEVEL_ERR, "bdb_idl_delete_key: delete failed: (%d)\n", rc ));
 709 #else
 710                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 711                                 "idl_delete failed (%d)\n",
 712                                 rc, 0, 0 );
 713 #endif
 714                         return rc;
 715                 }
 716
 717                 if( ids[0] == 0 ) {
 718                         /* delete the key */
 719                         rc = db->del( db, tid, key, 0 );
 720                         if( rc != 0 ) {
 721 #ifdef NEW_LOGGING
 722                                 LDAP_LOG(( "idl", LDAP_LEVEL_ERR, "bdb_idl_delete_key: delete failed: %s (%d)\n", db_strerror(rc), rc ));
 723 #else
 724                                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 725                                         "delete failed: %s (%d)\n",
 726                                         db_strerror(rc), rc, 0 );
 727 #endif
 728                         }
 729                         return rc;
 730                 }
 731
 732                 data.size = (ids[0]+1) * sizeof( ID );
 733         }
 734
 735         /* store the key */
 736         rc = db->put( db, tid, key, &data, 0 );
 737
 738 #endif /* BDB_IDL_MULTI */
 739
 740         if( rc != 0 ) {
 741 #ifdef NEW_LOGGING
 742                 LDAP_LOG(( "idl", LDAP_LEVEL_ERR, "bdb_idl_delete_key: put failed: %s (%d)\n", db_strerror(rc), rc ));
 743 #else
 744                 Debug( LDAP_DEBUG_ANY,
 745                         "=> bdb_idl_delete_key: put failed: %s (%d)\n",
 746                         db_strerror(rc), rc, 0 );
 747 #endif
 748         }
 749
 750         return rc;
 751 }
 752
 753
 754 /*
 755  * idl_intersection - return a = a intersection b
 756  */
 757 int
 758 bdb_idl_intersection(
 759         ID *a,
 760         ID *b )
 761 {
 762         ID ida, idb;
 763         ID idmax, idmin;
 764         ID cursora = 0, cursorb = 0, cursorc;
 765         int swap = 0;
 766
 767         if ( BDB_IDL_IS_ZERO( a ) || BDB_IDL_IS_ZERO( b ) ) {
 768                 a[0] = 0;
 769                 return 0;
 770         }
 771
 772         idmin = IDL_MAX( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) );
 773         idmax = IDL_MIN( BDB_IDL_LAST(a), BDB_IDL_LAST(b) );
 774         if ( idmin > idmax ) {
 775                 a[0] = 0;
 776                 return 0;
 777         } else if ( idmin == idmax ) {
 778                 a[0] = 1;
 779                 a[1] = idmin;
 780                 return 0;
 781         }
 782
 783         if ( BDB_IDL_IS_RANGE( a ) && BDB_IDL_IS_RANGE(b) ) {
 784                 a[1] = idmin;
 785                 a[2] = idmax;
 786                 return 0;
 787         }
 788
 789         if ( BDB_IDL_IS_RANGE( a ) ) {
 790                 ID *tmp = a;
 791                 a = b;
 792                 b = tmp;
 793                 swap = 1;
 794         }
 795
 796         if ( BDB_IDL_IS_RANGE( b ) && BDB_IDL_FIRST( b ) <= idmin &&
 797                 BDB_IDL_LAST( b ) >= idmax) {
 798                 if (idmax - idmin + 1 == a[0])
 799                 {
 800                         a[0] = NOID;
 801                         a[1] = idmin;
 802                         a[2] = idmax;
 803                 }
 804                 goto done;
 805         }
 806
 807         ida = bdb_idl_first( a, &cursora );
 808         idb = bdb_idl_first( b, &cursorb );
 809         cursorc = 0;
 810
 811         while( ida < idmin )
 812                 ida = bdb_idl_next( a, &cursora );
 813         while( idb < idmin )
 814                 idb = bdb_idl_next( b, &cursorb );
 815
 816         while( ida <= idmax || idb <= idmax ) {
 817                 if( ida == idb ) {
 818                         a[++cursorc] = ida;
 819                         ida = bdb_idl_next( a, &cursora );
 820                         idb = bdb_idl_next( b, &cursorb );
 821                 } else if ( ida < idb ) {
 822                         ida = bdb_idl_next( a, &cursora );
 823                 } else {
 824                         idb = bdb_idl_next( b, &cursorb );
 825                 }
 826         }
 827         a[0] = cursorc;
 828 done:
 829         if (swap)
 830                 BDB_IDL_CPY( b, a );
 831
 832         return 0;
 833 }
 834
 835
 836 /*
 837  * idl_union - return a = a union b
 838  */
 839 int
 840 bdb_idl_union(
 841         ID      *a,
 842         ID      *b )
 843 {
 844         ID ida, idb;
 845         ID cursora = 0, cursorb = 0, cursorc;
 846
 847         if ( BDB_IDL_IS_ZERO( b ) ) {
 848                 return 0;
 849         }
 850
 851         if ( BDB_IDL_IS_ZERO( a ) ) {
 852                 BDB_IDL_CPY( a, b );
 853                 return 0;
 854         }
 855
 856         if ( BDB_IDL_IS_RANGE( a ) || BDB_IDL_IS_RANGE(b) ) {
 857 over:           a[1] = IDL_MIN( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) );
 858                 a[2] = IDL_MAX( BDB_IDL_LAST(a), BDB_IDL_LAST(b) );
 859                 return 0;
 860         }
 861
 862         ida = bdb_idl_first( a, &cursora );
 863         idb = bdb_idl_first( b, &cursorb );
 864
 865         cursorc = b[0];
 866
 867         /* The distinct elements of a are cat'd to b */
 868         while( ida != NOID || idb != NOID ) {
 869                 if ( ida < idb ) {
 870                         if( ++cursorc > BDB_IDL_UM_MAX ) {
 871                                 a[0] = NOID;
 872                                 goto over;
 873                         }
 874                         b[cursorc] = ida;
 875                         ida = bdb_idl_next( a, &cursora );
 876
 877                 } else {
 878                         if ( ida == idb )
 879                                 ida = bdb_idl_next( a, &cursora );
 880                         idb = bdb_idl_next( b, &cursorb );
 881                 }
 882         }
 883
 884         /* b is copied back to a in sorted order */
 885         a[0] = cursorc;
 886         cursora = 1;
 887         cursorb = 1;
 888         cursorc = b[0]+1;
 889         while (cursorb <= b[0] || cursorc <= a[0]) {
 890                 if (cursorc > a[0])
 891                         idb = NOID;
 892                 else
 893                         idb = b[cursorc];
 894                 if (b[cursorb] < idb)
 895                         a[cursora++] = b[cursorb++];
 896                 else {
 897                         a[cursora++] = idb;
 898                         cursorc++;
 899                 }
 900         }
 901
 902         return 0;
 903 }
 904
 905
 906 #if 0
 907 /*
 908  * bdb_idl_notin - return a intersection ~b (or a minus b)
 909  */
 910 int
 911 bdb_idl_notin(
 912         ID      *a,
 913         ID      *b,
 914         ID *ids )
 915 {
 916         ID ida, idb;
 917         ID cursora = 0, cursorb = 0;
 918
 919         if( BDB_IDL_IS_ZERO( a ) ||
 920                 BDB_IDL_IS_ZERO( b ) ||
 921                 BDB_IDL_IS_RANGE( b ) )
 922         {
 923                 BDB_IDL_CPY( ids, a );
 924                 return 0;
 925         }
 926
 927         if( BDB_IDL_IS_RANGE( a ) ) {
 928                 BDB_IDL_CPY( ids, a );
 929                 return 0;
 930         }
 931
 932         ida = bdb_idl_first( a, &cursora ),
 933         idb = bdb_idl_first( b, &cursorb );
 934
 935         ids[0] = 0;
 936
 937         while( ida != NOID ) {
 938                 if ( idb == NOID ) {
 939                         /* we could shortcut this */
 940                         ids[++ids[0]] = ida;
 941                         ida = bdb_idl_next( a, &cursora );
 942
 943                 } else if ( ida < idb ) {
 944                         ids[++ids[0]] = ida;
 945                         ida = bdb_idl_next( a, &cursora );
 946
 947                 } else if ( ida > idb ) {
 948                         idb = bdb_idl_next( b, &cursorb );
 949
 950                 } else {
 951                         ida = bdb_idl_next( a, &cursora );
 952                         idb = bdb_idl_next( b, &cursorb );
 953                 }
 954         }
 955
 956         return 0;
 957 }
 958 #endif
 959
 960 ID bdb_idl_first( ID *ids, ID *cursor )
 961 {
 962         ID pos;
 963
 964         if ( ids[0] == 0 ) {
 965                 *cursor = NOID;
 966                 return NOID;
 967         }
 968
 969         if ( BDB_IDL_IS_RANGE( ids ) ) {
 970                 if( *cursor < ids[1] ) {
 971                         *cursor = ids[1];
 972                 }
 973                 return *cursor;
 974         }
 975
 976         if ( *cursor == 0 )
 977                 pos = 1;
 978         else
 979                 pos = bdb_idl_search( ids, *cursor );
 980
 981         if( pos > ids[0] ) {
 982                 return NOID;
 983         }
 984
 985         *cursor = pos;
 986         return ids[pos];
 987 }
 988
 989 ID bdb_idl_next( ID *ids, ID *cursor )
 990 {
 991         if ( BDB_IDL_IS_RANGE( ids ) ) {
 992                 if( ids[2] < ++(*cursor) ) {
 993                         return NOID;
 994                 }
 995                 return *cursor;
 996         }
 997
 998         if ( ++(*cursor) <= ids[0] ) {
 999                 return ids[*cursor];
1000         }
1001
1002         return NOID;
1003 }