Back to index

openldap  2.4.31
Defines | Functions
idl.c File Reference
#include "portable.h"
#include <stdio.h>
#include <ac/string.h>
#include "back-mdb.h"
#include "idl.h"

Go to the source code of this file.

Defines

#define IDL_MAX(x, y)   ( (x) > (y) ? (x) : (y) )
#define IDL_MIN(x, y)   ( (x) < (y) ? (x) : (y) )
#define IDL_CMP(x, y)   ( (x) < (y) ? -1 : (x) > (y) )
#define IDL_BINARY_SEARCH   1
#define SMALL   8
#define SWAP(a, b)   itmp=(a);(a)=(b);(b)=itmp

Functions

unsigned mdb_idl_search (ID *ids, ID id)
int mdb_idl_insert (ID *ids, ID id)
static int mdb_idl_delete (ID *ids, ID id)
static char * mdb_show_key (char *buf, void *val, size_t len)
int mdb_idl_fetch_key (BackendDB *be, MDB_txn *txn, MDB_dbi dbi, MDB_val *key, ID *ids, MDB_cursor **saved_cursor, int get_flag)
int mdb_idl_insert_keys (MDB_cursor *cursor, struct berval *keys, ID id)
int mdb_idl_delete_keys (MDB_cursor *cursor, struct berval *keys, ID id)
int mdb_idl_intersection (ID *a, ID *b)
int mdb_idl_union (ID *a, ID *b)
ID mdb_idl_first (ID *ids, ID *cursor)
ID mdb_idl_next (ID *ids, ID *cursor)
int mdb_idl_append_one (ID *ids, ID id)
int mdb_idl_append (ID *a, ID *b)
void mdb_idl_sort (ID *ids, ID *tmp)
unsigned mdb_id2l_search (ID2L ids, ID id)
 Search for an ID in an ID2L.
int mdb_id2l_insert (ID2L ids, ID2 *id)
 Insert an ID2 into a ID2L.

Define Documentation

#define IDL_BINARY_SEARCH   1
#define IDL_CMP (   x,
 
)    ( (x) < (y) ? -1 : (x) > (y) )

Definition at line 27 of file idl.c.

#define IDL_MAX (   x,
 
)    ( (x) > (y) ? (x) : (y) )

Definition at line 25 of file idl.c.

#define IDL_MIN (   x,
 
)    ( (x) < (y) ? (x) : (y) )

Definition at line 26 of file idl.c.

#define SMALL   8

Definition at line 1013 of file idl.c.

#define SWAP (   a,
  b 
)    itmp=(a);(a)=(b);(b)=itmp

Definition at line 1014 of file idl.c.


Function Documentation

int mdb_id2l_insert ( ID2L  ids,
ID2 id 
)

Insert an ID2 into a ID2L.

Parameters:
[in,out]idsThe ID2L to insert into.
[in]idThe ID2 to insert.
Returns:
0 on success, -1 if the ID was already present in the MIDL2.

Definition at line 1221 of file idl.c.

{
       unsigned x, i;

       x = mdb_id2l_search( ids, id->mid );
       assert( x > 0 );

       if( x < 1 ) {
              /* internal error */
              return -2;
       }

       if ( x <= ids[0].mid && ids[x].mid == id->mid ) {
              /* duplicate */
              return -1;
       }

       if ( ids[0].mid >= MDB_IDL_UM_MAX ) {
              /* too big */
              return -2;

       } else {
              /* insert id */
              ids[0].mid++;
              for (i=ids[0].mid; i>x; i--)
                     ids[i] = ids[i-1];
              ids[x] = *id;
       }

       return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

unsigned mdb_id2l_search ( ID2L  ids,
ID  id 
)

Search for an ID in an ID2L.

Parameters:
[in]idsThe ID2L to search.
[in]idThe ID to search for.
Returns:
The index of the first ID2 whose mid member is greater than or equal to id.

Definition at line 1186 of file idl.c.

{
       /*
        * binary search of id in ids
        * if found, returns position of id
        * if not found, returns first position greater than id
        */
       unsigned base = 0;
       unsigned cursor = 1;
       int val = 0;
       unsigned n = ids[0].mid;

       while( 0 < n ) {
              unsigned pivot = n >> 1;
              cursor = base + pivot + 1;
              val = IDL_CMP( id, ids[cursor].mid );

              if( val < 0 ) {
                     n = pivot;

              } else if ( val > 0 ) {
                     base = cursor;
                     n -= pivot + 1;

              } else {
                     return cursor;
              }
       }

       if( val > 0 ) {
              ++cursor;
       }
       return cursor;
}

Here is the caller graph for this function:

int mdb_idl_append ( ID a,
ID b 
)

Definition at line 960 of file idl.c.

{
       ID ida, idb, tmp, swap = 0;

       if ( MDB_IDL_IS_ZERO( b ) ) {
              return 0;
       }

       if ( MDB_IDL_IS_ZERO( a ) ) {
              MDB_IDL_CPY( a, b );
              return 0;
       }

       ida = MDB_IDL_LAST( a );
       idb = MDB_IDL_LAST( b );
       if ( MDB_IDL_IS_RANGE( a ) || MDB_IDL_IS_RANGE(b) ||
              a[0] + b[0] >= MDB_IDL_UM_MAX ) {
              a[2] = IDL_MAX( ida, idb );
              a[1] = IDL_MIN( a[1], b[1] );
              a[0] = NOID;
              return 0;
       }

       if ( b[0] > 1 && ida > idb ) {
              swap = idb;
              a[a[0]] = idb;
              b[b[0]] = ida;
       }

       if ( b[1] < a[1] ) {
              tmp = a[1];
              a[1] = b[1];
       } else {
              tmp = b[1];
       }
       a[0]++;
       a[a[0]] = tmp;

       if ( b[0] > 1 ) {
              int i = b[0] - 1;
              AC_MEMCPY(a+a[0]+1, b+2, i * sizeof(ID));
              a[0] += i;
       }
       if ( swap ) {
              b[b[0]] = swap;
       }
       return 0;
}
int mdb_idl_append_one ( ID ids,
ID  id 
)

Definition at line 921 of file idl.c.

{
       if (MDB_IDL_IS_RANGE( ids )) {
              /* if already in range, treat as a dup */
              if (id >= MDB_IDL_RANGE_FIRST(ids) && id <= MDB_IDL_RANGE_LAST(ids))
                     return -1;
              if (id < MDB_IDL_RANGE_FIRST(ids))
                     ids[1] = id;
              else if (id > MDB_IDL_RANGE_LAST(ids))
                     ids[2] = id;
              return 0;
       }
       if ( ids[0] ) {
              ID tmp;

              if (id < ids[1]) {
                     tmp = ids[1];
                     ids[1] = id;
                     id = tmp;
              }
              if ( ids[0] > 1 && id < ids[ids[0]] ) {
                     tmp = ids[ids[0]];
                     ids[ids[0]] = id;
                     id = tmp;
              }
       }
       ids[0]++;
       if ( ids[0] >= MDB_IDL_UM_MAX ) {
              ids[0] = NOID;
              ids[2] = id;
       } else {
              ids[ids[0]] = id;
       }
       return 0;
}
static int mdb_idl_delete ( ID ids,
ID  id 
) [static]

Definition at line 189 of file idl.c.

{
       unsigned x;

#if IDL_DEBUG > 1
       Debug( LDAP_DEBUG_ANY, "delete: %04lx at %d\n", (long) id, x, 0 );
       idl_dump( ids );
#elif IDL_DEBUG > 0
       idl_check( ids );
#endif

       if (MDB_IDL_IS_RANGE( ids )) {
              /* If deleting a range boundary, adjust */
              if ( ids[1] == id )
                     ids[1]++;
              else if ( ids[2] == id )
                     ids[2]--;
              /* deleting from inside a range is a no-op */

              /* If the range has collapsed, re-adjust */
              if ( ids[1] > ids[2] )
                     ids[0] = 0;
              else if ( ids[1] == ids[2] )
                     ids[1] = 1;
              return 0;
       }

       x = mdb_idl_search( ids, id );
       assert( x > 0 );

       if( x <= 0 ) {
              /* internal error */
              return -2;
       }

       if( x > ids[0] || ids[x] != id ) {
              /* not found */
              return -1;

       } else if ( --ids[0] == 0 ) {
              if( x != 1 ) {
                     return -3;
              }

       } else {
              AC_MEMCPY( &ids[x], &ids[x+1], (1+ids[0]-x) * sizeof(ID) );
       }

#if IDL_DEBUG > 1
       idl_dump( ids );
#elif IDL_DEBUG > 0
       idl_check( ids );
#endif

       return 0;
}

Here is the call graph for this function:

int mdb_idl_delete_keys ( MDB_cursor cursor,
struct berval keys,
ID  id 
)

Definition at line 544 of file idl.c.

{
       int    rc, k;
       MDB_val key, data;
       ID lo, hi, tmp, *i;
       char *err;
#ifndef       MISALIGNED_OK
       int kbuf[2];
#endif

       {
              char buf[16];
              Debug( LDAP_DEBUG_ARGS,
                     "mdb_idl_delete_keys: %lx %s\n", 
                     (long) id, mdb_show_key( buf, keys->bv_val, keys->bv_len ), 0 );
       }
       assert( id != NOID );

#ifndef MISALIGNED_OK
       if (keys[0].bv_len & ALIGNER)
              kbuf[1] = 0;
#endif
       for ( k=0; keys[k].bv_val; k++) {
       /* Fetch the first data item for this key, to see if it
        * exists and if it's a range.
        */
#ifndef MISALIGNED_OK
       if (keys[k].bv_len & ALIGNER) {
              key.mv_size = sizeof(kbuf);
              key.mv_data = kbuf;
              memcpy(key.mv_data, keys[k].bv_val, keys[k].bv_len);
       } else
#endif
       {
              key.mv_size = keys[k].bv_len;
              key.mv_data = keys[k].bv_val;
       }
       rc = mdb_cursor_get( cursor, &key, &data, MDB_SET );
       err = "c_get";
       if ( rc == 0 ) {
              memcpy( &tmp, data.mv_data, sizeof(ID) );
              i = data.mv_data;
              if ( tmp != 0 ) {
                     /* Not a range, just delete it */
                     data.mv_data = &id;
                     rc = mdb_cursor_get( cursor, &key, &data, MDB_GET_BOTH );
                     if ( rc != 0 ) {
                            err = "c_get id";
                            goto fail;
                     }
                     rc = mdb_cursor_del( cursor, 0 );
                     if ( rc != 0 ) {
                            err = "c_del id";
                            goto fail;
                     }
              } else {
                     /* It's a range, see if we need to rewrite
                      * the boundaries
                      */
                     lo = i[1];
                     hi = i[2];
                     if ( id == lo || id == hi ) {
                            ID lo2 = lo, hi2 = hi;
                            if ( id == lo ) {
                                   lo2++;
                            } else if ( id == hi ) {
                                   hi2--;
                            }
                            if ( lo2 >= hi2 ) {
                            /* The range has collapsed... */
                                   rc = mdb_cursor_del( cursor, MDB_NODUPDATA );
                                   if ( rc != 0 ) {
                                          err = "c_del dup";
                                          goto fail;
                                   }
                            } else {
                                   /* position on lo */
                                   rc = mdb_cursor_get( cursor, &key, &data, MDB_NEXT_DUP );
                                   if ( id == lo )
                                          data.mv_data = &lo2;
                                   else {
                                          /* position on hi */
                                          rc = mdb_cursor_get( cursor, &key, &data, MDB_NEXT_DUP );
                                          data.mv_data = &hi2;
                                   }
                                   /* Replace the current lo/hi */
                                   data.mv_size = sizeof(ID);
                                   rc = mdb_cursor_put( cursor, &key, &data, MDB_CURRENT );
                                   if ( rc != 0 ) {
                                          err = "c_put lo/hi";
                                          goto fail;
                                   }
                            }
                     }
              }
       } else {
              /* initial c_get failed, nothing was done */
fail:
              if ( rc == MDB_NOTFOUND )
                     rc = 0;
              if ( rc ) {
                     Debug( LDAP_DEBUG_ANY, "=> mdb_idl_delete_key: "
                            "%s failed: %s (%d)\n", err, mdb_strerror(rc), rc );
                     break;
              }
       }
       }
       return rc;
}

Here is the call graph for this function:

int mdb_idl_fetch_key ( BackendDB be,
MDB_txn txn,
MDB_dbi  dbi,
MDB_val key,
ID ids,
MDB_cursor **  saved_cursor,
int  get_flag 
)

Definition at line 262 of file idl.c.

{
       MDB_val data, key2, *kptr;
       MDB_cursor *cursor;
       ID *i;
       size_t len;
       int rc;
       MDB_cursor_op opflag;

       char keybuf[16];

       Debug( LDAP_DEBUG_ARGS,
              "mdb_idl_fetch_key: %s\n", 
              mdb_show_key( keybuf, key->mv_data, key->mv_size ), 0, 0 );

       assert( ids != NULL );

       if ( saved_cursor && *saved_cursor ) {
              opflag = MDB_NEXT;
       } else if ( get_flag == LDAP_FILTER_GE ) {
              opflag = MDB_SET_RANGE;
       } else if ( get_flag == LDAP_FILTER_LE ) {
              opflag = MDB_FIRST;
       } else {
              opflag = MDB_SET;
       }

       /* If we're not reusing an existing cursor, get a new one */
       if( opflag != MDB_NEXT ) {
              rc = mdb_cursor_open( txn, dbi, &cursor );
              if( rc != 0 ) {
                     Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
                            "cursor failed: %s (%d)\n", mdb_strerror(rc), rc, 0 );
                     return rc;
              }
       } else {
              cursor = *saved_cursor;
       }
       
       /* If this is a LE lookup, save original key so we can determine
        * when to stop. If this is a GE lookup, save the key since it
        * will be overwritten.
        */
       if ( get_flag == LDAP_FILTER_LE || get_flag == LDAP_FILTER_GE ) {
              key2.mv_data = keybuf;
              key2.mv_size = key->mv_size;
              AC_MEMCPY( keybuf, key->mv_data, key->mv_size );
              kptr = &key2;
       } else {
              kptr = key;
       }
       len = key->mv_size;
       rc = mdb_cursor_get( cursor, kptr, &data, opflag );

       /* skip presence key on range inequality lookups */
       while (rc == 0 && kptr->mv_size != len) {
              rc = mdb_cursor_get( cursor, kptr, &data, MDB_NEXT_NODUP );
       }
       /* If we're doing a LE compare and the new key is greater than
        * our search key, we're done
        */
       if (rc == 0 && get_flag == LDAP_FILTER_LE && memcmp( kptr->mv_data,
              key->mv_data, key->mv_size ) > 0 ) {
              rc = MDB_NOTFOUND;
       }
       if (rc == 0) {
              i = ids+1;
              rc = mdb_cursor_get( cursor, key, &data, MDB_GET_MULTIPLE );
              while (rc == 0) {
                     memcpy( i, data.mv_data, data.mv_size );
                     i += data.mv_size / sizeof(ID);
                     rc = mdb_cursor_get( cursor, key, &data, MDB_NEXT_MULTIPLE );
              }
              if ( rc == MDB_NOTFOUND ) rc = 0;
              ids[0] = i - &ids[1];
              /* On disk, a range is denoted by 0 in the first element */
              if (ids[1] == 0) {
                     if (ids[0] != MDB_IDL_RANGE_SIZE) {
                            Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
                                   "range size mismatch: expected %d, got %ld\n",
                                   MDB_IDL_RANGE_SIZE, ids[0], 0 );
                            mdb_cursor_close( cursor );
                            return -1;
                     }
                     MDB_IDL_RANGE( ids, ids[2], ids[3] );
              }
              data.mv_size = MDB_IDL_SIZEOF(ids);
       }

       if ( saved_cursor && rc == 0 ) {
              if ( !*saved_cursor )
                     *saved_cursor = cursor;
       }
       else
              mdb_cursor_close( cursor );

       if( rc == MDB_NOTFOUND ) {
              return rc;

       } else if( rc != 0 ) {
              Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
                     "get failed: %s (%d)\n",
                     mdb_strerror(rc), rc, 0 );
              return rc;

       } else if ( data.mv_size == 0 || data.mv_size % sizeof( ID ) ) {
              /* size not multiple of ID size */
              Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
                     "odd size: expected %ld multiple, got %ld\n",
                     (long) sizeof( ID ), (long) data.mv_size, 0 );
              return -1;

       } else if ( data.mv_size != MDB_IDL_SIZEOF(ids) ) {
              /* size mismatch */
              Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
                     "get size mismatch: expected %ld, got %ld\n",
                     (long) ((1 + ids[0]) * sizeof( ID )), (long) data.mv_size, 0 );
              return -1;
       }

       return rc;
}

Here is the call graph for this function:

Here is the caller graph for this function:

ID mdb_idl_first ( ID ids,
ID cursor 
)

Definition at line 872 of file idl.c.

{
       ID pos;

       if ( ids[0] == 0 ) {
              *cursor = NOID;
              return NOID;
       }

       if ( MDB_IDL_IS_RANGE( ids ) ) {
              if( *cursor < ids[1] ) {
                     *cursor = ids[1];
              }
              return *cursor;
       }

       if ( *cursor == 0 )
              pos = 1;
       else
              pos = mdb_idl_search( ids, *cursor );

       if( pos > ids[0] ) {
              return NOID;
       }

       *cursor = pos;
       return ids[pos];
}

Here is the call graph for this function:

Here is the caller graph for this function:

int mdb_idl_insert ( ID ids,
ID  id 
)

Definition at line 128 of file idl.c.

{
       unsigned x;

#if IDL_DEBUG > 1
       Debug( LDAP_DEBUG_ANY, "insert: %04lx at %d\n", (long) id, x, 0 );
       idl_dump( ids );
#elif IDL_DEBUG > 0
       idl_check( ids );
#endif

       if (MDB_IDL_IS_RANGE( ids )) {
              /* if already in range, treat as a dup */
              if (id >= MDB_IDL_RANGE_FIRST(ids) && id <= MDB_IDL_RANGE_LAST(ids))
                     return -1;
              if (id < MDB_IDL_RANGE_FIRST(ids))
                     ids[1] = id;
              else if (id > MDB_IDL_RANGE_LAST(ids))
                     ids[2] = id;
              return 0;
       }

       x = mdb_idl_search( ids, id );
       assert( x > 0 );

       if( x < 1 ) {
              /* internal error */
              return -2;
       }

       if ( x <= ids[0] && ids[x] == id ) {
              /* duplicate */
              return -1;
       }

       if ( ++ids[0] >= MDB_IDL_DB_MAX ) {
              if( id < ids[1] ) {
                     ids[1] = id;
                     ids[2] = ids[ids[0]-1];
              } else if ( ids[ids[0]-1] < id ) {
                     ids[2] = id;
              } else {
                     ids[2] = ids[ids[0]-1];
              }
              ids[0] = NOID;
       
       } else {
              /* insert id */
              AC_MEMCPY( &ids[x+1], &ids[x], (ids[0]-x) * sizeof(ID) );
              ids[x] = id;
       }

#if IDL_DEBUG > 1
       idl_dump( ids );
#elif IDL_DEBUG > 0
       idl_check( ids );
#endif

       return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int mdb_idl_insert_keys ( MDB_cursor cursor,
struct berval keys,
ID  id 
)

Definition at line 393 of file idl.c.

{
       MDB_val key, data;
       ID lo, hi, *i;
       char *err;
       int    rc, k;
       unsigned int flag = MDB_NODUPDATA;
#ifndef       MISALIGNED_OK
       int kbuf[2];
#endif

       {
              char buf[16];
              Debug( LDAP_DEBUG_ARGS,
                     "mdb_idl_insert_keys: %lx %s\n", 
                     (long) id, mdb_show_key( buf, keys->bv_val, keys->bv_len ), 0 );
       }

       assert( id != NOID );

#ifndef MISALIGNED_OK
       if (keys[0].bv_len & ALIGNER)
              kbuf[1] = 0;
#endif
       for ( k=0; keys[k].bv_val; k++ ) {
       /* Fetch the first data item for this key, to see if it
        * exists and if it's a range.
        */
#ifndef MISALIGNED_OK
       if (keys[k].bv_len & ALIGNER) {
              key.mv_size = sizeof(kbuf);
              key.mv_data = kbuf;
              memcpy(key.mv_data, keys[k].bv_val, keys[k].bv_len);
       } else
#endif
       {
              key.mv_size = keys[k].bv_len;
              key.mv_data = keys[k].bv_val;
       }
       rc = mdb_cursor_get( cursor, &key, &data, MDB_SET );
       err = "c_get";
       if ( rc == 0 ) {
              i = data.mv_data;
              memcpy(&lo, data.mv_data, sizeof(ID));
              if ( lo != 0 ) {
                     /* not a range, count the number of items */
                     size_t count;
                     rc = mdb_cursor_count( cursor, &count );
                     if ( rc != 0 ) {
                            err = "c_count";
                            goto fail;
                     }
                     if ( count >= MDB_IDL_DB_MAX ) {
                     /* No room, convert to a range */
                            lo = *i;
                            rc = mdb_cursor_get( cursor, &key, &data, MDB_LAST_DUP );
                            if ( rc != 0 && rc != MDB_NOTFOUND ) {
                                   err = "c_get last_dup";
                                   goto fail;
                            }
                            i = data.mv_data;
                            hi = *i;
                            /* Update hi/lo if needed */
                            if ( id < lo ) {
                                   lo = id;
                            } else if ( id > hi ) {
                                   hi = id;
                            }
                            /* delete the old key */
                            rc = mdb_cursor_del( cursor, MDB_NODUPDATA );
                            if ( rc != 0 ) {
                                   err = "c_del dups";
                                   goto fail;
                            }
                            /* Store the range */
                            data.mv_size = sizeof(ID);
                            data.mv_data = &id;
                            id = 0;
                            rc = mdb_cursor_put( cursor, &key, &data, 0 );
                            if ( rc != 0 ) {
                                   err = "c_put range";
                                   goto fail;
                            }
                            id = lo;
                            rc = mdb_cursor_put( cursor, &key, &data, 0 );
                            if ( rc != 0 ) {
                                   err = "c_put lo";
                                   goto fail;
                            }
                            id = hi;
                            rc = mdb_cursor_put( cursor, &key, &data, 0 );
                            if ( rc != 0 ) {
                                   err = "c_put hi";
                                   goto fail;
                            }
                     } else {
                     /* There's room, just store it */
                            if ( slapMode & SLAP_TOOL_QUICK )
                                   flag |= MDB_APPEND;
                            goto put1;
                     }
              } else {
                     /* It's a range, see if we need to rewrite
                      * the boundaries
                      */
                     lo = i[1];
                     hi = i[2];
                     if ( id < lo || id > hi ) {
                            /* position on lo */
                            rc = mdb_cursor_get( cursor, &key, &data, MDB_NEXT_DUP );
                            if ( id > hi ) {
                                   /* position on hi */
                                   rc = mdb_cursor_get( cursor, &key, &data, MDB_NEXT_DUP );
                            }
                            data.mv_size = sizeof(ID);
                            data.mv_data = &id;
                            /* Replace the current lo/hi */
                            rc = mdb_cursor_put( cursor, &key, &data, MDB_CURRENT );
                            if ( rc != 0 ) {
                                   err = "c_put lo/hi";
                                   goto fail;
                            }
                     }
              }
       } else if ( rc == MDB_NOTFOUND ) {
              flag &= ~MDB_APPEND;
put1:  data.mv_data = &id;
              data.mv_size = sizeof(ID);
              rc = mdb_cursor_put( cursor, &key, &data, flag );
              /* Don't worry if it's already there */
              if ( rc == MDB_KEYEXIST )
                     rc = 0;
              if ( rc ) {
                     err = "c_put id";
                     goto fail;
              }
       } else {
              /* initial c_get failed, nothing was done */
fail:
              Debug( LDAP_DEBUG_ANY, "=> mdb_idl_insert_keys: "
                     "%s failed: %s (%d)\n", err, mdb_strerror(rc), rc );
              break;
       }
       }
       return rc;
}

Here is the call graph for this function:

int mdb_idl_intersection ( ID a,
ID b 
)

Definition at line 662 of file idl.c.

{
       ID ida, idb;
       ID idmax, idmin;
       ID cursora = 0, cursorb = 0, cursorc;
       int swap = 0;

       if ( MDB_IDL_IS_ZERO( a ) || MDB_IDL_IS_ZERO( b ) ) {
              a[0] = 0;
              return 0;
       }

       idmin = IDL_MAX( MDB_IDL_FIRST(a), MDB_IDL_FIRST(b) );
       idmax = IDL_MIN( MDB_IDL_LAST(a), MDB_IDL_LAST(b) );
       if ( idmin > idmax ) {
              a[0] = 0;
              return 0;
       } else if ( idmin == idmax ) {
              a[0] = 1;
              a[1] = idmin;
              return 0;
       }

       if ( MDB_IDL_IS_RANGE( a ) ) {
              if ( MDB_IDL_IS_RANGE(b) ) {
              /* If both are ranges, just shrink the boundaries */
                     a[1] = idmin;
                     a[2] = idmax;
                     return 0;
              } else {
              /* Else swap so that b is the range, a is a list */
                     ID *tmp = a;
                     a = b;
                     b = tmp;
                     swap = 1;
              }
       }

       /* If a range completely covers the list, the result is
        * just the list. If idmin to idmax is contiguous, just
        * turn it into a range.
        */
       if ( MDB_IDL_IS_RANGE( b )
              && MDB_IDL_RANGE_FIRST( b ) <= MDB_IDL_RANGE_FIRST( a )
              && MDB_IDL_RANGE_LAST( b ) >= MDB_IDL_RANGE_LAST( a ) ) {
              if (idmax - idmin + 1 == a[0])
              {
                     a[0] = NOID;
                     a[1] = idmin;
                     a[2] = idmax;
              }
              goto done;
       }

       /* Fine, do the intersection one element at a time.
        * First advance to idmin in both IDLs.
        */
       cursora = cursorb = idmin;
       ida = mdb_idl_first( a, &cursora );
       idb = mdb_idl_first( b, &cursorb );
       cursorc = 0;

       while( ida <= idmax || idb <= idmax ) {
              if( ida == idb ) {
                     a[++cursorc] = ida;
                     ida = mdb_idl_next( a, &cursora );
                     idb = mdb_idl_next( b, &cursorb );
              } else if ( ida < idb ) {
                     ida = mdb_idl_next( a, &cursora );
              } else {
                     idb = mdb_idl_next( b, &cursorb );
              }
       }
       a[0] = cursorc;
done:
       if (swap)
              MDB_IDL_CPY( b, a );

       return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

ID mdb_idl_next ( ID ids,
ID cursor 
)

Definition at line 901 of file idl.c.

{
       if ( MDB_IDL_IS_RANGE( ids ) ) {
              if( ids[2] < ++(*cursor) ) {
                     return NOID;
              }
              return *cursor;
       }

       if ( ++(*cursor) <= ids[0] ) {
              return ids[*cursor];
       }

       return NOID;
}

Here is the caller graph for this function:

unsigned mdb_idl_search ( ID ids,
ID  id 
)

Definition at line 70 of file idl.c.

{
#define IDL_BINARY_SEARCH 1
#ifdef IDL_BINARY_SEARCH
       /*
        * binary search of id in ids
        * if found, returns position of id
        * if not found, returns first postion greater than id
        */
       unsigned base = 0;
       unsigned cursor = 1;
       int val = 0;
       unsigned n = ids[0];

#if IDL_DEBUG > 0
       idl_check( ids );
#endif

       while( 0 < n ) {
              unsigned pivot = n >> 1;
              cursor = base + pivot + 1;
              val = IDL_CMP( id, ids[cursor] );

              if( val < 0 ) {
                     n = pivot;

              } else if ( val > 0 ) {
                     base = cursor;
                     n -= pivot + 1;

              } else {
                     return cursor;
              }
       }
       
       if( val > 0 ) {
              ++cursor;
       }
       return cursor;

#else
       /* (reverse) linear search */
       int i;

#if IDL_DEBUG > 0
       idl_check( ids );
#endif

       for( i=ids[0]; i; i-- ) {
              if( id > ids[i] ) {
                     break;
              }
       }

       return i+1;
#endif
}

Here is the caller graph for this function:

void mdb_idl_sort ( ID ids,
ID tmp 
)

Definition at line 1017 of file idl.c.

{
       int *istack = (int *)tmp; /* Private stack, not used by caller */
       int i,j,k,l,ir,jstack;
       ID a, itmp;

       if ( MDB_IDL_IS_RANGE( ids ))
              return;

       ir = ids[0];
       l = 1;
       jstack = 0;
       for(;;) {
              if (ir - l < SMALL) {       /* Insertion sort */
                     for (j=l+1;j<=ir;j++) {
                            a = ids[j];
                            for (i=j-1;i>=1;i--) {
                                   if (ids[i] <= a) break;
                                   ids[i+1] = ids[i];
                            }
                            ids[i+1] = a;
                     }
                     if (jstack == 0) break;
                     ir = istack[jstack--];
                     l = istack[jstack--];
              } else {
                     k = (l + ir) >> 1;   /* Choose median of left, center, right */
                     SWAP(ids[k], ids[l+1]);
                     if (ids[l] > ids[ir]) {
                            SWAP(ids[l], ids[ir]);
                     }
                     if (ids[l+1] > ids[ir]) {
                            SWAP(ids[l+1], ids[ir]);
                     }
                     if (ids[l] > ids[l+1]) {
                            SWAP(ids[l], ids[l+1]);
                     }
                     i = l+1;
                     j = ir;
                     a = ids[l+1];
                     for(;;) {
                            do i++; while(ids[i] < a);
                            do j--; while(ids[j] > a);
                            if (j < i) break;
                            SWAP(ids[i],ids[j]);
                     }
                     ids[l+1] = ids[j];
                     ids[j] = a;
                     jstack += 2;
                     if (ir-i+1 >= j-1) {
                            istack[jstack] = ir;
                            istack[jstack-1] = i;
                            ir = j-1;
                     } else {
                            istack[jstack] = j-1;
                            istack[jstack-1] = l;
                            l = i;
                     }
              }
       }
}
int mdb_idl_union ( ID a,
ID b 
)

Definition at line 750 of file idl.c.

{
       ID ida, idb;
       ID cursora = 0, cursorb = 0, cursorc;

       if ( MDB_IDL_IS_ZERO( b ) ) {
              return 0;
       }

       if ( MDB_IDL_IS_ZERO( a ) ) {
              MDB_IDL_CPY( a, b );
              return 0;
       }

       if ( MDB_IDL_IS_RANGE( a ) || MDB_IDL_IS_RANGE(b) ) {
over:         ida = IDL_MIN( MDB_IDL_FIRST(a), MDB_IDL_FIRST(b) );
              idb = IDL_MAX( MDB_IDL_LAST(a), MDB_IDL_LAST(b) );
              a[0] = NOID;
              a[1] = ida;
              a[2] = idb;
              return 0;
       }

       ida = mdb_idl_first( a, &cursora );
       idb = mdb_idl_first( b, &cursorb );

       cursorc = b[0];

       /* The distinct elements of a are cat'd to b */
       while( ida != NOID || idb != NOID ) {
              if ( ida < idb ) {
                     if( ++cursorc > MDB_IDL_UM_MAX ) {
                            goto over;
                     }
                     b[cursorc] = ida;
                     ida = mdb_idl_next( a, &cursora );

              } else {
                     if ( ida == idb )
                            ida = mdb_idl_next( a, &cursora );
                     idb = mdb_idl_next( b, &cursorb );
              }
       }

       /* b is copied back to a in sorted order */
       a[0] = cursorc;
       cursora = 1;
       cursorb = 1;
       cursorc = b[0]+1;
       while (cursorb <= b[0] || cursorc <= a[0]) {
              if (cursorc > a[0])
                     idb = NOID;
              else
                     idb = b[cursorc];
              if (cursorb <= b[0] && b[cursorb] < idb)
                     a[cursora++] = b[cursorb++];
              else {
                     a[cursora++] = idb;
                     cursorc++;
              }
       }

       return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static char* mdb_show_key ( char *  buf,
void val,
size_t  len 
) [static]

Definition at line 247 of file idl.c.

{
       if ( len == 4 /* LUTIL_HASH_BYTES */ ) {
              unsigned char *c = val;
              sprintf( buf, "[%02x%02x%02x%02x]", c[0], c[1], c[2], c[3] );
              return buf;
       } else {
              return val;
       }
}

Here is the caller graph for this function: