heap.h

/*
 * $Id: heap.h,v 1.4 2001/10/08 16:18:31 hno Exp $
 *
 * AUTHOR: John Dilley, Hewlett Packard
 *
 * SQUID Web Proxy Cache          http://www.squid-cache.org/
 * ----------------------------------------------------------
 *
 *  Squid is the result of efforts by numerous individuals from
 *  the Internet community; see the CONTRIBUTORS file for full
 *  details.   Many organizations have provided support for Squid's
 *  development; see the SPONSORS file for full details.  Squid is
 *  Copyrighted (C) 2001 by the Regents of the University of
 *  California; see the COPYRIGHT file for full details.  Squid
 *  incorporates software developed and/or copyrighted by other
 *  sources; see the CREDITS file for full details.
 *
 *  This program 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 of the License, or
 *  (at your option) any later version.
 *  
 *  This program 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 this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
 *  
 */

/****************************************************************************
 * Copyright (C) 1999 by Hewlett Packard
 *
 * Heap data structure.  Used to store objects for cache replacement.  The
 * heap is implemented as a contiguous array in memory.  Heap sort and heap
 * update are done in-place.  The heap is ordered with the smallest value at
 * the top of the heap (as in the smallest object key value).  Child nodes
 * are larger than their parent.
 ****************************************************************************/

#ifndef	SQUID_HEAP_H
#define	SQUID_HEAP_H

/*
 * Function for generating heap keys.  The first argument will typically be
 * a dws_md_p passed in as a void *.  Should find a way to get type safety
 * without having heap know all about metadata objects...  The second arg is
 * the current aging factor for the heap.
 */
typedef unsigned long heap_mutex_t;
typedef void *heap_t;
typedef double heap_key;
typedef heap_key heap_key_func(heap_t, heap_key);


/*
 * Heap node.  Has a key value generated by a key_func, id (array index) so
 * it can be quickly found in its heap, and a pointer to a data object that
 * key_func can generate a key from.
 */
typedef struct _heap_node {
    heap_key key;
    unsigned long id;
    heap_t data;
} heap_node;


/*
 * Heap object.  Holds an array of heap_node objects along with a heap size
 * (array length), the index of the last heap element, and a key generation
 * function.  Also stores aging factor for this heap.
 */
typedef struct _heap {
    heap_mutex_t lock;
    unsigned long size;
    unsigned long last;
    heap_key_func *gen_key;	/* key generator for heap */
    heap_key age;		/* aging factor for heap */
    heap_node **nodes;
} heap;

/****************************************************************************
 * Public functions
 ****************************************************************************/

/* 
 * Create and initialize a new heap.
 */
extern heap *new_heap(int init_size, heap_key_func gen_key);

/* 
 * Delete a heap and clean up its memory.  Does not delete what the heap
 * nodes are pointing to!
 */
extern void delete_heap(heap *);

/*
 * Insert a new node into a heap, returning a pointer to it.  The heap_node
 * object returned is used to update or delete a heap object.  Nothing else
 * should be done with this data structure (especially modifying it!)  The
 * heap does not assume ownership of the data passed to it.
 */
extern heap_node *heap_insert(heap *, heap_t dat);

/*
 * Delete a node out of a heap.  Returns the heap data from the deleted
 * node.  The caller is responsible for freeing this data.
 */
extern heap_t heap_delete(heap *, heap_node * elm);

/*
 * The semantics of this routine is the same as the followings:
 *        heap_delete(hp, elm);
 *        heap_insert(hp, dat);
 * Returns the old data object from elm (the one being replaced).  The
 * caller must free this as necessary.
 */
extern heap_t heap_update(heap *, heap_node * elm, heap_t dat);

/* 
 * Generate a heap key for a given data object.  Alternative macro form:
 */
#ifdef	MACRO_DEBUG
extern heap_key heap_gen_key(heap * hp, heap_t dat);
#else
#define	heap_gen_key(hp,md)	((hp)->gen_key((md),(hp)->age))
#endif /* MACRO_DEBUG */


/* 
 * Extract the minimum (root) element and maintain the heap property.
 * Returns the data pointed to by the root node, which the caller must
 * free as necessary.
 */
extern heap_t heap_extractmin(heap *);

/* 
 * Extract the last leaf node (does not change the heap property).
 * Returns the data that had been in the heap which the caller must free if
 * necessary.  Note that the last node is guaranteed to be less than its
 * parent, but may not be less than any of the other (leaf or parent) notes
 * in the tree.  This operation is fast but imprecise.
 */
extern heap_t heap_extractlast(heap * hp);

/* 
 * Get the root key, the nth key, the root (smallest) element, or the nth
 * element.  None of these operations modify the heap.
 */
extern heap_key heap_peepminkey(heap *);
extern heap_key heap_peepkey(heap *, int n);

extern heap_t heap_peepmin(heap *);
extern heap_t heap_peep(heap *, int n);

/* 
 * Is the heap empty?  How many nodes (data objects) are in it? 
 */
#ifdef	MACRO_DEBUG
extern int heap_empty(heap *);
extern int heap_nodes(heap *);
#else /* MACRO_DEBUG */
#define	heap_nodes(heap)	((heap)->last)
#define	heap_empty(heap)	(((heap)->last <= 0) ? 1 : 0)
#endif /* MACRO_DEBUG */

/* 
 * Print the heap or a node in the heap.
 */
extern void heap_print(heap *);
extern void heap_printnode(char *msg, heap_node * elm);

extern int verify_heap_property(heap *);

#endif /* SQUID_HEAP_H */