1 /* Heap management. 2 */ 3 4 /* 5 6 Copyright (C) 1991-2003 The National Gallery 7 8 This program is free software; you can redistribute it and/or modify 9 it under the terms of the GNU General Public License as published by 10 the Free Software Foundation; either version 2 of the License, or 11 (at your option) any later version. 12 13 This program is distributed in the hope that it will be useful, 14 but WITHOUT ANY WARRANTY; without even the implied warranty of 15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 GNU General Public License for more details. 17 18 You should have received a copy of the GNU General Public License along 19 with this program; if not, write to the Free Software Foundation, Inc., 20 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 21 22 */ 23 24 /* 25 26 These files are distributed with VIPS - http://www.vips.ecs.soton.ac.uk 27 28 */ 29 30 /* Node type. Generally represent data objects. 31 * 32 * Don't use enum, as we want this to fit in 1 byte. 33 */ 34 typedef unsigned char NodeType; 35 #define TAG_APPL (0) /* Application */ 36 #define TAG_CONS (1) /* List cons */ 37 #define TAG_FREE (2) /* On free list */ 38 #define TAG_DOUBLE (3) /* Constant double */ 39 #define TAG_COMPLEX (4) /* Constant complex */ 40 #define TAG_GEN (5) /* List generator */ 41 #define TAG_CLASS (8) /* Class object */ 42 #define TAG_SHARED (9) /* Root of a common sub-expression */ 43 #define TAG_REFERENCE (10) /* Reference to a common sub-expression */ 44 #define TAG_FILE (12) /* Generate list from file */ 45 46 /* Element types. Generally represent operators. 47 */ 48 typedef unsigned char EType; 49 #define ELEMENT_NOVAL (0) /* No value */ 50 #define ELEMENT_NODE (1) /* Pointer to another node */ 51 #define ELEMENT_SYMBOL (2) /* Pointer to Symbol, reduces to value */ 52 #define ELEMENT_SYMREF (3) /* Pointer to Symbol, does not reduce */ 53 #define ELEMENT_COMPILEREF (4) /* Pointer to Compile, does not reduce */ 54 #define ELEMENT_CHAR (5) /* Boxed char type */ 55 #define ELEMENT_BOOL (6) /* Boxed bool type */ 56 #define ELEMENT_BINOP (7) /* Binary operator */ 57 #define ELEMENT_UNOP (8) /* Unary operator */ 58 #define ELEMENT_COMB (9) /* Combinator */ 59 #define ELEMENT_TAG (10) /* RHS of '.' operator */ 60 #define ELEMENT_MANAGED (11) /* A managed object */ 61 #define ELEMENT_CONSTRUCTOR (12)/* Class constructor */ 62 #define ELEMENT_ELIST (13) /* Empty list */ 63 64 /* Flags we attach to a node. 65 */ 66 typedef unsigned char NodeFlags; 67 #define FLAG_SERIAL (31) /* Serial number mask .. must be 1st */ 68 #define FLAG_PRINT (32) /* Marked (for decompile print) */ 69 #define FLAG_DEBUG (64) /* Marked (for debug traverse) */ 70 #define FLAG_MARK (128) /* Marked (for mark-sweep) */ 71 #define FLAG_ALL (255) /* All flags mask */ 72 73 /* Set the serial number without disturbing other stuff. 74 */ 75 #define SETSERIAL( FLAGS, SERIAL ) { \ 76 (FLAGS) = ((FLAGS) & (FLAG_SERIAL ^ FLAG_ALL)) | \ 77 ((SERIAL) & FLAG_SERIAL); \ 78 } 79 80 /* Combinators. Don't change the order of these! See reduce.c for an array 81 * indexed with a CombinatorType. 82 */ 83 typedef enum combinator_type { 84 COMB_S = 0, /* S combinator */ 85 COMB_SL, /* S-left combinator */ 86 COMB_SR, /* S-right combinator */ 87 COMB_I, /* Identity combinator */ 88 COMB_K, /* K combinator */ 89 COMB_GEN /* List generator combinator */ 90 } CombinatorType; 91 92 /* An element ... a tag plus a pointer. Use one of these to hold a pointer 93 * into a heap. 94 */ 95 typedef struct _Element { 96 EType type; 97 void *ele; 98 } Element; 99 100 /* A node on the heap. Should fit in 12 bytes on most machines. 101 */ 102 typedef struct _HeapNode { 103 /* Elements: either a pair of pointers, or a double. Sensible on most 104 * 32-bit systems, not so great on 64 bitters. 105 */ 106 union { 107 struct { 108 void *left; 109 void *right; 110 } ptrs; 111 double num; 112 } body; 113 114 /* Flags ... should fit in 4 bytes. 115 */ 116 NodeType type; /* What this is */ 117 NodeFlags flgs; /* GC flags etc */ 118 EType ltype; /* Type of left element */ 119 EType rtype; /* Type of right element */ 120 } HeapNode; 121 122 /* Put type/value pairs into nodes. Make sure we completely read before we 123 * write. 124 */ 125 #define PPUTLEFT(N,T,V) {\ 126 EType t99 = (T);\ 127 void *v99 = (void*)(V);\ 128 \ 129 (N)->ltype = t99;\ 130 (N)->body.ptrs.left = v99;\ 131 } 132 #define PPUTRIGHT(N,T,V) {\ 133 EType t99 = (T);\ 134 void *v99 = (void*)(V);\ 135 \ 136 (N)->rtype = t99;\ 137 (N)->body.ptrs.right = v99;\ 138 } 139 #define PPUT(N,Tl,Vl,Tr,Vr) {PPUTLEFT( N, Tl, Vl ); PPUTRIGHT( N, Tr, Vr );} 140 141 /* Get value as a HeapNode pointer (most common case). 142 */ 143 #define GETLEFT(N) ((HeapNode*)((N)->body.ptrs.left)) 144 #define GETRIGHT(N) ((HeapNode*)((N)->body.ptrs.right)) 145 #define GETLT(N) ((N)->ltype) 146 #define GETRT(N) ((N)->rtype) 147 148 /* A pointer to an element inside a HeapNode, or to an Element. 149 */ 150 typedef struct pelement { 151 EType *type; 152 void **ele; 153 } PElement; 154 155 /* Make a PElement point to a node. 156 */ 157 #define PEPOINTLEFT(N,P) \ 158 {(P)->type=&((N)->ltype);(P)->ele=&((N)->body.ptrs.left);} 159 #define PEPOINTRIGHT(N,P) \ 160 {(P)->type=&((N)->rtype);(P)->ele=&((N)->body.ptrs.right);} 161 162 /* Make a PElement point to an element. 163 */ 164 #define PEPOINTE(PE,E) \ 165 {(PE)->type=&((E)->type);(PE)->ele=&((E)->ele);} 166 167 /* Get from a PE. 168 */ 169 #define PEGETTYPE(P) (*((P)->type)) 170 #define PEGETVAL(P) ((HeapNode*)(*((P)->ele))) 171 #define PEGETE(P,E) ((E)->type = PEGETTYPE(P),(E)->ele = PEGETVAL(P)) 172 #define PEGETP(PE,T,V) ((T)=*((PE)->type),(V)=*((PE)->ele)) 173 174 /* Write to a PE. We are careful to eval all args before writing, in case we 175 * are writing to one of the inputs. 176 */ 177 #define PEPUTE(PE,E) {*((PE)->type)=(E)->type;*((PE)->ele)=(E)->ele;} 178 #define PEPUTPE(PEto,PEfrom) {\ 179 EType t99 = PEGETTYPE(PEfrom);\ 180 void *v99 = PEGETVAL(PEfrom);\ 181 \ 182 *((PEto)->type) = t99;\ 183 *((PEto)->ele) = v99;\ 184 } 185 #define PEPUTP(PE,T,V) {\ 186 EType t99 = (T);\ 187 void *v99 = GUINT_TO_POINTER(V);\ 188 \ 189 *((PE)->type) = t99;\ 190 *((PE)->ele) = v99;\ 191 } 192 193 /* Write a PE to a node. Again, make sure we read both before we write, in 194 * case we are writing an expression to ourselves. 195 */ 196 #define PEPUTLEFT(N,PE) {\ 197 EType t99 = PEGETTYPE(PE);\ 198 void *v99 = PEGETVAL(PE);\ 199 \ 200 (N)->ltype = t99;\ 201 (N)->body.ptrs.left = v99;\ 202 } 203 #define PEPUTRIGHT(N,PE) {\ 204 EType t99 = PEGETTYPE(PE);\ 205 void *v99 = PEGETVAL(PE);\ 206 \ 207 (N)->rtype = t99;\ 208 (N)->body.ptrs.right = v99;\ 209 } 210 211 /* Predicates. 212 */ 213 #define PEISBINOP(P) (PEGETTYPE(P) == ELEMENT_BINOP) 214 #define PEISBOOL(P) (PEGETTYPE(P) == ELEMENT_BOOL) 215 #define PEISCHAR(P) (PEGETTYPE(P) == ELEMENT_CHAR) 216 #define PEISCLASS(P) (PEISNODE(P) && PEGETVAL(P)->type == TAG_CLASS) 217 #define PEISCONSTRUCTOR(P) (PEGETTYPE(P) == ELEMENT_CONSTRUCTOR) 218 #define PEISCOMB(P) (PEGETTYPE(P) == ELEMENT_COMB) 219 #define PEISCOMPLEX(P) (PEISNODE(P) && PEGETVAL(P)->type == TAG_COMPLEX) 220 #define PEISTAG(P) (PEGETTYPE(P) == ELEMENT_TAG) 221 #define PEISMANAGED(P) (PEGETTYPE(P) == ELEMENT_MANAGED) 222 #define PEISMANAGEDGOBJECT(P) (PEISMANAGED(P) && \ 223 IS_MANAGEDGOBJECT( PEGETVAL(P) )) 224 #define PEISMANAGEDSTRING(P) (PEISMANAGED(P) && \ 225 IS_MANAGEDSTRING(PEGETVAL(P))) 226 #define PEISIMAGE(P) (PEISMANAGED(P) && IS_IMAGEINFO( PEGETVAL(P) )) 227 #define PEISVIPSOBJECT(P) \ 228 (PEISMANAGEDGOBJECT(P) && VIPS_IS_OBJECT( PEGETMANAGEDGOBJECT(P) )) 229 #define PEISFILE(P) (PEISMANAGED(P) && IS_MANAGEDFILE(PEGETVAL(P))) 230 #define PEISELIST(P) (PEGETTYPE(P) == ELEMENT_ELIST) 231 #define PEISFLIST(P) ((PEISNODE(P) && PEGETVAL(P)->type == TAG_CONS) || \ 232 PEISMANAGEDSTRING(P)) 233 #define PEISLIST(P) (PEISELIST(P) || PEISFLIST(P)) 234 #define PEISNOVAL(P) (PEGETTYPE(P) == ELEMENT_NOVAL) 235 #define PEISNUM(P) (PEISREAL(P) || PEISCOMPLEX(P)) 236 #define PEISNODE(P) (PEGETTYPE(P) == ELEMENT_NODE) 237 #define PEISREAL(P) (PEISNODE(P) && PEGETVAL(P)->type == TAG_DOUBLE) 238 #define PEISSYMBOL(P) (PEGETTYPE(P) == ELEMENT_SYMBOL) 239 #define PEISSYMREF(P) (PEGETTYPE(P) == ELEMENT_SYMREF) 240 #define PEISCOMPILEREF(P) (PEGETTYPE(P) == ELEMENT_COMPILEREF) 241 #define PEISUNOP(P) (PEGETTYPE(P) == ELEMENT_UNOP) 242 243 /* Extract bits of primitive compound types. 244 */ 245 #define PEGETSYMBOL(P) ((Symbol*)PEGETVAL(P)) 246 #define PEGETSYMREF(P) ((Symbol*)PEGETVAL(P)) 247 #define PEGETCOMPILE(P) ((Compile*)(PEGETVAL(P))) 248 #define PEGETBINOP(P) ((BinOp)PEGETVAL(P)) 249 #define PEGETUNOP(P) ((UnOp)PEGETVAL(P)) 250 #define PEGETCOMB(P) ((CombinatorType)PEGETVAL(P)) 251 #define PEGETTAG(P) ((char*)PEGETVAL(P)) 252 #define PEGETREAL(P) (PEGETVAL(P)->body.num) 253 #define PEGETBOOL(P) ((gboolean)GPOINTER_TO_UINT(PEGETVAL(P))) 254 #define PEGETCHAR(P) ((unsigned char)(GPOINTER_TO_UINT(PEGETVAL(P)))) 255 #define PEGETIMAGE(P) (((Imageinfo*)PEGETVAL(P))->im) 256 #define PEGETII(P) ((Imageinfo*)PEGETVAL(P)) 257 #define PEGETFILE(P) ((Managedfile*)PEGETVAL(P)) 258 #define PEGETMANAGED(P) ((Managed*)PEGETVAL(P)) 259 #define PEGETMANAGEDSTRING(P) ((Managedstring*)PEGETVAL(P)) 260 #define PEGETMANAGEDGOBJECT(P) (((Managedgobject*)PEGETVAL(P))->object) 261 #define PEGETVIPSOBJECT(P) \ 262 ((VipsObject*)(((Managedgobject*)PEGETVAL(P))->object)) 263 264 #define PEGETHD(P1,P2) PEPOINTLEFT(PEGETVAL(P2), P1) 265 #define PEGETTL(P1,P2) PEPOINTRIGHT(PEGETVAL(P2), P1) 266 267 #define PEGETREALPART(P) (GETLEFT(PEGETVAL(P))->body.num) 268 #define PEGETIMAGPART(P) (GETRIGHT(PEGETVAL(P))->body.num) 269 270 #define PEGETCLASSCOMPILE(P) (COMPILE(GETLEFT(PEGETVAL(P)))) 271 #define PEGETCLASSSECRET(P1,P2) PEPOINTLEFT(GETRIGHT(PEGETVAL(P2)),P1) 272 #define PEGETCLASSMEMBER(P1,P2) PEPOINTRIGHT(GETRIGHT(PEGETVAL(P2)),P1) 273 274 /* A block on the heap. 275 */ 276 struct _HeapBlock { 277 Heap *heap; /* Heap we are part of */ 278 HeapBlock *next; /* Next block in chain */ 279 HeapNode *node; /* Nodes on this block */ 280 int sz; /* Number of nodes in this block */ 281 }; 282 283 /* Function to get max heap size. 284 */ 285 typedef int (*heap_max_fn)( Heap * ); 286 287 #define TYPE_HEAP (heap_get_type()) 288 #define HEAP( obj ) \ 289 (G_TYPE_CHECK_INSTANCE_CAST( (obj), TYPE_HEAP, Heap )) 290 #define HEAP_CLASS( klass ) \ 291 (G_TYPE_CHECK_CLASS_CAST( (klass), TYPE_HEAP, HeapClass)) 292 #define IS_HEAP( obj ) \ 293 (G_TYPE_CHECK_INSTANCE_TYPE( (obj), TYPE_HEAP )) 294 #define IS_HEAP_CLASS( klass ) \ 295 (G_TYPE_CHECK_CLASS_TYPE( (klass), TYPE_HEAP )) 296 #define HEAP_GET_CLASS( obj ) \ 297 (G_TYPE_INSTANCE_GET_CLASS( (obj), TYPE_HEAP, HeapClass )) 298 299 struct _Heap { 300 iObject parent_object; 301 302 Compile *compile; /* If non-null, assoc. compile */ 303 304 heap_max_fn max_fn; /* Max nodes in this heap */ 305 int mxb; /* Max blocks until next check */ 306 int rsz; /* Nodes to allocate in each extra block */ 307 int nb; /* Number of blocks attached */ 308 HeapBlock *hb; /* List of current blocks */ 309 HeapNode *free; /* Start of free-node chain (sweep to here) */ 310 311 int ncells; /* Cells allocated */ 312 int nfree; /* Cells free */ 313 int serial; /* Last serial number we used */ 314 gboolean filled; /* Set on heap full */ 315 316 GHashTable *emark; /* Set of elements to mark on GC */ 317 GHashTable *rmark; /* Set of Reduce to mark on GC */ 318 GHashTable *mtable; /* Managed associated with this heap */ 319 320 guint gc_tid; /* id of gc delay timer */ 321 322 /* Set this to force unreffed objects out immediately. Handy for leak 323 * testing. 324 */ 325 gboolean flush; 326 }; 327 328 typedef struct _HeapClass { 329 iObjectClass parent_class; 330 331 /* My methods. 332 */ 333 } HeapClass; 334 335 /* Get a node from the free-list. No check for free-list exhausted! Set sym 336 * pointer in node to heap sym pointer. 337 */ 338 #ifdef DEBUG_HEAP 339 #define EXTRACTNODE( H, A ) \ 340 (heap_sanity( H ), (A) = (H)->free, (H)->free = GETLEFT( A ), 0) 341 #else /*!DEBUG_HEAP*/ 342 #define EXTRACTNODE( H, A ) \ 343 ((A) = (H)->free, (H)->free = GETLEFT( A ), 0) 344 #endif /*DEBUG_HEAP*/ 345 346 /* Allocate a new node from heap H, pop the pointer into A, return non-zero if 347 * alloc failed. Node is uninitialised! 348 */ 349 #define NEWNODE( H, A ) ( \ 350 (H)->free ? \ 351 EXTRACTNODE( H, A ): \ 352 (((A) = heap_getmem( H )) ? 0 : -1) \ 353 ) 354 355 typedef void *(*heap_safe_pointer_fn)( Heap *heap, PElement *, 356 void *, void *, void *, void * ); 357 void *heap_safe_pointer( Heap *heap, heap_safe_pointer_fn fn, 358 void *a, void *b, void *c, void *d ); 359 360 typedef void *(*heap_map_fn)( HeapNode *, void *, void *); 361 void *heap_map( HeapNode *hn, heap_map_fn fn, void *a, void *b ); 362 363 int heap_sanity( Heap *heap ); 364 365 void heap_check_all_destroyed( void ); 366 void heap_destroy( Heap *heap ); 367 GType heap_get_type( void ); 368 Heap *heap_new( Compile *compile, heap_max_fn max_fn, int stsz, int rsz ); 369 HeapNode *heap_getmem( Heap *heap ); 370 gboolean heap_gc( Heap *heap ); 371 void heap_gc_request( Heap *heap ); 372 void heap_register_element( Heap *heap, Element *root ); 373 void heap_unregister_element( Heap *heap, Element *root ); 374 void heap_register_reduce( Heap *heap, Reduce *rc ); 375 void heap_unregister_reduce( Heap *heap, Reduce *rc ); 376 void heap_set( Heap *heap, NodeFlags setmask ); 377 void heap_clear( Heap *heap, NodeFlags clearmask ); 378 int heap_serial_new( Heap *heap ); 379 380 gboolean heap_bool_new( Heap *heap, gboolean val, PElement *out ); 381 gboolean heap_real_new( Heap *heap, double in, PElement *out ); 382 gboolean heap_element_new( Heap *heap, Element *e, PElement *out ); 383 gboolean heap_complex_element_new( Heap *heap, 384 PElement *rp, PElement *ip, PElement *out ); 385 gboolean heap_complex_new( Heap *heap, double rp, double ip, PElement *out ); 386 gboolean heap_realvec_new( Heap *heap, int n, double *vec, PElement *out ); 387 gboolean heap_intvec_new( Heap *heap, int n, int *vec, PElement *out ); 388 void heap_list_init( PElement *list ); 389 gboolean heap_list_add( Heap *heap, PElement *list, PElement *data ); 390 gboolean heap_list_next( PElement *list ); 391 gboolean heap_list_cat( Reduce *rc, PElement *a, PElement *b, PElement *out ); 392 void heap_appl_init( PElement *base, PElement *func ); 393 gboolean heap_appl_add( Heap *heap, PElement *base, PElement *parm ); 394 gboolean heap_matrix_new( Heap *heap, 395 int xsize, int ysize, double *vec, PElement *out ); 396 gboolean heap_string_new( Heap *heap, const char *str, PElement *out ); 397 gboolean heap_managedstring_new( Heap *heap, const char *str, PElement *out ); 398 gboolean heap_lstring_new( Heap *heap, GSList *labels, PElement *out ); 399 gboolean heap_file_new( Heap *heap, const char *filename, PElement *out ); 400 401 gboolean heap_error_typecheck( PElement *e, 402 const char *name, const char *type ); 403 typedef void *(*heap_map_list_fn)( PElement *, void *, void * ); 404 void *heap_map_list( PElement *base, heap_map_list_fn fn, void *a, void *b ); 405 typedef void *(*heap_map_dict_fn)( const char *, PElement *, void *a, void *b ); 406 void *heap_map_dict( PElement *base, heap_map_dict_fn fn, void *a, void *b ); 407 408 gboolean heap_get_list( PElement *list ); 409 gboolean heap_get_list_next( PElement *list, PElement *data ); 410 gboolean heap_get_string( PElement *base, char *buf, int n ); 411 gboolean heap_get_lstring( PElement *base, GSList **labels ); 412 gboolean heap_get_bool( PElement *base, gboolean *out ); 413 gboolean heap_get_real( PElement *base, double *out ); 414 gboolean heap_get_class( PElement *base, PElement *out ); 415 gboolean heap_get_image( PElement *base, Imageinfo **out ); 416 int heap_get_realvec( PElement *base, double *buf, int n ); 417 int heap_get_imagevec( PElement *base, Imageinfo **buf, int n ); 418 gboolean heap_get_matrix_size( PElement *base, int *xsize, int *ysize ); 419 gboolean heap_get_matrix( PElement *base, 420 double *buf, int n, int *xsize, int *ysize ); 421 422 gboolean heap_is_elist( PElement *base, gboolean *out ); 423 gboolean heap_is_list( PElement *base, gboolean *out ); 424 gboolean heap_is_string( PElement *base, gboolean *out ); 425 gboolean heap_is_realvec( PElement *base, gboolean *out ); 426 gboolean heap_is_imagevec( PElement *base, gboolean *out ); 427 gboolean heap_is_matrix( PElement *base, gboolean *out ); 428 gboolean heap_is_class( PElement *base, gboolean *out ); 429 gboolean heap_is_instanceof_exact( const char *name, PElement *klass, 430 gboolean *out); 431 gboolean heap_is_instanceof( const char *name, PElement *klass, gboolean *out ); 432 433 int heap_list_length( PElement *base ); 434 int heap_list_length_max( PElement *base, int max_length ); 435 gboolean heap_list_index( PElement *base, int n, PElement *out ); 436 gboolean heap_reduce_strict( PElement *base ); 437 438 gboolean heap_copy( Heap *heap, Compile *compile, PElement *out ); 439 440 gboolean heap_ip_to_gvalue( PElement *in, GValue *out ); 441 gboolean heap_gvalue_to_ip( GValue *in, PElement *out ); 442 443 void graph_node( Heap *heap, VipsBuf *buf, HeapNode *root, gboolean fn ); 444 void graph_pelement( Heap *heap, VipsBuf *buf, PElement *root, gboolean fn ); 445 void graph_element( Heap *heap, VipsBuf *buf, Element *root, gboolean fn ); 446 void graph_pointer( PElement *root ); 447 448 /* Reduce and print, csh-style output. 449 */ 450 void graph_value( PElement *root ); 451