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-2000 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 #ifndef IDL_DEBUG
  22         /* enable basic checks for now */
  23 #define IDL_DEBUG 1
  24 #endif
  25
  26 #if IDL_DEBUG > 0
  27 static void idl_check( ID *ids )
  28 {
  29         if( BDB_IDL_IS_RANGE( ids ) ) {
  30                 assert( BDB_IDL_RANGE_FIRST(ids) <= BDB_IDL_RANGE_LAST(ids) );
  31         } else {
  32                 ID i;
  33                 for( i=1; i < ids[0]; i++ ) {
  34                         assert( ids[i+1] > ids[i] );
  35                 }
  36         }
  37 }
  38
  39 #if IDL_DEBUG > 1
  40 static void idl_dump( ID *ids )
  41 {
  42         if( BDB_IDL_IS_RANGE( ids ) ) {
  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
  48         } else {
  49                 ID i;
  50                 Debug( LDAP_DEBUG_ANY, "IDL: size %ld", (long) ids[0], 0, 0 );
  51
  52                 for( i=1; i<=ids[0]; i++ ) {
  53                         if( i % 16 == 1 ) {
  54                                 Debug( LDAP_DEBUG_ANY, "\n", 0, 0, 0 );
  55                         }
  56                         Debug( LDAP_DEBUG_ANY, "  %02lx", (long) ids[i], 0, 0 );
  57                 }
  58
  59                 Debug( LDAP_DEBUG_ANY, "\n", 0, 0, 0 );
  60         }
  61
  62         idl_check( ids );
  63 }
  64 #endif /* IDL_DEBUG > 1 */
  65 #endif /* IDL_DEBUG > 0 */
  66
  67 unsigned bdb_idl_search( ID *ids, ID id )
  68 {
  69 #define IDL_BINARY_SEARCH 1
  70 #ifdef IDL_BINARY_SEARCH
  71         /*
  72          * binary search of id in ids
  73          * if found, returns position of id
  74          * if not found, returns first postion greater than id
  75          */
  76         unsigned base = 0;
  77         unsigned cursor = 0;
  78         int val;
  79         unsigned n = ids[0];
  80
  81 #if IDL_DEBUG > 0
  82         idl_check( ids );
  83 #endif
  84
  85         while( 0 < n ) {
  86                 int pivot = n >> 1;
  87                 cursor = base + pivot;
  88                 val = IDL_CMP( id, ids[cursor + 1] );
  89
  90                 if( val < 0 ) {
  91                         n = pivot;
  92
  93                 } else if ( val > 0 ) {
  94                         base = cursor + 1;
  95                         n -= pivot + 1;
  96
  97                 } else {
  98                         return cursor + 1;
  99                 }
 100         }
 101
 102         if( val > 0 ) {
 103                 return cursor + 2;
 104         } else {
 105                 return cursor + 1;
 106         }
 107
 108 #else
 109         /* (reverse) linear search */
 110         int i;
 111
 112 #if IDL_DEBUG > 0
 113         idl_check( ids );
 114 #endif
 115
 116         for( i=ids[0]; i; i-- ) {
 117                 if( id > ids[i] ) {
 118                         break;
 119                 }
 120         }
 121
 122         return i+1;
 123 #endif
 124 }
 125
 126 static int idl_insert( ID *ids, ID id )
 127 {
 128         unsigned x = bdb_idl_search( ids, id );
 129
 130 #if IDL_DEBUG > 1
 131         Debug( LDAP_DEBUG_ANY, "insert: %04lx at %d\n", (long) id, x, 0 );
 132         idl_dump( ids );
 133 #elif IDL_DEBUG > 0
 134         idl_check( ids );
 135 #endif
 136
 137         assert( x > 0 );
 138
 139         if( x < 1 ) {
 140                 /* internal error */
 141                 return -2;
 142         }
 143
 144         if ( x <= ids[0] && ids[x] == id ) {
 145                 /* duplicate */
 146                 return -1;
 147         }
 148
 149         if ( ++ids[0] >= BDB_IDL_DB_MAX ) {
 150                 if( id < ids[1] ) {
 151                         ids[1] = id;
 152                         ids[2] = ids[ids[0]-1];
 153                 } else if ( ids[ids[0]-1] < id ) {
 154                         ids[2] = id;
 155                 } else {
 156                         ids[2] = ids[ids[0]-1];
 157                 }
 158                 ids[0] = NOID;
 159
 160         } else {
 161                 /* insert id */
 162                 AC_MEMCPY( &ids[x+1], &ids[x], (ids[0]-x) * sizeof(ID) );
 163                 ids[x] = id;
 164         }
 165
 166 #if IDL_DEBUG > 1
 167         idl_dump( ids );
 168 #elif IDL_DEBUG > 0
 169         idl_check( ids );
 170 #endif
 171
 172         return 0;
 173 }
 174
 175 static int idl_delete( ID *ids, ID id )
 176 {
 177         unsigned x = bdb_idl_search( ids, id );
 178
 179 #if IDL_DEBUG > 1
 180         Debug( LDAP_DEBUG_ANY, "delete: %04lx at %d\n", (long) id, x, 0 );
 181         idl_dump( ids );
 182 #elif IDL_DEBUG > 0
 183         idl_check( ids );
 184 #endif
 185
 186         assert( x > 0 );
 187
 188         if( x <= 0 ) {
 189                 /* internal error */
 190                 return -2;
 191         }
 192
 193         if( x > ids[0] || ids[x] != id ) {
 194                 /* not found */
 195                 return -1;
 196
 197         } else if ( --ids[0] == 0 ) {
 198                 if( x != 1 ) {
 199                         return -3;
 200                 }
 201
 202         } else {
 203                 AC_MEMCPY( &ids[x], &ids[x+1], (1+ids[0]-x) * sizeof(ID) );
 204         }
 205
 206 #if IDL_DEBUG > 1
 207         idl_dump( ids );
 208 #elif IDL_DEBUG > 0
 209         idl_check( ids );
 210 #endif
 211
 212         return 0;
 213 }
 214
 215 int
 216 bdb_idl_fetch_key(
 217         BackendDB       *be,
 218         DB                      *db,
 219         DB_TXN          *tid,
 220         DBT                     *key,
 221         ID                      *ids )
 222 {
 223         int rc;
 224         DBT data;
 225
 226         assert( ids != NULL );
 227
 228         DBTzero( &data );
 229         data.data = ids;
 230         data.ulen = BDB_IDL_UM_SIZEOF;
 231         data.flags = DB_DBT_USERMEM;
 232
 233         /* fetch it */
 234         rc = db->get( db, tid, key, &data, 0 );
 235
 236         if( rc == DB_NOTFOUND ) {
 237                 return rc;
 238
 239         } else if( rc != 0 ) {
 240                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 241                         "get failed: %s (%d)\n",
 242                         db_strerror(rc), rc, 0 );
 243                 return rc;
 244
 245         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 246                 /* size not multiple of ID size */
 247                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 248                         "odd size: expected %ld multiple, got %ld\n",
 249                         (long) sizeof( ID ), (long) data.size, 0 );
 250                 return -1;
 251
 252         } else if ( data.size != BDB_IDL_SIZEOF(ids) ) {
 253                 /* size mismatch */
 254                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
 255                         "get size mismatch: expected %ld, got %ld\n",
 256                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 257                 return -1;
 258         }
 259
 260         return rc;
 261 }
 262
 263 int
 264 bdb_idl_insert_key(
 265         BackendDB       *be,
 266         DB                      *db,
 267         DB_TXN          *tid,
 268         DBT                     *key,
 269         ID                      id )
 270 {
 271         int     rc;
 272         ID ids[BDB_IDL_DB_SIZE];
 273         DBT data;
 274
 275         /* for printable keys only */
 276         Debug( LDAP_DEBUG_ARGS,
 277                 "=> bdb_idl_insert_key: %s %ld\n",
 278                 (char *)key->data, (long) id, 0 );
 279
 280         assert( id != NOID );
 281
 282         data.data = ids;
 283         data.ulen = sizeof ids;
 284         data.flags = DB_DBT_USERMEM;
 285
 286         /* fetch the key for read/modify/write */
 287         rc = db->get( db, tid, key, &data, DB_RMW );
 288
 289         if( rc == DB_NOTFOUND ) {
 290                 ids[0] = 1;
 291                 ids[1] = id;
 292                 data.size = 2 * sizeof( ID );
 293
 294         } else if ( rc != 0 ) {
 295                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 296                         "get failed: %s (%d)\n",
 297                         db_strerror(rc), rc, 0 );
 298                 return rc;
 299
 300         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 301                 /* size not multiple of ID size */
 302                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 303                         "odd size: expected %ld multiple, got %ld\n",
 304                         (long) sizeof( ID ), (long) data.size, 0 );
 305                 return -1;
 306
 307         } else if ( data.size != BDB_IDL_SIZEOF(ids) ) {
 308                 /* size mismatch */
 309                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 310                         "get size mismatch: expected %ld, got %ld\n",
 311                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 312                 return -1;
 313
 314         } else if ( BDB_IDL_IS_RANGE(ids) ) {
 315                 if( id < ids[1] ) {
 316                         ids[1] = id;
 317                 } else if ( ids[2] > id ) {
 318                         ids[2] = id;
 319                 } else {
 320                         return 0;
 321                 }
 322
 323         } else {
 324                 rc = idl_insert( ids, id );
 325
 326                 if( rc != 0 ) {
 327                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 328                                 "idl_insert failed (%d)\n",
 329                                 rc, 0, 0 );
 330                         return rc;
 331                 }
 332
 333                 data.size = BDB_IDL_SIZEOF( ids );
 334         }
 335
 336         /* store the key */
 337         rc = db->put( db, tid, key, &data, 0 );
 338
 339         if( rc != 0 ) {
 340                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 341                         "put failed: %s (%d)\n",
 342                         db_strerror(rc), rc, 0 );
 343         }
 344         return rc;
 345 }
 346
 347 int
 348 bdb_idl_delete_key(
 349         BackendDB       *be,
 350         DB                      *db,
 351         DB_TXN          *tid,
 352         DBT                     *key,
 353         ID                      id )
 354 {
 355         int     rc;
 356         ID ids[BDB_IDL_DB_SIZE];
 357         DBT data;
 358
 359         /* for printable keys only */
 360         Debug( LDAP_DEBUG_ARGS,
 361                 "=> bdb_idl_delete_key: %s %ld\n",
 362                 (char *)key->data, (long) id, 0 );
 363
 364         assert( id != NOID );
 365
 366         data.data = ids;
 367         data.ulen = sizeof( ids );
 368         data.flags = DB_DBT_USERMEM;
 369
 370         /* fetch the key for read/modify/write */
 371         rc = db->get( db, tid, key, &data, DB_RMW );
 372
 373         if ( rc != 0 ) {
 374                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 375                         "get failed: %s (%d)\n",
 376                         db_strerror(rc), rc, 0 );
 377                 return rc;
 378
 379         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 380                 /* size not multiple of ID size */
 381                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 382                         "odd size: expected %ld multiple, got %ld\n",
 383                         (long) sizeof( ID ), (long) data.size, 0 );
 384                 return -1;
 385
 386         } else if ( BDB_IDL_IS_RANGE(ids) ) {
 387                 return 0;
 388
 389         } else if ( data.size != (1 + ids[0]) * sizeof( ID ) ) {
 390                 /* size mismatch */
 391                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 392                         "get size mismatch: expected %ld, got %ld\n",
 393                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 394                 return -1;
 395
 396         } else {
 397                 rc = idl_delete( ids, id );
 398
 399                 if( rc != 0 ) {
 400                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 401                                 "idl_delete failed (%d)\n",
 402                                 rc, 0, 0 );
 403                         return rc;
 404                 }
 405
 406                 if( ids[0] == 0 ) {
 407                         /* delete the key */
 408                         rc = db->del( db, tid, key, 0 );
 409                         if( rc != 0 ) {
 410                                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 411                                         "delete failed: %s (%d)\n",
 412                                         db_strerror(rc), rc, 0 );
 413                         }
 414                         return rc;
 415                 }
 416
 417                 data.size = (ids[0]+1) * sizeof( ID );
 418         }
 419
 420         /* store the key */
 421         rc = db->put( db, tid, key, &data, 0 );
 422
 423         if( rc != 0 ) {
 424                 Debug( LDAP_DEBUG_ANY,
 425                         "=> bdb_idl_delete_key: put failed: %s (%d)\n",
 426                         db_strerror(rc), rc, 0 );
 427         }
 428
 429         return rc;
 430 }
 431
 432
 433 /*
 434  * idl_intersection - return a intersection b
 435  */
 436 int
 437 bdb_idl_intersection(
 438         ID *a,
 439         ID *b,
 440         ID *ids )
 441 {
 442         ID ida, idb;
 443         ID cursora = 0, cursorb = 0;
 444
 445         if ( BDB_IDL_IS_ZERO( a ) || BDB_IDL_IS_ZERO( b ) ) {
 446                 ids[0] = 0;
 447                 return 0;
 448         }
 449
 450         if ( BDB_IDL_IS_RANGE( a ) && BDB_IDL_IS_RANGE(b) ) {
 451                 ids[0] = NOID;
 452                 ids[1] = IDL_MAX( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) );
 453                 ids[2] = IDL_MIN( BDB_IDL_LAST(a), BDB_IDL_FIRST(b) );
 454
 455                 if ( ids[1] == ids[2] ) {
 456                         ids[0] = 1;
 457                 } else if( ids[1] > ids[2] ) {
 458                         ids[0] = 0;
 459                 }
 460                 return 0;
 461         }
 462
 463         if( BDB_IDL_IS_RANGE( a ) ) {
 464                 ID *tmp = a;
 465                 a = b;
 466                 b = tmp;
 467         }
 468
 469         ida = bdb_idl_first( a, &cursora ),
 470         idb = bdb_idl_first( b, &cursorb );
 471
 472         ids[0] = 0;
 473
 474         while( ida != NOID && idb != NOID ) {
 475                 if( ida == idb ) {
 476                         ids[++ids[0]] = ida;
 477                         ida = bdb_idl_next( a, &cursora );
 478                         idb = bdb_idl_next( b, &cursorb );
 479                         if( BDB_IDL_IS_RANGE( b ) && idb < ida ) {
 480                                 if( ida > BDB_IDL_LAST( b ) ) {
 481                                         idb = NOID;
 482                                 } else {
 483                                         idb = ida;
 484                                         cursorb = ida;
 485                                 }
 486                         }
 487                 } else if ( ida < idb ) {
 488                         ida = bdb_idl_next( a, &cursora );
 489                 } else {
 490                         idb = bdb_idl_next( b, &cursorb );
 491                 }
 492         }
 493
 494         return 0;
 495 }
 496
 497
 498 /*
 499  * idl_union - return a union b
 500  */
 501 int
 502 bdb_idl_union(
 503         ID      *a,
 504         ID      *b,
 505         ID *ids )
 506 {
 507         ID ida, idb;
 508         ID cursora = 0, cursorb = 0;
 509
 510         if ( BDB_IDL_IS_ZERO( a ) ) {
 511                 BDB_IDL_CPY( ids, b );
 512                 return 0;
 513         }
 514
 515         if ( BDB_IDL_IS_ZERO( b ) ) {
 516                 BDB_IDL_CPY( ids, a );
 517                 return 0;
 518         }
 519
 520         if ( BDB_IDL_IS_RANGE( a ) || BDB_IDL_IS_RANGE(b) ) {
 521                 ids[0] = NOID;
 522                 ids[1] = IDL_MIN( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) );
 523                 ids[2] = IDL_MAX( BDB_IDL_LAST(a), BDB_IDL_FIRST(b) );
 524                 return 0;
 525         }
 526
 527         ida = bdb_idl_first( a, &cursora );
 528         idb = bdb_idl_first( b, &cursorb );
 529
 530         ids[0] = 0;
 531
 532         while( ida != NOID && idb != NOID ) {
 533                 if( ++ids[0] > BDB_IDL_UM_MAX ) {
 534                         ids[0] = NOID;
 535                         ids[2] = IDL_MAX( BDB_IDL_LAST(a), BDB_IDL_LAST(b) );
 536                         break;
 537                 }
 538
 539                 if ( ida < idb ) {
 540                         ids[ids[0]] = ida;
 541                         ida = bdb_idl_next( a, &cursora );
 542
 543                 } else if ( ida > idb ) {
 544                         ids[ids[0]] = idb;
 545                         idb = bdb_idl_next( b, &cursorb );
 546
 547                 } else {
 548                         ids[ids[0]] = ida;
 549                         ida = bdb_idl_next( a, &cursora );
 550                         idb = bdb_idl_next( b, &cursorb );
 551                 }
 552         }
 553
 554         return 0;
 555 }
 556
 557
 558 #if 0
 559 /*
 560  * bdb_idl_notin - return a intersection ~b (or a minus b)
 561  */
 562 int
 563 bdb_idl_notin(
 564         ID      *a,
 565         ID      *b,
 566         ID *ids )
 567 {
 568         ID ida, idb;
 569         ID cursora = 0, cursorb = 0;
 570
 571         if( BDB_IDL_IS_ZERO( a ) ||
 572                 BDB_IDL_IS_ZERO( b ) ||
 573                 BDB_IDL_IS_RANGE( b ) )
 574         {
 575                 BDB_IDL_CPY( ids, a );
 576                 return 0;
 577         }
 578
 579         if( BDB_IDL_IS_RANGE( a ) ) {
 580                 BDB_IDL_CPY( ids, a );
 581                 return 0;
 582         }
 583
 584         ida = bdb_idl_first( a, &cursora ),
 585         idb = bdb_idl_first( b, &cursorb );
 586
 587         ids[0] = 0;
 588
 589         while( ida != NOID ) {
 590                 if ( idb == NOID ) {
 591                         /* we could shortcut this */
 592                         ids[++ids[0]] = ida;
 593                         ida = bdb_idl_next( a, &cursora );
 594
 595                 } else if ( ida < idb ) {
 596                         ids[++ids[0]] = ida;
 597                         ida = bdb_idl_next( a, &cursora );
 598
 599                 } else if ( ida > idb ) {
 600                         idb = bdb_idl_next( b, &cursorb );
 601
 602                 } else {
 603                         ida = bdb_idl_next( a, &cursora );
 604                         idb = bdb_idl_next( b, &cursorb );
 605                 }
 606         }
 607
 608         return 0;
 609 }
 610 #endif
 611
 612 ID bdb_idl_first( ID *ids, ID *cursor )
 613 {
 614         ID pos;
 615
 616         if ( ids[0] == 0 ) {
 617                 *cursor = NOID;
 618                 return NOID;
 619         }
 620
 621         if ( BDB_IDL_IS_RANGE( ids ) ) {
 622                 if( *cursor < ids[1] ) {
 623                         *cursor = ids[1];
 624                 }
 625                 return *cursor;
 626         }
 627
 628         if ( *cursor == 0 )
 629                 pos = 1;
 630         else
 631                 pos = bdb_idl_search( ids, *cursor );
 632
 633         if( pos > ids[0] ) {
 634                 return NOID;
 635         }
 636
 637         *cursor = pos;
 638         return ids[pos];
 639 }
 640
 641 ID bdb_idl_next( ID *ids, ID *cursor )
 642 {
 643         if ( BDB_IDL_IS_RANGE( ids ) ) {
 644                 if( ids[2] < ++(*cursor) ) {
 645                         return NOID;
 646                 }
 647                 return *cursor;
 648         }
 649
 650         if ( ++(*cursor) <= ids[0] ) {
 651                 return ids[*cursor];
 652         }
 653
 654         return NOID;
 655 }