5 * A pvector is a dynamic pointer array implemented as an access tree
6 * of index pages of 256 pointers.
12 * A pvector_page is an array of 256 void* items.
14 typedef void* pvector_page[256];
19 * A pvector index is ether viewed in whole as an unsigned 64-bit
20 * integer, or in levels as 8 unsigned char level indexes. This
21 * implementation assumes LE integer layout.
24 unsigned long whole; // 64-bit unsigned integer
25 unsigned char level[8];
31 * A pvector is a compound of a size and a pvector_page pointer, which
32 * when non-null points out the top-most page of the pvector. The
33 * number of levels is derived from its size with level 0 being the
34 * leaf level of actual content. E.g., a pvector larger than 256
35 * items, has at least two levels, and generally N levels may span up
36 * to 256^N content entries.
38 typedef struct _pvector {
39 unsigned long size; //!< Limit for the logical entries[]
40 pvector_page *entries; //!< Pointer to entries indexing
43 // Number of slots for page S
44 #define PV_LEVEL_SIZE(S) ((int)(exp( 256, (S) )))
46 // The indexing part for level part p in index i
47 #define PV_PART(p,i) (((unsigned char*)&i)[p])
50 * Find the next used slot at given index or later. With a reclaim
51 * function, it will be invoked for verifying that the item is
52 * actually in use, in which case it returns 1. Otherwise it should
53 * reclaim any memory for the item and return 0;
55 void **pvector_next_used(
56 pvector *pv,unsigned long *index,
57 int (*reclaim)(pvector *pv,unsigned long index,void *item,void *data),
61 * Function: int pvector_resize(
62 * pvector *pv,unsigned long new_size,
63 * int (*reclaim)(pvector *,unsigned long,void *item,void *data),
70 * Tries to resize the given pvector to a new size. This may result in
71 * the introduction or removal of indexing pages, so that the leveling
72 * is consistent with the pvector size. Thus, if it grows into a new
73 * 256^N level, then one or more new upper level pages are inserted as
74 * needed. If it shrinks below the current level, then top-level pages
77 * Also, if the new size is smaller than currently, then the now
78 * excess tail of entries is scanned for any used slots and the given
79 * reclaim function is invoked successively for these. The reclaim
80 * function must, in addition to memory-managing the entry, return 0
81 * upon success and non-zero to veto the attempted pvector size
82 * change. The data argument is passed on to the reclaim function.
84 * The pvector_resize function returns 0 on success, with the size
85 * duly changed. Otherwise the function retains the current size and
86 * returns -index-1 for the index of the veto-ed entry.
89 pvector *pv, unsigned long new_size,
90 int (*reclaim)(pvector *pv,unsigned long index,void *item,void *data),
94 * Function: void **pvector_entry(pvector *pv,unsigned long index)
95 * \param pv - the pvector record
96 * \param index - the slot index
98 * [pgix,epix] = modulo( index, pv->page );
100 * \returns a direct pointer to the slot of the given index in the
101 * array, or 0 if the index is beyond the array limits (0-limit). Note
102 * that slot pointers are only valid while the pvector size is
105 extern void **pvector_entry(pvector *pv,unsigned long index);
108 * Function: unsigned long pvector_size(pvector *pv)
109 * \param pv - the pvector record
110 * \returns the size of the pvector.
112 inline unsigned long pvector_size(pvector *pv) {
116 void pvector_set(pvector *pv,unsigned long index,void *value);
118 void *pvector_get(pvector *pv,unsigned long index);
120 void pvector_append(pvector *pv,void *value);
122 void pvector_copy(pvector *dst,unsigned long di,
123 pvector *src,unsigned long si,unsigned long n);
125 void pvector_dump(pvector *pv,
126 int (*itemdump)(const unsigned long ,const void *));
128 void pvector_qsort(pvector *pv,int (*compar)(const void *,const void *));
130 void pvector_iterate(pvector *pv,
131 int (*itemfn)(unsigned long,void*,void*),