source/include/eidl.h

0001 /** @file eidl.h
0002  *  @brief EXDB ID List header file.
0003  *
0004  *  This file was originally part of back-bdb but has been
0005  *  modified for use in libedb. Most of the macros defined
0006  *  in this file are unused, just left over from the original.
0007  *
0008  *  This file is only used internally in libedb and its definitions
0009  *  are not exposed publicly.
0010  */
0011 /* $OpenLDAP$ */
0012 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
0013  *
0014  * Copyright 2000-2016 The OpenLDAP Foundation.
0015  * Portions Copyright 2001-2017 Howard Chu, Symas Corp.
0016  * All rights reserved.
0017  *
0018  * Redistribution and use in source and binary forms, with or without
0019  * modification, are permitted only as authorized by the OpenLDAP
0020  * Public License.
0021  *
0022  * A copy of this license is available in the file LICENSE in the
0023  * top-level directory of the distribution or, alternatively, at
0024  * <http://www.OpenLDAP.org/license.html>.
0025  */
0026
0027 #ifndef _EDB_EIDL_H_
0028 #define _EDB_EIDL_H_
0029
0030 #include "exdb.h"
0031
0032 #ifdef __cplusplus
0033 extern "C" {
0034 #endif
0035
0036 /** @defgroup internal  EXDB Internals
0037  *  @{
0038  */
0039
0040 /** @defgroup idls  ID List Management
0041  *  @{
0042  */
0043     /** A generic unsigned ID number. These were entryIDs in back-bdb.
0044      *  Preferably it should have the same size as a pointer.
0045      */
0046 typedef edb_size_t EDB_ID;
0047
0048     /** An IDL is an ID List, a sorted array of IDs. The first
0049      * element of the array is a counter for how many actual
0050      * IDs are in the list. In the original back-bdb code, IDLs are
0051      * sorted in ascending order. For libedb IDLs are sorted in
0052      * descending order.
0053      */
0054 typedef EDB_ID *EDB_IDL;
0055
0056 /* IDL sizes - likely should be even bigger
0057  *   limiting factors: sizeof(ID), thread stack size
0058  */
0059 #ifdef EDB_VL32
0060 #define EDB_IDL_LOGN    14  /* DB_SIZE is 2^14, UM_SIZE is 2^15 */
0061 #else
0062 #define EDB_IDL_LOGN    16  /* DB_SIZE is 2^16, UM_SIZE is 2^17 */
0063 #endif
0064 #define EDB_IDL_DB_SIZE     (1<<EDB_IDL_LOGN)
0065 #define EDB_IDL_UM_SIZE     (1<<(EDB_IDL_LOGN+1))
0066
0067 #define EDB_IDL_DB_MAX      (EDB_IDL_DB_SIZE-1)
0068 #define EDB_IDL_UM_MAX      (EDB_IDL_UM_SIZE-1)
0069
0070 #define EDB_IDL_SIZEOF(ids)     (((ids)[0]+1) * sizeof(EDB_ID))
0071 #define EDB_IDL_IS_ZERO(ids) ( (ids)[0] == 0 )
0072 #define EDB_IDL_CPY( dst, src ) (memcpy( dst, src, EDB_IDL_SIZEOF( src ) ))
0073 #define EDB_IDL_FIRST( ids )    ( (ids)[1] )
0074 #define EDB_IDL_LAST( ids )     ( (ids)[(ids)[0]] )
0075
0076     /** Current max length of an #edb_eidl_alloc()ed IDL */
0077 #define EDB_IDL_ALLOCLEN( ids ) ( (ids)[-1] )
0078
0079     /** Append ID to IDL. The IDL must be big enough. */
0080 #define edb_eidl_xappend(idl, id) do { \
0081         EDB_ID *xidl = (idl), xlen = ++(xidl[0]); \
0082         xidl[xlen] = (id); \
0083     } while (0)
0084
0085     /** Search for an ID in an IDL.
0086      * @param[in] ids   The IDL to search.
0087      * @param[in] id    The ID to search for.
0088      * @return  The index of the first ID greater than or equal to \b id.
0089      */
0090 unsigned edb_eidl_search( EDB_IDL ids, EDB_ID id );
0091
0092     /** Allocate an IDL.
0093      * Allocates memory for an IDL of the given size.
0094      * @return  IDL on success, NULL on failure.
0095      */
0096 EDB_IDL edb_eidl_alloc(int num);
0097
0098     /** Free an IDL.
0099      * @param[in] ids   The IDL to free.
0100      */
0101 void edb_eidl_free(EDB_IDL ids);
0102
0103     /** Shrink an IDL.
0104      * Return the IDL to the default size if it has grown larger.
0105      * @param[in,out] idp   Address of the IDL to shrink.
0106      */
0107 void edb_eidl_shrink(EDB_IDL *idp);
0108
0109     /** Make room for num additional elements in an IDL.
0110      * @param[in,out] idp   Address of the IDL.
0111      * @param[in] num   Number of elements to make room for.
0112      * @return  0 on success, ENOMEM on failure.
0113      */
0114 int edb_eidl_need(EDB_IDL *idp, unsigned num);
0115
0116     /** Append an ID onto an IDL.
0117      * @param[in,out] idp   Address of the IDL to append to.
0118      * @param[in] id    The ID to append.
0119      * @return  0 on success, ENOMEM if the IDL is too large.
0120      */
0121 int edb_eidl_append( EDB_IDL *idp, EDB_ID id );
0122
0123     /** Append an IDL onto an IDL.
0124      * @param[in,out] idp   Address of the IDL to append to.
0125      * @param[in] app   The IDL to append.
0126      * @return  0 on success, ENOMEM if the IDL is too large.
0127      */
0128 int edb_eidl_append_list( EDB_IDL *idp, EDB_IDL app );
0129
0130     /** Append an ID range onto an IDL.
0131      * @param[in,out] idp   Address of the IDL to append to.
0132      * @param[in] id    The lowest ID to append.
0133      * @param[in] n     Number of IDs to append.
0134      * @return  0 on success, ENOMEM if the IDL is too large.
0135      */
0136 int edb_eidl_append_range( EDB_IDL *idp, EDB_ID id, unsigned n );
0137
0138     /** Merge an IDL onto an IDL. The destination IDL must be big enough.
0139      * @param[in] idl   The IDL to merge into.
0140      * @param[in] merge The IDL to merge.
0141      */
0142 void edb_eidl_xmerge( EDB_IDL idl, EDB_IDL merge );
0143
0144     /** Sort an IDL.
0145      * @param[in,out] ids   The IDL to sort.
0146      */
0147 void edb_eidl_sort( EDB_IDL ids );
0148
0149     /** An ID2 is an ID/pointer pair.
0150      */
0151 typedef struct EDB_ID2 {
0152     EDB_ID mid;     /**< The ID */
0153     void *mptr;     /**< The pointer */
0154 } EDB_ID2;
0155
0156     /** An ID2L is an ID2 List, a sorted array of ID2s.
0157      * The first element's \b mid member is a count of how many actual
0158      * elements are in the array. The \b mptr member of the first element is unused.
0159      * The array is sorted in ascending order by \b mid.
0160      */
0161 typedef EDB_ID2 *EDB_ID2L;
0162
0163     /** Search for an ID in an ID2L.
0164      * @param[in] ids   The ID2L to search.
0165      * @param[in] id    The ID to search for.
0166      * @return  The index of the first ID2 whose \b mid member is greater than or equal to \b id.
0167      */
0168 unsigned edb_mid2l_search( EDB_ID2L ids, EDB_ID id );
0169
0170
0171     /** Insert an ID2 into a ID2L.
0172      * @param[in,out] ids   The ID2L to insert into.
0173      * @param[in] id    The ID2 to insert.
0174      * @return  0 on success, -1 if the ID was already present in the ID2L.
0175      */
0176 int edb_mid2l_insert( EDB_ID2L ids, EDB_ID2 *id );
0177
0178     /** Append an ID2 into a ID2L.
0179      * @param[in,out] ids   The ID2L to append into.
0180      * @param[in] id    The ID2 to append.
0181      * @return  0 on success, -2 if the ID2L is too big.
0182      */
0183 int edb_mid2l_append( EDB_ID2L ids, EDB_ID2 *id );
0184
0185 #ifdef EDB_VL32
0186 typedef struct EDB_ID3 {
0187     EDB_ID mid;     /**< The ID */
0188     void *mptr;     /**< The pointer */
0189     unsigned int mcnt;      /**< Number of pages */
0190     unsigned int mref;      /**< Refcounter */
0191 } EDB_ID3;
0192
0193 typedef EDB_ID3 *EDB_ID3L;
0194
0195 unsigned edb_mid3l_search( EDB_ID3L ids, EDB_ID id );
0196 int edb_mid3l_insert( EDB_ID3L ids, EDB_ID3 *id );
0197
0198 #endif /* EDB_VL32 */
0199 /** @} */
0200 /** @} */
0201 #ifdef __cplusplus
0202 }
0203 #endif
0204 #endif  /* _EDB_EIDL_H_ */