*nix Documentation Project
·  Home
 +   man pages
·  Linux HOWTOs
·  FreeBSD Tips
·  *niX Forums

  man pages->FreeBSD man pages -> heap_delete (3)              
Title
Content
Arch
Section
 

HEAP(2)

Contents


NAME    [Toc]    [Back]

     heap_new, heap_free, heap_insert, heap_delete, heap_increased,
     heap_decreased, heap_element, heap_for_each -- heap implementation of
     priority queues

SYNOPSIS    [Toc]    [Back]

     #include <isc/heap.h>

     heap_context
     heap_new(heap_higher_priority_func higher_priority,
	 heap_index_func index, int array_size_increment);

     int
     heap_free(heap_context ctx);

     int
     heap_insert(heap_context ctx, void *elt);

     int
     heap_delete(heap_context ctx, int i);

     int
     heap_increased(heap_context ctx, int i);

     int
     heap_decreased(heap_context ctx, int i);

     void *
     heap_element(heap_context ctx, int i);

     int
     heap_for_each(heap_context ctx, heap_for_each_func action, void *uap);

DESCRIPTION    [Toc]    [Back]

     These functions implement heap-based priority queues.  The user defines a
     priority scheme, and provides a function for comparison of the priority
     of heap elements (see the description of the heap_higher_priority_func
     function pointer, below).

     Each of the functions depends upon the heap_context type, which is a
     pointer to a struct heap_context (see heap.h for more information).

     The heap.h header file also defines the following set of function function
 pointers:

	   typedef int (*heap_higher_priority_func)(void *, void *);
	   typedef void (*heap_index_func)(void *, int);
	   typedef void (*heap_for_each_func)(void *, void *);

     These are pointers to user-defined functions.  The
     heap_higher_priority_func type is a pointer to a function which compares
     two different heap (queue) elements and returns an int which answers the
     question, "Does the first queue element have a higher priority than the
     second?"  In other words, a function pointer of this type must return a
     number greater than zero if the element indicated by the first argument
     is of a higher priority than that indicated by the second element, and
     zero otherwise.

     The other two function pointers are documented in the descriptions of
     heap_new() (heap_index_func) and heap_for_each() (heap_for_each_func),
     below.

     The function heap_new() initializes a struct heap_context and returns a
     pointer to it.  The higher_priority function pointer must be non-NULL.
     As explained above, this refers to a function supplied by the user which
     compares the priority of two different queue or heap elements; see above
     for more information.  The second argument, index, is a pointer to a
     user-defined function whose arguments are a heap element and its index in
     the heap.	Index is intended to provide the user a means of knowing the
     internal index of an element in the heap while maintaining the opacity of
     the implementation; since the user has to know the actual indexes of heap
     elements in order to use, e.g., heap_delete() or heap_element(), the user
     index function could store the index in the heap element, itself.	If
     index is non-NULL, then it is called whenever the index of an element
     changes, allowing the user to stay up-to-date with index changes.	The
     last argument, array_size_increment will be used, as its name suggests,
     by malloc(3) or realloc(3) to increment the array which implements the
     heap; if zero, a default value will be used.

     The heap_free() function frees the given heap_context argument (ctx),
     which also frees the entire heap, if it is non-NULL.  The argument ctx
     should be non-NULL.

     The heap_insert() function is used to insert the new heap element elt
     into the appropriate place (priority-wise) in the heap indicated by ctx
     (a pointer to a heap_context).  If non-NULL, the user-defined
     higher_priority function pointer associated with the indicated heap is
     used to determine that ``appropriate place''; the highest-priority elements
 are at the front of the queue (top of the heap).  (See the description
 of heap_new(), above, for more information.)

     The function heap_delete() is used to delete the i-th element of the
     queue (heap), and fixing up the queue (heap) from that element onward via
     the priority as determined by the user function pointed to by
     higher_priority function pointer (see description of heap_new(), above).

     heap_increased()

     heap_decreased()

     The heap_element() function returns the i-th element of the queue/heap
     indicated by ctx, if possible.

     The heap_for_each() function provides a mechanism for the user to increment
 through the entire queue (heap) and perform some action upon each of
     the queue elements.  This action is pointer to a user-defined function
     with two arguments, the first of which should be interpreted by the
     user's function as a heap element.  The second value passed to the user
     function is just the uap argument to heap_for_each(); this allows the
     user to specify additional arguments, if necessary, to the function
     pointed to by action.

RETURN VALUES    [Toc]    [Back]

     heap_new()        NULL if unable to malloc(3) a struct heap_context or if
		       the higher_priority function pointer is NULL; otherwise,
 a valid heap_context .

     heap_free()       -1 if ctx is NULL (with errno set to EINVAL); otherwise,
 0.

     heap_insert()     -1 if either ctx or elt is NULL, or if an attempt to
		       malloc(3) or realloc(3) the heap array fails (with
		       errno set to EINVAL or ENOMEM, respectively).  Otherwise,
 0.

     heap_delete()     -1 if ctx is NULL or i is out-of-range (with errno set
		       to EINVAL); 0 otherwise.

     heap_increased()  As for heap_delete().

     heap_decreased()  As for heap_delete().

     heap_element()    NULL if ctx is NULL or i out-of-bounds (with errno set
		       to EINVAL); otherwise, a pointer to the i-th queue element.


     heap_for_each()   -1 if either ctx or action is NULL (with errno set to
		       EINVAL); 0 otherwise.

FILES    [Toc]    [Back]

     heap.h	 heap library header file

DIAGNOSTICS    [Toc]    [Back]

     Please refer to RETURN VALUES.

ERRORS    [Toc]    [Back]

     The variable errno is set by heap_free(), heap_insert(), heap_delete(),
     heap_increased(), and heap_decreased() under the conditions of invalid
     input (EINVAL) or lack of memory (ENOMEM); please refer to RETURN VALUES.

SEE ALSO    [Toc]    [Back]

      
      
     malloc(3), realloc(3).

     Cormen, Leiserson, and Rivest, Introduction to Algorithms, chapter 7, MIT
     Press / McGraw Hill, 1990, ISBN 0-262-03141-8.

     Sedgewick, Algorithms, 2nd ed'n, chapter 11, Addison-Wesley, 1988, ISBN
     0-201-06673-4.

AUTHORS    [Toc]    [Back]

     The heap library was implemented by Bob Halley (halley@vix.com) of Vixie
     Enterprises, Inc., for the Internet Software consortium, and was adapted
     from the two books listed in the SEE ALSO section, above.

4th Berkeley Distribution	January 1, 1997      4th Berkeley Distribution
[ Back ]
 Similar pages
Name OS Title
SIMPLEQ_INSERT_HEAD NetBSD implementations of singlylinked lists, lists, simple queues, tail queues, and circular queues
SIMPLEQ_INSERT_TAIL NetBSD implementations of singlylinked lists, lists, simple queues, tail queues, and circular queues
SIMPLEQ_INSERT_AFTER NetBSD implementations of singlylinked lists, lists, simple queues, tail queues, and circular queues
SIMPLEQ_NEXT NetBSD implementations of singlylinked lists, lists, simple queues, tail queues, and circular queues
SIMPLEQ_REMOVE_HEAD NetBSD implementations of singlylinked lists, lists, simple queues, tail queues, and circular queues
TAILQ_EMPTY NetBSD implementations of singlylinked lists, lists, simple queues, tail queues, and circular queues
queue NetBSD implementations of singlylinked lists, lists, simple queues, tail queues, and circular queues
SIMPLEQ_INIT NetBSD implementations of singlylinked lists, lists, simple queues, tail queues, and circular queues
SIMPLEQ_HEAD_INITIALIZER NetBSD implementations of singlylinked lists, lists, simple queues, tail queues, and circular queues
LIST_EMPTY NetBSD implementations of singlylinked lists, lists, simple queues, tail queues, and circular queues
Copyright © 2004-2005 DeniX Solutions SRL
newsletter delivery service