diff options
Diffstat (limited to 'lib/vector.h')
| -rw-r--r-- | lib/vector.h | 348 |
1 files changed, 320 insertions, 28 deletions
diff --git a/lib/vector.h b/lib/vector.h index 6b27fd96..e69e628a 100644 --- a/lib/vector.h +++ b/lib/vector.h @@ -1,7 +1,9 @@ -/* - * Generic vector interface header. +/* Generic vector interface header. * Copyright (C) 1997, 98 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 @@ -17,47 +19,337 @@ * 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. + * 02111-1307, USA. */ #ifndef _ZEBRA_VECTOR_H #define _ZEBRA_VECTOR_H -/* struct for vector */ -struct _vector +/* Macro in case there are particular compiler issues. */ +#ifndef Inline + #define Inline static inline +#endif + +/*------------------------------------------------------------------------------ + * types and struct for vector + * + * NB: an entirely zero structure represents an entirely empty vector. + * + * TODO: could force vector_index to be 32 bits ? + */ +typedef void* p_vector_item ; +typedef unsigned int vector_index ; + +typedef struct vector* vector ; /* pointer to vector structure */ +typedef struct vector vector_t ; /* embedded vector structure */ +struct vector { - unsigned int active; /* number of active slots */ - unsigned int alloced; /* number of allocated slot */ - void **index; /* index to data */ + p_vector_item* p_items ; /* pointer to array of vector item pointers */ + vector_index end ; /* number of "active" item entries */ + vector_index limit ; /* number of allocated item entries */ }; -typedef struct _vector *vector; -#define VECTOR_MIN_SIZE 1 +/* Under very controlled circumstances, may access the vector body */ +typedef p_vector_item const* vector_body_t ; + +/* Values that control the allocation of the vector body. */ +/* NB: these must all be powers of 2. */ + +/* The body, when allocated, will have at least this many entries. */ +#define VECTOR_LIMIT_MIN 8 +/* When the body grows, it doubles in size, until it is this big. */ +/* After that it grows in units of this much. */ +#define VECTOR_LIMIT_DOUBLE_MAX 2048 +/* "Midway" between VECTOR_LIMIT_MIN and VECTOR_LIMIT_DOUBLE_MAX. */ +#define VECTOR_LIMIT_MID 128 +/* When growing in units of VECTOR_LIMIT_DOUBLE_MAX, this is the */ +/* minimum slack space to leave after the logical end of the vector. */ +#define VECTOR_LIMIT_SLACK_MIN ((VECTOR_LIMIT_DOUBLE_MAX) / 8) + +/* (Sometimes) useful macros. */ -/* (Sometimes) usefull macros. This macro convert index expression to - array expression. */ -/* Reference slot at given index, caller must ensure slot is active */ -#define vector_slot(V,I) ((V)->index[(I)]) -/* Number of active slots. - * Note that this differs from vector_count() as it the count returned - * will include any empty slots +/* Reference item at given index. */ +/* NB: does not guarantee the item is "active" (that is: within the */ +/* (logical) vector) -- but see vector_ensure. */ +/* Returns address of vector item. */ +/* See: VECTOR_ITEMS() for walking items in a vector. */ +/* See: vector_get_item(), which is preferable. */ +#define vector_slot(V,I) ((V)->p_items[(I)]) + +/* Number of "active" item entries -- (logical) end of the vector. */ +/* Note that this differs from vector_count() as this count will */ +/* include any NULL items. */ +#define vector_active(V) ((V)->end) + +/* To walk all items in a vector: + * + * vector_index i ; + * xxxxx* p_v ; + * + * for (VECTOR_ITEMS(v, p_v, i)) + * { + * ... i is index of current item + * ... p_v is address of current item value -- may be NULL + * } ; + * + * ... i is number of items in vector (including any NULLs) + */ +#define VECTOR_ITEMS(v, p_v, i)\ + (i) = 0 ;\ + (i) < (v)->end ? (((p_v) = (void*)(v)->p_items[i]), 1) \ + : (((p_v) = NULL), 0) ;\ + ++(i) + +/*============================================================================== + * Prototypes. */ -#define vector_active(V) ((V)->active) -/* Prototypes. */ extern vector vector_init (unsigned int size); -extern void vector_ensure (vector v, unsigned int num); -extern int vector_empty_slot (vector v); +Inline void vector_ensure(vector v, vector_index i) ; extern int vector_set (vector v, void *val); -extern int vector_set_index (vector v, unsigned int i, void *val); -extern void vector_unset (vector v, unsigned int i); -extern unsigned int vector_count (vector v); -extern void vector_only_wrapper_free (vector v); -extern void vector_only_index_free (void *index); +extern int vector_set_index (vector v, vector_index i, void *val); +#define vector_unset(v, i) (void)vector_unset_item(v, i) +extern vector_index vector_count (vector v); extern void vector_free (vector v); extern vector vector_copy (vector v); -extern void *vector_lookup (vector, unsigned int); -extern void *vector_lookup_ensure (vector, unsigned int); +extern void *vector_lookup (vector, vector_index); +extern void *vector_lookup_ensure (vector, vector_index); + +extern vector vector_init_new(vector v, unsigned int size) ; +extern vector vector_re_init(vector v, unsigned int size) ; +extern vector vector_reset(vector v, int free_structure) ; +extern p_vector_item vector_ream(vector v, int free_structure) ; + +/* Reset vector and free the vector structure. */ +#define vector_reset_free(v) vector_reset(v, 1) +/* Reset vector but free the heap structure. */ +#define vector_reset_keep(v) vector_reset(v, 0) +/* Ream out vector and free the vector structure. */ +#define vector_ream_free(v) vector_ream(v, 1) +/* Ream out vector but keep the vector structure. */ +#define vector_ream_keep(v) vector_ream(v, 0) + +Inline void vector_set_min_length(vector v, unsigned int len) ; +extern void vector_set_new_min_length(vector v, unsigned int len) ; + +Inline void vector_set_length(vector v, unsigned int len) ; +#define vector_set_end(v, l) vector_set_length(v, l) + +Inline vector_index vector_length(vector v) ; +#define vector_end(v) vector_length(v) +Inline int vector_is_empty(vector v) ; + +Inline vector_body_t vector_body(vector v) ; + +Inline p_vector_item vector_get_item(vector v, vector_index i) ; +Inline p_vector_item vector_get_first_item(vector v) ; +Inline p_vector_item vector_get_last_item(vector v) ; +Inline void vector_set_item(vector v, vector_index i, p_vector_item p_v) ; +Inline void vector_assign_item(vector v, vector_index dst, vector_index src) ; +extern p_vector_item vector_unset_item(vector v, vector_index i) ; +extern vector_index vector_trim(vector v) ; +extern vector_index vector_condense(vector v) ; + +extern void vector_insert_item(vector v, vector_index i, p_vector_item p_v) ; +extern void vector_insert_item_here(vector v, vector_index i, int rider, + p_vector_item p_v) ; +extern void vector_move_item(vector v, vector_index dst, vector_index src) ; +extern void vector_move_item_here(vector v, vector_index dst, int rider, + vector_index src) ; +extern p_vector_item vector_delete_item(vector v, vector_index i) ; +extern void vector_reverse(vector v) ; +extern void vector_part_reverse(vector v, vector_index i, unsigned int n) ; + +Inline void vector_push_item(vector v, p_vector_item p_v) ; +Inline p_vector_item vector_pop_item(vector v) ; + +extern void vector_insert(vector v, vector_index i, unsigned int n) ; +extern void vector_delete(vector v, vector_index i, unsigned int n) ; + +typedef int vector_bsearch_cmp(const void* const* pp_val, + const void* const* item) ; +vector_index vector_bsearch(vector v, vector_bsearch_cmp* cmp, + const void* p_val, int* result) ; +typedef int vector_sort_cmp(const void* const* a, const void* const* b) ; +void vector_sort(vector v, vector_sort_cmp* cmp) ; + +extern vector vector_copy_here(vector dst, vector src) ; +extern vector vector_move_here(vector dst, vector src) ; +extern vector vector_copy_append(vector dst, vector src) ; +extern vector vector_move_append(vector dst, vector src) ; + +#define vector_copy_extract(to, src, i_src, n_src) \ + vector_sak(1, to, NULL, 0, 0, src, i_src, n_src, 0) +#define vector_move_extract(to, src, i_src, n_src) \ + vector_sak(1, to, NULL, 0, 0, src, i_src, n_src, 1) +#define vector_copy_splice(to, dst, i_dst, n_dst, src, i_src, n_src) \ + vector_sak(1, to, dst, i_dst, n_dst, src, i_src, n_src, 0) +#define vector_move_splice(to, dst, i_dst, n_dst, src, i_src, n_src) \ + vector_sak(1, to, dst, i_dst, n_dst, src, i_src, n_src, 1) +#define vector_copy_replace(dst, i_dst, n_dst, src, i_src, n_src) \ + vector_sak(0, NULL, dst, i_dst, n_dst, src, i_src, n_src, 0) +#define vector_move_replace(dst, i_dst, n_dst, src, i_src, n_src) \ + vector_sak(0, NULL, dst, i_dst, n_dst, src, i_src, n_src, 1) + +extern vector vector_sak(int to_copy, vector to, + vector dst, vector_index i_dst, unsigned int n_dst, + vector src, vector_index i_src, unsigned int n_src, int src_move) ; + +extern void vector_discard(vector v, vector_index i) ; +extern void vector_chop(vector v) ; +extern void vector_decant(vector v) ; + +Inline vector_index vector_extend_by_1(vector v) ; +extern void vector_extend(vector v, vector_index new_end) ; + +/*============================================================================== + * The inline functions: + */ + +/* Extend vector by one item at the end, which is about to be set. */ +/* Returns index of new least item in the vector. */ +/* NB: if left unset, the item may be UNDEFINED. */ +Inline vector_index +vector_extend_by_1(vector v) +{ + vector_index i = v->end ; + + if (i < v->limit) + return v->end++ ; /* simple if we have room */ + + vector_extend(v, i + 1) ; /* the hard way */ + return i ; +} ; + +/* Ensure given index is "active". */ +/* Adjusts logical and physical end of the vector as required, filling */ +/* with NULLs upto any new logical end. */ +Inline void +vector_ensure(vector v, vector_index i) +{ + if (i < v->end) /* trivial if within vector */ + return ; + if ((i == v->end) && (i < v->limit)) /* simple if end and have room */ + v->p_items[v->end++] = NULL ; /* set NULL for complete safety */ + else + vector_extend(v, i + 1) ; /* do it the hard way */ +} ; + +/* Want vector to be at least the given length. */ +/* */ +/* Adjusts logical and physical end of the vector as required, filling */ +/* with NULLs upto any new logical end -- does not allocate any more */ +/* than is exactly necessary. */ +Inline void +vector_set_min_length(vector v, unsigned int len) +{ + if (len > v->end) /* will not reduce the length */ + vector_set_new_min_length(v, len) ; +} ; + +/* Want vector to be the given length. */ +/* */ +/* If this is less than the current length, items are discarded. It */ +/* is the caller's responsibility to have freed anything that needs it. */ +/* */ +/* Adjusts logical and physical end of the vector as required, filling */ +/* with NULLs upto any new logical end -- does not allocate any more */ +/* than is exactly necessary. */ +Inline void +vector_set_length(vector v, unsigned int len) +{ + if (len > v->end) + vector_set_new_min_length(v, len) ; /* Extend if new length greater */ + else + v->end = len ; /* chop */ +} ; + +/* Return index of end of vector (index of last item + 1) */ +Inline vector_index +vector_length(vector v) +{ + return v->end ; +} ; + +/* Returns whether vector is empty or not. */ +Inline int +vector_is_empty(vector v) +{ + return (v->end == 0) ; +} ; + +/* Returns highly restricted pointer to vector body */ +//Inline const void* const* +//vector_body(vector v) +//{ +// return (const void* const*)v->p_items ; +//} ; + +Inline vector_body_t +vector_body(vector v) +{ + return (vector_body_t)v->p_items ; +} ; + +/* Access functions -- Inline for obvious reasons. */ + +/* Get pointer to item. Returns NULL if accessing beyond end. */ +Inline p_vector_item +vector_get_item(vector v, vector_index i) +{ + return (i < v->end) ? v->p_items[i] : NULL ; +} ; + +/* Get pointer to first item. Returns NULL if vector empty. */ +Inline p_vector_item +vector_get_first_item(vector v) +{ + return (v->end != 0) ? v->p_items[0] : NULL ; +} ; + +/* Get pointer to last item. Returns NULL if vector empty. */ +Inline p_vector_item +vector_get_last_item(vector v) +{ + return (v->end != 0) ? v->p_items[v->end - 1] : NULL ; +} ; + +/* Set item value in vector. Extend vector if required. */ +/* NB: it is the caller's responsibility to release memory used by any */ +/* current value of the item, if required. */ +Inline void +vector_set_item(vector v, vector_index i, void* p_v) +{ + vector_ensure(v, i) ; + v->p_items[i] = (p_vector_item)p_v ; +} ; + +/* Set dst item to be a copy of the src item. Extend vector if required. + * + * NB: it is the caller's responsibility to look after the memory being + * used by the current dst item or the new (duplicated) src item. + */ +Inline void +vector_assign_item(vector v, vector_index dst, vector_index src) +{ + vector_set_item(v, dst, vector_get_item(v, src)) ; +} ; + +/* Push value onto vector, extending as required. */ +Inline void +vector_push_item(vector v, void* p_v) +{ + vector_index i = vector_extend_by_1(v) ; + v->p_items[i] = (p_vector_item)p_v ; +} ; + +/* Pop value from vector. Returns NULL if vector is empty. */ +/* NB: does NOT change the size of the vector body. */ +Inline p_vector_item +vector_pop_item(vector v) +{ + return (v->end > 0) ? v->p_items[--v->end] : NULL ; +} ; #endif /* _ZEBRA_VECTOR_H */ |