5 * A pvector is a dynamic pointer array implemented as an access tree
6 * of index pages of 256 pointers.
14 * A pvector_page is an array of 256 void* items.
16 typedef void* pvector_page[256];
21 * A pvector index is ether viewed in whole as an unsigned 64-bit
22 * integer, or in levels as 8 unsigned char level indexes. This
23 * implementation assumes LE integer layout.
27 unsigned char level[4];
33 * A pvector is a compound of a size and a pvector_page pointer, which
34 * when non-null points out the top-most page of the pvector. The
35 * number of levels is derived from its size with level 0 being the
36 * leaf level of actual content. E.g., a pvector larger than 256
37 * items, has at least two levels, and generally N levels may span up
38 * to 256^N content entries.
40 typedef struct _pvector {
41 unsigned int size; //!< Limit for the logical entries[]
42 pvector_page *entries; //!< Pointer to entries indexing
45 // Number of page levels for size S
46 #define PV_LEVELS(S) ((int)(( 39 - __builtin_clz( ((S)-1) | 1) ) / 8 ))
48 #define PV_LEVEL_SIZE(S) ((int)(exp( 256, (S) )))
50 // The indexing part for level part p in index i
51 #define PV_PART(p,i) (((unsigned char*)&i)[p])
54 * Function: int pvector_resize( pvector *pv,unsigned int new_size,
55 * int (*reclaim)(pvector *,int,void*) )
60 * Tries to resize the given pvector to a new size. This may result in
61 * the introduction or removal of indexing pages, so that the leveling
62 * is consistent with the pvector size. Thus, if it grows into a new
63 * 256^N level, then one or more new upper level pages are inserted as
64 * needed. If it shrinks below the current level, then top-level pages
67 * Also, if the new size is smaller than currently, then the now
68 * excess tail of entries is scanned for any used slots and the given
69 * reclaim function is invoked successively for these. The reclaim
70 * function must, in addition to memory-managing the entry, return 0
71 * upon success and non-zero to veto the attempted pvector size
74 * The pvector_resize function returns 0 on success, with the size
75 * duly changed. Otherwise the function retains the current size and
76 * returns -index-1 for the index of the veto-ed entry.
79 pvector *pv,unsigned int new_size,
80 int (*reclaim)(pvector *,int,void*) );
83 * Function: void **pvector_entry(pvector *pv,unsigned int index)
84 * \param pv - the pvector record
85 * \param index - the slot index
87 * [pgix,epix] = modulo( index, pv->page );
89 * \returns a direct pointer to the slot of the given index in the
90 * array, or 0 if the index is beyond the array limits (0-limit). Note
91 * that slot pointers are only valid while the pvector size is
94 extern void **pvector_entry(pvector *pv,unsigned int index);
97 * Function: unsigned int pvector_size(pvector *pv)
98 * \param pv - the pvector record
99 * \returns the size of the pvector.
101 inline unsigned int pvector_size(pvector *pv) {
105 void pvector_set(pvector *pv,unsigned int index,void *value);
107 void *pvector_get(pvector *pv,unsigned int index);