Annotation of embedaddon/dhcp/includes/heap.h, revision 1.1.1.1
1.1 misho 1: /*
2: * Copyright (C) 2004-2007 Internet Systems Consortium, Inc. ("ISC")
3: * Copyright (C) 1997-2001 Internet Software Consortium.
4: *
5: * Permission to use, copy, modify, and distribute this software for any
6: * purpose with or without fee is hereby granted, provided that the above
7: * copyright notice and this permission notice appear in all copies.
8: *
9: * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
10: * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
11: * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
12: * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
13: * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
14: * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
15: * PERFORMANCE OF THIS SOFTWARE.
16: */
17:
1.1.1.1 ! misho 18: /* $Id: heap.h,v 1.3 2007/05/19 19:16:25 dhankins Exp $ */
1.1 misho 19:
20: #ifndef ISC_HEAP_H
21: #define ISC_HEAP_H 1
22:
23: /*! \file isc/heap.h */
24:
25: /*%
26: * The comparision function returns ISC_TRUE if the first argument has
27: * higher priority than the second argument, and ISC_FALSE otherwise.
28: */
29: typedef isc_boolean_t (*isc_heapcompare_t)(void *, void *);
30:
31: /*%
32: * The index function allows the client of the heap to receive a callback
33: * when an item's index number changes. This allows it to maintain
34: * sync with its external state, but still delete itself, since deletions
35: * from the heap require the index be provided.
36: */
37: typedef void (*isc_heapindex_t)(void *, unsigned int);
38:
39: /*%
40: * The heapaction function is used when iterating over the heap.
41: *
42: * NOTE: The heap structure CANNOT BE MODIFIED during the call to
43: * isc_heap_foreach().
44: */
45: typedef void (*isc_heapaction_t)(void *, void *);
46:
47: typedef struct isc_heap isc_heap_t;
48:
49: isc_result_t
50: isc_heap_create(isc_heapcompare_t compare,
51: isc_heapindex_t index, unsigned int size_increment,
52: isc_heap_t **heapp);
53: /*!<
54: * \brief Create a new heap. The heap is implemented using a space-efficient
55: * storage method. When the heap elements are deleted space is not freed
56: * but will be reused when new elements are inserted.
57: *
58: * Requires:
59: *\li "mctx" is valid.
60: *\li "compare" is a function which takes two void * arguments and
61: * returns ISC_TRUE if the first argument has a higher priority than
62: * the second, and ISC_FALSE otherwise.
63: *\li "index" is a function which takes a void *, and an unsigned int
64: * argument. This function will be called whenever an element's
65: * index value changes, so it may continue to delete itself from the
66: * heap. This option may be NULL if this functionality is unneeded.
67: *\li "size_increment" is a hint about how large the heap should grow
68: * when resizing is needed. If this is 0, a default size will be
69: * used, which is currently 1024, allowing space for an additional 1024
70: * heap elements to be inserted before adding more space.
71: *\li "heapp" is not NULL, and "*heap" is NULL.
72: *
73: * Returns:
74: *\li ISC_R_SUCCESS - success
75: *\li ISC_R_NOMEMORY - insufficient memory
76: */
77:
78: void
79: isc_heap_destroy(isc_heap_t **heapp);
80: /*!<
81: * \brief Destroys a heap.
82: *
83: * Requires:
84: *\li "heapp" is not NULL and "*heap" points to a valid isc_heap_t.
85: */
86:
87: isc_result_t
88: isc_heap_insert(isc_heap_t *heap, void *elt);
89: /*!<
90: * \brief Inserts a new element into a heap.
91: *
92: * Requires:
93: *\li "heapp" is not NULL and "*heap" points to a valid isc_heap_t.
94: */
95:
96: void
97: isc_heap_delete(isc_heap_t *heap, unsigned int index);
98: /*!<
99: * \brief Deletes an element from a heap, by element index.
100: *
101: * Requires:
102: *\li "heapp" is not NULL and "*heap" points to a valid isc_heap_t.
103: *\li "index" is a valid element index, as provided by the "index" callback
104: * provided during heap creation.
105: */
106:
107: void
108: isc_heap_increased(isc_heap_t *heap, unsigned int index);
109: /*!<
110: * \brief Indicates to the heap that an element's priority has increased.
111: * This function MUST be called whenever an element has increased in priority.
112: *
113: * Requires:
114: *\li "heapp" is not NULL and "*heap" points to a valid isc_heap_t.
115: *\li "index" is a valid element index, as provided by the "index" callback
116: * provided during heap creation.
117: */
118:
119: void
120: isc_heap_decreased(isc_heap_t *heap, unsigned int index);
121: /*!<
122: * \brief Indicates to the heap that an element's priority has decreased.
123: * This function MUST be called whenever an element has decreased in priority.
124: *
125: * Requires:
126: *\li "heapp" is not NULL and "*heap" points to a valid isc_heap_t.
127: *\li "index" is a valid element index, as provided by the "index" callback
128: * provided during heap creation.
129: */
130:
131: void *
132: isc_heap_element(isc_heap_t *heap, unsigned int index);
133: /*!<
134: * \brief Returns the element for a specific element index.
135: *
136: * Requires:
137: *\li "heapp" is not NULL and "*heap" points to a valid isc_heap_t.
138: *\li "index" is a valid element index, as provided by the "index" callback
139: * provided during heap creation.
140: *
141: * Returns:
142: *\li A pointer to the element for the element index.
143: */
144:
145: void
146: isc_heap_foreach(isc_heap_t *heap, isc_heapaction_t action, void *uap);
147: /*!<
148: * \brief Iterate over the heap, calling an action for each element. The
149: * order of iteration is not sorted.
150: *
151: * Requires:
152: *\li "heapp" is not NULL and "*heap" points to a valid isc_heap_t.
153: *\li "action" is not NULL, and is a function which takes two arguments.
154: * The first is a void *, representing the element, and the second is
155: * "uap" as provided to isc_heap_foreach.
156: *\li "uap" is a caller-provided argument, and may be NULL.
157: *
158: * Note:
159: *\li The heap structure CANNOT be modified during this iteration. The only
160: * safe function to call while iterating the heap is isc_heap_element().
161: */
162:
163: #endif /* ISC_HEAP_H */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>