git.sur5r.net Git - openldap/blob - servers/slapd/back-mdb/idl.c

   1 /* idl.c - ldap id list handling routines */
   2 /* $OpenLDAP$ */
   3 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
   4  *
   5  * Copyright 2000-2013 The OpenLDAP Foundation.
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted only as authorized by the OpenLDAP
  10  * Public License.
  11  *
  12  * A copy of this license is available in the file LICENSE in the
  13  * top-level directory of the distribution or, alternatively, at
  14  * <http://www.OpenLDAP.org/license.html>.
  15  */
  16
  17 #include "portable.h"
  18
  19 #include <stdio.h>
  20 #include <ac/string.h>
  21
  22 #include "back-mdb.h"
  23 #include "idl.h"
  24
  25 #define IDL_MAX(x,y)    ( (x) > (y) ? (x) : (y) )
  26 #define IDL_MIN(x,y)    ( (x) < (y) ? (x) : (y) )
  27 #define IDL_CMP(x,y)    ( (x) < (y) ? -1 : (x) > (y) )
  28
  29 #if IDL_DEBUG > 0
  30 static void idl_check( ID *ids )
  31 {
  32         if( MDB_IDL_IS_RANGE( ids ) ) {
  33                 assert( MDB_IDL_RANGE_FIRST(ids) <= MDB_IDL_RANGE_LAST(ids) );
  34         } else {
  35                 ID i;
  36                 for( i=1; i < ids[0]; i++ ) {
  37                         assert( ids[i+1] > ids[i] );
  38                 }
  39         }
  40 }
  41
  42 #if IDL_DEBUG > 1
  43 static void idl_dump( ID *ids )
  44 {
  45         if( MDB_IDL_IS_RANGE( ids ) ) {
  46                 Debug( LDAP_DEBUG_ANY,
  47                         "IDL: range ( %ld - %ld )\n",
  48                         (long) MDB_IDL_RANGE_FIRST( ids ),
  49                         (long) MDB_IDL_RANGE_LAST( ids ) );
  50
  51         } else {
  52                 ID i;
  53                 Debug( LDAP_DEBUG_ANY, "IDL: size %ld", (long) ids[0], 0, 0 );
  54
  55                 for( i=1; i<=ids[0]; i++ ) {
  56                         if( i % 16 == 1 ) {
  57                                 Debug( LDAP_DEBUG_ANY, "\n", 0, 0, 0 );
  58                         }
  59                         Debug( LDAP_DEBUG_ANY, "  %02lx", (long) ids[i], 0, 0 );
  60                 }
  61
  62                 Debug( LDAP_DEBUG_ANY, "\n", 0, 0, 0 );
  63         }
  64
  65         idl_check( ids );
  66 }
  67 #endif /* IDL_DEBUG > 1 */
  68 #endif /* IDL_DEBUG > 0 */
  69
  70 unsigned mdb_idl_search( ID *ids, ID id )
  71 {
  72 #define IDL_BINARY_SEARCH 1
  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 = 1;
  81         int val = 0;
  82         unsigned n = ids[0];
  83
  84 #if IDL_DEBUG > 0
  85         idl_check( ids );
  86 #endif
  87
  88         while( 0 < n ) {
  89                 unsigned pivot = n >> 1;
  90                 cursor = base + pivot + 1;
  91                 val = IDL_CMP( id, ids[cursor] );
  92
  93                 if( val < 0 ) {
  94                         n = pivot;
  95
  96                 } else if ( val > 0 ) {
  97                         base = cursor;
  98                         n -= pivot + 1;
  99
 100                 } else {
 101                         return cursor;
 102                 }
 103         }
 104
 105         if( val > 0 ) {
 106                 ++cursor;
 107         }
 108         return cursor;
 109
 110 #else
 111         /* (reverse) linear search */
 112         int i;
 113
 114 #if IDL_DEBUG > 0
 115         idl_check( ids );
 116 #endif
 117
 118         for( i=ids[0]; i; i-- ) {
 119                 if( id > ids[i] ) {
 120                         break;
 121                 }
 122         }
 123
 124         return i+1;
 125 #endif
 126 }
 127
 128 int mdb_idl_insert( ID *ids, ID id )
 129 {
 130         unsigned x;
 131
 132 #if IDL_DEBUG > 1
 133         Debug( LDAP_DEBUG_ANY, "insert: %04lx at %d\n", (long) id, x, 0 );
 134         idl_dump( ids );
 135 #elif IDL_DEBUG > 0
 136         idl_check( ids );
 137 #endif
 138
 139         if (MDB_IDL_IS_RANGE( ids )) {
 140                 /* if already in range, treat as a dup */
 141                 if (id >= MDB_IDL_RANGE_FIRST(ids) && id <= MDB_IDL_RANGE_LAST(ids))
 142                         return -1;
 143                 if (id < MDB_IDL_RANGE_FIRST(ids))
 144                         ids[1] = id;
 145                 else if (id > MDB_IDL_RANGE_LAST(ids))
 146                         ids[2] = id;
 147                 return 0;
 148         }
 149
 150         x = mdb_idl_search( ids, id );
 151         assert( x > 0 );
 152
 153         if( x < 1 ) {
 154                 /* internal error */
 155                 return -2;
 156         }
 157
 158         if ( x <= ids[0] && ids[x] == id ) {
 159                 /* duplicate */
 160                 return -1;
 161         }
 162
 163         if ( ++ids[0] >= MDB_IDL_DB_MAX ) {
 164                 if( id < ids[1] ) {
 165                         ids[1] = id;
 166                         ids[2] = ids[ids[0]-1];
 167                 } else if ( ids[ids[0]-1] < id ) {
 168                         ids[2] = id;
 169                 } else {
 170                         ids[2] = ids[ids[0]-1];
 171                 }
 172                 ids[0] = NOID;
 173
 174         } else {
 175                 /* insert id */
 176                 AC_MEMCPY( &ids[x+1], &ids[x], (ids[0]-x) * sizeof(ID) );
 177                 ids[x] = id;
 178         }
 179
 180 #if IDL_DEBUG > 1
 181         idl_dump( ids );
 182 #elif IDL_DEBUG > 0
 183         idl_check( ids );
 184 #endif
 185
 186         return 0;
 187 }
 188
 189 static int mdb_idl_delete( ID *ids, ID id )
 190 {
 191         unsigned x;
 192
 193 #if IDL_DEBUG > 1
 194         Debug( LDAP_DEBUG_ANY, "delete: %04lx at %d\n", (long) id, x, 0 );
 195         idl_dump( ids );
 196 #elif IDL_DEBUG > 0
 197         idl_check( ids );
 198 #endif
 199
 200         if (MDB_IDL_IS_RANGE( ids )) {
 201                 /* If deleting a range boundary, adjust */
 202                 if ( ids[1] == id )
 203                         ids[1]++;
 204                 else if ( ids[2] == id )
 205                         ids[2]--;
 206                 /* deleting from inside a range is a no-op */
 207
 208                 /* If the range has collapsed, re-adjust */
 209                 if ( ids[1] > ids[2] )
 210                         ids[0] = 0;
 211                 else if ( ids[1] == ids[2] )
 212                         ids[1] = 1;
 213                 return 0;
 214         }
 215
 216         x = mdb_idl_search( ids, id );
 217         assert( x > 0 );
 218
 219         if( x <= 0 ) {
 220                 /* internal error */
 221                 return -2;
 222         }
 223
 224         if( x > ids[0] || ids[x] != id ) {
 225                 /* not found */
 226                 return -1;
 227
 228         } else if ( --ids[0] == 0 ) {
 229                 if( x != 1 ) {
 230                         return -3;
 231                 }
 232
 233         } else {
 234                 AC_MEMCPY( &ids[x], &ids[x+1], (1+ids[0]-x) * sizeof(ID) );
 235         }
 236
 237 #if IDL_DEBUG > 1
 238         idl_dump( ids );
 239 #elif IDL_DEBUG > 0
 240         idl_check( ids );
 241 #endif
 242
 243         return 0;
 244 }
 245
 246 static char *
 247 mdb_show_key(
 248         char            *buf,
 249         void            *val,
 250         size_t          len )
 251 {
 252         if ( len == 4 /* LUTIL_HASH_BYTES */ ) {
 253                 unsigned char *c = val;
 254                 sprintf( buf, "[%02x%02x%02x%02x]", c[0], c[1], c[2], c[3] );
 255                 return buf;
 256         } else {
 257                 return val;
 258         }
 259 }
 260
 261 int
 262 mdb_idl_fetch_key(
 263         BackendDB       *be,
 264         MDB_txn         *txn,
 265         MDB_dbi         dbi,
 266         MDB_val         *key,
 267         ID                      *ids,
 268         MDB_cursor      **saved_cursor,
 269         int                     get_flag )
 270 {
 271         MDB_val data, key2, *kptr;
 272         MDB_cursor *cursor;
 273         ID *i;
 274         size_t len;
 275         int rc;
 276         MDB_cursor_op opflag;
 277
 278         char keybuf[16];
 279
 280         Debug( LDAP_DEBUG_ARGS,
 281                 "mdb_idl_fetch_key: %s\n",
 282                 mdb_show_key( keybuf, key->mv_data, key->mv_size ), 0, 0 );
 283
 284         assert( ids != NULL );
 285
 286         if ( saved_cursor && *saved_cursor ) {
 287                 opflag = MDB_NEXT;
 288         } else if ( get_flag == LDAP_FILTER_GE ) {
 289                 opflag = MDB_SET_RANGE;
 290         } else if ( get_flag == LDAP_FILTER_LE ) {
 291                 opflag = MDB_FIRST;
 292         } else {
 293                 opflag = MDB_SET;
 294         }
 295
 296         /* If we're not reusing an existing cursor, get a new one */
 297         if( opflag != MDB_NEXT ) {
 298                 rc = mdb_cursor_open( txn, dbi, &cursor );
 299                 if( rc != 0 ) {
 300                         Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
 301                                 "cursor failed: %s (%d)\n", mdb_strerror(rc), rc, 0 );
 302                         return rc;
 303                 }
 304         } else {
 305                 cursor = *saved_cursor;
 306         }
 307
 308         /* If this is a LE lookup, save original key so we can determine
 309          * when to stop. If this is a GE lookup, save the key since it
 310          * will be overwritten.
 311          */
 312         if ( get_flag == LDAP_FILTER_LE || get_flag == LDAP_FILTER_GE ) {
 313                 key2.mv_data = keybuf;
 314                 key2.mv_size = key->mv_size;
 315                 AC_MEMCPY( keybuf, key->mv_data, key->mv_size );
 316                 kptr = &key2;
 317         } else {
 318                 kptr = key;
 319         }
 320         len = key->mv_size;
 321         rc = mdb_cursor_get( cursor, kptr, &data, opflag );
 322
 323         /* skip presence key on range inequality lookups */
 324         while (rc == 0 && kptr->mv_size != len) {
 325                 rc = mdb_cursor_get( cursor, kptr, &data, MDB_NEXT_NODUP );
 326         }
 327         /* If we're doing a LE compare and the new key is greater than
 328          * our search key, we're done
 329          */
 330         if (rc == 0 && get_flag == LDAP_FILTER_LE && memcmp( kptr->mv_data,
 331                 key->mv_data, key->mv_size ) > 0 ) {
 332                 rc = MDB_NOTFOUND;
 333         }
 334         if (rc == 0) {
 335                 i = ids+1;
 336                 rc = mdb_cursor_get( cursor, key, &data, MDB_GET_MULTIPLE );
 337                 while (rc == 0) {
 338                         memcpy( i, data.mv_data, data.mv_size );
 339                         i += data.mv_size / sizeof(ID);
 340                         rc = mdb_cursor_get( cursor, key, &data, MDB_NEXT_MULTIPLE );
 341                 }
 342                 if ( rc == MDB_NOTFOUND ) rc = 0;
 343                 ids[0] = i - &ids[1];
 344                 /* On disk, a range is denoted by 0 in the first element */
 345                 if (ids[1] == 0) {
 346                         if (ids[0] != MDB_IDL_RANGE_SIZE) {
 347                                 Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
 348                                         "range size mismatch: expected %d, got %ld\n",
 349                                         MDB_IDL_RANGE_SIZE, ids[0], 0 );
 350                                 mdb_cursor_close( cursor );
 351                                 return -1;
 352                         }
 353                         MDB_IDL_RANGE( ids, ids[2], ids[3] );
 354                 }
 355                 data.mv_size = MDB_IDL_SIZEOF(ids);
 356         }
 357
 358         if ( saved_cursor && rc == 0 ) {
 359                 if ( !*saved_cursor )
 360                         *saved_cursor = cursor;
 361         }
 362         else
 363                 mdb_cursor_close( cursor );
 364
 365         if( rc == MDB_NOTFOUND ) {
 366                 return rc;
 367
 368         } else if( rc != 0 ) {
 369                 Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
 370                         "get failed: %s (%d)\n",
 371                         mdb_strerror(rc), rc, 0 );
 372                 return rc;
 373
 374         } else if ( data.mv_size == 0 || data.mv_size % sizeof( ID ) ) {
 375                 /* size not multiple of ID size */
 376                 Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
 377                         "odd size: expected %ld multiple, got %ld\n",
 378                         (long) sizeof( ID ), (long) data.mv_size, 0 );
 379                 return -1;
 380
 381         } else if ( data.mv_size != MDB_IDL_SIZEOF(ids) ) {
 382                 /* size mismatch */
 383                 Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
 384                         "get size mismatch: expected %ld, got %ld\n",
 385                         (long) ((1 + ids[0]) * sizeof( ID )), (long) data.mv_size, 0 );
 386                 return -1;
 387         }
 388
 389         return rc;
 390 }
 391
 392 int
 393 mdb_idl_insert_keys(
 394         BackendDB       *be,
 395         MDB_cursor      *cursor,
 396         struct berval *keys,
 397         ID                      id )
 398 {
 399         struct mdb_info *mdb = be->be_private;
 400         MDB_val key, data;
 401         ID lo, hi, *i;
 402         char *err;
 403         int     rc = 0, k;
 404         unsigned int flag = MDB_NODUPDATA;
 405 #ifndef MISALIGNED_OK
 406         int kbuf[2];
 407 #endif
 408
 409         {
 410                 char buf[16];
 411                 Debug( LDAP_DEBUG_ARGS,
 412                         "mdb_idl_insert_keys: %lx %s\n",
 413                         (long) id, mdb_show_key( buf, keys->bv_val, keys->bv_len ), 0 );
 414         }
 415
 416         assert( id != NOID );
 417
 418 #ifndef MISALIGNED_OK
 419         if (keys[0].bv_len & ALIGNER)
 420                 kbuf[1] = 0;
 421 #endif
 422         for ( k=0; keys[k].bv_val; k++ ) {
 423         /* Fetch the first data item for this key, to see if it
 424          * exists and if it's a range.
 425          */
 426 #ifndef MISALIGNED_OK
 427         if (keys[k].bv_len & ALIGNER) {
 428                 key.mv_size = sizeof(kbuf);
 429                 key.mv_data = kbuf;
 430                 memcpy(key.mv_data, keys[k].bv_val, keys[k].bv_len);
 431         } else
 432 #endif
 433         {
 434                 key.mv_size = keys[k].bv_len;
 435                 key.mv_data = keys[k].bv_val;
 436         }
 437         rc = mdb_cursor_get( cursor, &key, &data, MDB_SET );
 438         err = "c_get";
 439         if ( rc == 0 ) {
 440                 i = data.mv_data;
 441                 memcpy(&lo, data.mv_data, sizeof(ID));
 442                 if ( lo != 0 ) {
 443                         /* not a range, count the number of items */
 444                         size_t count;
 445                         rc = mdb_cursor_count( cursor, &count );
 446                         if ( rc != 0 ) {
 447                                 err = "c_count";
 448                                 goto fail;
 449                         }
 450                         if ( count >= MDB_IDL_DB_MAX ) {
 451                         /* No room, convert to a range */
 452                                 lo = *i;
 453                                 rc = mdb_cursor_get( cursor, &key, &data, MDB_LAST_DUP );
 454                                 if ( rc != 0 && rc != MDB_NOTFOUND ) {
 455                                         err = "c_get last_dup";
 456                                         goto fail;
 457                                 }
 458                                 i = data.mv_data;
 459                                 hi = *i;
 460                                 /* Update hi/lo if needed */
 461                                 if ( id < lo ) {
 462                                         lo = id;
 463                                 } else if ( id > hi ) {
 464                                         hi = id;
 465                                 }
 466                                 /* delete the old key */
 467                                 rc = mdb_cursor_del( cursor, MDB_NODUPDATA );
 468                                 if ( rc != 0 ) {
 469                                         err = "c_del dups";
 470                                         goto fail;
 471                                 }
 472                                 /* Store the range */
 473                                 data.mv_size = sizeof(ID);
 474                                 data.mv_data = &id;
 475                                 id = 0;
 476                                 rc = mdb_cursor_put( cursor, &key, &data, 0 );
 477                                 if ( rc != 0 ) {
 478                                         err = "c_put range";
 479                                         goto fail;
 480                                 }
 481                                 id = lo;
 482                                 rc = mdb_cursor_put( cursor, &key, &data, 0 );
 483                                 if ( rc != 0 ) {
 484                                         err = "c_put lo";
 485                                         goto fail;
 486                                 }
 487                                 id = hi;
 488                                 rc = mdb_cursor_put( cursor, &key, &data, 0 );
 489                                 if ( rc != 0 ) {
 490                                         err = "c_put hi";
 491                                         goto fail;
 492                                 }
 493                         } else {
 494                         /* There's room, just store it */
 495                                 if (id == mdb->mi_nextid)
 496                                         flag |= MDB_APPENDDUP;
 497                                 goto put1;
 498                         }
 499                 } else {
 500                         /* It's a range, see if we need to rewrite
 501                          * the boundaries
 502                          */
 503                         lo = i[1];
 504                         hi = i[2];
 505                         if ( id < lo || id > hi ) {
 506                                 /* position on lo */
 507                                 rc = mdb_cursor_get( cursor, &key, &data, MDB_NEXT_DUP );
 508                                 if ( rc != 0 ) {
 509                                         err = "c_get lo";
 510                                         goto fail;
 511                                 }
 512                                 if ( id > hi ) {
 513                                         /* position on hi */
 514                                         rc = mdb_cursor_get( cursor, &key, &data, MDB_NEXT_DUP );
 515                                         if ( rc != 0 ) {
 516                                                 err = "c_get hi";
 517                                                 goto fail;
 518                                         }
 519                                 }
 520                                 data.mv_size = sizeof(ID);
 521                                 data.mv_data = &id;
 522                                 /* Replace the current lo/hi */
 523                                 rc = mdb_cursor_put( cursor, &key, &data, MDB_CURRENT );
 524                                 if ( rc != 0 ) {
 525                                         err = "c_put lo/hi";
 526                                         goto fail;
 527                                 }
 528                         }
 529                 }
 530         } else if ( rc == MDB_NOTFOUND ) {
 531                 flag &= ~MDB_APPENDDUP;
 532 put1:   data.mv_data = &id;
 533                 data.mv_size = sizeof(ID);
 534                 rc = mdb_cursor_put( cursor, &key, &data, flag );
 535                 /* Don't worry if it's already there */
 536                 if ( rc == MDB_KEYEXIST )
 537                         rc = 0;
 538                 if ( rc ) {
 539                         err = "c_put id";
 540                         goto fail;
 541                 }
 542         } else {
 543                 /* initial c_get failed, nothing was done */
 544 fail:
 545                 Debug( LDAP_DEBUG_ANY, "=> mdb_idl_insert_keys: "
 546                         "%s failed: %s (%d)\n", err, mdb_strerror(rc), rc );
 547                 break;
 548         }
 549         }
 550         return rc;
 551 }
 552
 553 int
 554 mdb_idl_delete_keys(
 555         BackendDB       *be,
 556         MDB_cursor      *cursor,
 557         struct berval *keys,
 558         ID                      id )
 559 {
 560         int     rc = 0, k;
 561         MDB_val key, data;
 562         ID lo, hi, tmp, *i;
 563         char *err;
 564 #ifndef MISALIGNED_OK
 565         int kbuf[2];
 566 #endif
 567
 568         {
 569                 char buf[16];
 570                 Debug( LDAP_DEBUG_ARGS,
 571                         "mdb_idl_delete_keys: %lx %s\n",
 572                         (long) id, mdb_show_key( buf, keys->bv_val, keys->bv_len ), 0 );
 573         }
 574         assert( id != NOID );
 575
 576 #ifndef MISALIGNED_OK
 577         if (keys[0].bv_len & ALIGNER)
 578                 kbuf[1] = 0;
 579 #endif
 580         for ( k=0; keys[k].bv_val; k++) {
 581         /* Fetch the first data item for this key, to see if it
 582          * exists and if it's a range.
 583          */
 584 #ifndef MISALIGNED_OK
 585         if (keys[k].bv_len & ALIGNER) {
 586                 key.mv_size = sizeof(kbuf);
 587                 key.mv_data = kbuf;
 588                 memcpy(key.mv_data, keys[k].bv_val, keys[k].bv_len);
 589         } else
 590 #endif
 591         {
 592                 key.mv_size = keys[k].bv_len;
 593                 key.mv_data = keys[k].bv_val;
 594         }
 595         rc = mdb_cursor_get( cursor, &key, &data, MDB_SET );
 596         err = "c_get";
 597         if ( rc == 0 ) {
 598                 memcpy( &tmp, data.mv_data, sizeof(ID) );
 599                 i = data.mv_data;
 600                 if ( tmp != 0 ) {
 601                         /* Not a range, just delete it */
 602                         data.mv_data = &id;
 603                         rc = mdb_cursor_get( cursor, &key, &data, MDB_GET_BOTH );
 604                         if ( rc != 0 ) {
 605                                 err = "c_get id";
 606                                 goto fail;
 607                         }
 608                         rc = mdb_cursor_del( cursor, 0 );
 609                         if ( rc != 0 ) {
 610                                 err = "c_del id";
 611                                 goto fail;
 612                         }
 613                 } else {
 614                         /* It's a range, see if we need to rewrite
 615                          * the boundaries
 616                          */
 617                         lo = i[1];
 618                         hi = i[2];
 619                         if ( id == lo || id == hi ) {
 620                                 ID lo2 = lo, hi2 = hi;
 621                                 if ( id == lo ) {
 622                                         lo2++;
 623                                 } else if ( id == hi ) {
 624                                         hi2--;
 625                                 }
 626                                 if ( lo2 >= hi2 ) {
 627                                 /* The range has collapsed... */
 628                                         rc = mdb_cursor_del( cursor, MDB_NODUPDATA );
 629                                         if ( rc != 0 ) {
 630                                                 err = "c_del dup";
 631                                                 goto fail;
 632                                         }
 633                                 } else {
 634                                         /* position on lo */
 635                                         rc = mdb_cursor_get( cursor, &key, &data, MDB_NEXT_DUP );
 636                                         if ( id == lo )
 637                                                 data.mv_data = &lo2;
 638                                         else {
 639                                                 /* position on hi */
 640                                                 rc = mdb_cursor_get( cursor, &key, &data, MDB_NEXT_DUP );
 641                                                 data.mv_data = &hi2;
 642                                         }
 643                                         /* Replace the current lo/hi */
 644                                         data.mv_size = sizeof(ID);
 645                                         rc = mdb_cursor_put( cursor, &key, &data, MDB_CURRENT );
 646                                         if ( rc != 0 ) {
 647                                                 err = "c_put lo/hi";
 648                                                 goto fail;
 649                                         }
 650                                 }
 651                         }
 652                 }
 653         } else {
 654                 /* initial c_get failed, nothing was done */
 655 fail:
 656                 if ( rc == MDB_NOTFOUND )
 657                         rc = 0;
 658                 if ( rc ) {
 659                         Debug( LDAP_DEBUG_ANY, "=> mdb_idl_delete_key: "
 660                                 "%s failed: %s (%d)\n", err, mdb_strerror(rc), rc );
 661                         break;
 662                 }
 663         }
 664         }
 665         return rc;
 666 }
 667
 668
 669 /*
 670  * idl_intersection - return a = a intersection b
 671  */
 672 int
 673 mdb_idl_intersection(
 674         ID *a,
 675         ID *b )
 676 {
 677         ID ida, idb;
 678         ID idmax, idmin;
 679         ID cursora = 0, cursorb = 0, cursorc;
 680         int swap = 0;
 681
 682         if ( MDB_IDL_IS_ZERO( a ) || MDB_IDL_IS_ZERO( b ) ) {
 683                 a[0] = 0;
 684                 return 0;
 685         }
 686
 687         idmin = IDL_MAX( MDB_IDL_FIRST(a), MDB_IDL_FIRST(b) );
 688         idmax = IDL_MIN( MDB_IDL_LAST(a), MDB_IDL_LAST(b) );
 689         if ( idmin > idmax ) {
 690                 a[0] = 0;
 691                 return 0;
 692         } else if ( idmin == idmax ) {
 693                 a[0] = 1;
 694                 a[1] = idmin;
 695                 return 0;
 696         }
 697
 698         if ( MDB_IDL_IS_RANGE( a ) ) {
 699                 if ( MDB_IDL_IS_RANGE(b) ) {
 700                 /* If both are ranges, just shrink the boundaries */
 701                         a[1] = idmin;
 702                         a[2] = idmax;
 703                         return 0;
 704                 } else {
 705                 /* Else swap so that b is the range, a is a list */
 706                         ID *tmp = a;
 707                         a = b;
 708                         b = tmp;
 709                         swap = 1;
 710                 }
 711         }
 712
 713         /* If a range completely covers the list, the result is
 714          * just the list. If idmin to idmax is contiguous, just
 715          * turn it into a range.
 716          */
 717         if ( MDB_IDL_IS_RANGE( b )
 718                 && MDB_IDL_RANGE_FIRST( b ) <= MDB_IDL_FIRST( a )
 719                 && MDB_IDL_RANGE_LAST( b ) >= MDB_IDL_LLAST( a ) ) {
 720                 if (idmax - idmin + 1 == a[0])
 721                 {
 722                         a[0] = NOID;
 723                         a[1] = idmin;
 724                         a[2] = idmax;
 725                 }
 726                 goto done;
 727         }
 728
 729         /* Fine, do the intersection one element at a time.
 730          * First advance to idmin in both IDLs.
 731          */
 732         cursora = cursorb = idmin;
 733         ida = mdb_idl_first( a, &cursora );
 734         idb = mdb_idl_first( b, &cursorb );
 735         cursorc = 0;
 736
 737         while( ida <= idmax || idb <= idmax ) {
 738                 if( ida == idb ) {
 739                         a[++cursorc] = ida;
 740                         ida = mdb_idl_next( a, &cursora );
 741                         idb = mdb_idl_next( b, &cursorb );
 742                 } else if ( ida < idb ) {
 743                         ida = mdb_idl_next( a, &cursora );
 744                 } else {
 745                         idb = mdb_idl_next( b, &cursorb );
 746                 }
 747         }
 748         a[0] = cursorc;
 749 done:
 750         if (swap)
 751                 MDB_IDL_CPY( b, a );
 752
 753         return 0;
 754 }
 755
 756
 757 /*
 758  * idl_union - return a = a union b
 759  */
 760 int
 761 mdb_idl_union(
 762         ID      *a,
 763         ID      *b )
 764 {
 765         ID ida, idb;
 766         ID cursora = 0, cursorb = 0, cursorc;
 767
 768         if ( MDB_IDL_IS_ZERO( b ) ) {
 769                 return 0;
 770         }
 771
 772         if ( MDB_IDL_IS_ZERO( a ) ) {
 773                 MDB_IDL_CPY( a, b );
 774                 return 0;
 775         }
 776
 777         if ( MDB_IDL_IS_RANGE( a ) || MDB_IDL_IS_RANGE(b) ) {
 778 over:           ida = IDL_MIN( MDB_IDL_FIRST(a), MDB_IDL_FIRST(b) );
 779                 idb = IDL_MAX( MDB_IDL_LAST(a), MDB_IDL_LAST(b) );
 780                 a[0] = NOID;
 781                 a[1] = ida;
 782                 a[2] = idb;
 783                 return 0;
 784         }
 785
 786         ida = mdb_idl_first( a, &cursora );
 787         idb = mdb_idl_first( b, &cursorb );
 788
 789         cursorc = b[0];
 790
 791         /* The distinct elements of a are cat'd to b */
 792         while( ida != NOID || idb != NOID ) {
 793                 if ( ida < idb ) {
 794                         if( ++cursorc > MDB_IDL_UM_MAX ) {
 795                                 goto over;
 796                         }
 797                         b[cursorc] = ida;
 798                         ida = mdb_idl_next( a, &cursora );
 799
 800                 } else {
 801                         if ( ida == idb )
 802                                 ida = mdb_idl_next( a, &cursora );
 803                         idb = mdb_idl_next( b, &cursorb );
 804                 }
 805         }
 806
 807         /* b is copied back to a in sorted order */
 808         a[0] = cursorc;
 809         cursora = 1;
 810         cursorb = 1;
 811         cursorc = b[0]+1;
 812         while (cursorb <= b[0] || cursorc <= a[0]) {
 813                 if (cursorc > a[0])
 814                         idb = NOID;
 815                 else
 816                         idb = b[cursorc];
 817                 if (cursorb <= b[0] && b[cursorb] < idb)
 818                         a[cursora++] = b[cursorb++];
 819                 else {
 820                         a[cursora++] = idb;
 821                         cursorc++;
 822                 }
 823         }
 824
 825         return 0;
 826 }
 827
 828
 829 #if 0
 830 /*
 831  * mdb_idl_notin - return a intersection ~b (or a minus b)
 832  */
 833 int
 834 mdb_idl_notin(
 835         ID      *a,
 836         ID      *b,
 837         ID *ids )
 838 {
 839         ID ida, idb;
 840         ID cursora = 0, cursorb = 0;
 841
 842         if( MDB_IDL_IS_ZERO( a ) ||
 843                 MDB_IDL_IS_ZERO( b ) ||
 844                 MDB_IDL_IS_RANGE( b ) )
 845         {
 846                 MDB_IDL_CPY( ids, a );
 847                 return 0;
 848         }
 849
 850         if( MDB_IDL_IS_RANGE( a ) ) {
 851                 MDB_IDL_CPY( ids, a );
 852                 return 0;
 853         }
 854
 855         ida = mdb_idl_first( a, &cursora ),
 856         idb = mdb_idl_first( b, &cursorb );
 857
 858         ids[0] = 0;
 859
 860         while( ida != NOID ) {
 861                 if ( idb == NOID ) {
 862                         /* we could shortcut this */
 863                         ids[++ids[0]] = ida;
 864                         ida = mdb_idl_next( a, &cursora );
 865
 866                 } else if ( ida < idb ) {
 867                         ids[++ids[0]] = ida;
 868                         ida = mdb_idl_next( a, &cursora );
 869
 870                 } else if ( ida > idb ) {
 871                         idb = mdb_idl_next( b, &cursorb );
 872
 873                 } else {
 874                         ida = mdb_idl_next( a, &cursora );
 875                         idb = mdb_idl_next( b, &cursorb );
 876                 }
 877         }
 878
 879         return 0;
 880 }
 881 #endif
 882
 883 ID mdb_idl_first( ID *ids, ID *cursor )
 884 {
 885         ID pos;
 886
 887         if ( ids[0] == 0 ) {
 888                 *cursor = NOID;
 889                 return NOID;
 890         }
 891
 892         if ( MDB_IDL_IS_RANGE( ids ) ) {
 893                 if( *cursor < ids[1] ) {
 894                         *cursor = ids[1];
 895                 }
 896                 return *cursor;
 897         }
 898
 899         if ( *cursor == 0 )
 900                 pos = 1;
 901         else
 902                 pos = mdb_idl_search( ids, *cursor );
 903
 904         if( pos > ids[0] ) {
 905                 return NOID;
 906         }
 907
 908         *cursor = pos;
 909         return ids[pos];
 910 }
 911
 912 ID mdb_idl_next( ID *ids, ID *cursor )
 913 {
 914         if ( MDB_IDL_IS_RANGE( ids ) ) {
 915                 if( ids[2] < ++(*cursor) ) {
 916                         return NOID;
 917                 }
 918                 return *cursor;
 919         }
 920
 921         if ( ++(*cursor) <= ids[0] ) {
 922                 return ids[*cursor];
 923         }
 924
 925         return NOID;
 926 }
 927
 928 /* Add one ID to an unsorted list. We ensure that the first element is the
 929  * minimum and the last element is the maximum, for fast range compaction.
 930  *   this means IDLs up to length 3 are always sorted...
 931  */
 932 int mdb_idl_append_one( ID *ids, ID id )
 933 {
 934         if (MDB_IDL_IS_RANGE( ids )) {
 935                 /* if already in range, treat as a dup */
 936                 if (id >= MDB_IDL_RANGE_FIRST(ids) && id <= MDB_IDL_RANGE_LAST(ids))
 937                         return -1;
 938                 if (id < MDB_IDL_RANGE_FIRST(ids))
 939                         ids[1] = id;
 940                 else if (id > MDB_IDL_RANGE_LAST(ids))
 941                         ids[2] = id;
 942                 return 0;
 943         }
 944         if ( ids[0] ) {
 945                 ID tmp;
 946
 947                 if (id < ids[1]) {
 948                         tmp = ids[1];
 949                         ids[1] = id;
 950                         id = tmp;
 951                 }
 952                 if ( ids[0] > 1 && id < ids[ids[0]] ) {
 953                         tmp = ids[ids[0]];
 954                         ids[ids[0]] = id;
 955                         id = tmp;
 956                 }
 957         }
 958         ids[0]++;
 959         if ( ids[0] >= MDB_IDL_UM_MAX ) {
 960                 ids[0] = NOID;
 961                 ids[2] = id;
 962         } else {
 963                 ids[ids[0]] = id;
 964         }
 965         return 0;
 966 }
 967
 968 /* Append sorted list b to sorted list a. The result is unsorted but
 969  * a[1] is the min of the result and a[a[0]] is the max.
 970  */
 971 int mdb_idl_append( ID *a, ID *b )
 972 {
 973         ID ida, idb, tmp, swap = 0;
 974
 975         if ( MDB_IDL_IS_ZERO( b ) ) {
 976                 return 0;
 977         }
 978
 979         if ( MDB_IDL_IS_ZERO( a ) ) {
 980                 MDB_IDL_CPY( a, b );
 981                 return 0;
 982         }
 983
 984         ida = MDB_IDL_LAST( a );
 985         idb = MDB_IDL_LAST( b );
 986         if ( MDB_IDL_IS_RANGE( a ) || MDB_IDL_IS_RANGE(b) ||
 987                 a[0] + b[0] >= MDB_IDL_UM_MAX ) {
 988                 a[2] = IDL_MAX( ida, idb );
 989                 a[1] = IDL_MIN( a[1], b[1] );
 990                 a[0] = NOID;
 991                 return 0;
 992         }
 993
 994         if ( b[0] > 1 && ida > idb ) {
 995                 swap = idb;
 996                 a[a[0]] = idb;
 997                 b[b[0]] = ida;
 998         }
 999
1000         if ( b[1] < a[1] ) {
1001                 tmp = a[1];
1002                 a[1] = b[1];
1003         } else {
1004                 tmp = b[1];
1005         }
1006         a[0]++;
1007         a[a[0]] = tmp;
1008
1009         if ( b[0] > 1 ) {
1010                 int i = b[0] - 1;
1011                 AC_MEMCPY(a+a[0]+1, b+2, i * sizeof(ID));
1012                 a[0] += i;
1013         }
1014         if ( swap ) {
1015                 b[b[0]] = swap;
1016         }
1017         return 0;
1018 }
1019
1020 #if 1
1021
1022 /* Quicksort + Insertion sort for small arrays */
1023
1024 #define SMALL   8
1025 #define SWAP(a,b)       itmp=(a);(a)=(b);(b)=itmp
1026
1027 void
1028 mdb_idl_sort( ID *ids, ID *tmp )
1029 {
1030         int *istack = (int *)tmp; /* Private stack, not used by caller */
1031         int i,j,k,l,ir,jstack;
1032         ID a, itmp;
1033
1034         if ( MDB_IDL_IS_RANGE( ids ))
1035                 return;
1036
1037         ir = ids[0];
1038         l = 1;
1039         jstack = 0;
1040         for(;;) {
1041                 if (ir - l < SMALL) {   /* Insertion sort */
1042                         for (j=l+1;j<=ir;j++) {
1043                                 a = ids[j];
1044                                 for (i=j-1;i>=1;i--) {
1045                                         if (ids[i] <= a) break;
1046                                         ids[i+1] = ids[i];
1047                                 }
1048                                 ids[i+1] = a;
1049                         }
1050                         if (jstack == 0) break;
1051                         ir = istack[jstack--];
1052                         l = istack[jstack--];
1053                 } else {
1054                         k = (l + ir) >> 1;      /* Choose median of left, center, right */
1055                         SWAP(ids[k], ids[l+1]);
1056                         if (ids[l] > ids[ir]) {
1057                                 SWAP(ids[l], ids[ir]);
1058                         }
1059                         if (ids[l+1] > ids[ir]) {
1060                                 SWAP(ids[l+1], ids[ir]);
1061                         }
1062                         if (ids[l] > ids[l+1]) {
1063                                 SWAP(ids[l], ids[l+1]);
1064                         }
1065                         i = l+1;
1066                         j = ir;
1067                         a = ids[l+1];
1068                         for(;;) {
1069                                 do i++; while(ids[i] < a);
1070                                 do j--; while(ids[j] > a);
1071                                 if (j < i) break;
1072                                 SWAP(ids[i],ids[j]);
1073                         }
1074                         ids[l+1] = ids[j];
1075                         ids[j] = a;
1076                         jstack += 2;
1077                         if (ir-i+1 >= j-l) {
1078                                 istack[jstack] = ir;
1079                                 istack[jstack-1] = i;
1080                                 ir = j-1;
1081                         } else {
1082                                 istack[jstack] = j-1;
1083                                 istack[jstack-1] = l;
1084                                 l = i;
1085                         }
1086                 }
1087         }
1088 }
1089
1090 #else
1091
1092 /* 8 bit Radix sort + insertion sort
1093  *
1094  * based on code from http://www.cubic.org/docs/radix.htm
1095  * with improvements by ebackes@symas.com and hyc@symas.com
1096  *
1097  * This code is O(n) but has a relatively high constant factor. For lists
1098  * up to ~50 Quicksort is slightly faster; up to ~100 they are even.
1099  * Much faster than quicksort for lists longer than ~100. Insertion
1100  * sort is actually superior for lists <50.
1101  */
1102
1103 #define BUCKETS (1<<8)
1104 #define SMALL   50
1105
1106 void
1107 mdb_idl_sort( ID *ids, ID *tmp )
1108 {
1109         int count, soft_limit, phase = 0, size = ids[0];
1110         ID *idls[2];
1111         unsigned char *maxv = (unsigned char *)&ids[size];
1112
1113         if ( MDB_IDL_IS_RANGE( ids ))
1114                 return;
1115
1116         /* Use insertion sort for small lists */
1117         if ( size <= SMALL ) {
1118                 int i,j;
1119                 ID a;
1120
1121                 for (j=1;j<=size;j++) {
1122                         a = ids[j];
1123                         for (i=j-1;i>=1;i--) {
1124                                 if (ids[i] <= a) break;
1125                                 ids[i+1] = ids[i];
1126                         }
1127                         ids[i+1] = a;
1128                 }
1129                 return;
1130         }
1131
1132         tmp[0] = size;
1133         idls[0] = ids;
1134         idls[1] = tmp;
1135
1136 #if BYTE_ORDER == BIG_ENDIAN
1137     for (soft_limit = 0; !maxv[soft_limit]; soft_limit++);
1138 #else
1139     for (soft_limit = sizeof(ID)-1; !maxv[soft_limit]; soft_limit--);
1140 #endif
1141
1142         for (
1143 #if BYTE_ORDER == BIG_ENDIAN
1144         count = sizeof(ID)-1; count >= soft_limit; --count
1145 #else
1146         count = 0; count <= soft_limit; ++count
1147 #endif
1148         ) {
1149                 unsigned int num[BUCKETS], * np, n, sum;
1150                 int i;
1151         ID *sp, *source, *dest;
1152         unsigned char *bp, *source_start;
1153
1154                 source = idls[phase]+1;
1155                 dest = idls[phase^1]+1;
1156                 source_start =  ((unsigned char *) source) + count;
1157
1158         np = num;
1159         for ( i = BUCKETS; i > 0; --i ) *np++ = 0;
1160
1161                 /* count occurences of every byte value */
1162                 bp = source_start;
1163         for ( i = size; i > 0; --i, bp += sizeof(ID) )
1164                                 num[*bp]++;
1165
1166                 /* transform count into index by summing elements and storing
1167                  * into same array
1168                  */
1169         sum = 0;
1170         np = num;
1171         for ( i = BUCKETS; i > 0; --i ) {
1172                 n = *np;
1173                 *np++ = sum;
1174                 sum += n;
1175         }
1176
1177                 /* fill dest with the right values in the right place */
1178                 bp = source_start;
1179         sp = source;
1180         for ( i = size; i > 0; --i, bp += sizeof(ID) ) {
1181                 np = num + *bp;
1182                 dest[*np] = *sp++;
1183                 ++(*np);
1184         }
1185                 phase ^= 1;
1186         }
1187
1188         /* copy back from temp if needed */
1189         if ( phase ) {
1190                 ids++; tmp++;
1191                 for ( count = 0; count < size; ++count )
1192                         *ids++ = *tmp++;
1193         }
1194 }
1195 #endif  /* Quick vs Radix */
1196
1197 unsigned mdb_id2l_search( ID2L ids, ID id )
1198 {
1199         /*
1200          * binary search of id in ids
1201          * if found, returns position of id
1202          * if not found, returns first position greater than id
1203          */
1204         unsigned base = 0;
1205         unsigned cursor = 1;
1206         int val = 0;
1207         unsigned n = ids[0].mid;
1208
1209         while( 0 < n ) {
1210                 unsigned pivot = n >> 1;
1211                 cursor = base + pivot + 1;
1212                 val = IDL_CMP( id, ids[cursor].mid );
1213
1214                 if( val < 0 ) {
1215                         n = pivot;
1216
1217                 } else if ( val > 0 ) {
1218                         base = cursor;
1219                         n -= pivot + 1;
1220
1221                 } else {
1222                         return cursor;
1223                 }
1224         }
1225
1226         if( val > 0 ) {
1227                 ++cursor;
1228         }
1229         return cursor;
1230 }
1231
1232 int mdb_id2l_insert( ID2L ids, ID2 *id )
1233 {
1234         unsigned x, i;
1235
1236         x = mdb_id2l_search( ids, id->mid );
1237         assert( x > 0 );
1238
1239         if( x < 1 ) {
1240                 /* internal error */
1241                 return -2;
1242         }
1243
1244         if ( x <= ids[0].mid && ids[x].mid == id->mid ) {
1245                 /* duplicate */
1246                 return -1;
1247         }
1248
1249         if ( ids[0].mid >= MDB_IDL_UM_MAX ) {
1250                 /* too big */
1251                 return -2;
1252
1253         } else {
1254                 /* insert id */
1255                 ids[0].mid++;
1256                 for (i=ids[0].mid; i>x; i--)
1257                         ids[i] = ids[i-1];
1258                 ids[x] = *id;
1259         }
1260
1261         return 0;
1262 }