| 1 |
/** @file midl.h |
| 2 |
* @brief LMDB ID List header file. |
| 3 |
* |
| 4 |
* This file was originally part of back-bdb but has been |
| 5 |
* modified for use in libmdb. Most of the macros defined |
| 6 |
* in this file are unused, just left over from the original. |
| 7 |
* |
| 8 |
* This file is only used internally in libmdb and its definitions |
| 9 |
* are not exposed publicly. |
| 10 |
*/ |
| 11 |
/* $OpenLDAP$ */ |
| 12 |
/* This work is part of OpenLDAP Software <http://www.openldap.org/>. |
| 13 |
* |
| 14 |
* Copyright 2000-2019 The OpenLDAP Foundation. |
| 15 |
* Portions Copyright 2001-2018 Howard Chu, Symas Corp. |
| 16 |
* All rights reserved. |
| 17 |
* |
| 18 |
* Redistribution and use in source and binary forms, with or without |
| 19 |
* modification, are permitted only as authorized by the OpenLDAP |
| 20 |
* Public License. |
| 21 |
* |
| 22 |
* A copy of this license is available in the file LICENSE in the |
| 23 |
* top-level directory of the distribution or, alternatively, at |
| 24 |
* <http://www.OpenLDAP.org/license.html>. |
| 25 |
*/ |
| 26 |
|
| 27 |
#ifndef _MDB_MIDL_H_ |
| 28 |
#define _MDB_MIDL_H_ |
| 29 |
|
| 30 |
#include <stddef.h> |
| 31 |
|
| 32 |
#ifdef __cplusplus |
| 33 |
extern "C" { |
| 34 |
#endif |
| 35 |
|
| 36 |
/** @defgroup internal LMDB Internals |
| 37 |
* @{ |
| 38 |
*/ |
| 39 |
|
| 40 |
/** @defgroup idls ID List Management |
| 41 |
* @{ |
| 42 |
*/ |
| 43 |
/** A generic unsigned ID number. These were entryIDs in back-bdb. |
| 44 |
* Preferably it should have the same size as a pointer. |
| 45 |
*/ |
| 46 |
typedef size_t MDB_ID; |
| 47 |
|
| 48 |
/** An IDL is an ID List, a sorted array of IDs. The first |
| 49 |
* element of the array is a counter for how many actual |
| 50 |
* IDs are in the list. In the original back-bdb code, IDLs are |
| 51 |
* sorted in ascending order. For libmdb IDLs are sorted in |
| 52 |
* descending order. |
| 53 |
*/ |
| 54 |
typedef MDB_ID *MDB_IDL; |
| 55 |
|
| 56 |
/* IDL sizes - likely should be even bigger |
| 57 |
* limiting factors: sizeof(ID), thread stack size |
| 58 |
*/ |
| 59 |
#ifndef MDB_IDL_LOGN |
| 60 |
#define MDB_IDL_LOGN 16 /* DB_SIZE is 2^16, UM_SIZE is 2^17 */ |
| 61 |
#endif |
| 62 |
#define MDB_IDL_DB_SIZE (1<<MDB_IDL_LOGN) |
| 63 |
#define MDB_IDL_UM_SIZE (1<<(MDB_IDL_LOGN+1)) |
| 64 |
|
| 65 |
#define MDB_IDL_DB_MAX (MDB_IDL_DB_SIZE-1) |
| 66 |
#define MDB_IDL_UM_MAX (MDB_IDL_UM_SIZE-1) |
| 67 |
|
| 68 |
#define MDB_IDL_SIZEOF(ids) (((ids)[0]+1) * sizeof(MDB_ID)) |
| 69 |
#define MDB_IDL_IS_ZERO(ids) ( (ids)[0] == 0 ) |
| 70 |
#define MDB_IDL_CPY( dst, src ) (memcpy( dst, src, MDB_IDL_SIZEOF( src ) )) |
| 71 |
#define MDB_IDL_FIRST( ids ) ( (ids)[1] ) |
| 72 |
#define MDB_IDL_LAST( ids ) ( (ids)[(ids)[0]] ) |
| 73 |
|
| 74 |
/** Current max length of an #mdb_midl_alloc()ed IDL */ |
| 75 |
#define MDB_IDL_ALLOCLEN( ids ) ( (ids)[-1] ) |
| 76 |
|
| 77 |
/** Append ID to IDL. The IDL must be big enough. */ |
| 78 |
#define mdb_midl_xappend(idl, id) do { \ |
| 79 |
MDB_ID *xidl = (idl), xlen = ++(xidl[0]); \ |
| 80 |
xidl[xlen] = (id); \ |
| 81 |
} while (0) |
| 82 |
|
| 83 |
/** Search for an ID in an IDL. |
| 84 |
* @param[in] ids The IDL to search. |
| 85 |
* @param[in] id The ID to search for. |
| 86 |
* @return The index of the first ID greater than or equal to \b id. |
| 87 |
*/ |
| 88 |
unsigned mdb_midl_search( MDB_IDL ids, MDB_ID id ); |
| 89 |
|
| 90 |
/** Allocate an IDL. |
| 91 |
* Allocates memory for an IDL of the given size. |
| 92 |
* @return IDL on success, NULL on failure. |
| 93 |
*/ |
| 94 |
MDB_IDL mdb_midl_alloc(int num); |
| 95 |
|
| 96 |
/** Free an IDL. |
| 97 |
* @param[in] ids The IDL to free. |
| 98 |
*/ |
| 99 |
void mdb_midl_free(MDB_IDL ids); |
| 100 |
|
| 101 |
/** Shrink an IDL. |
| 102 |
* Return the IDL to the default size if it has grown larger. |
| 103 |
* @param[in,out] idp Address of the IDL to shrink. |
| 104 |
*/ |
| 105 |
void mdb_midl_shrink(MDB_IDL *idp); |
| 106 |
|
| 107 |
/** Make room for num additional elements in an IDL. |
| 108 |
* @param[in,out] idp Address of the IDL. |
| 109 |
* @param[in] num Number of elements to make room for. |
| 110 |
* @return 0 on success, ENOMEM on failure. |
| 111 |
*/ |
| 112 |
int mdb_midl_need(MDB_IDL *idp, unsigned num); |
| 113 |
|
| 114 |
/** Append an ID onto an IDL. |
| 115 |
* @param[in,out] idp Address of the IDL to append to. |
| 116 |
* @param[in] id The ID to append. |
| 117 |
* @return 0 on success, ENOMEM if the IDL is too large. |
| 118 |
*/ |
| 119 |
int mdb_midl_append( MDB_IDL *idp, MDB_ID id ); |
| 120 |
|
| 121 |
/** Append an IDL onto an IDL. |
| 122 |
* @param[in,out] idp Address of the IDL to append to. |
| 123 |
* @param[in] app The IDL to append. |
| 124 |
* @return 0 on success, ENOMEM if the IDL is too large. |
| 125 |
*/ |
| 126 |
int mdb_midl_append_list( MDB_IDL *idp, MDB_IDL app ); |
| 127 |
|
| 128 |
/** Append an ID range onto an IDL. |
| 129 |
* @param[in,out] idp Address of the IDL to append to. |
| 130 |
* @param[in] id The lowest ID to append. |
| 131 |
* @param[in] n Number of IDs to append. |
| 132 |
* @return 0 on success, ENOMEM if the IDL is too large. |
| 133 |
*/ |
| 134 |
int mdb_midl_append_range( MDB_IDL *idp, MDB_ID id, unsigned n ); |
| 135 |
|
| 136 |
/** Merge an IDL onto an IDL. The destination IDL must be big enough. |
| 137 |
* @param[in] idl The IDL to merge into. |
| 138 |
* @param[in] merge The IDL to merge. |
| 139 |
*/ |
| 140 |
void mdb_midl_xmerge( MDB_IDL idl, MDB_IDL merge ); |
| 141 |
|
| 142 |
/** Sort an IDL. |
| 143 |
* @param[in,out] ids The IDL to sort. |
| 144 |
*/ |
| 145 |
void mdb_midl_sort( MDB_IDL ids ); |
| 146 |
|
| 147 |
/** An ID2 is an ID/pointer pair. |
| 148 |
*/ |
| 149 |
typedef struct MDB_ID2 { |
| 150 |
MDB_ID mid; /**< The ID */ |
| 151 |
void *mptr; /**< The pointer */ |
| 152 |
} MDB_ID2; |
| 153 |
|
| 154 |
/** An ID2L is an ID2 List, a sorted array of ID2s. |
| 155 |
* The first element's \b mid member is a count of how many actual |
| 156 |
* elements are in the array. The \b mptr member of the first element is unused. |
| 157 |
* The array is sorted in ascending order by \b mid. |
| 158 |
*/ |
| 159 |
typedef MDB_ID2 *MDB_ID2L; |
| 160 |
|
| 161 |
/** Search for an ID in an ID2L. |
| 162 |
* @param[in] ids The ID2L to search. |
| 163 |
* @param[in] id The ID to search for. |
| 164 |
* @return The index of the first ID2 whose \b mid member is greater than or equal to \b id. |
| 165 |
*/ |
| 166 |
unsigned mdb_mid2l_search( MDB_ID2L ids, MDB_ID id ); |
| 167 |
|
| 168 |
|
| 169 |
/** Insert an ID2 into a ID2L. |
| 170 |
* @param[in,out] ids The ID2L to insert into. |
| 171 |
* @param[in] id The ID2 to insert. |
| 172 |
* @return 0 on success, -1 if the ID was already present in the ID2L. |
| 173 |
*/ |
| 174 |
int mdb_mid2l_insert( MDB_ID2L ids, MDB_ID2 *id ); |
| 175 |
|
| 176 |
/** Append an ID2 into a ID2L. |
| 177 |
* @param[in,out] ids The ID2L to append into. |
| 178 |
* @param[in] id The ID2 to append. |
| 179 |
* @return 0 on success, -2 if the ID2L is too big. |
| 180 |
*/ |
| 181 |
int mdb_mid2l_append( MDB_ID2L ids, MDB_ID2 *id ); |
| 182 |
|
| 183 |
/** @} */ |
| 184 |
/** @} */ |
| 185 |
#ifdef __cplusplus |
| 186 |
} |
| 187 |
#endif |
| 188 |
#endif /* _MDB_MIDL_H_ */ |