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_insert_key(
 216         BackendDB       *be,
 217         DB                      *db,
 218         DB_TXN          *tid,
 219         DBT                     *key,
 220         ID                      id )
 221 {
 222         int     rc;
 223         ID ids[BDB_IDL_DB_SIZE];
 224         DBT data;
 225
 226         /* for printable keys only */
 227         Debug( LDAP_DEBUG_ARGS,
 228                 "=> bdb_idl_insert_key: %s %ld\n",
 229                 key->data, (long) id, 0 );
 230
 231         assert( id != NOID );
 232
 233         data.data = ids;
 234         data.ulen = sizeof( ids );
 235         data.flags = DB_DBT_USERMEM;
 236
 237         /* fetch the key for read/modify/write */
 238         rc = db->get( db, tid, key, &data, DB_RMW );
 239
 240         if( rc == DB_NOTFOUND ) {
 241                 ids[0] = 1;
 242                 ids[1] = id;
 243                 data.size = 2 * sizeof( ID );
 244
 245         } else if ( rc != 0 ) {
 246                 Debug( LDAP_DEBUG_ANY,
 247                         "=> bdb_idl_insert_key: get failed: %s (%d)\n",
 248                         db_strerror(rc), rc, 0 );
 249                 return rc;
 250
 251         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 252                 /* size not multiple of ID size */
 253                 Debug( LDAP_DEBUG_ANY,
 254                         "=> bdb_idl_insert_key: odd size: expected %ld multiple, got %ld\n",
 255                         (long) sizeof( ID ), (long) data.size, 0 );
 256                 return -1;
 257
 258         } else if ( BDB_IDL_IS_RANGE(ids) ) {
 259                 if( id < ids[1] ) {
 260                         ids[1] = id;
 261                 } else if ( ids[2] > id ) {
 262                         ids[2] = id;
 263                 } else {
 264                         return 0;
 265                 }
 266
 267         } else if ( data.size != (1 + ids[0]) * sizeof( ID ) ) {
 268                 /* size mismatch */
 269                 Debug( LDAP_DEBUG_ANY,
 270                         "=> bdb_idl_insert_key: get size mismatch: expected %ld, got %ld\n",
 271                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 272                 return -1;
 273
 274         } else {
 275                 rc = idl_insert( ids, id );
 276
 277                 if( rc != 0 ) {
 278                         Debug( LDAP_DEBUG_ANY,
 279                                 "=> bdb_idl_insert_key: idl_insert failed (%d)\n",
 280                                 rc, 0, 0 );
 281                         return rc;
 282                 }
 283
 284                 if( BDB_IDL_IS_RANGE( ids ) ) {
 285                         data.size = BDB_IDL_RANGE_SIZE;
 286                 } else {
 287                         data.size = (ids[0]+1) * sizeof( ID );
 288                 }
 289         }
 290
 291         /* store the key */
 292         rc = db->put( db, tid, key, &data, 0 );
 293
 294         if( rc != 0 ) {
 295                 Debug( LDAP_DEBUG_ANY,
 296                         "=> bdb_idl_insert_key: get failed: %s (%d)\n",
 297                         db_strerror(rc), rc, 0 );
 298         }
 299         return rc;
 300 }
 301
 302 int
 303 bdb_idl_delete_key(
 304         BackendDB       *be,
 305         DB                      *db,
 306         DB_TXN          *tid,
 307         DBT                     *key,
 308         ID                      id )
 309 {
 310         int     rc;
 311         ID ids[BDB_IDL_DB_SIZE];
 312         DBT data;
 313
 314         /* for printable keys only */
 315         Debug( LDAP_DEBUG_ARGS,
 316                 "=> bdb_idl_delete_key: %s %ld\n",
 317                 key->data, (long) id, 0 );
 318
 319         assert( id != NOID );
 320
 321         data.data = ids;
 322         data.ulen = sizeof( ids );
 323         data.flags = DB_DBT_USERMEM;
 324
 325         /* fetch the key for read/modify/write */
 326         rc = db->get( db, tid, key, &data, DB_RMW );
 327
 328         if ( rc != 0 ) {
 329                 Debug( LDAP_DEBUG_ANY,
 330                         "=> bdb_idl_delete_key: get failed: %s (%d)\n",
 331                         db_strerror(rc), rc, 0 );
 332                 return rc;
 333
 334         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 335                 /* size not multiple of ID size */
 336                 Debug( LDAP_DEBUG_ANY,
 337                         "=> bdb_idl_delete_key: odd size: expected %ld multiple, got %ld\n",
 338                         (long) sizeof( ID ), (long) data.size, 0 );
 339                 return -1;
 340
 341         } else if ( BDB_IDL_IS_RANGE(ids) ) {
 342                 return 0;
 343
 344         } else if ( data.size != (1 + ids[0]) * sizeof( ID ) ) {
 345                 /* size mismatch */
 346                 Debug( LDAP_DEBUG_ANY,
 347                         "=> bdb_idl_delete_key: get size mismatch: expected %ld, got %ld\n",
 348                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 349                 return -1;
 350
 351         } else {
 352                 rc = idl_delete( ids, id );
 353
 354                 if( rc != 0 ) {
 355                         Debug( LDAP_DEBUG_ANY,
 356                                 "=> bdb_idl_delete_key: idl_delete failed (%d)\n",
 357                                 rc, 0, 0 );
 358                         return rc;
 359                 }
 360
 361                 if( ids[0] == 0 ) {
 362                         /* delete the key */
 363                         rc = db->del( db, tid, key, 0 );
 364                         if( rc != 0 ) {
 365                                 Debug( LDAP_DEBUG_ANY,
 366                                         "=> bdb_idl_delete_key: delete failed: %s (%d)\n",
 367                                         db_strerror(rc), rc, 0 );
 368                         }
 369                         return rc;
 370                 }
 371
 372                 data.size = (ids[0]+1) * sizeof( ID );
 373         }
 374
 375         /* store the key */
 376         rc = db->put( db, tid, key, &data, 0 );
 377
 378         if( rc != 0 ) {
 379                 Debug( LDAP_DEBUG_ANY,
 380                         "=> bdb_idl_delete_key: put failed: %s (%d)\n",
 381                         db_strerror(rc), rc, 0 );
 382         }
 383
 384         return rc;
 385 }
 386
 387
 388 /*
 389  * idl_intersection - return a intersection b
 390  */
 391 int
 392 bdb_idl_intersection(
 393         ID *a,
 394         ID *b,
 395         ID *ids )
 396 {
 397         ID ida, idb;
 398         ID cursora, cursorb;
 399
 400         if ( BDB_IDL_IS_ZERO( a ) || BDB_IDL_IS_ZERO( b ) ) {
 401                 ids[0] = 0;
 402                 return 0;
 403         }
 404
 405         if ( BDB_IDL_IS_RANGE( a ) && BDB_IDL_IS_RANGE(b) ) {
 406                 ids[0] = NOID;
 407                 ids[1] = IDL_MAX( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) );
 408                 ids[2] = IDL_MIN( BDB_IDL_LAST(a), BDB_IDL_FIRST(b) );
 409
 410                 if ( ids[1] == ids[2] ) {
 411                         ids[0] = 1;
 412                 } else if( ids[1] > ids[2] ) {
 413                         ids[0] = 0;
 414                 }
 415                 return 0;
 416         }
 417
 418         if( BDB_IDL_IS_RANGE( a ) ) {
 419                 ID *tmp = a;
 420                 a = b;
 421                 b = tmp;
 422         }
 423
 424         ida = bdb_idl_first( a, &cursora ),
 425         idb = bdb_idl_first( b, &cursorb );
 426
 427         ids[0] = 0;
 428
 429         while( ida != NOID && idb != NOID ) {
 430                 if( ida == idb ) {
 431                         ids[++ids[0]] = ida;
 432                         ida = bdb_idl_next( a, &cursora );
 433                         idb = bdb_idl_next( b, &cursorb );
 434                         if( BDB_IDL_IS_RANGE( b ) && idb < ida ) {
 435                                 if( ida > BDB_IDL_LAST( b ) ) {
 436                                         idb = NOID;
 437                                 } else {
 438                                         idb = ida;
 439                                         cursorb = ida;
 440                                 }
 441                         }
 442                 } else if ( ida < idb ) {
 443                         ida = bdb_idl_next( a, &cursora );
 444                 } else {
 445                         idb = bdb_idl_next( b, &cursorb );
 446                 }
 447         }
 448
 449         return 0;
 450 }
 451
 452
 453 /*
 454  * idl_union - return a union b
 455  */
 456 int
 457 bdb_idl_union(
 458         ID      *a,
 459         ID      *b,
 460         ID *ids )
 461 {
 462         ID ida, idb;
 463         ID cursora, cursorb;
 464
 465         if ( BDB_IDL_IS_ZERO( a ) ) {
 466                 BDB_IDL_CPY( ids, b );
 467                 return 0;
 468         }
 469
 470         if ( BDB_IDL_IS_ZERO( b ) ) {
 471                 BDB_IDL_CPY( ids, a );
 472                 return 0;
 473         }
 474
 475         if ( BDB_IDL_IS_RANGE( a ) || BDB_IDL_IS_RANGE(b) ) {
 476                 ids[0] = NOID;
 477                 ids[1] = IDL_MIN( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) );
 478                 ids[2] = IDL_MAX( BDB_IDL_LAST(a), BDB_IDL_FIRST(b) );
 479                 return 0;
 480         }
 481
 482         ida = bdb_idl_first( a, &cursora ),
 483         idb = bdb_idl_first( b, &cursorb );
 484
 485         ids[0] = 0;
 486
 487         while( ida != NOID && idb != NOID ) {
 488                 if( ++ids[0] > BDB_IDL_MAX ) {
 489                         ids[0] = NOID;
 490                         ids[2] = IDL_MAX( BDB_IDL_LAST(a), BDB_IDL_LAST(b) );
 491                         break;
 492                 }
 493
 494                 if ( ida < idb ) {
 495                         ids[ids[0]] = ida;
 496                         ida = bdb_idl_next( a, &cursora );
 497
 498                 } else if ( ida > idb ) {
 499                         ids[ids[0]] = idb;
 500                         idb = bdb_idl_next( b, &cursorb );
 501
 502                 } else {
 503                         ids[ids[0]] = ida;
 504                         ida = bdb_idl_next( a, &cursora );
 505                         idb = bdb_idl_next( b, &cursorb );
 506                 }
 507         }
 508
 509         return 0;
 510 }
 511
 512
 513 /*
 514  * bdb_idl_notin - return a intersection ~b (or a minus b)
 515  */
 516 int
 517 bdb_idl_notin(
 518         ID      *a,
 519         ID      *b,
 520         ID *ids )
 521 {
 522         ID ida, idb;
 523         ID cursora, cursorb;
 524
 525         if( BDB_IDL_IS_ZERO( a ) ||
 526                 BDB_IDL_IS_ZERO( b ) ||
 527                 BDB_IDL_IS_RANGE( b ) )
 528         {
 529                 BDB_IDL_CPY( ids, a );
 530                 return 0;
 531         }
 532
 533         if( BDB_IDL_IS_RANGE( a ) ) {
 534                 BDB_IDL_CPY( ids, a );
 535                 return 0;
 536         }
 537
 538         ida = bdb_idl_first( a, &cursora ),
 539         idb = bdb_idl_first( b, &cursorb );
 540
 541         ids[0] = 0;
 542
 543         while( ida != NOID ) {
 544                 if ( idb == NOID ) {
 545                         /* we could shortcut this */
 546                         ids[++ids[0]] = ida;
 547                         ida = bdb_idl_next( a, &cursora );
 548
 549                 } else if ( ida < idb ) {
 550                         ids[++ids[0]] = ida;
 551                         ida = bdb_idl_next( a, &cursora );
 552
 553                 } else if ( ida > idb ) {
 554                         idb = bdb_idl_next( b, &cursorb );
 555
 556                 } else {
 557                         ida = bdb_idl_next( a, &cursora );
 558                         idb = bdb_idl_next( b, &cursorb );
 559                 }
 560         }
 561
 562         return 0;
 563 }
 564
 565 ID bdb_idl_first( ID *ids, ID *cursor )
 566 {
 567         ID pos;
 568
 569         if ( ids[0] == 0 ) {
 570                 *cursor = NOID;
 571                 return NOID;
 572         }
 573
 574         if ( BDB_IDL_IS_RANGE( ids ) ) {
 575                 if( *cursor < ids[1] ) {
 576                         *cursor = ids[1];
 577                 }
 578                 return *cursor;
 579         }
 580
 581         pos = bdb_idl_search( ids, *cursor );
 582
 583         if( pos > ids[0] ) {
 584                 return NOID;
 585         }
 586
 587         *cursor = pos;
 588         return ids[pos];
 589 }
 590
 591 ID bdb_idl_next( ID *ids, ID *cursor )
 592 {
 593         if ( BDB_IDL_IS_RANGE( ids ) ) {
 594                 if( ids[2] < ++(*cursor) ) {
 595                         return NOID;
 596                 }
 597                 return *cursor;
 598         }
 599
 600         if ( *cursor < ids[0] ) {
 601                 return ids[(*cursor)++];
 602         }
 603
 604         return NOID;
 605 }
 606