Back to index

openldap  2.4.31
idl.c
Go to the documentation of this file.
00001 /* idl.c - ldap id list handling routines */
00002 /* $OpenLDAP$ */
00003 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
00004  *
00005  * Copyright 2000-2012 The OpenLDAP Foundation.
00006  * All rights reserved.
00007  *
00008  * Redistribution and use in source and binary forms, with or without
00009  * modification, are permitted only as authorized by the OpenLDAP
00010  * Public License.
00011  *
00012  * A copy of this license is available in the file LICENSE in the
00013  * top-level directory of the distribution or, alternatively, at
00014  * <http://www.OpenLDAP.org/license.html>.
00015  */
00016 
00017 #include "portable.h"
00018 
00019 #include <stdio.h>
00020 #include <ac/string.h>
00021 
00022 #include "back-mdb.h"
00023 #include "idl.h"
00024 
00025 #define IDL_MAX(x,y) ( (x) > (y) ? (x) : (y) )
00026 #define IDL_MIN(x,y) ( (x) < (y) ? (x) : (y) )
00027 #define IDL_CMP(x,y) ( (x) < (y) ? -1 : (x) > (y) )
00028 
00029 #if IDL_DEBUG > 0
00030 static void idl_check( ID *ids )
00031 {
00032        if( MDB_IDL_IS_RANGE( ids ) ) {
00033               assert( MDB_IDL_RANGE_FIRST(ids) <= MDB_IDL_RANGE_LAST(ids) );
00034        } else {
00035               ID i;
00036               for( i=1; i < ids[0]; i++ ) {
00037                      assert( ids[i+1] > ids[i] );
00038               }
00039        }
00040 }
00041 
00042 #if IDL_DEBUG > 1
00043 static void idl_dump( ID *ids )
00044 {
00045        if( MDB_IDL_IS_RANGE( ids ) ) {
00046               Debug( LDAP_DEBUG_ANY,
00047                      "IDL: range ( %ld - %ld )\n",
00048                      (long) MDB_IDL_RANGE_FIRST( ids ),
00049                      (long) MDB_IDL_RANGE_LAST( ids ) );
00050 
00051        } else {
00052               ID i;
00053               Debug( LDAP_DEBUG_ANY, "IDL: size %ld", (long) ids[0], 0, 0 );
00054 
00055               for( i=1; i<=ids[0]; i++ ) {
00056                      if( i % 16 == 1 ) {
00057                             Debug( LDAP_DEBUG_ANY, "\n", 0, 0, 0 );
00058                      }
00059                      Debug( LDAP_DEBUG_ANY, "  %02lx", (long) ids[i], 0, 0 );
00060               }
00061 
00062               Debug( LDAP_DEBUG_ANY, "\n", 0, 0, 0 );
00063        }
00064 
00065        idl_check( ids );
00066 }
00067 #endif /* IDL_DEBUG > 1 */
00068 #endif /* IDL_DEBUG > 0 */
00069 
00070 unsigned mdb_idl_search( ID *ids, ID id )
00071 {
00072 #define IDL_BINARY_SEARCH 1
00073 #ifdef IDL_BINARY_SEARCH
00074        /*
00075         * binary search of id in ids
00076         * if found, returns position of id
00077         * if not found, returns first postion greater than id
00078         */
00079        unsigned base = 0;
00080        unsigned cursor = 1;
00081        int val = 0;
00082        unsigned n = ids[0];
00083 
00084 #if IDL_DEBUG > 0
00085        idl_check( ids );
00086 #endif
00087 
00088        while( 0 < n ) {
00089               unsigned pivot = n >> 1;
00090               cursor = base + pivot + 1;
00091               val = IDL_CMP( id, ids[cursor] );
00092 
00093               if( val < 0 ) {
00094                      n = pivot;
00095 
00096               } else if ( val > 0 ) {
00097                      base = cursor;
00098                      n -= pivot + 1;
00099 
00100               } else {
00101                      return cursor;
00102               }
00103        }
00104        
00105        if( val > 0 ) {
00106               ++cursor;
00107        }
00108        return cursor;
00109 
00110 #else
00111        /* (reverse) linear search */
00112        int i;
00113 
00114 #if IDL_DEBUG > 0
00115        idl_check( ids );
00116 #endif
00117 
00118        for( i=ids[0]; i; i-- ) {
00119               if( id > ids[i] ) {
00120                      break;
00121               }
00122        }
00123 
00124        return i+1;
00125 #endif
00126 }
00127 
00128 int mdb_idl_insert( ID *ids, ID id )
00129 {
00130        unsigned x;
00131 
00132 #if IDL_DEBUG > 1
00133        Debug( LDAP_DEBUG_ANY, "insert: %04lx at %d\n", (long) id, x, 0 );
00134        idl_dump( ids );
00135 #elif IDL_DEBUG > 0
00136        idl_check( ids );
00137 #endif
00138 
00139        if (MDB_IDL_IS_RANGE( ids )) {
00140               /* if already in range, treat as a dup */
00141               if (id >= MDB_IDL_RANGE_FIRST(ids) && id <= MDB_IDL_RANGE_LAST(ids))
00142                      return -1;
00143               if (id < MDB_IDL_RANGE_FIRST(ids))
00144                      ids[1] = id;
00145               else if (id > MDB_IDL_RANGE_LAST(ids))
00146                      ids[2] = id;
00147               return 0;
00148        }
00149 
00150        x = mdb_idl_search( ids, id );
00151        assert( x > 0 );
00152 
00153        if( x < 1 ) {
00154               /* internal error */
00155               return -2;
00156        }
00157 
00158        if ( x <= ids[0] && ids[x] == id ) {
00159               /* duplicate */
00160               return -1;
00161        }
00162 
00163        if ( ++ids[0] >= MDB_IDL_DB_MAX ) {
00164               if( id < ids[1] ) {
00165                      ids[1] = id;
00166                      ids[2] = ids[ids[0]-1];
00167               } else if ( ids[ids[0]-1] < id ) {
00168                      ids[2] = id;
00169               } else {
00170                      ids[2] = ids[ids[0]-1];
00171               }
00172               ids[0] = NOID;
00173        
00174        } else {
00175               /* insert id */
00176               AC_MEMCPY( &ids[x+1], &ids[x], (ids[0]-x) * sizeof(ID) );
00177               ids[x] = id;
00178        }
00179 
00180 #if IDL_DEBUG > 1
00181        idl_dump( ids );
00182 #elif IDL_DEBUG > 0
00183        idl_check( ids );
00184 #endif
00185 
00186        return 0;
00187 }
00188 
00189 static int mdb_idl_delete( ID *ids, ID id )
00190 {
00191        unsigned x;
00192 
00193 #if IDL_DEBUG > 1
00194        Debug( LDAP_DEBUG_ANY, "delete: %04lx at %d\n", (long) id, x, 0 );
00195        idl_dump( ids );
00196 #elif IDL_DEBUG > 0
00197        idl_check( ids );
00198 #endif
00199 
00200        if (MDB_IDL_IS_RANGE( ids )) {
00201               /* If deleting a range boundary, adjust */
00202               if ( ids[1] == id )
00203                      ids[1]++;
00204               else if ( ids[2] == id )
00205                      ids[2]--;
00206               /* deleting from inside a range is a no-op */
00207 
00208               /* If the range has collapsed, re-adjust */
00209               if ( ids[1] > ids[2] )
00210                      ids[0] = 0;
00211               else if ( ids[1] == ids[2] )
00212                      ids[1] = 1;
00213               return 0;
00214        }
00215 
00216        x = mdb_idl_search( ids, id );
00217        assert( x > 0 );
00218 
00219        if( x <= 0 ) {
00220               /* internal error */
00221               return -2;
00222        }
00223 
00224        if( x > ids[0] || ids[x] != id ) {
00225               /* not found */
00226               return -1;
00227 
00228        } else if ( --ids[0] == 0 ) {
00229               if( x != 1 ) {
00230                      return -3;
00231               }
00232 
00233        } else {
00234               AC_MEMCPY( &ids[x], &ids[x+1], (1+ids[0]-x) * sizeof(ID) );
00235        }
00236 
00237 #if IDL_DEBUG > 1
00238        idl_dump( ids );
00239 #elif IDL_DEBUG > 0
00240        idl_check( ids );
00241 #endif
00242 
00243        return 0;
00244 }
00245 
00246 static char *
00247 mdb_show_key(
00248        char          *buf,
00249        void          *val,
00250        size_t        len )
00251 {
00252        if ( len == 4 /* LUTIL_HASH_BYTES */ ) {
00253               unsigned char *c = val;
00254               sprintf( buf, "[%02x%02x%02x%02x]", c[0], c[1], c[2], c[3] );
00255               return buf;
00256        } else {
00257               return val;
00258        }
00259 }
00260 
00261 int
00262 mdb_idl_fetch_key(
00263        BackendDB     *be,
00264        MDB_txn              *txn,
00265        MDB_dbi              dbi,
00266        MDB_val              *key,
00267        ID                   *ids,
00268        MDB_cursor    **saved_cursor,
00269        int                  get_flag )
00270 {
00271        MDB_val data, key2, *kptr;
00272        MDB_cursor *cursor;
00273        ID *i;
00274        size_t len;
00275        int rc;
00276        MDB_cursor_op opflag;
00277 
00278        char keybuf[16];
00279 
00280        Debug( LDAP_DEBUG_ARGS,
00281               "mdb_idl_fetch_key: %s\n", 
00282               mdb_show_key( keybuf, key->mv_data, key->mv_size ), 0, 0 );
00283 
00284        assert( ids != NULL );
00285 
00286        if ( saved_cursor && *saved_cursor ) {
00287               opflag = MDB_NEXT;
00288        } else if ( get_flag == LDAP_FILTER_GE ) {
00289               opflag = MDB_SET_RANGE;
00290        } else if ( get_flag == LDAP_FILTER_LE ) {
00291               opflag = MDB_FIRST;
00292        } else {
00293               opflag = MDB_SET;
00294        }
00295 
00296        /* If we're not reusing an existing cursor, get a new one */
00297        if( opflag != MDB_NEXT ) {
00298               rc = mdb_cursor_open( txn, dbi, &cursor );
00299               if( rc != 0 ) {
00300                      Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
00301                             "cursor failed: %s (%d)\n", mdb_strerror(rc), rc, 0 );
00302                      return rc;
00303               }
00304        } else {
00305               cursor = *saved_cursor;
00306        }
00307        
00308        /* If this is a LE lookup, save original key so we can determine
00309         * when to stop. If this is a GE lookup, save the key since it
00310         * will be overwritten.
00311         */
00312        if ( get_flag == LDAP_FILTER_LE || get_flag == LDAP_FILTER_GE ) {
00313               key2.mv_data = keybuf;
00314               key2.mv_size = key->mv_size;
00315               AC_MEMCPY( keybuf, key->mv_data, key->mv_size );
00316               kptr = &key2;
00317        } else {
00318               kptr = key;
00319        }
00320        len = key->mv_size;
00321        rc = mdb_cursor_get( cursor, kptr, &data, opflag );
00322 
00323        /* skip presence key on range inequality lookups */
00324        while (rc == 0 && kptr->mv_size != len) {
00325               rc = mdb_cursor_get( cursor, kptr, &data, MDB_NEXT_NODUP );
00326        }
00327        /* If we're doing a LE compare and the new key is greater than
00328         * our search key, we're done
00329         */
00330        if (rc == 0 && get_flag == LDAP_FILTER_LE && memcmp( kptr->mv_data,
00331               key->mv_data, key->mv_size ) > 0 ) {
00332               rc = MDB_NOTFOUND;
00333        }
00334        if (rc == 0) {
00335               i = ids+1;
00336               rc = mdb_cursor_get( cursor, key, &data, MDB_GET_MULTIPLE );
00337               while (rc == 0) {
00338                      memcpy( i, data.mv_data, data.mv_size );
00339                      i += data.mv_size / sizeof(ID);
00340                      rc = mdb_cursor_get( cursor, key, &data, MDB_NEXT_MULTIPLE );
00341               }
00342               if ( rc == MDB_NOTFOUND ) rc = 0;
00343               ids[0] = i - &ids[1];
00344               /* On disk, a range is denoted by 0 in the first element */
00345               if (ids[1] == 0) {
00346                      if (ids[0] != MDB_IDL_RANGE_SIZE) {
00347                             Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
00348                                    "range size mismatch: expected %d, got %ld\n",
00349                                    MDB_IDL_RANGE_SIZE, ids[0], 0 );
00350                             mdb_cursor_close( cursor );
00351                             return -1;
00352                      }
00353                      MDB_IDL_RANGE( ids, ids[2], ids[3] );
00354               }
00355               data.mv_size = MDB_IDL_SIZEOF(ids);
00356        }
00357 
00358        if ( saved_cursor && rc == 0 ) {
00359               if ( !*saved_cursor )
00360                      *saved_cursor = cursor;
00361        }
00362        else
00363               mdb_cursor_close( cursor );
00364 
00365        if( rc == MDB_NOTFOUND ) {
00366               return rc;
00367 
00368        } else if( rc != 0 ) {
00369               Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
00370                      "get failed: %s (%d)\n",
00371                      mdb_strerror(rc), rc, 0 );
00372               return rc;
00373 
00374        } else if ( data.mv_size == 0 || data.mv_size % sizeof( ID ) ) {
00375               /* size not multiple of ID size */
00376               Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
00377                      "odd size: expected %ld multiple, got %ld\n",
00378                      (long) sizeof( ID ), (long) data.mv_size, 0 );
00379               return -1;
00380 
00381        } else if ( data.mv_size != MDB_IDL_SIZEOF(ids) ) {
00382               /* size mismatch */
00383               Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
00384                      "get size mismatch: expected %ld, got %ld\n",
00385                      (long) ((1 + ids[0]) * sizeof( ID )), (long) data.mv_size, 0 );
00386               return -1;
00387        }
00388 
00389        return rc;
00390 }
00391 
00392 int
00393 mdb_idl_insert_keys(
00394        MDB_cursor    *cursor,
00395        struct berval *keys,
00396        ID                   id )
00397 {
00398        MDB_val key, data;
00399        ID lo, hi, *i;
00400        char *err;
00401        int    rc, k;
00402        unsigned int flag = MDB_NODUPDATA;
00403 #ifndef       MISALIGNED_OK
00404        int kbuf[2];
00405 #endif
00406 
00407        {
00408               char buf[16];
00409               Debug( LDAP_DEBUG_ARGS,
00410                      "mdb_idl_insert_keys: %lx %s\n", 
00411                      (long) id, mdb_show_key( buf, keys->bv_val, keys->bv_len ), 0 );
00412        }
00413 
00414        assert( id != NOID );
00415 
00416 #ifndef MISALIGNED_OK
00417        if (keys[0].bv_len & ALIGNER)
00418               kbuf[1] = 0;
00419 #endif
00420        for ( k=0; keys[k].bv_val; k++ ) {
00421        /* Fetch the first data item for this key, to see if it
00422         * exists and if it's a range.
00423         */
00424 #ifndef MISALIGNED_OK
00425        if (keys[k].bv_len & ALIGNER) {
00426               key.mv_size = sizeof(kbuf);
00427               key.mv_data = kbuf;
00428               memcpy(key.mv_data, keys[k].bv_val, keys[k].bv_len);
00429        } else
00430 #endif
00431        {
00432               key.mv_size = keys[k].bv_len;
00433               key.mv_data = keys[k].bv_val;
00434        }
00435        rc = mdb_cursor_get( cursor, &key, &data, MDB_SET );
00436        err = "c_get";
00437        if ( rc == 0 ) {
00438               i = data.mv_data;
00439               memcpy(&lo, data.mv_data, sizeof(ID));
00440               if ( lo != 0 ) {
00441                      /* not a range, count the number of items */
00442                      size_t count;
00443                      rc = mdb_cursor_count( cursor, &count );
00444                      if ( rc != 0 ) {
00445                             err = "c_count";
00446                             goto fail;
00447                      }
00448                      if ( count >= MDB_IDL_DB_MAX ) {
00449                      /* No room, convert to a range */
00450                             lo = *i;
00451                             rc = mdb_cursor_get( cursor, &key, &data, MDB_LAST_DUP );
00452                             if ( rc != 0 && rc != MDB_NOTFOUND ) {
00453                                    err = "c_get last_dup";
00454                                    goto fail;
00455                             }
00456                             i = data.mv_data;
00457                             hi = *i;
00458                             /* Update hi/lo if needed */
00459                             if ( id < lo ) {
00460                                    lo = id;
00461                             } else if ( id > hi ) {
00462                                    hi = id;
00463                             }
00464                             /* delete the old key */
00465                             rc = mdb_cursor_del( cursor, MDB_NODUPDATA );
00466                             if ( rc != 0 ) {
00467                                    err = "c_del dups";
00468                                    goto fail;
00469                             }
00470                             /* Store the range */
00471                             data.mv_size = sizeof(ID);
00472                             data.mv_data = &id;
00473                             id = 0;
00474                             rc = mdb_cursor_put( cursor, &key, &data, 0 );
00475                             if ( rc != 0 ) {
00476                                    err = "c_put range";
00477                                    goto fail;
00478                             }
00479                             id = lo;
00480                             rc = mdb_cursor_put( cursor, &key, &data, 0 );
00481                             if ( rc != 0 ) {
00482                                    err = "c_put lo";
00483                                    goto fail;
00484                             }
00485                             id = hi;
00486                             rc = mdb_cursor_put( cursor, &key, &data, 0 );
00487                             if ( rc != 0 ) {
00488                                    err = "c_put hi";
00489                                    goto fail;
00490                             }
00491                      } else {
00492                      /* There's room, just store it */
00493                             if ( slapMode & SLAP_TOOL_QUICK )
00494                                    flag |= MDB_APPEND;
00495                             goto put1;
00496                      }
00497               } else {
00498                      /* It's a range, see if we need to rewrite
00499                       * the boundaries
00500                       */
00501                      lo = i[1];
00502                      hi = i[2];
00503                      if ( id < lo || id > hi ) {
00504                             /* position on lo */
00505                             rc = mdb_cursor_get( cursor, &key, &data, MDB_NEXT_DUP );
00506                             if ( id > hi ) {
00507                                    /* position on hi */
00508                                    rc = mdb_cursor_get( cursor, &key, &data, MDB_NEXT_DUP );
00509                             }
00510                             data.mv_size = sizeof(ID);
00511                             data.mv_data = &id;
00512                             /* Replace the current lo/hi */
00513                             rc = mdb_cursor_put( cursor, &key, &data, MDB_CURRENT );
00514                             if ( rc != 0 ) {
00515                                    err = "c_put lo/hi";
00516                                    goto fail;
00517                             }
00518                      }
00519               }
00520        } else if ( rc == MDB_NOTFOUND ) {
00521               flag &= ~MDB_APPEND;
00522 put1:  data.mv_data = &id;
00523               data.mv_size = sizeof(ID);
00524               rc = mdb_cursor_put( cursor, &key, &data, flag );
00525               /* Don't worry if it's already there */
00526               if ( rc == MDB_KEYEXIST )
00527                      rc = 0;
00528               if ( rc ) {
00529                      err = "c_put id";
00530                      goto fail;
00531               }
00532        } else {
00533               /* initial c_get failed, nothing was done */
00534 fail:
00535               Debug( LDAP_DEBUG_ANY, "=> mdb_idl_insert_keys: "
00536                      "%s failed: %s (%d)\n", err, mdb_strerror(rc), rc );
00537               break;
00538        }
00539        }
00540        return rc;
00541 }
00542 
00543 int
00544 mdb_idl_delete_keys(
00545        MDB_cursor    *cursor,
00546        struct berval *keys,
00547        ID                   id )
00548 {
00549        int    rc, k;
00550        MDB_val key, data;
00551        ID lo, hi, tmp, *i;
00552        char *err;
00553 #ifndef       MISALIGNED_OK
00554        int kbuf[2];
00555 #endif
00556 
00557        {
00558               char buf[16];
00559               Debug( LDAP_DEBUG_ARGS,
00560                      "mdb_idl_delete_keys: %lx %s\n", 
00561                      (long) id, mdb_show_key( buf, keys->bv_val, keys->bv_len ), 0 );
00562        }
00563        assert( id != NOID );
00564 
00565 #ifndef MISALIGNED_OK
00566        if (keys[0].bv_len & ALIGNER)
00567               kbuf[1] = 0;
00568 #endif
00569        for ( k=0; keys[k].bv_val; k++) {
00570        /* Fetch the first data item for this key, to see if it
00571         * exists and if it's a range.
00572         */
00573 #ifndef MISALIGNED_OK
00574        if (keys[k].bv_len & ALIGNER) {
00575               key.mv_size = sizeof(kbuf);
00576               key.mv_data = kbuf;
00577               memcpy(key.mv_data, keys[k].bv_val, keys[k].bv_len);
00578        } else
00579 #endif
00580        {
00581               key.mv_size = keys[k].bv_len;
00582               key.mv_data = keys[k].bv_val;
00583        }
00584        rc = mdb_cursor_get( cursor, &key, &data, MDB_SET );
00585        err = "c_get";
00586        if ( rc == 0 ) {
00587               memcpy( &tmp, data.mv_data, sizeof(ID) );
00588               i = data.mv_data;
00589               if ( tmp != 0 ) {
00590                      /* Not a range, just delete it */
00591                      data.mv_data = &id;
00592                      rc = mdb_cursor_get( cursor, &key, &data, MDB_GET_BOTH );
00593                      if ( rc != 0 ) {
00594                             err = "c_get id";
00595                             goto fail;
00596                      }
00597                      rc = mdb_cursor_del( cursor, 0 );
00598                      if ( rc != 0 ) {
00599                             err = "c_del id";
00600                             goto fail;
00601                      }
00602               } else {
00603                      /* It's a range, see if we need to rewrite
00604                       * the boundaries
00605                       */
00606                      lo = i[1];
00607                      hi = i[2];
00608                      if ( id == lo || id == hi ) {
00609                             ID lo2 = lo, hi2 = hi;
00610                             if ( id == lo ) {
00611                                    lo2++;
00612                             } else if ( id == hi ) {
00613                                    hi2--;
00614                             }
00615                             if ( lo2 >= hi2 ) {
00616                             /* The range has collapsed... */
00617                                    rc = mdb_cursor_del( cursor, MDB_NODUPDATA );
00618                                    if ( rc != 0 ) {
00619                                           err = "c_del dup";
00620                                           goto fail;
00621                                    }
00622                             } else {
00623                                    /* position on lo */
00624                                    rc = mdb_cursor_get( cursor, &key, &data, MDB_NEXT_DUP );
00625                                    if ( id == lo )
00626                                           data.mv_data = &lo2;
00627                                    else {
00628                                           /* position on hi */
00629                                           rc = mdb_cursor_get( cursor, &key, &data, MDB_NEXT_DUP );
00630                                           data.mv_data = &hi2;
00631                                    }
00632                                    /* Replace the current lo/hi */
00633                                    data.mv_size = sizeof(ID);
00634                                    rc = mdb_cursor_put( cursor, &key, &data, MDB_CURRENT );
00635                                    if ( rc != 0 ) {
00636                                           err = "c_put lo/hi";
00637                                           goto fail;
00638                                    }
00639                             }
00640                      }
00641               }
00642        } else {
00643               /* initial c_get failed, nothing was done */
00644 fail:
00645               if ( rc == MDB_NOTFOUND )
00646                      rc = 0;
00647               if ( rc ) {
00648                      Debug( LDAP_DEBUG_ANY, "=> mdb_idl_delete_key: "
00649                             "%s failed: %s (%d)\n", err, mdb_strerror(rc), rc );
00650                      break;
00651               }
00652        }
00653        }
00654        return rc;
00655 }
00656 
00657 
00658 /*
00659  * idl_intersection - return a = a intersection b
00660  */
00661 int
00662 mdb_idl_intersection(
00663        ID *a,
00664        ID *b )
00665 {
00666        ID ida, idb;
00667        ID idmax, idmin;
00668        ID cursora = 0, cursorb = 0, cursorc;
00669        int swap = 0;
00670 
00671        if ( MDB_IDL_IS_ZERO( a ) || MDB_IDL_IS_ZERO( b ) ) {
00672               a[0] = 0;
00673               return 0;
00674        }
00675 
00676        idmin = IDL_MAX( MDB_IDL_FIRST(a), MDB_IDL_FIRST(b) );
00677        idmax = IDL_MIN( MDB_IDL_LAST(a), MDB_IDL_LAST(b) );
00678        if ( idmin > idmax ) {
00679               a[0] = 0;
00680               return 0;
00681        } else if ( idmin == idmax ) {
00682               a[0] = 1;
00683               a[1] = idmin;
00684               return 0;
00685        }
00686 
00687        if ( MDB_IDL_IS_RANGE( a ) ) {
00688               if ( MDB_IDL_IS_RANGE(b) ) {
00689               /* If both are ranges, just shrink the boundaries */
00690                      a[1] = idmin;
00691                      a[2] = idmax;
00692                      return 0;
00693               } else {
00694               /* Else swap so that b is the range, a is a list */
00695                      ID *tmp = a;
00696                      a = b;
00697                      b = tmp;
00698                      swap = 1;
00699               }
00700        }
00701 
00702        /* If a range completely covers the list, the result is
00703         * just the list. If idmin to idmax is contiguous, just
00704         * turn it into a range.
00705         */
00706        if ( MDB_IDL_IS_RANGE( b )
00707               && MDB_IDL_RANGE_FIRST( b ) <= MDB_IDL_RANGE_FIRST( a )
00708               && MDB_IDL_RANGE_LAST( b ) >= MDB_IDL_RANGE_LAST( a ) ) {
00709               if (idmax - idmin + 1 == a[0])
00710               {
00711                      a[0] = NOID;
00712                      a[1] = idmin;
00713                      a[2] = idmax;
00714               }
00715               goto done;
00716        }
00717 
00718        /* Fine, do the intersection one element at a time.
00719         * First advance to idmin in both IDLs.
00720         */
00721        cursora = cursorb = idmin;
00722        ida = mdb_idl_first( a, &cursora );
00723        idb = mdb_idl_first( b, &cursorb );
00724        cursorc = 0;
00725 
00726        while( ida <= idmax || idb <= idmax ) {
00727               if( ida == idb ) {
00728                      a[++cursorc] = ida;
00729                      ida = mdb_idl_next( a, &cursora );
00730                      idb = mdb_idl_next( b, &cursorb );
00731               } else if ( ida < idb ) {
00732                      ida = mdb_idl_next( a, &cursora );
00733               } else {
00734                      idb = mdb_idl_next( b, &cursorb );
00735               }
00736        }
00737        a[0] = cursorc;
00738 done:
00739        if (swap)
00740               MDB_IDL_CPY( b, a );
00741 
00742        return 0;
00743 }
00744 
00745 
00746 /*
00747  * idl_union - return a = a union b
00748  */
00749 int
00750 mdb_idl_union(
00751        ID     *a,
00752        ID     *b )
00753 {
00754        ID ida, idb;
00755        ID cursora = 0, cursorb = 0, cursorc;
00756 
00757        if ( MDB_IDL_IS_ZERO( b ) ) {
00758               return 0;
00759        }
00760 
00761        if ( MDB_IDL_IS_ZERO( a ) ) {
00762               MDB_IDL_CPY( a, b );
00763               return 0;
00764        }
00765 
00766        if ( MDB_IDL_IS_RANGE( a ) || MDB_IDL_IS_RANGE(b) ) {
00767 over:         ida = IDL_MIN( MDB_IDL_FIRST(a), MDB_IDL_FIRST(b) );
00768               idb = IDL_MAX( MDB_IDL_LAST(a), MDB_IDL_LAST(b) );
00769               a[0] = NOID;
00770               a[1] = ida;
00771               a[2] = idb;
00772               return 0;
00773        }
00774 
00775        ida = mdb_idl_first( a, &cursora );
00776        idb = mdb_idl_first( b, &cursorb );
00777 
00778        cursorc = b[0];
00779 
00780        /* The distinct elements of a are cat'd to b */
00781        while( ida != NOID || idb != NOID ) {
00782               if ( ida < idb ) {
00783                      if( ++cursorc > MDB_IDL_UM_MAX ) {
00784                             goto over;
00785                      }
00786                      b[cursorc] = ida;
00787                      ida = mdb_idl_next( a, &cursora );
00788 
00789               } else {
00790                      if ( ida == idb )
00791                             ida = mdb_idl_next( a, &cursora );
00792                      idb = mdb_idl_next( b, &cursorb );
00793               }
00794        }
00795 
00796        /* b is copied back to a in sorted order */
00797        a[0] = cursorc;
00798        cursora = 1;
00799        cursorb = 1;
00800        cursorc = b[0]+1;
00801        while (cursorb <= b[0] || cursorc <= a[0]) {
00802               if (cursorc > a[0])
00803                      idb = NOID;
00804               else
00805                      idb = b[cursorc];
00806               if (cursorb <= b[0] && b[cursorb] < idb)
00807                      a[cursora++] = b[cursorb++];
00808               else {
00809                      a[cursora++] = idb;
00810                      cursorc++;
00811               }
00812        }
00813 
00814        return 0;
00815 }
00816 
00817 
00818 #if 0
00819 /*
00820  * mdb_idl_notin - return a intersection ~b (or a minus b)
00821  */
00822 int
00823 mdb_idl_notin(
00824        ID     *a,
00825        ID     *b,
00826        ID *ids )
00827 {
00828        ID ida, idb;
00829        ID cursora = 0, cursorb = 0;
00830 
00831        if( MDB_IDL_IS_ZERO( a ) ||
00832               MDB_IDL_IS_ZERO( b ) ||
00833               MDB_IDL_IS_RANGE( b ) )
00834        {
00835               MDB_IDL_CPY( ids, a );
00836               return 0;
00837        }
00838 
00839        if( MDB_IDL_IS_RANGE( a ) ) {
00840               MDB_IDL_CPY( ids, a );
00841               return 0;
00842        }
00843 
00844        ida = mdb_idl_first( a, &cursora ),
00845        idb = mdb_idl_first( b, &cursorb );
00846 
00847        ids[0] = 0;
00848 
00849        while( ida != NOID ) {
00850               if ( idb == NOID ) {
00851                      /* we could shortcut this */
00852                      ids[++ids[0]] = ida;
00853                      ida = mdb_idl_next( a, &cursora );
00854 
00855               } else if ( ida < idb ) {
00856                      ids[++ids[0]] = ida;
00857                      ida = mdb_idl_next( a, &cursora );
00858 
00859               } else if ( ida > idb ) {
00860                      idb = mdb_idl_next( b, &cursorb );
00861 
00862               } else {
00863                      ida = mdb_idl_next( a, &cursora );
00864                      idb = mdb_idl_next( b, &cursorb );
00865               }
00866        }
00867 
00868        return 0;
00869 }
00870 #endif
00871 
00872 ID mdb_idl_first( ID *ids, ID *cursor )
00873 {
00874        ID pos;
00875 
00876        if ( ids[0] == 0 ) {
00877               *cursor = NOID;
00878               return NOID;
00879        }
00880 
00881        if ( MDB_IDL_IS_RANGE( ids ) ) {
00882               if( *cursor < ids[1] ) {
00883                      *cursor = ids[1];
00884               }
00885               return *cursor;
00886        }
00887 
00888        if ( *cursor == 0 )
00889               pos = 1;
00890        else
00891               pos = mdb_idl_search( ids, *cursor );
00892 
00893        if( pos > ids[0] ) {
00894               return NOID;
00895        }
00896 
00897        *cursor = pos;
00898        return ids[pos];
00899 }
00900 
00901 ID mdb_idl_next( ID *ids, ID *cursor )
00902 {
00903        if ( MDB_IDL_IS_RANGE( ids ) ) {
00904               if( ids[2] < ++(*cursor) ) {
00905                      return NOID;
00906               }
00907               return *cursor;
00908        }
00909 
00910        if ( ++(*cursor) <= ids[0] ) {
00911               return ids[*cursor];
00912        }
00913 
00914        return NOID;
00915 }
00916 
00917 /* Add one ID to an unsorted list. We ensure that the first element is the
00918  * minimum and the last element is the maximum, for fast range compaction.
00919  *   this means IDLs up to length 3 are always sorted...
00920  */
00921 int mdb_idl_append_one( ID *ids, ID id )
00922 {
00923        if (MDB_IDL_IS_RANGE( ids )) {
00924               /* if already in range, treat as a dup */
00925               if (id >= MDB_IDL_RANGE_FIRST(ids) && id <= MDB_IDL_RANGE_LAST(ids))
00926                      return -1;
00927               if (id < MDB_IDL_RANGE_FIRST(ids))
00928                      ids[1] = id;
00929               else if (id > MDB_IDL_RANGE_LAST(ids))
00930                      ids[2] = id;
00931               return 0;
00932        }
00933        if ( ids[0] ) {
00934               ID tmp;
00935 
00936               if (id < ids[1]) {
00937                      tmp = ids[1];
00938                      ids[1] = id;
00939                      id = tmp;
00940               }
00941               if ( ids[0] > 1 && id < ids[ids[0]] ) {
00942                      tmp = ids[ids[0]];
00943                      ids[ids[0]] = id;
00944                      id = tmp;
00945               }
00946        }
00947        ids[0]++;
00948        if ( ids[0] >= MDB_IDL_UM_MAX ) {
00949               ids[0] = NOID;
00950               ids[2] = id;
00951        } else {
00952               ids[ids[0]] = id;
00953        }
00954        return 0;
00955 }
00956 
00957 /* Append sorted list b to sorted list a. The result is unsorted but
00958  * a[1] is the min of the result and a[a[0]] is the max.
00959  */
00960 int mdb_idl_append( ID *a, ID *b )
00961 {
00962        ID ida, idb, tmp, swap = 0;
00963 
00964        if ( MDB_IDL_IS_ZERO( b ) ) {
00965               return 0;
00966        }
00967 
00968        if ( MDB_IDL_IS_ZERO( a ) ) {
00969               MDB_IDL_CPY( a, b );
00970               return 0;
00971        }
00972 
00973        ida = MDB_IDL_LAST( a );
00974        idb = MDB_IDL_LAST( b );
00975        if ( MDB_IDL_IS_RANGE( a ) || MDB_IDL_IS_RANGE(b) ||
00976               a[0] + b[0] >= MDB_IDL_UM_MAX ) {
00977               a[2] = IDL_MAX( ida, idb );
00978               a[1] = IDL_MIN( a[1], b[1] );
00979               a[0] = NOID;
00980               return 0;
00981        }
00982 
00983        if ( b[0] > 1 && ida > idb ) {
00984               swap = idb;
00985               a[a[0]] = idb;
00986               b[b[0]] = ida;
00987        }
00988 
00989        if ( b[1] < a[1] ) {
00990               tmp = a[1];
00991               a[1] = b[1];
00992        } else {
00993               tmp = b[1];
00994        }
00995        a[0]++;
00996        a[a[0]] = tmp;
00997 
00998        if ( b[0] > 1 ) {
00999               int i = b[0] - 1;
01000               AC_MEMCPY(a+a[0]+1, b+2, i * sizeof(ID));
01001               a[0] += i;
01002        }
01003        if ( swap ) {
01004               b[b[0]] = swap;
01005        }
01006        return 0;
01007 }
01008 
01009 #if 1
01010 
01011 /* Quicksort + Insertion sort for small arrays */
01012 
01013 #define SMALL 8
01014 #define       SWAP(a,b)     itmp=(a);(a)=(b);(b)=itmp
01015 
01016 void
01017 mdb_idl_sort( ID *ids, ID *tmp )
01018 {
01019        int *istack = (int *)tmp; /* Private stack, not used by caller */
01020        int i,j,k,l,ir,jstack;
01021        ID a, itmp;
01022 
01023        if ( MDB_IDL_IS_RANGE( ids ))
01024               return;
01025 
01026        ir = ids[0];
01027        l = 1;
01028        jstack = 0;
01029        for(;;) {
01030               if (ir - l < SMALL) {       /* Insertion sort */
01031                      for (j=l+1;j<=ir;j++) {
01032                             a = ids[j];
01033                             for (i=j-1;i>=1;i--) {
01034                                    if (ids[i] <= a) break;
01035                                    ids[i+1] = ids[i];
01036                             }
01037                             ids[i+1] = a;
01038                      }
01039                      if (jstack == 0) break;
01040                      ir = istack[jstack--];
01041                      l = istack[jstack--];
01042               } else {
01043                      k = (l + ir) >> 1;   /* Choose median of left, center, right */
01044                      SWAP(ids[k], ids[l+1]);
01045                      if (ids[l] > ids[ir]) {
01046                             SWAP(ids[l], ids[ir]);
01047                      }
01048                      if (ids[l+1] > ids[ir]) {
01049                             SWAP(ids[l+1], ids[ir]);
01050                      }
01051                      if (ids[l] > ids[l+1]) {
01052                             SWAP(ids[l], ids[l+1]);
01053                      }
01054                      i = l+1;
01055                      j = ir;
01056                      a = ids[l+1];
01057                      for(;;) {
01058                             do i++; while(ids[i] < a);
01059                             do j--; while(ids[j] > a);
01060                             if (j < i) break;
01061                             SWAP(ids[i],ids[j]);
01062                      }
01063                      ids[l+1] = ids[j];
01064                      ids[j] = a;
01065                      jstack += 2;
01066                      if (ir-i+1 >= j-1) {
01067                             istack[jstack] = ir;
01068                             istack[jstack-1] = i;
01069                             ir = j-1;
01070                      } else {
01071                             istack[jstack] = j-1;
01072                             istack[jstack-1] = l;
01073                             l = i;
01074                      }
01075               }
01076        }
01077 }
01078 
01079 #else
01080 
01081 /* 8 bit Radix sort + insertion sort
01082  * 
01083  * based on code from http://www.cubic.org/docs/radix.htm
01084  * with improvements by mbackes@symas.com and hyc@symas.com
01085  *
01086  * This code is O(n) but has a relatively high constant factor. For lists
01087  * up to ~50 Quicksort is slightly faster; up to ~100 they are even.
01088  * Much faster than quicksort for lists longer than ~100. Insertion
01089  * sort is actually superior for lists <50.
01090  */
01091 
01092 #define BUCKETS      (1<<8)
01093 #define SMALL 50
01094 
01095 void
01096 mdb_idl_sort( ID *ids, ID *tmp )
01097 {
01098        int count, soft_limit, phase = 0, size = ids[0];
01099        ID *idls[2];
01100        unsigned char *maxv = (unsigned char *)&ids[size];
01101 
01102        if ( MDB_IDL_IS_RANGE( ids ))
01103               return;
01104 
01105        /* Use insertion sort for small lists */
01106        if ( size <= SMALL ) {
01107               int i,j;
01108               ID a;
01109 
01110               for (j=1;j<=size;j++) {
01111                      a = ids[j];
01112                      for (i=j-1;i>=1;i--) {
01113                             if (ids[i] <= a) break;
01114                             ids[i+1] = ids[i];
01115                      }
01116                      ids[i+1] = a;
01117               }
01118               return;
01119        }
01120 
01121        tmp[0] = size;
01122        idls[0] = ids;
01123        idls[1] = tmp;
01124 
01125 #if BYTE_ORDER == BIG_ENDIAN
01126     for (soft_limit = 0; !maxv[soft_limit]; soft_limit++);
01127 #else
01128     for (soft_limit = sizeof(ID)-1; !maxv[soft_limit]; soft_limit--);
01129 #endif
01130 
01131        for (
01132 #if BYTE_ORDER == BIG_ENDIAN
01133        count = sizeof(ID)-1; count >= soft_limit; --count
01134 #else
01135        count = 0; count <= soft_limit; ++count
01136 #endif
01137        ) {
01138               unsigned int num[BUCKETS], * np, n, sum;
01139               int i;
01140         ID *sp, *source, *dest;
01141         unsigned char *bp, *source_start;
01142 
01143               source = idls[phase]+1;
01144               dest = idls[phase^1]+1;
01145               source_start =  ((unsigned char *) source) + count;
01146 
01147         np = num;
01148         for ( i = BUCKETS; i > 0; --i ) *np++ = 0;
01149 
01150               /* count occurences of every byte value */
01151               bp = source_start;
01152         for ( i = size; i > 0; --i, bp += sizeof(ID) )
01153                             num[*bp]++;
01154 
01155               /* transform count into index by summing elements and storing
01156                * into same array
01157                */
01158         sum = 0;
01159         np = num;
01160         for ( i = BUCKETS; i > 0; --i ) {
01161                 n = *np;
01162                 *np++ = sum;
01163                 sum += n;
01164         }
01165 
01166               /* fill dest with the right values in the right place */
01167               bp = source_start;
01168         sp = source;
01169         for ( i = size; i > 0; --i, bp += sizeof(ID) ) {
01170                 np = num + *bp;
01171                 dest[*np] = *sp++;
01172                 ++(*np);
01173         }
01174               phase ^= 1;
01175        }
01176 
01177        /* copy back from temp if needed */
01178        if ( phase ) {
01179               ids++; tmp++;
01180               for ( count = 0; count < size; ++count ) 
01181                      *ids++ = *tmp++;
01182        }
01183 }
01184 #endif /* Quick vs Radix */
01185 
01186 unsigned mdb_id2l_search( ID2L ids, ID id )
01187 {
01188        /*
01189         * binary search of id in ids
01190         * if found, returns position of id
01191         * if not found, returns first position greater than id
01192         */
01193        unsigned base = 0;
01194        unsigned cursor = 1;
01195        int val = 0;
01196        unsigned n = ids[0].mid;
01197 
01198        while( 0 < n ) {
01199               unsigned pivot = n >> 1;
01200               cursor = base + pivot + 1;
01201               val = IDL_CMP( id, ids[cursor].mid );
01202 
01203               if( val < 0 ) {
01204                      n = pivot;
01205 
01206               } else if ( val > 0 ) {
01207                      base = cursor;
01208                      n -= pivot + 1;
01209 
01210               } else {
01211                      return cursor;
01212               }
01213        }
01214 
01215        if( val > 0 ) {
01216               ++cursor;
01217        }
01218        return cursor;
01219 }
01220 
01221 int mdb_id2l_insert( ID2L ids, ID2 *id )
01222 {
01223        unsigned x, i;
01224 
01225        x = mdb_id2l_search( ids, id->mid );
01226        assert( x > 0 );
01227 
01228        if( x < 1 ) {
01229               /* internal error */
01230               return -2;
01231        }
01232 
01233        if ( x <= ids[0].mid && ids[x].mid == id->mid ) {
01234               /* duplicate */
01235               return -1;
01236        }
01237 
01238        if ( ids[0].mid >= MDB_IDL_UM_MAX ) {
01239               /* too big */
01240               return -2;
01241 
01242        } else {
01243               /* insert id */
01244               ids[0].mid++;
01245               for (i=ids[0].mid; i>x; i--)
01246                      ids[i] = ids[i-1];
01247               ids[x] = *id;
01248        }
01249 
01250        return 0;
01251 }