cgit.sxemacs.org Git - sxemacs/blob - modules/ase/ase-heap.h

   1 /*
   2   ase-heap.h -- Heaps
   3   Copyright (C) 2007 Sebastian Freundt
   4
   5   Author:  Sebastian Freundt <hroptatyr@sxemacs.org>
   6
   7   * This file is part of SXEmacs.
   8   *
   9   * Redistribution and use in source and binary forms, with or without
  10   * modification, are permitted provided that the following conditions
  11   * are met:
  12   *
  13   * 1. Redistributions of source code must retain the above copyright
  14   *    notice, this list of conditions and the following disclaimer.
  15   *
  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.
  19   *
  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.
  23   *
  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.
  35   */
  36
  37 /* Synched up with: Not in FSF. */
  38
  39 #ifndef INCLUDED_ase_heap_h_
  40 #define INCLUDED_ase_heap_h_ 1
  41
  42 #include "ase.h"
  43
  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;
  50
  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*);
  56
  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;
  62
  63 extern void LTX_PUBINIT(ase_heap)(void);
  64 extern void LTX_PUBREINIT(ase_heap)(void);
  65 extern void LTX_PUBDEINIT(ase_heap)(void);
  66
  67 \f
  68 enum ase_heap_kind_e {
  69         ASE_HEAP_DYNAMIC,
  70         ASE_HEAP_DENSE,
  71         ASE_HEAP_WEAK,
  72         NUMBER_OF_ASE_HEAP_KINDS
  73 };
  74
  75 struct ase_heap_ops_s {
  76         ase_heap_constr_f constrf;
  77         ase_heap_wrap_f wrapf;
  78         ase_heap_add_f addf;
  79         ase_heap_pop_f popf;
  80 };
  81
  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 */
  88
  89         int coloured;           /* whether we store coloured items */
  90
  91         /* just a ref counter for those nifty recycled items */
  92         sxe_refcounter_t refcnt;
  93 };
  94
  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
  98
  99 struct ase_dheap_s {
 100         Lisp_Object *cells;
 101         Lisp_Object *colours;
 102
 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) */
 108
 109         /* options to control the heap's behaviour */
 110         ASE_HEAP_OPTIONS_SORCERY;
 111 };
 112
 113 struct ase_wheap_s {
 114         Lisp_Object *cells;
 115         Lisp_Object *colours;
 116         int *rbits;
 117
 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) */
 123
 124         /* options to control the heap's behaviour */
 125         ASE_HEAP_OPTIONS_SORCERY;
 126 };
 127
 128 struct ase_yheap_s {
 129         ase_yheap_cell_t root;
 130         ase_yheap_cell_t first_free;
 131         ase_yheap_cell_t last_free;
 132
 133         /* status and mutex for the entire heap */
 134         ASE_HEAP_MUTEX_SORCERY;
 135         int heapp;              /* if heap obeys the heap property */
 136         size_t size;
 137         size_t alloc;
 138
 139         /* options to control the heap's behaviour */
 140         ASE_HEAP_OPTIONS_SORCERY;
 141 };
 142
 143 \f
 144 /* general heap thing (independent from underlying representation) */
 145 #define ASE_HEAPP(_i)                                           \
 146         (DYNACATP(_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)                                               \
 151         do {                                                            \
 152                 if (!ASE_HEAPP(x))                                      \
 153                         dead_wrong_type_argument(Qase_heapp, x);        \
 154         } while (0)
 155 #define CONCHECK_ASE_HEAP(x)                                            \
 156         do {                                                            \
 157                 if (!ASE_HEAPP(x))                                      \
 158                         x = wrong_type_argument(Qase_heapp, x);         \
 159         } while (0)
 160
 161 /* options and mutexes are generic */
 162 /* options */
 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)
 176 /* mutex */
 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))))
 182
 183 /* yheaps */
 184 #define ASE_YHEAPP(_i)                                          \
 185         (DYNACATP(_i) && EQ(XDYNACAT(_i)->type, Qase_yheap))
 186 #define CHECK_ASE_YHEAP(x)                                              \
 187         do {                                                            \
 188                 if (!ASE_YHEAPP(x))                                     \
 189                         dead_wrong_type_argument(Qase_yheapp, x);       \
 190         } while (0)
 191 #define CONCHECK_ASE_YHEAP(x)                                           \
 192         do {                                                            \
 193                 if (!ASE_YHEAPP(x))                                     \
 194                         x = wrong_type_argument(Qase_yheapp, x);        \
 195         } while (0)
 196 #define XSETASE_YHEAP(_res, _int)       (_res) = _ase_wrap_heap((_int))
 197 #define XASE_YHEAP(_x)                  ((ase_yheap_t)get_dynacat(_x))
 198
 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)
 202 /* status */
 203 #define ase_yheap_heapp(_x)             ((_x)->heapp)
 204 #define ase_yheap_size(_x)              ((_x)->size)
 205 #define ase_yheap_alloc(_x)             ((_x)->alloc)
 206
 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)
 215
 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);
 223
 224 /* dense heaps */
 225 #define ASE_DHEAPP(_i)                                          \
 226         (DYNACATP(_i) && EQ(XDYNACAT(_i)->type, Qase_dheap))
 227 #define CHECK_ASE_DHEAP(x)                                              \
 228         do {                                                            \
 229                 if (!ASE_DHEAPP(x))                                     \
 230                         dead_wrong_type_argument(Qase_dheapp, x);       \
 231         } while (0)
 232 #define CONCHECK_ASE_DHEAP(x)                                           \
 233         do {                                                            \
 234                 if (!ASE_DHEAPP(x))                                     \
 235                         x = wrong_type_argument(Qase_dheapp, x);                \
 236         } while (0)
 237 #define XSETASE_DHEAP(_res, _int)       (_res) = _ase_wrap_dheap((_int))
 238 #define XASE_DHEAP(_x)                  ((ase_dheap_t)get_dynacat(_x))
 239
 240 #define ase_dheap_cells(_x)             ((_x)->cells)
 241 #define ase_dheap_colours(_x)           ((_x)->colours)
 242 /* status */
 243 #define ase_dheap_heapp(_x)             ((_x)->heapp)
 244 #define ase_dheap_size(_x)              ((_x)->size)
 245 #define ase_dheap_alloc(_x)             ((_x)->alloc)
 246
 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);
 254
 255 /* weak heaps */
 256 #define ASE_WHEAPP(_i)                                          \
 257         (DYNACATP(_i) && EQ(XDYNACAT(_i)->type, Qase_wheap))
 258 #define CHECK_ASE_WHEAP(x)                                              \
 259         do {                                                            \
 260                 if (!ASE_WHEAPP(x))                                     \
 261                         dead_wrong_type_argument(Qase_wheapp, x);       \
 262         } while (0)
 263 #define CONCHECK_ASE_WHEAP(x)                                           \
 264         do {                                                            \
 265                 if (!ASE_WHEAPP(x))                                     \
 266                         x = wrong_type_argument(Qase_wheapp, x);                \
 267         } while (0)
 268 #define XSETASE_WHEAP(_res, _int)       (_res) = _ase_wrap_wheap((_int))
 269 #define XASE_WHEAP(_x)                  ((ase_wheap_t)get_dynacat(_x))
 270
 271 #define ase_wheap_cells(_x)             ((_x)->cells)
 272 #define ase_wheap_colours(_x)           ((_x)->colours)
 273 #define ase_wheap_rbits(_x)             ((_x)->rbits)
 274 /* status */
 275 #define ase_wheap_heapp(_x)             ((_x)->heapp)
 276 #define ase_wheap_size(_x)              ((_x)->size)
 277 #define ase_wheap_alloc(_x)             ((_x)->alloc)
 278
 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);
 287
 288 \f
 289 /* dyna heaps */
 290 static inline ase_yheap_t _ase_make_yheap(ase_heap_options_t opts);
 291 static 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);
 297
 298 /* dense heaps */
 299 static inline ase_dheap_t _ase_make_dheap(ase_heap_options_t opts);
 300 static 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);
 306
 307 /* weak heaps */
 308 static inline ase_wheap_t _ase_make_wheap(ase_heap_options_t opts);
 309 static 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);
 315
 316 /* misc */
 317 EXFUN(Fase_heap, MANY);
 318 EXFUN(Fase_add_heap, 3);
 319 EXFUN(Fase_pop_heap, 1);
 320
 321 extern struct ase_heap_ops_s ase_heap_ops[NUMBER_OF_ASE_HEAP_KINDS];
 322
 323 #endif  /* INCLUDED_ase_heap_h_ */