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