5 * A qvector is a dynamic pointer array implemented as an access tree
6 * of index pages. The indexing is done using "unsigned long" indexes.
11 * This is the general indexing used for qvector access.
13 typedef unsigned long qvector_index;
16 * Macro: QV_INDEX_BITS
17 * This defines the number of bits of a qvector index
19 #define QV_INDEX_BITS sizeof( qvector_index )
22 * Macro: QV_LEVEL_BITS
23 * This defines the number of bits in the indexing bit field.
25 #define QV_LEVEL_BITS 4
28 * Macro: QV_INDEX_FIELDS
29 * This defines the number of bit fields in an qvector index
31 #define QV_INDEX_FIELDS ( ( QV_INDEX_BITS - 1 ) / QV_LEVEL_BITS + 1 )
35 * This defines the number of slots spanned by an index level
37 #define QV_SLOTS ( 1 << QV_LEVEL_BITS )
42 * A qvector_page is an array of 16 void* items.
44 typedef void* qvector_page[ QV_SLOTS ];
48 * This is QV_LEVEL_BITS size bit field
50 typedef struct { int bits:QV_LEVEL_BITS; } qvector_field;
53 * Type: qvector_indexing
55 * A qvector index is ether viewed in whole as an QV_INDEX_BITS wide
56 * unsigned, or in levels as a packed array of qvector_field index
57 * parts. This implementation assumes LE integer layout.
60 qvector_index whole; // as a whole
61 qvector_field level[ QV_INDEX_FIELDS ]; // qua bits fields
67 * A qvector is a compound of a size and a qvector_page pointer, which
68 * when non-null points out the top-most page of the qvector. The
69 * number of levels is derived from its size with level 0 being the
70 * leaf level of actual content. E.g., a qvector larger than 16
71 * items, has at least two levels, and generally N levels may span up
72 * to 16^N content entries.
74 typedef struct _qvector {
75 qvector_index size; //!< Limit for the logical entries[]
76 qvector_page *entries; //!< Pointer to entries indexing
79 // Number of slots for page S
80 #define PV_LEVEL_SIZE(S) ((int)(exp( 16, (S) )))
82 // The indexing part for level part p in index i
83 #define PV_PART(i,p) (((qvector_indexing*)(i))->level[ p ].bits)
86 * Find the next used slot at given index or later. With a reclaim
87 * function, it will be invoked for verifying that the item is
88 * actually in use, in which case it returns 1. Otherwise it should
89 * reclaim any memory for the item and return 0;
91 void **qvector_next_used(
92 qvector *pv,qvector_index *index,
93 int (*reclaim)(qvector *pv,qvector_index index,void *item,void *data),
97 * Function: int qvector_resize(
98 * qvector *pv,qvector_index new_size,
99 * int (*reclaim)(qvector *,qvector_index,void *item,void *data),
106 * Tries to resize the given qvector to a new size. This may result in
107 * the introduction or removal of indexing pages, so that the leveling
108 * is consistent with the qvector size. Thus, if it grows into a new
109 * 16^N level, then one or more new upper level pages are inserted as
110 * needed. If it shrinks below the current level, then top-level pages
113 * Also, if the new size is smaller than currently, then the now
114 * excess tail of entries is scanned for any used slots and the given
115 * reclaim function is invoked successively for these. The reclaim
116 * function must, in addition to memory-managing the entry, return 0
117 * upon success and non-zero to veto the attempted qvector size
118 * change. The data argument is passed on to the reclaim function.
120 * The qvector_resize function returns 0 on success, with the size
121 * duly changed. Otherwise the function retains the current size and
122 * returns -index-1 for the index of the veto-ed entry.
125 qvector *pv, qvector_index new_size,
126 int (*reclaim)(qvector *pv,qvector_index index,void *item,void *data),
130 * Function: void **qvector_entry(qvector *pv,qvector_index index)
131 * \param pv - the qvector record
132 * \param index - the slot index
134 * [pgix,epix] = modulo( index, pv->page );
136 * \returns a direct pointer to the slot of the given index in the
137 * array, or 0 if the index is beyond the array limits (0-limit). Note
138 * that slot pointers are only valid while the qvector size is
141 extern void **qvector_entry(qvector *pv,qvector_index index);
144 * Function: qvector_index qvector_size(qvector *pv)
145 * \param pv - the qvector record
146 * \returns the size of the qvector.
148 inline qvector_index qvector_size(qvector *pv) {
152 void qvector_set(qvector *pv,qvector_index index,void *value);
154 void *qvector_get(qvector *pv,qvector_index index);
156 void qvector_append(qvector *pv,void *value);
158 void qvector_copy(qvector *dst,qvector_index di,
159 qvector *src,qvector_index si,qvector_index n);
161 void qvector_dump(qvector *pv,
162 int (*itemdump)(const qvector_index ,const void *));
164 void qvector_qsort(qvector *pv,int (*compar)(const void *,const void *));
166 void qvector_iterate(qvector *pv,
167 int (*itemfn)(qvector_index,void*,void*),