Back to index

openldap  2.4.31
Classes | Defines | Typedefs | Functions
idl.h File Reference
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

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

Defines

#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)   (AC_MEMCPY( dst, src, MDB_IDL_SIZEOF( src ) ))
#define MDB_IDL_ID(mdb, ids, id)   MDB_IDL_RANGE( ids, id, NOID )
#define MDB_IDL_ALL(ids)   MDB_IDL_RANGE( ids, 1, NOID )
#define MDB_IDL_FIRST(ids)   ( (ids)[1] )
#define MDB_IDL_LAST(ids)
#define MDB_IDL_N(ids)

Typedefs

typedef struct ID2 ID2
 An ID2 is an ID/value pair.
typedef ID2ID2L
 An ID2L is an ID2 List, a sorted array of ID2s.
typedef struct IdScopes IdScopes

Functions

LDAP_BEGIN_DECL 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.

Class Documentation

struct IdScopes

Definition at line 85 of file idl.h.

Collaboration diagram for IdScopes:
Class Members
ID id
MDB_cursor * mc
MDB_txn * mt
int nscope
int numrdns
ID2L scopes

Define Documentation

#define MDB_IDL_ALL (   ids)    MDB_IDL_RANGE( ids, 1, NOID )

Definition at line 62 of file idl.h.

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

Definition at line 59 of file idl.h.

#define MDB_IDL_DB_MAX   (MDB_IDL_DB_SIZE-1)

Definition at line 28 of file idl.h.

#define MDB_IDL_DB_SIZE   (1<<MDB_IDL_LOGN)

Definition at line 24 of file idl.h.

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

Definition at line 64 of file idl.h.

#define MDB_IDL_ID (   mdb,
  ids,
  id 
)    MDB_IDL_RANGE( ids, id, NOID )

Definition at line 61 of file idl.h.

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

Definition at line 56 of file idl.h.

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

Definition at line 32 of file idl.h.

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

Definition at line 55 of file idl.h.

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

Definition at line 65 of file idl.h.

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

Definition at line 23 of file idl.h.

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

Definition at line 68 of file idl.h.

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

Definition at line 41 of file idl.h.

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

Definition at line 38 of file idl.h.

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

Definition at line 39 of file idl.h.

#define MDB_IDL_RANGE_SIZE   (3)

Definition at line 33 of file idl.h.

#define MDB_IDL_RANGE_SIZEOF   (MDB_IDL_RANGE_SIZE * sizeof(ID))

Definition at line 34 of file idl.h.

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

Definition at line 35 of file idl.h.

#define MDB_IDL_UM_MAX   (MDB_IDL_UM_SIZE-1)

Definition at line 30 of file idl.h.

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

Definition at line 25 of file idl.h.

#define MDB_IDL_UM_SIZEOF   (MDB_IDL_UM_SIZE * sizeof(ID))

Definition at line 26 of file idl.h.

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

Definition at line 48 of file idl.h.


Typedef Documentation

typedef struct ID2 ID2

An ID2 is an ID/value 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 83 of file idl.h.

typedef struct IdScopes IdScopes

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:

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: