[rrq/rrqmisc.git] / vector / vector.h

#ifndef vector_H
#define vector_H

/** \file
 *
 * A vector is a dynamic pointer array implemented as an access tree
 * of index pages. The indexing is done using "unsigned long" indexes,
 * and the level 0 index corresponds to actual items.
 *
 * Actual vectors are assigned a leveling variant which defines the
 * index page size for the vector. This must not be changed for a
 * vector with entries.
 */

/**
 * \brief This is the general indexing used for vector access.
 *
 * \related vector
 */
typedef unsigned long vector_index;

/**
 * \brief A vector_page is an array of void* items. Its size depends
 * on the applicable vector variant.
 *
 * \related vector
 */
typedef void* vector_page[];

/**
 * \brief The implementation variants.
 *
 * - byte_index_levels (0) has 8-bit indexing parts and index pages
 *   with 256 pointers,
 *
 * - nibble_index_levels (1) has 4-bit indexing parts and index pages
 *   with 16 pointers,
 *
 * - bitpair_index_levels (2) has 2-bit indexing parts and index pages
 *   with 4 pointers,
 *
 * - single_index_level (3) has a single page that is sized as the
 *   vector.
 *
 * The first three variants are managed by adding/removing full pages
 * of the indexing tree upon resize and access. The single_index_level
 * variant is managed by using realloc upon resize. In all cases
 * shrinking a vector might mean to reclaim items about to be "lost",
 * if any, via a provided item reclaim callback function. The callback
 * function may then also veto the shrinking.
 *
 * \related vector
 */
enum vector_variant {
    byte_index_levels = 0,
    nibble_index_levels = 1,
    bitpair_index_levels = 2,
    single_index_level = 3
};

/**
 * A vector struct is the "foot part" of a representation that
 * constitutes the implementation variant for a vector abstraction. It
 * holds the variant indicator, the intended slot size and a root
 * pointer for the indexing structure, which consist of indexing pages
 * according to the variant.
 */
typedef struct {
    /**
     * The indexing variant.
     */
    enum vector_variant variant;

    /**
     * The size of the vector.
     */
    vector_index size;

    /**
     * The root page of the indexing tree.
     */
    vector_page *entries;
} vector;

/**
 * \brief Return the number of slots spanned by an index level for the
 * given vector variant.
 *
 * - 0 indicates 8-bit index parts, and 256 page slots
 * - 1 indicates 4-bit index parts, and 16 page slots
 * - 2 indicates 2-bit index parts, and 4 page slots
 * - 3 indicates 64-bit index parts, and 1 page level following the size
 * 
 * The type 3 vector is managed by using realloc.
 * \related vector
 */
extern unsigned long VECTOR_SLOTS(vector *pv);

/**
 * \brief Find the nearest used (non-null) slot at given or higher
 * index.
 *
 * \param pv is the vector concerned.
 *
 * \param index is the index to change.
 *
 * \returns a pointer to the first non-null vector slot from the given
 * index, and *index set accordingly. If no non-null slot is found,
 * the 0 is returned and *index is set to the vector size.
 *
 * \related vector
 */
extern void **vector_next_used(vector *pv,vector_index *index);

/**
 * \brief Find the nearest used (non-null) slot at given or lower
 * index.
 *
 * \param pv is the vector concerned.
 *
 * \param index is the index to change.
 *
 * \returns a pointer to the first non-null vector slot from the given
 * index, and *index set accordingly. If no non-null slot is found,
 * the 0 is returned and *index is set to the vector size.
 *
 * \related vector
 */
extern void **vector_prev_used(vector *pv,vector_index *index);

/**
 * \brief Resize a vector.
 *
 * \param pv is the vector concerned.
 *
 * \param new_size is the new size it should have,
 *
 * \param reclaim is used upon shrinking in size for handling any
 * current items above the new size, or vetoing the attempted resize.
 *
 * \param data is passed on the the reclaim function to use as context
 * as needed.
 *
 * \returns the index of a resizing veto any, or <0 otherwise, with -1
 * indicating success and -2 indicating OOM.
 *
 * This function attempts to resize the given vector to a new size.
 * This may result in the introduction or removal of indexing pages,
 * so that the index tree leveling is consistent with the vector size.
 * Thus, if it grows into a new level, then one or more new upper
 * level pages are inserted as needed. If it shrinks below the current
 * level, then top-level pages are removed.
 *
 * Also, if the new size is smaller than currently, then the now
 * excess tail of entries is scanned for any used slots and the given
 * reclaim function is invoked successively for these. The reclaim
 * function must, in addition to memory-managing the entry, return 0
 * upon success, or non-zero to veto the attempted vector size change.
 * The data argument is passed on to the reclaim function as given.
 *
 * \related vector
 */
extern int vector_resize(
    vector *pv, vector_index new_size,
    int (*reclaim)(vector *pv,vector_index index,void *item,void *data),
    void *data );

/** 
 * \brief Return pointer to the indexed page slot at the requested
 * level, and adding intermediate index pages if so requested.
 *
 * \param pv is the vector concerned.
 *
 * \param index is the slot index.
 *
 * \param level is the indexing level to access. Level 0 is the leaf
 * level that holds the slots for the items; level 1 is one level up,
 * for vectors larger than 256 items; ans so on.
 *
 * \param add is a flag to indicate (with 1) that missing index pages
 * should be added, or (with 0) that the function should simply return
 * null if an index page to access at any level is missing.
 *
 * \returns a pointer to the slot for the indexed item (level 0), or
 * (for higher levels) the slot for the index page on the access path
 * to the indexed item. The function returns 0 if the access path is
 * broken by a missing index page, or (with add==1) the allocation of
 * a new index page fails.
 *
 * \note The index tree for the vector is populated on demand only
 * where access has been requested.
 *
 * \related vector
 */
extern void **vector_access(vector *pv,vector_index index,int level,int add);

/**
 * \brief Return the slot value at the given index.
 *
 * \param pv is the vector concerned.
 *
 * \param index is the slot index.
 *
 * \returns a direct pointer to the slot of the given index in the
 * array, or 0 if the index is beyond the array limits (0-limit).
 *
 * \note Note that slot pointers are only valid while the vector size
 * is unchanged.
 *
 * \related vector
 */
extern void **vector_entry(vector *pv,vector_index index); 

/**
 * \param pv - the vector concerned
 * \returns the size of the vector.
 * \related vector
 */
#define vector_size(pv) ((vector_index) (pv)->size)

/**
 * \brief Set the vector value at the given index.
 *
 * \param pv is the vector concerned
 * \param index is the index for the slot to assign
 * \param value is the new slot value
 *
 * \note An assignment of 0 will be treated as an unused slot.
 *
 * \related vector
 */
extern void vector_set(vector *pv,vector_index index,void *value);

/**
 * \brief Set the vector value at the given index and return the prior
 * value.
 *
 * \param pv is the vector concerned
 * \param index is the index for the slot to assign
 * \param value is the new slot value
 *
 * \note An assignment of 0 will be treated as an unused slot.
 *
 * \related vector
 */
extern void *vector_get_set(vector *pv,vector_index index,void *value);

/**
 * \brief Get the vector value at the given index.
 *
 * \param pv is the vector concerned
 * \param index is the index for the slot to assign
 *
 * \note This function will allocate all traversed indeex tree pages
 * even for accessing an unassigned slot.
 *
 * \related vector
 */
extern void *vector_get(vector *pv,vector_index index);

/**
 * \brief Grow the vector by one and assign the added slot.
 *
 * \param pv is the vector concerned
 * \param value is the new slot value
 *
 * \related vector
 */
extern void vector_append(vector *pv,void *value);

/**
 * \brief Copy a consecutive region from one vector into another, or
 * possibly the same vector.
 *
 * \param pv is the vector concerned
 * \param value is the new slot value
 *
 * \note This transfers all slots from the source region to the
 * destination region, including zero slots. The vectors must be large
 * enough for the transfer, which is carried out from lowest to
 * highest or highest to lowest index depending on wther the move is
 * to higher index or to lower index respectively.
 *
 * \related vector
 */
extern void vector_copy(
    vector *dst,vector_index di,
    vector *src,vector_index si,
    vector_index n);

/**
 * \brief Allocate a copy of a vector into one in the given variant.
 */
extern vector *vector_clone(enum vector_variant variant,vector *src);

/**
 * \brief Utility function that invokes the itemdump function for all
 * used (non-null) slots.
 *
 * \related vector
 * \seealso vector_iterate
 */
extern void vector_dump(
    vector *pv,
    void (*itemdump)(const vector_index ,const void *));

/**
 * \brief Sort a vector with quicksort using the provided ordering
 * collback function.
 *
 * \related vector
 */
extern void vector_qsort(vector *pv,int (*compar)(const void *,const void *));

/**
 * Steps through the vector item by item invoking the given function
 * for each. Continues stepping while the item function returns 0.
 *
 * \related vector
 */
extern void vector_iterate(
    vector *pv, vector_index start,
    int (*itemfn)(vector_index,void *item,void *data),
    void *data);

/**
 * \brief Binary search in a sorted vector for an item of the given
 * key, with a callback function providing the sorting order.
 *
 * \param pv is the vector concerned.
 *
 * \param index is a vector_index pointer for returning the index of
 * the found item.
 *
 * \param key is the lookup key to find.
 *
 * \param compare is a callback function that should return the search
 * direction given a key and an item. It should return 0 if the key is
 * a match for the item, <0 if the sought item is expected at a higher
 * index, and >0 if the sought item is expected at a lower index.
 *
 * \return a pointer to the found item and *index set to its index. If
 * there is no matching item, then 0 is returned, and the index is set
 * to the vector size.
 *
 * \related vector
 */
extern void *vector_bsearch(
    vector *pv, vector_index *index, const void *key,
    int (*compare)(const void *key, const void *item));

/**
 * \brief Find the index for a given value
 *
 * \param pv is the vector concerned
 * \param is the value to find
 *
 * This function scans the vector for the first, if any, occurrence of
 * the value, or returns pv->size if not found.
 *
 * \related vector
 */
extern vector_index vector_find(vector *pv,void *value);

/**
 * \brief Find the next used slot at or after the given index.
 *
 * \param pv the vector concerned.
 * \param index pointer to the index to advance.
 * \return the new index, or the vector size if no unused slot is
 * found.
 *
 * Scans forward in the vector for the first unused (null) vector slot
 * at or after the given index. Returns pv->size if full.
 *
 * \related vector
 */
extern vector_index vector_next_unused(vector *pv,vector_index index);

#endif