Back to index

openldap  2.4.31
Classes | Defines | Typedefs | Functions
ID List Management
MDB Internals
Collaboration diagram for ID List Management:

Classes

struct  ID2
 An ID2 is an ID/pointer pair. More...

Defines

#define CMP(x, y)   ( (x) < (y) ? -1 : (x) > (y) )
#define SMALL   8
#define SWAP(a, b)   { itmp=(a); (a)=(b); (b)=itmp; }
#define NOID   (~(ID)0)
#define MDB_IDL_LOGN   16 /* DB_SIZE is 2^16, UM_SIZE is 2^17 */
#define MDB_IDL_DB_SIZE   (1<<MDB_IDL_LOGN)
#define MDB_IDL_UM_SIZE   (1<<(MDB_IDL_LOGN+1))
#define MDB_IDL_UM_SIZEOF   (MDB_IDL_UM_SIZE * sizeof(ID))
#define MDB_IDL_DB_MAX   (MDB_IDL_DB_SIZE-1)
#define MDB_IDL_UM_MAX   (MDB_IDL_UM_SIZE-1)
#define MDB_IDL_IS_RANGE(ids)   ((ids)[0] == NOID)
#define MDB_IDL_RANGE_SIZE   (3)
#define MDB_IDL_RANGE_SIZEOF   (MDB_IDL_RANGE_SIZE * sizeof(ID))
#define MDB_IDL_SIZEOF(ids)
#define MDB_IDL_RANGE_FIRST(ids)   ((ids)[1])
#define MDB_IDL_RANGE_LAST(ids)   ((ids)[2])
#define MDB_IDL_RANGE(ids, f, l)
#define MDB_IDL_ZERO(ids)
#define MDB_IDL_IS_ZERO(ids)   ( (ids)[0] == 0 )
#define MDB_IDL_IS_ALL(range, ids)
#define MDB_IDL_CPY(dst, src)   (memcpy( dst, src, MDB_IDL_SIZEOF( src ) ))
#define MDB_IDL_ID(bdb, ids, id)   MDB_IDL_RANGE( ids, id, ((bdb)->bi_lastid) )
#define MDB_IDL_ALL(bdb, ids)   MDB_IDL_RANGE( ids, 1, ((bdb)->bi_lastid) )
#define MDB_IDL_FIRST(ids)   ( (ids)[1] )
#define MDB_IDL_LAST(ids)
#define MDB_IDL_N(ids)

Typedefs

typedef size_t ID
 A generic ID number.
typedef IDIDL
 An IDL is an ID List, a sorted array of IDs.
typedef struct ID2 ID2
 An ID2 is an ID/pointer pair.
typedef ID2ID2L
 An ID2L is an ID2 List, a sorted array of ID2s.

Functions

IDL mdb_midl_alloc ()
 Allocate an IDL.
void mdb_midl_free (IDL ids)
 Free an IDL.
int mdb_midl_shrink (IDL *idp)
 Shrink an IDL.
int mdb_midl_append (IDL *idp, ID id)
 Append an ID onto an IDL.
int mdb_midl_append_list (IDL *idp, IDL app)
 Append an IDL onto an IDL.
void mdb_midl_sort (IDL ids)
 Sort an IDL.
unsigned mdb_mid2l_search (ID2L ids, ID id)
 Search for an ID in an ID2L.
int mdb_mid2l_insert (ID2L ids, ID2 *id)
 Insert an ID2 into a ID2L.

Class Documentation

struct ID2

An ID2 is an ID/pointer pair.

An ID2 is an ID/value pair.

Definition at line 152 of file midl.h.

Collaboration diagram for ID2:
Class Members
ID mid The ID.
void * mptr The pointer.
MDB_val mval The value.

Define Documentation

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

Definition at line 31 of file midl.c.

#define MDB_IDL_ALL (   bdb,
  ids 
)    MDB_IDL_RANGE( ids, 1, ((bdb)->bi_lastid) )

Definition at line 95 of file midl.h.

#define MDB_IDL_CPY (   dst,
  src 
)    (memcpy( dst, src, MDB_IDL_SIZEOF( src ) ))

Definition at line 92 of file midl.h.

#define MDB_IDL_DB_MAX   (MDB_IDL_DB_SIZE-1)

Definition at line 61 of file midl.h.

#define MDB_IDL_DB_SIZE   (1<<MDB_IDL_LOGN)

Definition at line 57 of file midl.h.

#define MDB_IDL_FIRST (   ids)    ( (ids)[1] )

Definition at line 97 of file midl.h.

#define MDB_IDL_ID (   bdb,
  ids,
  id 
)    MDB_IDL_RANGE( ids, id, ((bdb)->bi_lastid) )

Definition at line 94 of file midl.h.

#define MDB_IDL_IS_ALL (   range,
  ids 
)
Value:
( (ids)[0] == NOID \
       && (ids)[1] <= (range)[1] && (range)[2] <= (ids)[2] )

Definition at line 89 of file midl.h.

#define MDB_IDL_IS_RANGE (   ids)    ((ids)[0] == NOID)

Definition at line 65 of file midl.h.

#define MDB_IDL_IS_ZERO (   ids)    ( (ids)[0] == 0 )

Definition at line 88 of file midl.h.

#define MDB_IDL_LAST (   ids)
Value:
( MDB_IDL_IS_RANGE(ids) \
       ? (ids)[2] : (ids)[(ids)[0]] )

Definition at line 98 of file midl.h.

#define MDB_IDL_LOGN   16 /* DB_SIZE is 2^16, UM_SIZE is 2^17 */

Definition at line 56 of file midl.h.

#define MDB_IDL_N (   ids)
Value:
( MDB_IDL_IS_RANGE(ids) \
       ? ((ids)[2]-(ids)[1])+1 : (ids)[0] )

Definition at line 101 of file midl.h.

#define MDB_IDL_RANGE (   ids,
  f,
  l 
)
Value:
do { \
              (ids)[0] = NOID; \
              (ids)[1] = (f);  \
              (ids)[2] = (l);  \
       } while(0)

Definition at line 74 of file midl.h.

#define MDB_IDL_RANGE_FIRST (   ids)    ((ids)[1])

Definition at line 71 of file midl.h.

#define MDB_IDL_RANGE_LAST (   ids)    ((ids)[2])

Definition at line 72 of file midl.h.

#define MDB_IDL_RANGE_SIZE   (3)

Definition at line 66 of file midl.h.

#define MDB_IDL_RANGE_SIZEOF   (MDB_IDL_RANGE_SIZE * sizeof(ID))

Definition at line 67 of file midl.h.

#define MDB_IDL_SIZEOF (   ids)
Value:
((MDB_IDL_IS_RANGE(ids) \
       ? MDB_IDL_RANGE_SIZE : ((ids)[0]+1)) * sizeof(ID))

Definition at line 68 of file midl.h.

#define MDB_IDL_UM_MAX   (MDB_IDL_UM_SIZE-1)

Definition at line 63 of file midl.h.

#define MDB_IDL_UM_SIZE   (1<<(MDB_IDL_LOGN+1))

Definition at line 58 of file midl.h.

#define MDB_IDL_UM_SIZEOF   (MDB_IDL_UM_SIZE * sizeof(ID))

Definition at line 59 of file midl.h.

#define MDB_IDL_ZERO (   ids)
Value:
do { \
              (ids)[0] = 0; \
              (ids)[1] = 0; \
              (ids)[2] = 0; \
       } while(0)

Definition at line 81 of file midl.h.

#define NOID   (~(ID)0)

Definition at line 51 of file midl.h.

#define SMALL   8

Definition at line 184 of file midl.c.

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

Definition at line 185 of file midl.c.


Typedef Documentation

typedef size_t ID

A generic ID number.

These were entryIDs in back-bdb. Preferably it should have the same size as a pointer.

Definition at line 41 of file midl.h.

typedef struct ID2 ID2

An ID2 is an ID/pointer pair.

typedef ID2* ID2L

An ID2L is an ID2 List, a sorted array of ID2s.

The first element's mid member is a count of how many actual elements are in the array. The mptr member of the first element is unused. The array is sorted in ascending order by mid.

Definition at line 162 of file midl.h.

typedef ID* IDL

An IDL is an ID List, a sorted array of IDs.

The first element of the array is a counter for how many actual IDs are in the list. In the original back-bdb code, IDLs are sorted in ascending order. For libmdb IDLs are sorted in descending order.

Definition at line 49 of file midl.h.


Function Documentation

int mdb_mid2l_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 ID2L.

Definition at line 283 of file midl.c.

{
       unsigned x, i;

       x = mdb_mid2l_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_mid2l_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 248 of file midl.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 = 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:

Allocate an IDL.

Allocates memory for an IDL of a default size.

Returns:
IDL on success, NULL on failure.

Definition at line 120 of file midl.c.

{
       IDL ids = malloc((MDB_IDL_UM_MAX+1) * sizeof(ID));
       *ids++ = MDB_IDL_UM_MAX;
       return ids;
}

Here is the caller graph for this function:

int mdb_midl_append ( IDL idp,
ID  id 
)

Append an ID onto an IDL.

Parameters:
[in,out]idpAddress of the IDL to append to.
[in]idThe ID to append.
Returns:
0 on success, -1 if the IDL is too large.

Definition at line 144 of file midl.c.

{
       IDL ids = *idp;
       /* Too big? */
       if (ids[0] >= ids[-1]) {
              IDL idn = ids-1;
              /* grow it */
              idn = realloc(idn, (*idn + MDB_IDL_UM_MAX + 1) * sizeof(ID));
              if (!idn)
                     return -1;
              *idn++ += MDB_IDL_UM_MAX;
              ids = idn;
              *idp = ids;
       }
       ids[0]++;
       ids[ids[0]] = id;
       return 0;
}

Here is the caller graph for this function:

int mdb_midl_append_list ( IDL idp,
IDL  app 
)

Append an IDL onto an IDL.

Parameters:
[in,out]idpAddress of the IDL to append to.
[in]appThe IDL to append.
Returns:
0 on success, -1 if the IDL is too large.

Definition at line 163 of file midl.c.

{
       IDL ids = *idp;
       /* Too big? */
       if (ids[0] + app[0] >= ids[-1]) {
              IDL idn = ids-1;
              /* grow it */
              idn = realloc(idn, (*idn + app[-1]) * sizeof(ID));
              if (!idn)
                     return -1;
              *idn++ += app[-1];
              ids = idn;
              *idp = ids;
       }
       memcpy(&ids[ids[0]+1], &app[1], app[0] * sizeof(ID));
       ids[0] += app[0];
       return 0;
}

Here is the caller graph for this function:

Free an IDL.

Parameters:
[in]idsThe IDL to free.

Definition at line 127 of file midl.c.

{
       free(ids-1);
}

Here is the caller graph for this function:

int mdb_midl_shrink ( IDL idp)

Shrink an IDL.

Return the IDL to the default size if it has grown larger.

Parameters:
[in,out]idpAddress of the IDL to shrink.
Returns:
0 on no change, non-zero if shrunk.

Definition at line 132 of file midl.c.

{
       IDL ids = *idp;
       if (ids[-1] > MDB_IDL_UM_MAX) {
              ids = realloc(ids, (MDB_IDL_UM_MAX+1) * sizeof(ID));
              *ids++ = MDB_IDL_UM_MAX;
              *idp = ids;
              return 1;
       }
       return 0;
}

Here is the caller graph for this function:

Sort an IDL.

Parameters:
[in,out]idsThe IDL to sort.

Definition at line 188 of file midl.c.

{
       /* Max possible depth of int-indexed tree * 2 items/level */
       int istack[sizeof(int)*CHAR_BIT * 2];
       int i,j,k,l,ir,jstack;
       ID a, itmp;

       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;
                     }
              }
       }
}

Here is the caller graph for this function: