1 /* Copyright 2020 Nico Sonack
2  *
3  * Redistribution and use in source and binary forms, with or without
4  * modification, are permitted provided that the following conditions
5  * are met:
6  *
7  * 1. Redistributions of source code must retain the above copyright
8  * notice, this list of conditions and the following disclaimer.
9  *
10  * 2. Redistributions in binary form must reproduce the above
11  * copyright notice, this list of conditions and the following
12  * disclaimer in the documentation and/or other materials provided
13  * with the distribution.
14  *
15  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
17  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
18  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
19  * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
20  * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
22  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
24  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
26  * OF THE POSSIBILITY OF SUCH DAMAGE.
27  */
28 
29 #ifndef HEAP_H_
30 #define HEAP_H_
31 
32 #include <tlci/string.h>
33 
34 #define SCOPE_MAX_ENTRIES 64
35 typedef struct scope {
36     unsigned long hashes[SCOPE_MAX_ENTRIES];
37     struct heap_cell* references[SCOPE_MAX_ENTRIES];
38     size_t end;
39 } scope_t;
40 
41 typedef enum cell_type {
42     NIL,
43     IDENT,
44     AP,
45     ABS,
46     CLOSURE,
47     LET,
48     RELEASE,
49     COMMAND,
50     TOKENPOS
51 } cell_type_t;
52 
53 typedef struct abstr_cell {
54     struct heap_cell* var;
55     struct heap_cell* body;
56 } abstr_cell_t;
57 
58 typedef struct command_cell {
59     struct heap_cell* command;
60     struct heap_cell* next;
61 } command_cell_t;
62 
63 typedef struct closure_cell {
64     struct heap_cell* var;
65     struct heap_cell* body;
66     scope_t* closed_scope;
67 } closure_cell_t;
68 
69 typedef struct token_pos_cell {
70     unsigned int line;
71     unsigned int col;
72     string filename;
73 } token_pos_cell_t;
74 
75 typedef struct ident_cell {
76     string identifier;
77     struct heap_cell* token_pos;
78 } ident_cell_t;
79 
80 typedef struct let_cell {
81     struct heap_cell* name;
82     struct heap_cell* value;
83 } let_cell_t;
84 
85 typedef struct app_cell {
86     struct heap_cell* function;
87     struct heap_cell* argument;
88 } app_cell_t;
89 
90 typedef union cell_content {
91     ident_cell_t as_ident;
92     abstr_cell_t as_abstr;
93     app_cell_t as_app;
94     let_cell_t as_let;
95     struct heap_cell* as_release;
96     closure_cell_t as_closure;
97     command_cell_t as_command;
98     token_pos_cell_t as_token_pos;
99 } cell_content_t;
100 
101 typedef struct heap_cell {
102     cell_type_t type;
103     cell_content_t content;
104     int is_alive;
105 } heap_cell_t;
106 
107 #define HEAP_POOL_CAPACITY (HEAP_CELL_COUNT * sizeof(heap_cell_t))
108 
109 typedef struct heap {
110     size_t end;
111     heap_cell_t* mem_pool;
112     size_t free_memory;
113 } heap_t;
114 
115 heap_t* heap_create(void);
116 void heap_garbage_sweep(heap_t*);
117 heap_cell_t* heap_alloc_ident(heap_t*, heap_cell_t*, string);
118 heap_cell_t* heap_alloc_let(heap_t*, heap_cell_t*, heap_cell_t*);
119 heap_cell_t* heap_alloc_release(heap_t*, heap_cell_t*);
120 heap_cell_t* heap_alloc_ap(heap_t*, heap_cell_t*, heap_cell_t*);
121 heap_cell_t* heap_alloc_token_pos(heap_t*, string, unsigned int, unsigned int);
122 heap_cell_t* heap_alloc_abs(heap_t*, heap_cell_t*, heap_cell_t*);
123 heap_cell_t* heap_alloc_cls(heap_t*, heap_cell_t*, heap_cell_t*, scope_t*);
124 heap_cell_t* heap_alloc_cmd(heap_t*, heap_cell_t*, heap_cell_t*);
125 heap_cell_t* heap_alloc_nil(heap_t*);
126 void heap_print_cell(heap_t*, heap_cell_t*);
127 void heap_destroy(heap_t*);
128 
129 #endif
130