1 /* timebase.c -- management of calls, time bases and heaps for moxc */
2
3 /*****************************************************************************
4 * Change Log
5 * Date | Change
6 *-----------+-----------------------------------------------------------------
7 * 2-Apr-91 | JDW : further changes
8 * 21-Mar-92 | GWL : abort recovery
9 * 28-Apr-03 | DM : true->TRUE
10 *****************************************************************************/
11
12
13 #include "stdio.h"
14 #include "cext.h"
15 #include "userio.h"
16 #include "midifns.h"
17 #include "timebase.h"
18 #include "moxc.h"
19
20
21 timebase_type timebase_queue = NULL; /* waiting to run timebase queue */
22 call_type callfree = NULL; /* free list */
23
24 private void fatal(const char *msg);
25
26
27 /****************************************************************************
28 * timebase_create
29 * Inputs:
30 * maxsize is the initial size of the heap
31 * Outputs:
32 * returns an initialized timebase_type
33 ****************************************************************************/
34
timebase_create(maxsize)35 timebase_type timebase_create(maxsize)
36 int maxsize;
37 {
38 static char *error_msg = "Out of memory in timebase_create()";
39 timebase_type base = (timebase_type) memget(sizeof(timebase_node));
40 if (!base) fatal(error_msg);
41 base->next = NULL;
42 base->next_time = MAXTIME;
43 base->virt_base = 0L;
44 base->real_base = 0L;
45 base->rate = 256L;
46 base->heap_size = 0;
47 base->heap_max = maxsize;
48 base->heap = (call_type *) memget(sizeof(call_type) * maxsize);
49 if (!base->heap) fatal(error_msg);
50 return base;
51 }
52
53 /****************************************************************************
54 * callinsert
55 * Inputs:
56 * timebase_type base: the time base and heap
57 * call_type call: the call to insert in heap
58 * Outputs:
59 none
60 * Implementation:
61 * linear insertion; to be changed to heap
62 ****************************************************************************/
63
callinsert(base,call)64 void callinsert(base, call)
65 timebase_type base;
66 call_type call;
67 {
68 int i;
69 register call_type *heap = base->heap;
70
71 /* handle overflow -- this should never be executed if the user
72 * gives the right initial heap size
73 */
74 base->heap_size++;
75 if (base->heap_size >= base->heap_max) {
76 call_type *new_heap = (call_type *)
77 memget((base->heap_max << 1) * sizeof(call_type));
78 int i;
79 call_type *oldptr;
80 call_type *newptr;
81 if (!new_heap) {
82 gprintf(TRANS, "Out of space, can't allocate new heap\n");
83 EXIT(1);
84 }
85
86 oldptr = base->heap;
87 newptr = new_heap;
88
89 for (i = base->heap_max; i > 0; i--) *newptr++ = *oldptr++;
90 memfree((char *) heap, base->heap_max * sizeof(call_type));
91 base->heap = heap = new_heap;
92 base->heap_max = (base->heap_max << 1);
93 }
94
95 /* now do the heap insert */
96 i = base->heap_size;
97 while (i > 1) {
98 int parent = i >> 1;
99 if (heap[parent]->u.e.time < call->u.e.time ||
100 (heap[parent]->u.e.time == call->u.e.time &&
101 heap[parent]->u.e.priority <= call->u.e.priority)) break;
102 heap[i] = heap[parent];
103 i = parent;
104 }
105 heap[i] = call;
106
107 /* if next_time might change, reinsert base into queue */
108 if (heap[1] == call) {
109 remove_base(base);
110 insert_base(base);
111 }
112 }
113
114 /****************************************************************************
115 * callshow
116 * Inputs:
117 * calltype call: the call to show
118 * Effect:
119 * prints a description of call
120 * Assumes:
121 * call is not null
122 ****************************************************************************/
callshow(call)123 void callshow(call)
124 call_type call;
125 {
126 int i;
127 gprintf(TRANS,"address: %p\n", call);
128 gprintf(TRANS,"time: %ld\n", call->u.e.time);
129 gprintf(TRANS,"routine: %p\n", call->u.e.routine);
130 gprintf(TRANS,"parameters:");
131 for (i = 0; i < MAX_CALL_ARGS; i++) {
132 gprintf(TRANS, " %p", call->u.e.p.arg[i]);
133 }
134 gprintf(TRANS, "\n");
135 }
136
137 /***************************************************************
138 * fatal
139 *
140 * Input : msg: a message to be displayed
141 * Effect: print message and exit program
142 ***************************************************************/
143
fatal(const char * msg)144 private void fatal(const char *msg)
145 {
146 gprintf(FATAL, msg);
147 EXIT(1);
148 }
149
150 /***************************************************************
151 * timebase_free
152 *
153 * Input : a time base
154 * Effect: deallocate the time base
155 ***************************************************************/
156
timebase_free(timebase)157 void timebase_free(timebase)
158 timebase_type timebase;
159 {
160 remove_base(timebase);
161 if (timebase->heap) {
162 memfree((char *) timebase->heap,
163 (timebase->heap_max * sizeof(call_type)));
164 }
165 memfree((char *) timebase, sizeof(timebase_node));
166 }
167
168 /***************************************************************
169 * insert_base
170 *
171 * Input : a time base not in the list
172 * Effect: insert timebase at the appropriate spot in the list
173 * computes the next_time field from the top of the heap
174 ***************************************************************/
175
insert_base(timebase)176 void insert_base(timebase)
177 timebase_type timebase;
178 {
179 register timebase_type *ptr = &timebase_queue;
180 register time_type next_time = MAXTIME;
181 /* compute next_time */
182 if (timebase->heap_size != 0) {
183 register call_type call = timebase->heap[1];
184 /* virt to real calculation */
185 next_time = (virt_to_real_256(timebase, call->u.e.time) &
186 0xFFFFFF00) + call->u.e.priority;
187 /* gprintf(TRANS,
188 "insert next_time is %ld, vt %ld, rb %ld, vb %ld rt %ld\n",
189 next_time, timebase->heap[1]->u.e.time,
190 timebase->real_base, timebase->virt_base, timebase->rate);
191 */
192 }
193 timebase->next_time = next_time;
194
195 if (next_time != MAXTIME) {
196 /* insert into the list */
197 while (TRUE) {
198 if (! *ptr) {
199 *ptr = timebase;
200 timebase->next = NULL;
201 return;
202 } else if ((*ptr)->next_time >= next_time) {
203 timebase->next = *ptr;
204 *ptr = timebase;
205 return;
206 } else ptr = &((*ptr)->next);
207 }
208 }
209 }
210
211 /***************************************************************
212 * remove_base
213 *
214 * Input : timebase
215 * Effect: if timebase is in the queue, remove it
216 ***************************************************************/
217
remove_base(timebase)218 void remove_base(timebase)
219 timebase_type timebase;
220 {
221 timebase_type *ptr = &timebase_queue;
222 while (*ptr) {
223 if (*ptr == timebase) {
224 *ptr = timebase->next;
225 return;
226 } else ptr = &((*ptr)->next);
227 }
228 }
229
230 /***************************************************************
231 * remove_call
232 *
233 * Input : a timebase -- passed as a global
234 * Assumes: a_timebase->heap_size > 0
235 * Returns: the earliest call in the queue
236 * Effect: removes the earliest call in the queue
237 ***************************************************************/
238
remove_call(timebase_type a_timebase)239 call_type remove_call(timebase_type a_timebase)
240 {
241 register call_type *heap = a_timebase->heap;
242 call_type result = heap[1];
243 register call_type large;
244 int i = 1;
245 int child = i << 1;;
246 large = heap[a_timebase->heap_size--];
247 while (child <= a_timebase->heap_size) {
248 if (child + 1 <= a_timebase->heap_size) {
249 if (heap[child + 1]->u.e.time < heap[child]->u.e.time ||
250 (heap[child + 1]->u.e.time == heap[child]->u.e.time &&
251 heap[child + 1]->u.e.priority < heap[child]->u.e.priority))
252 child++;
253 }
254 /* child is now the index of the least child */
255 if (large->u.e.time < heap[child]->u.e.time ||
256 (large->u.e.time == heap[child]->u.e.time &&
257 large->u.e.priority <= heap[child]->u.e.priority)) break;
258 /* swap */
259 heap[i] = heap[child];
260 i = child;
261 child = i << 1;
262 }
263 heap[i] = large;
264 return result;
265 }
266
267 /***************************************************************
268 * set_rate
269 *
270 * Input : timebase and new rate
271 * Effect: makes the current rate of timebase be rate
272 ***************************************************************/
273
set_rate(base,rate)274 void set_rate(base, rate)
275 timebase_type base;
276 time_type rate;
277 {
278 if (base == timebase) base->virt_base = virttime;
279 else base->virt_base = real_to_virt(base, eventtime);
280 base->real_base = eventtime;
281 base->rate = rate;
282 /* gprintf(TRANS, "new real_base %ld virt_base %ld\n",
283 base->real_base, base->virt_base);
284 */
285 remove_base(base);
286 insert_base(base);
287 }
288
289 /***************************************************************
290 * set_virttime
291 *
292 * Input : virtual time
293 * Effect: makes the current virtual time of timebase be vtime
294 ***************************************************************/
295
set_virttime(base,vtime)296 void set_virttime(base, vtime)
297 timebase_type base;
298 time_type vtime;
299 {
300 base->real_base = eventtime;
301 base->virt_base = vtime;
302 if (base == timebase) virttime = vtime;
303 remove_base(base);
304 insert_base(base);
305 }
306
307 /***************************************************************
308 * timebase_use
309 *
310 * Input : a timebase to use for scheduling
311 * Effect: sets up globals: timebase, virttime
312 ***************************************************************/
313
timebase_use(base)314 void timebase_use(base)
315 register timebase_type base;
316 {
317 if (timebase != base) {
318 timebase = base;
319 virttime = real_to_virt(base, eventtime);
320 }
321 }
322