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 == -1 ) {
 327                         Debug( LDAP_DEBUG_TRACE, "=> bdb_idl_insert_key: dup\n",
 328                                 0, 0, 0 );
 329                         return 0;
 330                 }
 331                 if( rc != 0 ) {
 332                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 333                                 "idl_insert failed (%d)\n",
 334                                 rc, 0, 0 );
 335
 336                         return rc;
 337                 }
 338
 339                 data.size = BDB_IDL_SIZEOF( ids );
 340         }
 341
 342         /* store the key */
 343         rc = db->put( db, tid, key, &data, 0 );
 344
 345         if( rc != 0 ) {
 346                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
 347                         "put failed: %s (%d)\n",
 348                         db_strerror(rc), rc, 0 );
 349         }
 350         return rc;
 351 }
 352
 353 int
 354 bdb_idl_delete_key(
 355         BackendDB       *be,
 356         DB                      *db,
 357         DB_TXN          *tid,
 358         DBT                     *key,
 359         ID                      id )
 360 {
 361         int     rc;
 362         ID ids[BDB_IDL_DB_SIZE];
 363         DBT data;
 364
 365         /* for printable keys only */
 366         Debug( LDAP_DEBUG_ARGS,
 367                 "=> bdb_idl_delete_key: %s %ld\n",
 368                 (char *)key->data, (long) id, 0 );
 369
 370         assert( id != NOID );
 371
 372         data.data = ids;
 373         data.ulen = sizeof( ids );
 374         data.flags = DB_DBT_USERMEM;
 375
 376         /* fetch the key for read/modify/write */
 377         rc = db->get( db, tid, key, &data, DB_RMW );
 378
 379         if ( rc != 0 ) {
 380                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 381                         "get failed: %s (%d)\n",
 382                         db_strerror(rc), rc, 0 );
 383                 return rc;
 384
 385         } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
 386                 /* size not multiple of ID size */
 387                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 388                         "odd size: expected %ld multiple, got %ld\n",
 389                         (long) sizeof( ID ), (long) data.size, 0 );
 390                 return -1;
 391
 392         } else if ( BDB_IDL_IS_RANGE(ids) ) {
 393                 return 0;
 394
 395         } else if ( data.size != (1 + ids[0]) * sizeof( ID ) ) {
 396                 /* size mismatch */
 397                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 398                         "get size mismatch: expected %ld, got %ld\n",
 399                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
 400                 return -1;
 401
 402         } else {
 403                 rc = idl_delete( ids, id );
 404
 405                 if( rc != 0 ) {
 406                         Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 407                                 "idl_delete failed (%d)\n",
 408                                 rc, 0, 0 );
 409                         return rc;
 410                 }
 411
 412                 if( ids[0] == 0 ) {
 413                         /* delete the key */
 414                         rc = db->del( db, tid, key, 0 );
 415                         if( rc != 0 ) {
 416                                 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
 417                                         "delete failed: %s (%d)\n",
 418                                         db_strerror(rc), rc, 0 );
 419                         }
 420                         return rc;
 421                 }
 422
 423                 data.size = (ids[0]+1) * sizeof( ID );
 424         }
 425
 426         /* store the key */
 427         rc = db->put( db, tid, key, &data, 0 );
 428
 429         if( rc != 0 ) {
 430                 Debug( LDAP_DEBUG_ANY,
 431                         "=> bdb_idl_delete_key: put failed: %s (%d)\n",
 432                         db_strerror(rc), rc, 0 );
 433         }
 434
 435         return rc;
 436 }
 437
 438
 439 /*
 440  * idl_intersection - return a = a intersection b
 441  */
 442 int
 443 bdb_idl_intersection(
 444         ID *a,
 445         ID *b )
 446 {
 447         ID ida, idb;
 448         ID idmax, idmin;
 449         ID cursora = 0, cursorb = 0, cursorc;
 450         int swap = 0;
 451
 452         if ( BDB_IDL_IS_ZERO( a ) || BDB_IDL_IS_ZERO( b ) ) {
 453                 a[0] = 0;
 454                 return 0;
 455         }
 456
 457         idmin = IDL_MAX( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) );
 458         idmax = IDL_MIN( BDB_IDL_LAST(a), BDB_IDL_LAST(b) );
 459         if ( idmin > idmax ) {
 460                 a[0] = 0;
 461                 return 0;
 462         } else if ( idmin == idmax ) {
 463                 a[0] = 1;
 464                 a[1] = idmin;
 465                 return 0;
 466         }
 467
 468         if ( BDB_IDL_IS_RANGE( a ) && BDB_IDL_IS_RANGE(b) ) {
 469                 a[1] = idmin;
 470                 a[2] = idmax;
 471                 return 0;
 472         }
 473
 474         if ( BDB_IDL_IS_RANGE( a ) ) {
 475                 ID *tmp = a;
 476                 a = b;
 477                 b = tmp;
 478                 swap = 1;
 479         }
 480
 481         if ( BDB_IDL_IS_RANGE( b ) && BDB_IDL_FIRST( b ) <= idmin &&
 482                 BDB_IDL_LAST( b ) >= idmax) {
 483                 if (idmax - idmin + 1 == a[0])
 484                 {
 485                         a[0] = NOID;
 486                         a[1] = idmin;
 487                         a[2] = idmax;
 488                 }
 489                 goto done;
 490         }
 491
 492         ida = bdb_idl_first( a, &cursora );
 493         idb = bdb_idl_first( b, &cursorb );
 494         cursorc = 0;
 495
 496         while( ida < idmin )
 497                 ida = bdb_idl_next( a, &cursora );
 498         while( idb < idmin )
 499                 idb = bdb_idl_next( b, &cursorb );
 500
 501         while( ida <= idmax || idb <= idmax ) {
 502                 if( ida == idb ) {
 503                         a[++cursorc] = ida;
 504                         ida = bdb_idl_next( a, &cursora );
 505                         idb = bdb_idl_next( b, &cursorb );
 506                 } else if ( ida < idb ) {
 507                         ida = bdb_idl_next( a, &cursora );
 508                 } else {
 509                         idb = bdb_idl_next( b, &cursorb );
 510                 }
 511         }
 512         a[0] = cursorc;
 513 done:
 514         if (swap)
 515                 BDB_IDL_CPY( b, a );
 516
 517         return 0;
 518 }
 519
 520
 521 /*
 522  * idl_union - return a = a union b
 523  */
 524 int
 525 bdb_idl_union(
 526         ID      *a,
 527         ID      *b )
 528 {
 529         ID ida, idb;
 530         ID cursora = 0, cursorb = 0, cursorc;
 531
 532         if ( BDB_IDL_IS_ZERO( b ) ) {
 533                 return 0;
 534         }
 535
 536         if ( BDB_IDL_IS_ZERO( a ) ) {
 537                 BDB_IDL_CPY( a, b );
 538                 return 0;
 539         }
 540
 541         if ( BDB_IDL_IS_RANGE( a ) || BDB_IDL_IS_RANGE(b) ) {
 542 over:           a[1] = IDL_MIN( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) );
 543                 a[2] = IDL_MAX( BDB_IDL_LAST(a), BDB_IDL_LAST(b) );
 544                 return 0;
 545         }
 546
 547         ida = bdb_idl_first( a, &cursora );
 548         idb = bdb_idl_first( b, &cursorb );
 549
 550         cursorc = b[0];
 551
 552         /* The distinct elements of a are cat'd to b */
 553         while( ida != NOID || idb != NOID ) {
 554                 if ( ida < idb ) {
 555                         if( ++cursorc > BDB_IDL_UM_MAX ) {
 556                                 a[0] = NOID;
 557                                 goto over;
 558                         }
 559                         b[cursorc] = ida;
 560                         ida = bdb_idl_next( a, &cursora );
 561
 562                 } else {
 563                         if ( ida == idb )
 564                                 ida = bdb_idl_next( a, &cursora );
 565                         idb = bdb_idl_next( b, &cursorb );
 566                 }
 567         }
 568
 569         /* b is copied back to a in sorted order */
 570         a[0] = cursorc;
 571         cursora = 1;
 572         cursorb = 1;
 573         cursorc = b[0]+1;
 574         while (cursorb <= b[0] || cursorc <= a[0]) {
 575                 if (cursorc > a[0])
 576                         idb = NOID;
 577                 else
 578                         idb = b[cursorc];
 579                 if (b[cursorb] < idb)
 580                         a[cursora++] = b[cursorb++];
 581                 else {
 582                         a[cursora++] = idb;
 583                         cursorc++;
 584                 }
 585         }
 586
 587         return 0;
 588 }
 589
 590
 591 #if 0
 592 /*
 593  * bdb_idl_notin - return a intersection ~b (or a minus b)
 594  */
 595 int
 596 bdb_idl_notin(
 597         ID      *a,
 598         ID      *b,
 599         ID *ids )
 600 {
 601         ID ida, idb;
 602         ID cursora = 0, cursorb = 0;
 603
 604         if( BDB_IDL_IS_ZERO( a ) ||
 605                 BDB_IDL_IS_ZERO( b ) ||
 606                 BDB_IDL_IS_RANGE( b ) )
 607         {
 608                 BDB_IDL_CPY( ids, a );
 609                 return 0;
 610         }
 611
 612         if( BDB_IDL_IS_RANGE( a ) ) {
 613                 BDB_IDL_CPY( ids, a );
 614                 return 0;
 615         }
 616
 617         ida = bdb_idl_first( a, &cursora ),
 618         idb = bdb_idl_first( b, &cursorb );
 619
 620         ids[0] = 0;
 621
 622         while( ida != NOID ) {
 623                 if ( idb == NOID ) {
 624                         /* we could shortcut this */
 625                         ids[++ids[0]] = ida;
 626                         ida = bdb_idl_next( a, &cursora );
 627
 628                 } else if ( ida < idb ) {
 629                         ids[++ids[0]] = ida;
 630                         ida = bdb_idl_next( a, &cursora );
 631
 632                 } else if ( ida > idb ) {
 633                         idb = bdb_idl_next( b, &cursorb );
 634
 635                 } else {
 636                         ida = bdb_idl_next( a, &cursora );
 637                         idb = bdb_idl_next( b, &cursorb );
 638                 }
 639         }
 640
 641         return 0;
 642 }
 643 #endif
 644
 645 ID bdb_idl_first( ID *ids, ID *cursor )
 646 {
 647         ID pos;
 648
 649         if ( ids[0] == 0 ) {
 650                 *cursor = NOID;
 651                 return NOID;
 652         }
 653
 654         if ( BDB_IDL_IS_RANGE( ids ) ) {
 655                 if( *cursor < ids[1] ) {
 656                         *cursor = ids[1];
 657                 }
 658                 return *cursor;
 659         }
 660
 661         if ( *cursor == 0 )
 662                 pos = 1;
 663         else
 664                 pos = bdb_idl_search( ids, *cursor );
 665
 666         if( pos > ids[0] ) {
 667                 return NOID;
 668         }
 669
 670         *cursor = pos;
 671         return ids[pos];
 672 }
 673
 674 ID bdb_idl_next( ID *ids, ID *cursor )
 675 {
 676         if ( BDB_IDL_IS_RANGE( ids ) ) {
 677                 if( ids[2] < ++(*cursor) ) {
 678                         return NOID;
 679                 }
 680                 return *cursor;
 681         }
 682
 683         if ( ++(*cursor) <= ids[0] ) {
 684                 return ids[*cursor];
 685         }
 686
 687         return NOID;
 688 }