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