/* Generic vector interface routine -- functions * Copyright (C) 1997 Kunihiro Ishiguro * * 24-Nov-2009 -- extended to add a number of new operations on vectors. * Copyright (C) 2009 Chris Hall (GMCH), Highwayman * * This file is part of GNU Zebra. * * GNU Zebra is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License as published by the * Free Software Foundation; either version 2, or (at your option) any * later version. * * GNU Zebra is distributed in the hope that it will be useful, but * WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * General Public License for more details. * * You should have received a copy of the GNU General Public License * along with GNU Zebra; see the file COPYING. If not, write to the Free * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA * 02111-1307, USA. */ #include "misc.h" #include "vector.h" #include "memory.h" /* Vectors are implemented as a structure which points to an array of pointers * to vector items. That array -- the body of the vector -- can change size, * and therefore may move around in memory. * * The vector structure may be statically allocated, embedded in another * structure, or allocated dynamically. In any case the vector operations * require the address of the vector structure -- see typedef for vector. * * Vector items are accessed by index, fetching and storing pointers to * those items. Can also push and pop items. * * A vector has a known (logical) end position. Everything beyond the end is * defined to be NULL. When a vector is initialised it is set empty. * * At any given moment the vector body has a limit on the number of items it * can accommodate (the physical end). * * A vector will grow to accommodate what is put into it. Adding items beyond * the (logical) end moves it. Adding items beyond the (physical) limit causes * the body to be extended to suit, and to leave some spare space for future * expansion. * * While the vector is small (see VECTOR_LIMIT_DOUBLE_MAX) the body will grow by * doubling in size. When it is larger, it grows to be multiples of * VECTOR_LIMIT_DOUBLE_MAX. * * Deleting items reduces the (logical) end position, but does NOT release * memory -- the (physical) limit is not changed. * * To release memory: vector_chop will release everything beyond the current * end; vector_decant will create a new body of exactly the current size, * releasing the old body; vector_discard will release everything beyond a * given position. * * NB: you can set a vector item to be NULL. If you set a vector item beyond * the current end, NULL items are inserted in the vector. * * NB: when setting a vector item it is the caller's responsibility to * deallocate any pre-existing value of the item. * * NB: when deleting items it is also the caller's responsibility to deallocate * any values that require it. * * Implementation Notes * * Everything beyond the (logical) end is implicitly NULL. * * Actual memory between (logical) end and (physical) limit is UNDEFINED. So * when advancing the end some care has to be taken to ensure that any new * items in the vector are either set to something or cleared to NULL. * * It would have been possible to ensure that everything between end and limit * is cleared to NULL, but that is more work -- in particular it creates work * when it is not always required. */ #define P_ITEMS_SIZE(n) SIZE(p_vector_item, n) /*============================================================================== * Initialisation, allocation, reset etc. */ /*------------------------------------------------------------------------------ * Initialise a brand new vector, setting it empty. * * Allocates vector structure if none given -- that is, if v == NULL. * * If size is given as zero, no body is allocated, otherwise body of exactly * the required size is allocated. * * NB: discards any existing vector body -- so it is the caller's responsibility * to release any existing body, and any items in that body. */ extern vector vector_init_new(vector v, vector_length_t limit) { if (v == NULL) v = XCALLOC(MTYPE_VECTOR, sizeof(struct vector)) ; else memset(v, 0, sizeof(struct vector)) ; if (limit != 0) { v->p_items = XMALLOC(MTYPE_VECTOR_BODY, P_ITEMS_SIZE(limit)) ; v->limit = limit ; } ; return v ; } ; /*------------------------------------------------------------------------------ * Initialize vector : allocate memory and return vector. * allocates body with at least 1 entry. * * This is a "legacy" function. */ extern vector vector_init (vector_length_t limit) { return vector_init_new(NULL, limit ? limit : 1) ; /* at least 1 entry */ } ; /*------------------------------------------------------------------------------ * Basic: free the vector body and the vector structure. * * NB: it is the caller's responsibility to release any vector item values * *before* doing this. */ void vector_free (vector v) { XFREE (MTYPE_VECTOR_BODY, v->p_items); XFREE (MTYPE_VECTOR, v); } ; /*------------------------------------------------------------------------------ * Re-initialise vector (or create new one), setting it empty. * * Allocates vector structure if none given -- that is, if v == NULL. * * If size is given as zero, no body is allocated, but any existing body is * retained. (vector_reset() will discard body.) * * Otherwise ensures existing body is at least the required size, or a body * of exactly the required size is allocated. * * NB: when re-initialising an existing vector it is the caller's responsibility * to release any vector item values *before* doing this. * */ extern vector vector_re_init(vector v, vector_length_t limit) { if ((v == NULL) || (v->p_items == NULL)) return vector_init_new(v, limit) ; v->end = 0 ; if (v->limit < limit) { v->p_items = XREALLOC(MTYPE_VECTOR_BODY, v->p_items, P_ITEMS_SIZE(limit)) ; v->limit = limit ; } ; return v ; } ; /*------------------------------------------------------------------------------ * Free the vector body, and (if required) free the vector structure. * * Return NULL if releases vector, otherwise the address of the vector. * * NB: it is the caller's responsibility to release any vector item values * *before* doing this. */ vector vector_reset(vector v, free_keep_b free_structure) { if (v == NULL) return NULL ; /* allow for already freed vector */ if (v->p_items != NULL) XFREE(MTYPE_VECTOR_BODY, v->p_items) ; if (free_structure) { confirm(free_it == true) ; XFREE(MTYPE_VECTOR, v) ; return NULL ; } else return vector_init_new(v, 0) ; } ; /*------------------------------------------------------------------------------ * Set vector length to be (at least) the given fixed length. * * There must be a vector. * * Does nothing if the vector is already as long or longer than the given * length. * * If the body is not big enough for the new length, allocates or extends to * exactly the new length. Otherwise, leaves body as it is. * * Appends NULLs as required to extend to the required length. * * Note that the existing contents of the vector are preserved in all cases. */ Private void vector_set_new_min_length(vector v, vector_length_t len) { assert (v != NULL) ; if (len > v->limit) { if (v->p_items == NULL) v->p_items = XMALLOC(MTYPE_VECTOR_BODY, P_ITEMS_SIZE(len)) ; else v->p_items = XREALLOC(MTYPE_VECTOR_BODY, v->p_items, P_ITEMS_SIZE(len)) ; v->limit = len ; } ; if (v->end < len) vector_extend(v, len) ; } ; /*------------------------------------------------------------------------------ * Pop item from vector, stepping past any NULLs. * If vector is empty, free the body and, if required, the vector structure. * * Useful for emptying out and discarding a vector: * * while ((p_v = vector_ream_out(v, 1))) * ... do what's required to release the item p_v * * Returns NULL if vector was empty and has now been freed as required. */ p_vector_item vector_ream(vector v, free_keep_b free_structure) { p_vector_item p_v ; if (v == NULL) return NULL ; while (v->end != 0) { p_v = v->p_items[--v->end] ; if (p_v != NULL) return p_v ; /* return non-NULL item */ } ; /* vector is empty: free the body, and (if required) the vector structure. */ vector_reset(v, free_structure) ; return NULL ; /* signals end */ } ; /*============================================================================== * Unset item, condensing and trimming vector. * * These are legacy operations. */ /*------------------------------------------------------------------------------ * Unset item at given index (ie set it NULL). * * Return the old value of the item. * * If the item at the current (logical) end of the vector is NULL, move the * end backwards until finds a non-NULL item, or the vector becomes empty. */ extern p_vector_item vector_unset_item(vector v, vector_index_t i) { p_vector_item was ; if (i < v->end) { was = v->p_items[i] ; v->p_items[i] = NULL ; } else if (v->end == 0) return NULL ; /* avoid test for last entry NULL if is empty */ else was = NULL ; if (v->p_items[v->end - 1] == NULL) vector_trim(v) ; return was ; } ; /*------------------------------------------------------------------------------ * Trim any NULL entries at the current (logical) end of the vector. * * Returns the (new) length (end) of the vector. */ extern vector_length_t vector_trim(vector v) { vector_length_t e = v->end ; while ((e > 0) && (v->p_items[e - 1] == NULL)) --e ; v->end = e ; return e ; } ; /*------------------------------------------------------------------------------ * Removes any NULL entries from the given vector. * * Returns the (new) length (end) of the vector. */ extern vector_length_t vector_condense(vector v) { vector_length_t e = 0 ; vector_index_t j ; /* Find first NULL, if any */ while ((e < v->end) && (v->p_items[e] != NULL)) ++e ; /* Quit if no NULLs (or vector is empty) */ if (e == v->end) return e ; /* Shuffle any remaining non-NULL down */ for (j = e + 1 ; j < v->end ; ++j) if (v->p_items[j] != NULL) v->p_items[e++] = v->p_items[j] ; v->end = e ; return e ; } ; /*============================================================================== * Inserting and deleting items. */ /*------------------------------------------------------------------------------ * Insert item in vector, before item at given position * Move items and extend vector as required. */ extern void vector_insert_item(vector v, vector_index_t i, void* p_v) { if ((i == v->end) && (i < v->limit)) ++v->end ; else vector_insert(v, i, 1) ; v->p_items[i] = (p_vector_item)p_v ; } ; /*------------------------------------------------------------------------------ * Insert item in vector at given position with rider: * * rider < 0 -- insert before the item at the given position * rider == 0 -- insert at the given position -- REPLACING any existing value * rider > 0 -- insert after the item at the given position * * NB: when an item is replaced, it is the caller's responsibility to release * any memory used by the item, if required. * * Move items and extend vector as required. */ extern void vector_insert_item_here(vector v, vector_index_t i, int rider, p_vector_item p_v) { if (rider == 0) return vector_set_item(v, i, p_v) ; if (rider > 0) ++i ; /* insert before next item */ vector_insert_item(v, i, p_v) ; } ; /*------------------------------------------------------------------------------ * Delete item from vector. * * Move items as required. Reduces number of items in the vector (unless * the item in question is beyond the end of the vector !) * * Returns: the item that has just been deleted. * * NB: it is the caller's responsibility to release memory used by any * current value of the item, if required. * * NB: does NOT change the size of the vector body. */ extern p_vector_item vector_delete_item(vector v, vector_index_t i) { p_vector_item p_e ; if (i < v->end) { p_e = v->p_items[i] ; /* pick up the current value */ if (i != (v->end - 1)) vector_delete(v, i, 1) ; else v->end = i ; return p_e ; } else return NULL ; } ; /*============================================================================== * Moving items within vector. */ /*------------------------------------------------------------------------------ * Move item in vector from source position to destination position. * * Moves intervening items up or down as required. * * Extends vector to include the destination, if required. * * A source item beyond the end of the vector is implicitly NULL. */ extern void vector_move_item(vector v, vector_index_t i_dst, vector_index_t i_src) { p_vector_item* pp_s ; p_vector_item* pp_d ; p_vector_item p_e ; vector_length_t old_end = v->end ; /* Worry about whether both source and destination exist. */ if (i_dst >= old_end) { vector_insert(v, i_dst, 1) ; /* ensure destination exists */ if (i_src >= old_end) return ; /* both were beyond the end */ } else if (i_src >= old_end) { i_src = old_end ; /* clamp to just beyond last */ vector_insert(v, i_src, 1) ; /* create empty entry */ } ; if (i_dst == i_src) /* avoid work and edge case */ return ; /* Both src and dst are within the vector and src != dst */ pp_s = &v->p_items[i_src] ; /* address of src entry */ pp_d = &v->p_items[i_dst] ; /* address of dst entry */ p_e = *pp_s ; /* pick up item to move */ if (i_src < i_dst) memmove(pp_s, pp_s+1, P_ITEMS_SIZE(i_dst - i_src)) ; else memmove(pp_d+1, pp_d, P_ITEMS_SIZE(i_src - i_dst)) ; *pp_d = p_e ; /* put down the item to move */ } ; /*------------------------------------------------------------------------------ * Move item in vector to given position with rider: * * rider < 0 -- move to before the item at the given position * rider == 0 -- move to replace item at the given position * rider > 0 -- move to after the item at the given position * * NB: it is the caller's responsibility to release the any existing value * that will be replaced. * * NB: replacing an item by itself (rider == 0, i_dst == i_src) deletes it ! * * Move items and extend vector as required. */ void vector_move_item_here(vector v, vector_index_t i_dst, int rider, vector_index_t i_src) { if (rider != 0) { if (i_src < i_dst) { if (rider < 0) --i_dst ; /* moving up places src after dst */ } else if (i_src > i_dst) { if (rider > 0) ++i_dst ; /* moving down places src before dst */ } ; vector_move_item(v, i_dst, i_src) ; } else { /* to replace: copy and then delete. */ vector_set_item(v, i_dst, vector_get_item(v, i_src)) ; vector_delete_item(v, i_src) ; } ; } ; /*------------------------------------------------------------------------------ * Reverse vector: reverse the order of items in the vector. */ extern void vector_reverse(vector v) { if (v != NULL) vector_part_reverse(v, 0, v->end) ; } ; /*------------------------------------------------------------------------------ * Reverse portion of vector. */ extern void vector_part_reverse(vector v, vector_index_t i, vector_length_t n) { vector_index_t j ; if (v == NULL) return ; if ((i + n) > v->limit) vector_extend(v, i + n) ; /* ensure portion exists */ if (n <= 1) return ; j = i + n - 1 ; /* j > i, because n > 1 */ do { p_vector_item p_i = v->p_items[i] ; v->p_items[i++] = v->p_items[j] ; v->p_items[j--] = p_i ; } while (j > i) ; } ; /*============================================================================== * Copying, moving and appending entire vectors. */ static void vector_new_limit(vector v, vector_length_t new_end) ; /*------------------------------------------------------------------------------ * Shallow vector copy -- copies pointers to item values, not the values. * * Creates a new vector. * * NB: creates new vector with same limit as existing one, but copies only * the known items (ie up to end, not up to limit). */ vector vector_copy (vector v) { vector new = vector_init_new(NULL, v->limit) ; new->end = v->end; if (v->limit > 0) memcpy(new->p_items, v->p_items, P_ITEMS_SIZE(v->end)) ; return new; } /*------------------------------------------------------------------------------ * Shallow vector copy -- copies pointers to item values, not the values. * Creates a new vector or re-initialises an existing one. * * NB: creates new vector with same limit as existing one, but copies only * the known items (ie up to end, not up to limit). * * NB: if re-initialising existing vector, it is the caller's responsibility * to release any existing items if that is required. * * NB: if re-initialising existing vector, it is the caller's responsibility * to ensure the vector structure is currently valid. * * NB: do NOT try copying a vector to itself !! */ vector vector_copy_here(vector dst, vector src) { assert((src != NULL) && (src != dst)) ; dst = vector_re_init(dst, src->limit) ; dst->end = src->end; if (src->end > 0) memcpy(dst->p_items, src->p_items, P_ITEMS_SIZE(src->end)) ; return dst ; } ; /*------------------------------------------------------------------------------ * Vector move -- moves body of vector. * * Creates a new vector or re-initialises an existing one. * Leaves the source vector empty -- does not release the structure. * * NB: if re-initialising existing vector, it is the caller's responsibility * to release any existing items if that is required. * * NB: if re-initialising existing vector, it is the caller's responsibility * to ensure the vector structure is currently valid. * * NB: do NOT try moving a vector to itself !! */ extern vector vector_move_here(vector dst, vector src) { assert((src != NULL) && (src != dst)) ; if (dst != NULL) dst = vector_reset(dst, 0) ; /* Reset to deallocate any existing body */ else dst = vector_init_new(dst, 0) ; /* Create new structure sans body. */ *dst = *src ; /* Copy the vector structure */ vector_init_new(src, 0) ; /* Set empty, forgetting body */ return dst ; } /*------------------------------------------------------------------------------ * Shallow vector copy append -- copies pointers to item values, not the values. * * Appends copied pointers to the destination vector. * * Creates a new destination vector if required. * * NB: Can append to self. */ extern vector vector_copy_append(vector dst, vector src) { vector_index_t new_end ; assert(src != NULL) ; if (dst != NULL) { new_end = dst->end + src->end ; if (new_end > dst->limit) vector_new_limit(dst, new_end) ; } else { new_end = src->end ; vector_init_new(dst, new_end) ; } ; if (src->end) memcpy(&dst->p_items[dst->end], src->p_items, P_ITEMS_SIZE(src->end)) ; dst->end = new_end ; /* Done last, allows for append to self ! */ return dst ; } ; /*------------------------------------------------------------------------------ * Vector move append -- moves pointers to item values. * * Appends moved pointers to the destination vector. * * Creates a new destination vector if required (dst == NULL). * * Leaves the source vector empty -- does not release the structure. * * NB: do NOT try moving a vector to itself !! */ extern vector vector_move_append(vector dst, vector src) { assert((src != NULL) && (src != dst)) ; if ((dst == NULL) || (dst->end == 0)) return vector_move_here(dst, src) ; /* Easy way to do it if dst empty */ vector_copy_append(dst, src) ; /* Extend dst and copy src */ vector_init_new(src, 0) ; /* Set empty, forgetting body */ return dst ; } ; /*============================================================================== * Portmanteau splice/extract/replace function. * * All take a portion of 'src' vector and: * * splice: * * a) replace a portion of the 'dst' vector by a portion of the 'src' vector * copying the replaced portion of the 'dst' vector to the 'to' vector * b) either: leave 'src' unchanged -- copy * or: remove the stuff copied from 'src' -- move * * Arguments: to_copy -- true * to -- vector, or NULL => allocate new vector * dst -- vector * i_dst -- start of portion to replace * n_dst -- length of portion to replace. 0 => insertion. * src -- vector, or NULL => nothing to copy/move * i_src -- start of portion to copy/move * n_src -- length of portion to copy/move. 0 => nothing. * src_move -- true => move, otherwise copy. * * Returns: the (possibly new) 'to' vector * * NB: 'to', 'dst' and 'src' must be distinct vectors. * * extract: * * a) copy a portion of the 'src' vector to the 'to' vector * c) either: leave 'src' unchanged -- copy * or: remove the stuff copied from 'src' -- move * * Arguments: to_copy -- true * to -- vector, or NULL => allocate new vector * dst -- NULL * i_dst -- ignored * n_dst -- ignored * src -- vector, or NULL => nothing to copy/move * i_src -- start of portion to copy/move * n_src -- length of portion to copy/move. 0 => nothing. * src_move -- true => move, otherwise copy. * * Returns: the (possibly new) 'to' vector * * NB: 'to' and 'src' must be distinct vectors. * * replace: * * a) replace a portion of the 'dst' vector by a portion of the 'src' vector * b) either: leave 'src' unchanged -- copy * or: remove the stuff copied from 'src' -- move * * Arguments: to_copy -- false * to -- ignored * dst -- vector * i_dst -- start of portion to replace * n_dst -- length of portion to replace. 0 => insertion. * src -- vector, or NULL => nothing to copy/move * i_src -- start of portion to copy/move * n_src -- length of portion to copy/move. 0 => nothing. * src_move -- true => move, otherwise copy. * * Returns: original 'to' argument * * NB: 'dst' and 'src' must be distinct vectors. * * All copies are shallow -- pointers to item values are copied, not the values. * * NB: any existing contents of the 'to' vector are discarded. * * NB: it is the caller's responsibility to release memory allocated to any * items which are discarded in these operations. * * NB: for splice and replace, the resulting destination vector will be at * least i_dst + n_src long. (Even if is copying actual or implied NULLs * from the source.) * * NB: where new vectors are created, they will be of exactly the required size. * * NB: where an existing vector is reused, it is the caller's responsibility * to ensure the vector structure is currently valid (by vector_init_new() * or by ensuring it is zeroized). */ extern vector vector_sak(int to_copy, vector to, vector dst, vector_index_t i_dst, vector_length_t n_dst, vector src, vector_index_t i_src, vector_length_t n_src, int src_move) { int dst_replace ; /* true => replace portion of 'dst' */ vector_index_t new_dst_end = 0 ; /* new end of dst */ vector_length_t n_dst_nulls ; /* number of implicit NULLs to add */ vector_length_t n_dst_move ; /* number of items to move up or down */ vector_length_t n_src_real ; /* number of items to really copy */ vector_length_t n_src_nulls ; /* number of implicit NULLs to "copy" */ assert((to == NULL) || (dst == NULL) || (to != dst)) ; assert((src == NULL) || (dst == NULL) || (src != dst)) ; /* Worry about how much we really have in the source vector. */ n_src_real = n_src ; /* assume all real */ n_src_nulls = 0 ; /* so no NULLs to "copy" */ if (n_src != 0) { if ((src == NULL) || (i_src >= src->end)) n_src_real = 0 ; else if ((i_src + n_src) > src->end) n_src_real = src->end - i_src ; n_src_nulls = n_src - n_src_real ; } ; /* If no 'dst' vector, then this is an extract. */ n_dst_move = 0 ; /* assume nothing to move */ n_dst_nulls = 0 ; /* assume no NULLs to add */ if (dst == NULL) /* For extract: set up dst, i_dst and n_dst so that can copy to the */ /* 'to' vector as if from 'dst'. */ { dst_replace = 0 ; /* no replacement operation */ dst = src ; /* copy from here */ i_dst = i_src ; n_dst = n_src_real ; } else /* Reduce n_dst to the number of actual items to be replaced. */ /* */ /* Calculate the new end of 'dst'. */ { dst_replace = 1 ; /* have replacement to do */ if (i_dst >= dst->end) /* If i_dst is beyond the end of 'dst', then there is nothing */ /* to replace (so set n_dst == 0). Will be adding n_src items */ /* at i_dst -- so new end must be i_dst + n_src. */ { n_dst_nulls = i_dst - dst->end ; /* fill from end to i_dst */ n_dst = 0 ; /* nothing to replace */ new_dst_end = i_dst + n_src ; /* all beyond current end */ } else /* If i_dst + n_dst is beyond the end of 'dst', reduce n_dst to */ /* number of items up to the end. */ /* Will remove n_dst items and insert n_src, so end will move */ /* by n_src - n_dst. */ { if ((i_dst + n_dst) > dst->end) n_dst = dst->end - i_dst ; /* what we actually replace */ else if (n_dst != n_src) n_dst_move = dst->end - (i_dst + n_dst) ; /* what we move up or down */ new_dst_end = dst->end + n_src - n_dst ; /* end depends on amount added */ /* & amount actually replaced */ } ; } ; /* Copy portion of 'dst' (or of 'src') to 'to', if required. */ /* */ /* Have arranged: n_dst -- number of items to copy, all existent */ /* dst -- vector to copy from -- if n_dst > 0 */ /* i_dst -- first item to copy -- if n_dst > 0 */ if (to_copy) { to = vector_re_init(to, n_dst) ; /* reinitialise or create */ to->end = n_dst ; if (n_dst > 0) memcpy(to->p_items, &dst->p_items[i_dst], P_ITEMS_SIZE(n_dst)) ; } ; /* Replace portion of 'dst' by portion of 'src', if required. */ /* */ /* Have arranged: */ /* */ /* new_dst_end -- end of dst once dust settles */ /* n_dst_nulls -- number of NULLs to insert at dst->end to fill up */ /* to i_dst (when i_dst is beyond old end.) */ /* n_dst_move -- number of items in dst to move up or down to */ /* leave n_src item hole at i_dst to fill in. */ /* n_src_real -- number of real src items at i_src to copy to dst */ /* at i_dst. */ /* n_src_nulls -- number of nulls to add to fill to i_dst + n_src. */ if (dst_replace) { if (new_dst_end > dst->limit) /* extend body if required */ vector_new_limit(dst, new_dst_end) ; if (n_dst_nulls > 0) memset(&dst->p_items[dst->end], 0, P_ITEMS_SIZE(n_dst_nulls)) ; if (n_dst_move > 0) memmove(&dst->p_items[i_dst + n_dst], &dst->p_items[i_dst + n_src], P_ITEMS_SIZE(n_dst_move)) ; if (n_src_real > 0) memcpy(&dst->p_items[i_dst], &src->p_items[i_src], P_ITEMS_SIZE(n_src_real)) ; if (n_src_nulls > 0) memset(&dst->p_items[i_dst + n_src_real], 0, P_ITEMS_SIZE(n_src_nulls)) ; dst->end = new_dst_end ; } ; /* Delete portion of 'src', if required (and have 'src' !) */ if (src_move && (n_src_real != 0)) vector_delete(src, i_src, n_src_real) ; /* Done -- return 'to' vector as promised. */ return to ; } ; /*============================================================================== * Legacy Vector Operations */ /*------------------------------------------------------------------------------ * Set value to the smallest empty slot. * * Returns: index of slot used. */ extern int vector_set (vector v, void *val) { vector_index_t i; i = 0 ; while (1) { if (i == v->end) { i = vector_extend_by_1(v) ; break ; } if (v->p_items[i] == NULL) break ; ++i ; } ; v->p_items[i] = val; return i ; } /*------------------------------------------------------------------------------ * Set value to specified index slot. * * Returns: index of slot (as given) */ extern int vector_set_index (vector v, vector_index_t i, void *val) { vector_ensure (v, i); v->p_items[i] = val; return i; } /*------------------------------------------------------------------------------ * Look up vector -- get the i'th item. * * Returns: the i'th item -- NULL if item is null, or i >= logical len of vector */ extern p_vector_item vector_lookup (vector v, vector_index_t i) { if (i >= v->end) return NULL; return v->p_items[i]; } /*------------------------------------------------------------------------------ * Lookup vector, ensure it -- get i'th item and ensure logical len > i. * * Returns: the i'th item -- NULL if item is null */ extern p_vector_item vector_lookup_ensure (vector v, vector_index_t i) { vector_ensure (v, i); return v->p_items[i]; } /*------------------------------------------------------------------------------ * Count the number of not empty slots. */ extern vector_length_t vector_count (vector v) { vector_index_t i; vector_length_t count = 0; for (i = 0; i < v->end; i++) if (v->p_items[i] != NULL) count++; return count; } /*============================================================================== * Sorting and Searching vector. */ /*------------------------------------------------------------------------------ * Sort the given vector. * * NB: the comparison function receives a pointer to the pointer to the * vector item's value. * * NB: if there are NULL items in the vector, the comparison function MUST * be ready for them. */ extern void vector_sort(vector v, vector_sort_cmp* cmp) { if (v->end <= 1) return ; /* Stop dead if 0 or 1 items */ typedef int qsort_cmp(const void*, const void*) ; qsort(v->p_items, v->end, sizeof(p_vector_item), (qsort_cmp*)cmp) ; } ; /*------------------------------------------------------------------------------ * Perform binary search on the given vector. * * The vector MUST be sorted in the order implied by the comparison function * given. The vector need not contain unique values, but this search makes * no effort to select any particular instance of a sequence of equals. * * Returns: * * result == 0: found an equal value. * index returned is of first entry found which is equal to * the value sought. There may be other equal values, before * and/or after this one in the vector. * * result == +1: value not found and vector not empty. * index returned is of the largest entry whose value is less * than the value sought. * (The value sought belongs after this point.) * * result == -1: value is less than everything in the vector, or the * vector is empty. * index returned is 0 * * NB: The comparison function takes arguments which are: * * const void** pointer to pointer to value being searched for. * const void** pointer to pointer to vector item to compare with * * The value being searched for need not be in the same form as a vector * item. However, if it is then the same comparison function can be used * to sort and search. * * NB: if there are NULL items in the vector, the comparison function MUST * be ready for them. */ extern vector_index_t vector_bsearch(vector v, vector_bsearch_cmp* cmp, const void* p_val, int* result) { vector_index_t il, iv, ih ; int c ; if (v->end <= 1) { *result = (v->end == 0) ? -1 : cmp(&p_val, (const cvp*)&v->p_items[0]) ; return 0 ; /* Stop dead if 0 or 1 items */ } ; /* We have at least two items. */ il = 0 ; ih = v->end - 1 ; /* Pick off the edge cases: >= last and <= first. */ if ((c = cmp(&p_val, (const cvp*)&v->p_items[ih])) >= 0) { *result = c ; /* 0 => found. +1 => val > last */ return ih ; /* return high index. */ } ; if ((c = cmp(&p_val, (const cvp*)&v->p_items[il])) <= 0) { *result = c ; /* 0 => found. -1 => val < first */ return il ; /* return low index. */ } /* Now binary chop. We know that item[il] < val < item[ih] */ /* We also know that il < ih */ while (1) { iv = (il + ih) / 2 ; if (iv == il) /* true if (ih == il+1) */ { *result = +1 ; return il ; /* return il: item[il] < val < item[il+1] */ } ; /* We now know that il < iv < ih */ c = cmp(&p_val, (const cvp*)&v->p_items[iv]) ; if (c == 0) { *result = 0 ; return iv ; /* found !! */ } if (c < 0) ih = iv ; /* step down iv > il, so new ih > il */ else il = iv ; /* step up iv < ih, so new il < ih */ } ; } ; /*============================================================================== * Mechanics for adding/deleting items and managing the vector (logical) end * and (physical) limit. */ /* Extract the LS bit of unsigned integer 'x'. */ #define lsbit(x) ((x) & ((~(x)) + 1)) /* Round 'x' up to a multiple of 'm' */ #define multiple(x, m) ((((x) + (m) - 1) / (m)) * (m)) /*------------------------------------------------------------------------------ * Set new limit to suit new end for given vector. * * The new limit will be at least: VECTOR_LIMIT_MIN. * * While the vector is relatively small, the limit is doubled until there * is at least 1/8 of the new vector free. * * Beyond VECTOR_LIMIT_DOUBLE_MAX, however, the limit is set to the * smallest multiple of VECTOR_LIMIT_DOUBLE_MAX which gives at least * VECTOR_LIMIT_SLACK_MIN free entries beyond the new end. * * This is an attempt to balance the cost of repeated reallocations of * memory against the cost of possible wasted space at the end of the * vector. * * NB: the new_limit depends entirely on the new end position. (Current * end position is ignored.) * * NB: the new limit may be less than the current limit, in which case the * vector body is reduced in size. * * Except for any size set when the vector is initialised, the vector body * size will be a power of 2 or a multiple of VECTOR_LIMIT_DOUBLE_MAX. * (Vectors are regular in their habits, which may help the memory allocator). * * TODO: what to do if calculation of new_limit overflows, or calculation * of P_ITEMS_SIZE will ? */ static void vector_new_limit(vector v, vector_index_t new_end) { vector_length_t old_limit = v->limit ; vector_length_t new_limit ; if (new_end > ((VECTOR_LIMIT_DOUBLE_MAX * 7) / 8)) { new_limit = multiple(new_end + VECTOR_LIMIT_SLACK_MIN, VECTOR_LIMIT_DOUBLE_MAX) ; } else { /* Want the new_limit to be a power of 2. */ /* If the old_limit was a power of 2, start from there. */ /* Otherwise start from a power of 2 less than new_end: either the */ /* minimum value or a value mid way to VECTOR_LIMIT_DOUBLE_MAX. */ if ( (old_limit != 0) && (old_limit == lsbit(old_limit)) && (new_end >= old_limit) ) new_limit = old_limit ; else new_limit = (new_end < VECTOR_LIMIT_MID) ? VECTOR_LIMIT_MIN : VECTOR_LIMIT_MID ; while (new_end > ((new_limit * 7) / 8)) new_limit *= 2 ; } ; v->p_items = XREALLOC(MTYPE_VECTOR_BODY, v->p_items, P_ITEMS_SIZE(new_limit)) ; v->limit = new_limit ; } ; /*------------------------------------------------------------------------------ * Extend vector and set new (logical) end. * * Extends body if required. * Ensures everything between old and new end is set NULL. * * NB: expects new end > old end, but copes with new end <= old end. */ extern void vector_extend(vector v, vector_length_t new_end) { vector_length_t old_end = v->end ; if (new_end > v->limit) vector_new_limit(v, new_end) ; v->end = new_end ; if (new_end > old_end) memset(&v->p_items[old_end], 0, P_ITEMS_SIZE(new_end - old_end)) ; } ; /*------------------------------------------------------------------------------ * Insert entries into vector: insert 'n' NULL entries at location 'i'. * * Updates end (and limit) to be at least 'i' + 'n'. * (So if 'i' < end then end becomes end + 'n', else end becomes 'i' + 'n'.) */ extern void vector_insert(vector v, vector_index_t i, vector_length_t n) { vector_length_t old_end, new_end ; vector_length_t n_above ; /* If i < old end, then we are inserting n NULLs, and need * to shuffle at least one item up. * else we are setting new end to i + n and need to NULL * fill from old end to the new end. */ old_end = v->end ; if (i < old_end) { if (n == 0) return ; /* give up now if not inserting anything */ n_above = old_end - i ; /* number of items to shuffle up.. >= 1 */ new_end = old_end + n ; } else { n_above = 0 ; /* nothing to shuffle up. */ new_end = i + n ; i = old_end ; /* where to zeroize from */ n = new_end - old_end ; /* how much to zeroize */ } ; /* Now we extend the body if we need to. */ if (new_end > v->limit) vector_new_limit(v, new_end) ; v->end = new_end ; if (n_above > 0) memmove(&v->p_items[i + n], &v->p_items[i], P_ITEMS_SIZE(n_above)) ; memset(&v->p_items[i], 0, P_ITEMS_SIZE(n)) ; } ; /*------------------------------------------------------------------------------ * Delete items from vector: delete 'n' items at location 'i'. * * Does nothing if 'i' is beyond current end of vector or if 'n' == 0. * * Deletes from 'i' to end if less than 'n' items to the end. * * NB: does NOT change the size of the body. * * NB: it is the caller's responsibility to have released any memory allocated * for the items that are being deleted. */ extern void vector_delete(vector v, vector_index_t i, vector_length_t n) { vector_length_t old_end, new_end ; old_end = v->end ; if ((i >= old_end) || (n == 0)) return ; /* If i + n < old_end, we have 1 or more items to keep and move down */ if ((i + n) < old_end) { memmove(&v->p_items[i], &v->p_items[i + n], P_ITEMS_SIZE(old_end - (i + n))) ; new_end = old_end - n ; } else { new_end = i ; /* We are keeping nothing above 'i' */ /* NB: new_end < old_end */ } ; v->end = new_end ; /* account for stuff dropped */ } ; /*------------------------------------------------------------------------------ * Discard entries from vector: discard entries from location 'i' onwards. * * Releases memory from 'i' onwards. * Releases the body altogether if this sets the vector empty ('i' == 0). * Sets new end of vector iff 'i' < current end. * * Does nothing if 'i' is beyond current limit (physical end) of vector. * * NB: it is the caller's responsibility to have released any memory allocated * for the items that are being discarded. */ extern void vector_discard(vector v, vector_index_t i) { if (i >= v->limit) return ; if (i == 0) vector_reset(v, 0) ; /* reset, without releasing the structure */ else { v->limit = i ; if (i < v->end) v->end = i ; v->p_items = XREALLOC(MTYPE_VECTOR_BODY, v->p_items, P_ITEMS_SIZE(i)) ; } ; } ; /*------------------------------------------------------------------------------ * Chop vector at the current (logical) end. * * Releases the body altogether if the vector is currently empty. */ extern void vector_chop(vector v) { vector_length_t new_limit = v->end ; if (new_limit == 0) vector_reset(v, 0) ; /* reset, without releasing the structure */ else if (new_limit != v->limit) { v->limit = new_limit ; v->p_items = XREALLOC(MTYPE_VECTOR_BODY, v->p_items, P_ITEMS_SIZE(new_limit)) ; } ; } ; /*------------------------------------------------------------------------------ * Decant vector into a new body allocated to current logical size, and * release the old body. * * Releases the body altogether if the vector is currently empty. */ extern void vector_decant(vector v) { p_vector_item* p_old_body ; vector_length_t new_limit = v->end ; if (new_limit == 0) vector_reset(v, 0) ; /* reset, without releasing the structure */ else { p_old_body = v->p_items ; vector_init_new(v, new_limit) ; /* initialise with new body */ memcpy(v->p_items, p_old_body, P_ITEMS_SIZE(new_limit)) ; /* copy the old body across */ v->end = new_limit ; XFREE(MTYPE_VECTOR_BODY, p_old_body) ; } ; } ;