Loading...
Searching...
No Matches
ID List Management
LMDB Internals

## Data Structures

struct | MDB_ID2

## Macros

#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_DB_MAX (MDB_IDL_DB_SIZE-1)
#define | MDB_IDL_UM_MAX (MDB_IDL_UM_SIZE-1)
#define | MDB_IDL_SIZEOF(ids)
#define | MDB_IDL_IS_ZERO(ids)
#define | MDB_IDL_CPY(dst, src)
#define | MDB_IDL_FIRST(ids)
#define | MDB_IDL_LAST(ids)
#define | MDB_IDL_ALLOCLEN(ids)
#define | mdb_midl_xappend(idl, id)
#define | CMP(x, y)
#define | SMALL 8
#define | MIDL_SWAP(a, b)

## Typedefs

typedef size_t | MDB_ID
typedef MDB_ID * | MDB_IDL
typedef MDB_ID2 * | MDB_ID2L

## Functions

unsigned | mdb_midl_search (MDB_IDL ids, MDB_ID id)
MDB_IDL | mdb_midl_alloc (int num)
void | mdb_midl_free (MDB_IDL ids)
void | mdb_midl_shrink (MDB_IDL *idp)
int | mdb_midl_need (MDB_IDL *idp, unsigned num)
int | mdb_midl_append (MDB_IDL *idp, MDB_ID id)
int | mdb_midl_append_list (MDB_IDL *idp, MDB_IDL app)
int | mdb_midl_append_range (MDB_IDL *idp, MDB_ID id, unsigned n)
void | mdb_midl_xmerge (MDB_IDL idl, MDB_IDL merge)
void | mdb_midl_sort (MDB_IDL ids)
unsigned | mdb_mid2l_search (MDB_ID2L ids, MDB_ID id)
int | mdb_mid2l_insert (MDB_ID2L ids, MDB_ID2 *id)
int | mdb_mid2l_append (MDB_ID2L ids, MDB_ID2 *id)
static int | mdb_midl_grow (MDB_IDL *idp, int num)

## Detailed Description

## Data Structure Documentation

## MDB_ID2

struct MDB_ID2

An ID2 is an ID/pointer pair.

### Data Fields

MDB_ID | mid
void * | mptr

#### Field Documentation

## mid

MDB_ID MDB_ID2::mid

The ID

## mptr

void* MDB_ID2::mptr

The pointer

## Macro Definition Documentation

## MDB_IDL_SIZEOF

#define MDB_IDL_SIZEOF | ( |  | ids | ) |

Value:
(((ids)[0]+1) * sizeof(MDB_ID))
MDB_ID
size_t MDB_ID
Definition midl.h:46

## MDB_IDL_IS_ZERO

#define MDB_IDL_IS_ZERO | ( |  | ids | ) |

Value:
( (ids)[0] == 0 )

## MDB_IDL_CPY

#define MDB_IDL_CPY | ( |  | dst,
|  |  | src )

Value:
(memcpy( dst, src, MDB_IDL_SIZEOF( src ) ))

## MDB_IDL_FIRST

#define MDB_IDL_FIRST | ( |  | ids | ) |

Value:
( (ids)[1] )

## MDB_IDL_LAST

#define MDB_IDL_LAST | ( |  | ids | ) |

Value:
( (ids)[(ids)[0]] )

## MDB_IDL_ALLOCLEN

#define MDB_IDL_ALLOCLEN | ( |  | ids | ) |

Value:
( (ids)[-1] )

Current max length of an mdb_midl_alloc()ed IDL

## mdb_midl_xappend

#define mdb_midl_xappend | ( |  | idl,
|  |  | id )

Value:
do { \
MDB_ID *xidl = (idl), xlen = ++(xidl[0]); \
xidl[xlen] = (id); \
} while (0)

Append ID to IDL. The IDL must be big enough.

## CMP

#define CMP | ( |  | x,
|  |  | y )

Value:
( (x) < (y) ? -1 : (x) > (y) )

## MIDL_SWAP

#define MIDL_SWAP | ( |  | a,
|  |  | b )

Value:
{ itmp=(a); (a)=(b); (b)=itmp; }

## Typedef Documentation

## MDB_ID

typedef size_t MDB_ID

A generic unsigned ID number. These were entryIDs in back-bdb. Preferably it should have the same size as a pointer.

## MDB_IDL

typedef MDB_ID* MDB_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.

## MDB_ID2L

typedef MDB_ID2* MDB_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.

## Function Documentation

## mdb_midl_search()

unsigned mdb_midl_search | ( | MDB_IDL | ids,
|  | MDB_ID | id )

Search for an ID in an IDL.

Parameters

  [in] | ids | The IDL to search.
  [in] | id | The ID to search for.

Returns
  The index of the first ID greater than or equal to id.

## mdb_midl_alloc()

MDB_IDL mdb_midl_alloc | ( | int | num | ) |

Allocate an IDL. Allocates memory for an IDL of the given size.

Returns
  IDL on success, NULL on failure.

## mdb_midl_free()

void mdb_midl_free | ( | MDB_IDL | ids | ) |

Free an IDL.

Parameters

  [in] | ids | The IDL to free.

## mdb_midl_shrink()

void mdb_midl_shrink | ( | MDB_IDL * | idp | ) |

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

Parameters

  [in,out] | idp | Address of the IDL to shrink.

## mdb_midl_need()

int mdb_midl_need | ( | MDB_IDL * | idp,
|  | unsigned | num )

Make room for num additional elements in an IDL.

Parameters

  [in,out] | idp | Address of the IDL.
  [in] | num | Number of elements to make room for.

Returns
  0 on success, ENOMEM on failure.

## mdb_midl_append()

int mdb_midl_append | ( | MDB_IDL * | idp,
|  | MDB_ID | id )

Append an ID onto an IDL.

Parameters

  [in,out] | idp | Address of the IDL to append to.
  [in] | id | The ID to append.

Returns
  0 on success, ENOMEM if the IDL is too large.

## mdb_midl_append_list()

int mdb_midl_append_list | ( | MDB_IDL * | idp,
|  | MDB_IDL | app )

Append an IDL onto an IDL.

Parameters

  [in,out] | idp | Address of the IDL to append to.
  [in] | app | The IDL to append.

Returns
  0 on success, ENOMEM if the IDL is too large.

## mdb_midl_append_range()

int mdb_midl_append_range | ( | MDB_IDL * | idp,
|  | MDB_ID | id,
|  | unsigned | n )

Append an ID range onto an IDL.

Parameters

  [in,out] | idp | Address of the IDL to append to.
  [in] | id | The lowest ID to append.
  [in] | n | Number of IDs to append.

Returns
  0 on success, ENOMEM if the IDL is too large.

## mdb_midl_xmerge()

void mdb_midl_xmerge | ( | MDB_IDL | idl,
|  | MDB_IDL | merge )

Merge an IDL onto an IDL. The destination IDL must be big enough.

Parameters

  [in] | idl | The IDL to merge into.
  [in] | merge | The IDL to merge.

## mdb_midl_sort()

void mdb_midl_sort | ( | MDB_IDL | ids | ) |

Sort an IDL.

Parameters

  [in,out] | ids | The IDL to sort.

## mdb_mid2l_search()

unsigned mdb_mid2l_search | ( | MDB_ID2L | ids,
|  | MDB_ID | id )

Search for an ID in an ID2L.

Parameters

  [in] | ids | The ID2L to search.
  [in] | id | The ID to search for.

Returns
  The index of the first ID2 whose mid member is greater than or equal to id.

## mdb_mid2l_insert()

int mdb_mid2l_insert | ( | MDB_ID2L | ids,
|  | MDB_ID2 * | id )

Insert an ID2 into a ID2L.

Parameters

  [in,out] | ids | The ID2L to insert into.
  [in] | id | The ID2 to insert.

Returns
  0 on success, -1 if the ID was already present in the ID2L.

## mdb_mid2l_append()

int mdb_mid2l_append | ( | MDB_ID2L | ids,
|  | MDB_ID2 * | id )

Append an ID2 into a ID2L.

Parameters

  [in,out] | ids | The ID2L to append into.
  [in] | id | The ID2 to append.

Returns
  0 on success, -2 if the ID2L is too big.