3 Copyright (C) 2007 Sebastian Freundt
5 Author: Sebastian Freundt <hroptatyr@sxemacs.org>
7 * This file is part of SXEmacs.
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
20 * 3. Neither the name of the author nor the names of any contributors
21 * may be used to endorse or promote products derived from this
22 * software without specific prior written permission.
24 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR "AS IS" AND ANY EXPRESS OR
25 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
26 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
27 * DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
29 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
30 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
31 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
32 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
33 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
34 * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
37 /* Synched up with: Not in FSF. */
39 #ifndef INCLUDED_ase_heap_h_
40 #define INCLUDED_ase_heap_h_ 1
44 typedef enum ase_heap_kind_e ase_heap_kind_t;
45 typedef struct ase_heap_options_s *ase_heap_options_t;
46 typedef struct ase_dheap_s *ase_dheap_t;
47 typedef struct ase_wheap_s *ase_wheap_t;
48 typedef struct ase_yheap_cell_s *ase_yheap_cell_t;
49 typedef struct ase_yheap_s *ase_yheap_t;
51 typedef struct ase_heap_ops_s *ase_heap_ops_t;
52 typedef void*(*ase_heap_constr_f)(ase_heap_options_t);
53 typedef Lisp_Object(*ase_heap_wrap_f)(void*);
54 typedef void(*ase_heap_add_f)(void*, Lisp_Object, Lisp_Object);
55 typedef Lisp_Object(*ase_heap_pop_f)(void*);
57 extern Lisp_Object Qase_heap, Qase_heapp;
58 extern Lisp_Object Qase_yheap, Qase_yheapp;
59 extern Lisp_Object Qase_dheap, Qase_dheapp;
60 extern Lisp_Object Qase_wheap, Qase_wheapp;
61 extern Lisp_Object Qase_heap_default_kind;
63 extern void LTX_PUBINIT(ase_heap)(void);
64 extern void LTX_PUBREINIT(ase_heap)(void);
65 extern void LTX_PUBDEINIT(ase_heap)(void);
68 enum ase_heap_kind_e {
72 NUMBER_OF_ASE_HEAP_KINDS
75 struct ase_heap_ops_s {
76 ase_heap_constr_f constrf;
77 ase_heap_wrap_f wrapf;
82 struct ase_heap_options_s {
83 ase_binary_relation_t po; /* partial order to look for
84 * in ent_binary_reltable */
85 ase_binary_relation_f pof; /* partial order function */
86 ase_heap_kind_t kind; /* representation of the heap */
87 size_t min_size; /* minimum size of the dense array */
89 int coloured; /* whether we store coloured items */
91 /* just a ref counter for those nifty recycled items */
92 sxe_refcounter_t refcnt;
95 /* that way we can use a global macro */
96 #define ASE_HEAP_MUTEX_SORCERY sxe_mutex_t mtx
97 #define ASE_HEAP_OPTIONS_SORCERY ase_heap_options_t options
101 Lisp_Object *colours;
103 /* status and mutex for the entire heap */
104 ASE_HEAP_MUTEX_SORCERY;
105 int heapp; /* if heap obeys the heap property */
106 size_t alloc; /* allocated size of the heap */
107 size_t size; /* size of the heap (used cells) */
109 /* options to control the heap's behaviour */
110 ASE_HEAP_OPTIONS_SORCERY;
115 Lisp_Object *colours;
118 /* status and mutex for the entire heap */
119 ASE_HEAP_MUTEX_SORCERY;
120 int heapp; /* if heap obeys the heap property */
121 size_t alloc; /* allocated size of the heap */
122 size_t size; /* size of the heap (used cells) */
124 /* options to control the heap's behaviour */
125 ASE_HEAP_OPTIONS_SORCERY;
129 ase_yheap_cell_t root;
130 ase_yheap_cell_t first_free;
131 ase_yheap_cell_t last_free;
133 /* status and mutex for the entire heap */
134 ASE_HEAP_MUTEX_SORCERY;
135 int heapp; /* if heap obeys the heap property */
139 /* options to control the heap's behaviour */
140 ASE_HEAP_OPTIONS_SORCERY;
144 /* general heap thing (independent from underlying representation) */
145 #define ASE_HEAPP(_i) \
147 (EQ(XDYNACAT(_i)->type, Qase_wheap) || \
148 EQ(XDYNACAT(_i)->type, Qase_dheap) || \
149 EQ(XDYNACAT(_i)->type, Qase_yheap)))
150 #define CHECK_ASE_HEAP(x) \
153 dead_wrong_type_argument(Qase_heapp, x); \
155 #define CONCHECK_ASE_HEAP(x) \
158 x = wrong_type_argument(Qase_heapp, x); \
161 /* options and mutexes are generic */
163 #define ase_heap_options(_x) ((_x)->options)
164 #define ase_heap_options_po(_x) ((_x)->po)
165 #define ase_heap_options_pof(_x) ((_x)->pof)
166 #define ase_heap_options_kind(_x) ((_x)->kind)
167 #define ase_heap_options_min_size(_x) ((_x)->min_size)
168 #define ase_heap_options_coloured(_x) ((_x)->coloured)
169 #define ase_heap_options_refcnt(_x) ((_x)->refcnt)
170 #define ase_heap_opts_po(_x) (ase_heap_options(_x)->po)
171 #define ase_heap_opts_pof(_x) (ase_heap_options(_x)->pof)
172 #define ase_heap_opts_kind(_x) (ase_heap_options(_x)->kind)
173 #define ase_heap_opts_min_size(_x) (ase_heap_options(_x)->min_size)
174 #define ase_heap_opts_coloured(_x) (ase_heap_options(_x)->coloured)
175 #define ase_heap_opts_refcnt(_x) (ase_heap_options(_x)->refcnt)
177 #define ase_heap_mtx(_x) ((_x)->mtx)
178 #define ase_heap_init_mutex(_x) (SXE_MUTEX_INIT(&(ase_heap_mtx(_x))))
179 #define ase_heap_fini_mutex(_x) (SXE_MUTEX_FINI(&(ase_heap_mtx(_x))))
180 #define ase_heap_lock(_x) (SXE_MUTEX_LOCK(&(ase_heap_mtx(_x))))
181 #define ase_heap_unlock(_x) (SXE_MUTEX_UNLOCK(&(ase_heap_mtx(_x))))
184 #define ASE_YHEAPP(_i) \
185 (DYNACATP(_i) && EQ(XDYNACAT(_i)->type, Qase_yheap))
186 #define CHECK_ASE_YHEAP(x) \
188 if (!ASE_YHEAPP(x)) \
189 dead_wrong_type_argument(Qase_yheapp, x); \
191 #define CONCHECK_ASE_YHEAP(x) \
193 if (!ASE_YHEAPP(x)) \
194 x = wrong_type_argument(Qase_yheapp, x); \
196 #define XSETASE_YHEAP(_res, _int) (_res) = _ase_wrap_heap((_int))
197 #define XASE_YHEAP(_x) ((ase_yheap_t)get_dynacat(_x))
199 #define ase_yheap_root(_x) ((_x)->root)
200 #define ase_yheap_first_free(_x) ((_x)->first_free)
201 #define ase_yheap_last_free(_x) ((_x)->last_free)
203 #define ase_yheap_heapp(_x) ((_x)->heapp)
204 #define ase_yheap_size(_x) ((_x)->size)
205 #define ase_yheap_alloc(_x) ((_x)->alloc)
207 #define ase_yheap_cell_data(_x) ((_x)->data)
208 #define ase_yheap_cell_colour(_x) ((_x)->colour)
209 #define ase_yheap_cell_left(_x) ((_x)->left)
210 #define ase_yheap_cell_right(_x) ((_x)->right)
211 #define ase_yheap_cell_mother(_x) ((_x)->mother)
212 #define ase_yheap_cell_father(_x) ((_x)->father)
213 #define ase_yheap_cell_next(_x) ((_x)->next)
214 #define ase_yheap_cell_prev(_x) ((_x)->prev)
216 extern void ase_yheapify(ase_yheap_t);
217 extern Lisp_Object ase_yheap_to_listX(ase_yheap_t);
218 extern Lisp_Object ase_yheap_to_list(ase_yheap_t);
219 extern Lisp_Object ase_yheap_to_vectorX(ase_yheap_t);
220 extern Lisp_Object ase_yheap_to_vector(ase_yheap_t);
221 extern Lisp_Object ase_yheap_to_dllistX(ase_yheap_t);
222 extern Lisp_Object ase_yheap_to_dllist(ase_yheap_t);
225 #define ASE_DHEAPP(_i) \
226 (DYNACATP(_i) && EQ(XDYNACAT(_i)->type, Qase_dheap))
227 #define CHECK_ASE_DHEAP(x) \
229 if (!ASE_DHEAPP(x)) \
230 dead_wrong_type_argument(Qase_dheapp, x); \
232 #define CONCHECK_ASE_DHEAP(x) \
234 if (!ASE_DHEAPP(x)) \
235 x = wrong_type_argument(Qase_dheapp, x); \
237 #define XSETASE_DHEAP(_res, _int) (_res) = _ase_wrap_dheap((_int))
238 #define XASE_DHEAP(_x) ((ase_dheap_t)get_dynacat(_x))
240 #define ase_dheap_cells(_x) ((_x)->cells)
241 #define ase_dheap_colours(_x) ((_x)->colours)
243 #define ase_dheap_heapp(_x) ((_x)->heapp)
244 #define ase_dheap_size(_x) ((_x)->size)
245 #define ase_dheap_alloc(_x) ((_x)->alloc)
247 extern void ase_dheap_sort(ase_dheap_t);
248 extern Lisp_Object ase_dheap_to_listX(ase_dheap_t);
249 extern Lisp_Object ase_dheap_to_list(ase_dheap_t);
250 extern Lisp_Object ase_dheap_to_vectorX(ase_dheap_t);
251 extern Lisp_Object ase_dheap_to_vector(ase_dheap_t);
252 extern Lisp_Object ase_dheap_to_dllistX(ase_dheap_t);
253 extern Lisp_Object ase_dheap_to_dllist(ase_dheap_t);
256 #define ASE_WHEAPP(_i) \
257 (DYNACATP(_i) && EQ(XDYNACAT(_i)->type, Qase_wheap))
258 #define CHECK_ASE_WHEAP(x) \
260 if (!ASE_WHEAPP(x)) \
261 dead_wrong_type_argument(Qase_wheapp, x); \
263 #define CONCHECK_ASE_WHEAP(x) \
265 if (!ASE_WHEAPP(x)) \
266 x = wrong_type_argument(Qase_wheapp, x); \
268 #define XSETASE_WHEAP(_res, _int) (_res) = _ase_wrap_wheap((_int))
269 #define XASE_WHEAP(_x) ((ase_wheap_t)get_dynacat(_x))
271 #define ase_wheap_cells(_x) ((_x)->cells)
272 #define ase_wheap_colours(_x) ((_x)->colours)
273 #define ase_wheap_rbits(_x) ((_x)->rbits)
275 #define ase_wheap_heapp(_x) ((_x)->heapp)
276 #define ase_wheap_size(_x) ((_x)->size)
277 #define ase_wheap_alloc(_x) ((_x)->alloc)
279 extern void _ase_wheapify(ase_wheap_t);
280 extern void ase_wheap_sort(ase_wheap_t);
281 extern Lisp_Object ase_wheap_to_listX(ase_wheap_t);
282 extern Lisp_Object ase_wheap_to_list(ase_wheap_t);
283 extern Lisp_Object ase_wheap_to_vectorX(ase_wheap_t);
284 extern Lisp_Object ase_wheap_to_vector(ase_wheap_t);
285 extern Lisp_Object ase_wheap_to_dllistX(ase_wheap_t);
286 extern Lisp_Object ase_wheap_to_dllist(ase_wheap_t);
290 extern inline ase_yheap_t _ase_make_yheap(ase_heap_options_t opts);
291 extern inline Lisp_Object _ase_wrap_yheap(ase_yheap_t);
292 extern Lisp_Object ase_make_yheap(ase_heap_options_t opts);
293 extern void ase_add_yheap(ase_yheap_t h, Lisp_Object o, Lisp_Object colour);
294 extern Lisp_Object ase_pop_yheap(ase_yheap_t h);
295 extern Lisp_Object ase_yheap_top(ase_yheap_t h);
296 extern Lisp_Object ase_yheap_top_rank(ase_yheap_t h);
299 extern inline ase_dheap_t _ase_make_dheap(ase_heap_options_t opts);
300 extern inline Lisp_Object _ase_wrap_dheap(ase_dheap_t);
301 extern Lisp_Object ase_make_dheap(ase_heap_options_t opts);
302 extern void ase_add_dheap(ase_dheap_t h, Lisp_Object o, Lisp_Object colour);
303 extern Lisp_Object ase_pop_dheap(ase_dheap_t h);
304 extern Lisp_Object ase_dheap_top(ase_dheap_t h);
305 extern Lisp_Object ase_dheap_top_rank(ase_dheap_t h);
308 extern inline ase_wheap_t _ase_make_wheap(ase_heap_options_t opts);
309 extern inline Lisp_Object _ase_wrap_wheap(ase_wheap_t);
310 extern Lisp_Object ase_make_wheap(ase_heap_options_t opts);
311 extern void ase_add_wheap(ase_wheap_t h, Lisp_Object o, Lisp_Object colour);
312 extern Lisp_Object ase_pop_wheap(ase_wheap_t h);
313 extern Lisp_Object ase_wheap_top(ase_wheap_t h);
314 extern Lisp_Object ase_wheap_top_rank(ase_wheap_t h);
317 EXFUN(Fase_heap, MANY);
318 EXFUN(Fase_add_heap, 3);
319 EXFUN(Fase_pop_heap, 1);
321 extern struct ase_heap_ops_s ase_heap_ops[NUMBER_OF_ASE_HEAP_KINDS];
323 #endif /* INCLUDED_ase_heap_h_ */