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