path: root/lib/heap.c

/* Generic heap data structure -- functions.
 * 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 <zebra.h>

#include "zassert.h"
#include "heap.h"
#include "memory.h"

/* Heaps are implemented as a structure which includes a vector structure.
 * So items in the heap are items in a vector, which are pointers to the item
 * values.
 *
 * The heap structure may be statically allocated, embedded in another
 * structure, or allocated dynamically.  In any case the heap operations
 * require the address of the heap structure -- see typedef for heap.
 *
 * An essential component of a heap is its comparison function.  So, a heap
 * CANNOT be used before it has been initialised and the comparison function
 * set.  (This is unlike a vector, which may be implicitly initialised empty by
 * zeroising the vector structure.)
 *
 * Items may be pushed onto or popped off the heap, which is organised so that
 * the top item has the smallest value -- according to the heap's comparison
 * function.  (For equal values, the order is undefined.)
 *
 * The top item in the heap may be examined, and its value may be updated.
 * (Updating the top item is more efficient than popping and then pushing it.)
 *
 * Items may be deleted from the heap.  Items may have their value updated
 * while they are in the heap.  Both of these operations cause the heap to be
 * reorganised to maintain the heap's partial ordering.  Note: these operations
 * require knowledge of where in the heap the item is -- which, by default, is
 * done by a linear scan of the heap.  For large heaps, there is the option to
 * keep a "backlink" from the item to it's heap position.
 *
 * Vectors may be pushed onto a heap -- copying or moving the contents.
 *
 * Heaps may popped to a vector -- copying or moving the contents.  The
 * resulting vector is fully sorted.
 *
 * ----------------------------
 * Comparison function for heap.
 *
 *   int heap_cmp(...** a, ...** b) ...
 *
 * Must return -1, 0, +1 : where -1 => a < b, 0 => a == b & +1 => a > b
 *
 * Heap will sort "smallest" to the top.  If you want the biggest at the top,
 * return -1 * usual comparison.  Note that the effective heap ordering for
 * equal values is, essentially, random.
 *
 * NB: like other comparison functions (cf qsort) the parameters are pointers
 *     to pointers to the value.
 *
 * NB: there should never be NULL items in the heap.
 */

/*==============================================================================
 * Initialisation, allocation, reset etc.
 */

static heap
heap_setup(heap h, int new_vector, vector_index size, heap_cmp* cmp,
                              int with_backlink, unsigned int backlink_offset) ;

/* Initialize heap -- allocating heap structure if required.
 *
 * Does not allocate the underlying vector if the heap is initialised empty.
 *
 * eg:
 *
 *  ... = heap_new_init_simple(NULL, 0, (heap_cmp*)my_cmp)
 *
 * See:  #define heap_init_new_simple(h, size, cmp)
 *       #define heap_init_new_backlinked(h, size, cmp, offset)
 *
 * NB: when initialising an existing heap structure it is ESSENTIAL that
 *     any previous heap and its contents have been released, because this
 *     function simply discards whatever was there before.  (This function may
 *     be called to initialise a heap structure which has never been
 *     initialised.)
 *
 * Backlink:
 *
 *   The heap_delete_item and heap_update_item functions need the heap
 *   position of the item.  The default way of finding that is to scan the
 *   underlying heap array, looking for the address of the item.
 *
 *   If either of these functions is done often and on large heaps, it is
 *   possible to speed this up by implementing a 'backlink'.  This requires
 *   a field of type heap_backlink_t in the item structure, and it is the
 *   offset of that which must be initialised here, eg:
 *
 *     ... = heap_new_init_backlinked(NULL, 0, (heap_cmp*)my_cmp,
 *     				offset_of(struct xxx_heap_item, backlink)) ;
 *
 *   This adds a little extra work to every change in the heap -- keeping the
 *   backlink of any moved item up to date.  But avoids a linear search for
 *   every heap_delete_item or heap_update_item.
 *
 * Returns the heap which has been initialised.
 */
heap
heap_init_new(heap h, unsigned int size, heap_cmp* cmp,
                                int with_backlink, unsigned int backlink_offset)
{
  if (h == NULL)
    h = XCALLOC(MTYPE_HEAP, sizeof(struct heap)) ;
  else
    memset(h, 0, sizeof(struct heap)) ;

  return heap_setup(h, 1, size, cmp, with_backlink, backlink_offset) ;
} ;

/* Reinitialise heap (or create a new one, if h == NULL).
 *
 * Allocates heap structure if none given -- allocating vector if size != 0.
 * Otherwise, re-initialise the heap and any vector (reusing its memory).
 *
 * See:  #define heap_re_init_simple(h, size, cmp)
 *       #define heap_re_init_backlinked(h, size, cmp, offset)
 *
 * NB: when reinitialising an existing heap it is the caller's
 *     responsibility to release any item values *before* doing this.
 *
 * Returns the heap that has been reinitialised.
 */
heap
heap_re_init(heap h, unsigned int size, heap_cmp* cmp,
                                int with_backlink, unsigned int backlink_offset)
{
  if (h == NULL)
    return heap_init_new(h, size, cmp, with_backlink, backlink_offset) ;
  else
    return heap_setup(h, 0, size, cmp, with_backlink, backlink_offset) ;
} ;

/* Release heap contents (underlying vector), and (if required) release the
 * heap structure.
 *
 * Returns NULL if releases heap, otherwise the reset heap.
 *
 * If does not release the heap, it retains the comparison function and any
 * backlink setting -- so heap can be reused without reinitialising it.
 *
 * NB: it is the callers responsibility to release any heap item values
 *     *before* doing this.
 */
heap
heap_reset(heap h, int free_structure)
{
  vector_reset_keep(&h->v) ;    /* vector structure is embedded in the heap   */

  if (free_structure)
    XFREE(MTYPE_VECTOR, h) ;    /* sets h = NULL */

  return h ;
} ;

/* Common set-up for heap_init_new() & heap_reset().
 */
static heap
heap_setup(heap h, int new_vector, unsigned int size, heap_cmp* cmp,
                                int with_backlink, unsigned int backlink_offset)
{
  assert(cmp != NULL) ;         /* or there will be tears */

  h->cmp   = cmp ;
  h->state = with_backlink ? Heap_Has_Backlink : 0 ;
  h->backlink_offset = backlink_offset ;

  if (new_vector)
    vector_init_new(&h->v, size) ;
  else
    vector_re_init(&h->v, size) ;

  return h ;
} ;

/* Ream (another) item out of the given heap.
 *
 * If heap is empty, release the underlying vector, and (if required) release
 * the heap structure.
 *
 * See: #define heap_ream_free(h) heap_ream(h, 1)
 *      #define heap_ream_keep(h) heap_ream(h, 0)
 *
 * Useful for emptying out and resetting/discarding a heap:
 *
 *     while ((p_v = heap_ream_free(h)))
 *       ... do what's required to release the item p_v
 *
 * Returns NULL when heap is empty (and structure has been freed, if required).
 *
 * If does not release the heap, it retains the comparison function and any
 * backlink setting -- so heap can be reused without reinitialising it.
 *
 * NB: once the process of reaming a heap has started: (a) MUST NOT attempt to
 *     use the heap until process completes, and (b) MUST complete the process.
 *
 * NB: items are reamed out in no defined order.
 */
p_vector_item
heap_ream(heap h, int free_structure)
{
  p_vector_item p_v ;

  if (h == NULL)
    return NULL ;

  if ((p_v = vector_ream_keep(&h->v)) == NULL)
    heap_reset(h, free_structure) ;

  return p_v ;
} ;

/*==============================================================================
 * Simple Heap Operations -- see also the Inline functions.
 */

/* Pop item off the heap.
 *
 * Returns the popped value, which is NULL if the heap was (and still is) empty.
 */
p_vector_item
heap_pop_item(heap h)
{
  p_vector_item p_v ;
  p_vector_item p_x ;

  p_v = vector_pop_item(&h->v) ;  /* extract last item, if any 	          */
  if ((p_v == NULL) || (h->v.end == 0))
    return p_v ;                  /* done if empty or last was also first */

  p_x = h->v.p_items[0] ;	  /* this is what we are popping	  */

  heap_bubble_down(h, 0, p_v) ;	  /* reposition what was the last item	  */
				  /* updating any backlink		  */
  return p_x ;
} ;

/* Pop one item off the heap and promptly push another.
 *
 * In this combination, the pop is essentially free.
 *
 * Returns the popped value, which is NULL if the heap was (and still is) empty.
 */
p_vector_item
heap_pop_push_item(heap h, p_vector_item p_v)
{
  p_vector_item p_x ;

  dassert(p_v != NULL) ;           /* no NULLs, thank you.               */

  p_x = heap_top_item(h) ;         /* what we are popping                */

  if (p_x == NULL)
    heap_push_item(h, p_v) ;       /* for empty heap, this deals with    */
                                   /* extending heap etc.                */
  else
    heap_bubble_down(h, 0, p_v) ;  /* position the replacement           */
                                   /* setting any backlink               */
  return p_x ;
} ;

/*==============================================================================
 * Heap Operations which use 'backlink', if implemented.
 */

/* Delete given item from the heap.
 *
 * See notes on backlink, above.
 *
 * NB: do NOT try this on items which are not in the given heap !
 */
void
heap_delete_item(heap h, p_vector_item p_v)
{
  p_vector_item p_x ;
  vector_index i ;

  i = heap_find_item(h, p_v) ;    /* index of item to be deleted              */

  p_x = vector_pop_item(&h->v) ;  /* extract last item, if any 	              */

  if (i < h->v.end)               /* if not deleting the last item...         */
    heap_bubble(h, i, p_x) ;      /* ...reinsert what was last, at the delete */
                                  /* position, updating any backlink          */
} ;

/*==============================================================================
 * Other Heap Operations.
 */

/* Push entire vector onto heap copying or moving items as required.
 *
 * Copy or move vector to end of heap's vector, then move each
 * (non-NULL) item into heap order (discarding any NULL items).
 *
 * See: #define heap_push_vector_copy(h, v)
 *      #define heap_push_vector_move(h, v)
 */
void
heap_push_vector(heap h, vector v, int move_vector)
{
  vector_index i = h->v.end ;
  vector_index e ;
  vector_index n = v->end ;
  p_vector_item p_v ;

  if (move_vector)
    vector_move_append(&h->v, v) ;
  else
    vector_copy_append(&h->v, v) ;

  e = i ;                           /* old end of the heap.     */
  while (n--) {
    p_v = h->v.p_items[i++] ;
    if (p_v != NULL)
      heap_bubble_up(h, e++, p_v) ; /* move new item into position in heap  */
                                    /* setting any backlink                 */
  } ;

  h->v.end = e ;                    /* new end of heap          */
} ;

/* Pop given heap to vector -- creating vector if required (v == NULL).
 *
 * Resulting vector is fully sorted.
 *
 * Moves or copies the contents of the heap.
 *
 * See: #define heap_pop_vector_copy(v, h)
 *      #define heap_pop_vector_move(v, h)
 *
 * NB: when creating new vector, will be exactly the required size.
 *
 * 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.
 */
vector
heap_pop_vector(vector v, heap h, int move_heap)
{
  vector_index n = h->v.end ;
  vector_index i ;

  v = vector_re_init(v, n) ;      /* guarantees >= 'n' items in vector  */
  v->end = n ;

  for (i = 0 ; i < n ; i++)
    v->p_items[i] = heap_pop_item(h) ;

  if (!move_heap)
    vector_copy_here(&h->v, v) ;  /* fully sorted is also heap ordered ! */

  return v ;
} ;

/*==============================================================================
 * The Heap internal mechanics.
 */

/* Returns pointer to backlink value in heap item: lvalue or rvalue	*/
#define HEAP_BACKLINK(h, p_v) \
  *(heap_backlink_t*)((char*)(p_v) + (h)->backlink_offset)
/* Sets backlink, if required.						*/
#define heap_set_backlink(h, p_v, i) \
  if ((h)->state & Heap_Has_Backlink) HEAP_BACKLINK(h, p_v) = (i)

/* Returns index of parent.		*/
#define HEAP_UP(i)   (((i) - 1) / 2)
/* Returns index of left child.		*/
#define HEAP_DOWN(i) (((i) * 2) + 1)

/* Insert given item in the required place in heap, given that there is now
 * a hole at the given position -- may move up or down the heap, or stay put.
 *
 * Bubbles up or down as required.
 *
 * Note that this sets the backlink on the given item.
 */
private void
heap_bubble(heap h, vector_index i, p_vector_item p_v)
{
  /* If this is < parent, we bubble upwards.	*/
  if ((i != 0) && (h->cmp(&p_v, &h->v.p_items[HEAP_UP(i)]) < 0))
    heap_bubble_up(h, i, p_v) ;
  /* Otherwise we try bubbling downwards.       */
  else
    heap_bubble_down(h, i, p_v) ;
} ;

/* Insert given item in the required place in heap, given that there is now
 * a hole at the given position -- where we know may *only* move up the heap.
 *
 * Note that this sets the backlink on the given item.
 *
 * NB: ignores anything in the heap beyond 'i' -- in particular does not use
 *     v.end at all.  So this can be used to work along a vector and bring
 *     items into heap order.
 */
private void
heap_bubble_up(heap h, vector_index i, p_vector_item p_v)
{
  p_vector_item* ha = h->v.p_items ;  /* underlying array        */
  vector_index   ip ;                 /* index of parent         */
  p_vector_item  p_p ;                /* pointer to parent item  */

  dassert(ha != NULL) ;

  while (i != 0)
    {
      ip = HEAP_UP(i) ;
      p_p = ha[ip] ;                    /* get parent                   */

      if (h->cmp(&p_v, &p_p) >= 0)
	break ;				/* stop when value >= parent	*/

      ha[i] = p_p ;		        /* move parent down...		*/
      heap_set_backlink(h, p_p, i) ;	/* ...updating any backlink	*/

      i = ip ;				/* move up the heap		*/
    } ;

  ha[i] = p_v ;		                /* place in new position...	*/
  heap_set_backlink(h, p_v, i) ;	/* ...updating any backlink	*/
} ;

/* Insert given item in the required place in heap, given that there is now
 * a hole at the given position -- where we know may *only* move down the heap.
 *
 * Note that this sets the backlink on the given item.
 */
private void
heap_bubble_down(heap h, vector_index i, p_vector_item p_v)
{
  vector_index   e  = h->v.end ;      /* end of heap          */
  vector_index ic ;                   /* index of child       */
  vector_index is ;                   /* index of sibling     */
  p_vector_item p_c ;                 /* pointer to child     */
  p_vector_item p_s ;                 /* pointer to sibling   */

  p_vector_item* ha = h->v.p_items ;  /* underlying array     */
  dassert(ha != NULL) ;

  while (1)
    {
      ic = HEAP_DOWN(i) ;
      if (ic >= e)
	break ;                        /* Quit if run out of heap !     */
      p_c = ha[ic] ;                   /* get left hand child           */

      is = ic + 1 ;
      if (is < e)                      /* is there a right hand child ? */
	{
	  p_s = ha[is] ;               /* get right hand child          */
	  if (h->cmp(&p_s, &p_c) < 0)
	    {
	      ic  = is ;               /* select smaller sibling        */
	      p_c = p_s ;
	    } ;
	} ;

      if (h->cmp(&p_v, &p_c) <= 0)
        break ;                        /* stop when <= both children    */

      ha[i] = p_c ;                    /* move smaller child up         */
      heap_set_backlink(h, p_c, i) ;   /* ...updating any backlink	*/

      i = ic ;                         /* move down the heap		*/
    } ;

  ha[i] = p_v ;                         /* place in new position...     */
  heap_set_backlink(h, p_v, i) ;        /* ...updating any backlink     */
} ;

/* Find index of given item in the given heap.		*/
private vector_index
heap_find_item(heap h, p_vector_item p_v)
{
  vector_index i ;

  if (h->state & Heap_Has_Backlink)
    i = HEAP_BACKLINK(h, p_v) ;
  else
    {
      for (i = 0 ; i < h->v.end ; ++i)
	if (h->v.p_items[i] == p_v)
	  return i ;
    } ;

  assert((i < h->v.end) && (h->v.p_items[i] == p_v)) ;

  return i ;
} ;