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