path: root/lib/vector.h

/* 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
 * 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.
 */

#ifndef _ZEBRA_VECTOR_H
#define _ZEBRA_VECTOR_H

/* 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
{
  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         */
};

/* 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.						      */

/* 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.
 */

extern vector vector_init (unsigned int size);
Inline void vector_ensure(vector v, vector_index i) ;
extern int vector_set (vector v, void *val);
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, 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 */