1 #ifdef RCSID
2 static char RCSid[] =
3 "$Header: d:/cvsroot/tads/tads3/VMUNDO.CPP,v 1.3 1999/07/11 00:46:58 MJRoberts Exp $";
4 #endif
5
6 /*
7 * Copyright (c) 1998, 2002 Michael J. Roberts. All Rights Reserved.
8 *
9 * Please see the accompanying license file, LICENSE.TXT, for information
10 * on using and copying this software.
11 */
12 /*
13 Name
14 vmundo.cpp - undo manager
15 Function
16
17 Notes
18
19 Modified
20 10/29/98 MJRoberts - Creation
21 */
22
23 #include "t3std.h"
24 #include "vmtype.h"
25 #include "vmobj.h"
26 #include "vmundo.h"
27
28 /*
29 * create the undo manager
30 */
CVmUndo(size_t undo_record_cnt,uint max_savepts)31 CVmUndo::CVmUndo(size_t undo_record_cnt, uint max_savepts)
32 {
33 /* remember the maximum number of savepoints */
34 max_savepts_ = max_savepts;
35
36 /*
37 * initialize the savepoint to number 0 (this is arbitrary, but we
38 * might as well start here)
39 */
40 cur_savept_ = 0;
41
42 /* no savepoints have been created yet */
43 savept_cnt_ = 0;
44
45 /* create the undo record array */
46 rec_arr_size_ = undo_record_cnt;
47 rec_arr_ = (CVmUndoMeta *)t3malloc(rec_arr_size_
48 * sizeof(rec_arr_[0]));
49
50 /* we have no records at all yet, so we have no "firsts" */
51 cur_first_ = 0;
52 oldest_first_ = 0;
53
54 /* start allocating from the first entry in the array */
55 next_free_ = rec_arr_;
56 }
57
58 /*
59 * delete the undo manager
60 */
~CVmUndo()61 CVmUndo::~CVmUndo()
62 {
63 /* delete the array of undo records */
64 t3free(rec_arr_);
65 }
66
67 /*
68 * create a savepoint
69 */
create_savept(VMG0_)70 void CVmUndo::create_savept(VMG0_)
71 {
72 CVmUndoMeta *rec;
73
74 /*
75 * Allocate an undo record to serve as the link pointer for this
76 * savepoint. If this fails, we cannot create a savepoint; we won't
77 * need to do anything else in this case, since we will have deleted
78 * all existing savepoints if we ran out of records.
79 */
80 rec = alloc_rec(vmg0_);
81 if (rec == 0)
82 return;
83
84 /* if we have an old savepoint, the new record starts the next one */
85 if (cur_first_ != 0)
86 cur_first_->link.next_first = rec;
87
88 /* the old savepoint (if any) is our previous savepoint */
89 rec->link.prev_first = cur_first_;
90
91 /* there's nothing after us yet */
92 rec->link.next_first = 0;
93
94 /* this record is now the current savepoint's first record */
95 cur_first_ = rec;
96
97 /*
98 * if we didn't have any savepoints recorded yet, this is now the
99 * first record in the oldest savepoint
100 */
101 if (oldest_first_ == 0)
102 oldest_first_ = rec;
103
104 /*
105 * increment the savepoint number, wrapping to zero if we reach the
106 * highest value we can store
107 */
108 if (cur_savept_ == VM_SAVEPT_MAX)
109 cur_savept_ = 0;
110 else
111 ++cur_savept_;
112
113 /*
114 * if we're already storing the maximum number of savepoints we're
115 * allowed to store simultaneously, drop the oldest savepoint;
116 * otherwise, simply increment the savepoint counter
117 */
118 if (savept_cnt_ == max_savepts_)
119 {
120 /* we have the maximum number of savepoints; discard the oldest */
121 drop_oldest_savept(vmg0_);
122 }
123
124 /* count the new savepoint */
125 ++savept_cnt_;
126
127 /* notify the objects that we're starting a new savepoint */
128 G_obj_table->notify_new_savept();
129 }
130
131 /*
132 * Discard the oldest savepoint
133 */
drop_oldest_savept(VMG0_)134 void CVmUndo::drop_oldest_savept(VMG0_)
135 {
136 vm_savept_t oldest;
137
138 /* if there are no savepoints, there's nothing to do */
139 if (savept_cnt_ == 0)
140 return;
141
142 /*
143 * The oldest savepoint number is (cur - cnt), adjusted for wrapping
144 * if we go below zero.
145 */
146 if (cur_savept_ >= savept_cnt_)
147 oldest = cur_savept_ - savept_cnt_;
148 else
149 oldest = VM_SAVEPT_MAX - (savept_cnt_ - cur_savept_) + 1;
150
151 /* decrement the savepoint count, now that this one is gone */
152 --savept_cnt_;
153
154 /* forget the oldest lead pointer */
155 if (oldest_first_ != 0)
156 {
157 CVmUndoMeta *meta;
158
159 /*
160 * discard records from the oldest lead pointer to the next
161 * oldest lead pointer
162 */
163 for (meta = oldest_first_, inc_rec_ptr(&meta) ;
164 meta != oldest_first_->link.next_first && meta != next_free_ ; )
165 {
166 /* discard this entry, if it still exists */
167 if (meta->rec.obj != VM_INVALID_OBJ)
168 vm_objp(vmg_ meta->rec.obj)->discard_undo(vmg_ &meta->rec);
169
170 /* advance to the next record */
171 inc_rec_ptr(&meta);
172 }
173
174 /* advance the oldest pointer to the next savepoint's first record */
175 oldest_first_ = oldest_first_->link.next_first;
176
177 /* there's now nothing before this one */
178 if (oldest_first_ != 0)
179 oldest_first_->link.prev_first = 0;
180 }
181
182 /* if we don't have an oldest, we also don't have a current */
183 if (oldest_first_ == 0)
184 cur_first_ = 0;
185 }
186
187 /*
188 * Drop all undo information
189 */
drop_undo(VMG0_)190 void CVmUndo::drop_undo(VMG0_)
191 {
192 /* delete each savepoint until we have none left */
193 while (savept_cnt_ != 0)
194 drop_oldest_savept(vmg0_);
195
196 /* reset the savepoint number */
197 cur_savept_ = 0;
198
199 /* we have no "firsts" */
200 cur_first_ = 0;
201 oldest_first_ = 0;
202
203 /* start allocating from the start of the array */
204 next_free_ = rec_arr_;
205 }
206
207 /*
208 * Allocate an undo record. If we run out of free records, delete
209 * savepoints, starting with the oldest savepoint, until we have a free
210 * record.
211 */
alloc_rec(VMG0_)212 CVmUndoMeta *CVmUndo::alloc_rec(VMG0_)
213 {
214 /*
215 * keep trying until we find an entry or run out of savepoints to
216 * delete
217 */
218 for (;;)
219 {
220 /*
221 * If we have no savepoints at all, all records are free.
222 * Otherwise, if the next free pointer hasn't bumped up against
223 * the oldest allocated record yet, we can allocate another
224 * record.
225 */
226 if (savept_cnt_ == 0 || next_free_ != oldest_first_)
227 {
228 CVmUndoMeta *ret;
229
230 /* remember the current free record */
231 ret = next_free_;
232
233 /*
234 * advance to the next record, wrapping if we reach the end
235 * of the array (since we treat the array as circular)
236 */
237 inc_rec_ptr(&next_free_);
238
239 /* return the record */
240 return ret;
241 }
242
243 /*
244 * If we have at least one old savepoint, discard the oldest
245 * savepoint, which may free up some records, and try again;
246 * otherwise, give up.
247 */
248 if (savept_cnt_ > 1)
249 {
250 /*
251 * we have at least one old savepoint we can discard - get
252 * rid of it and try again
253 */
254 drop_oldest_savept(vmg0_);
255 }
256 else
257 {
258 /*
259 * we are down to our last savepoint (or none at all) - it's
260 * no longer valid (since we can't keep it complete due to
261 * the lack of available records), so delete it and return
262 * failure
263 */
264 drop_oldest_savept(vmg0_);
265 return 0;
266 }
267 }
268 }
269
270 /*
271 * Add a new record with a property ID key
272 */
add_new_record_prop_key(VMG_ vm_obj_id_t obj,vm_prop_id_t key,const vm_val_t * val)273 void CVmUndo::add_new_record_prop_key(VMG_ vm_obj_id_t obj, vm_prop_id_t key,
274 const vm_val_t *val)
275 {
276 CVmUndoRecord *rec;
277
278 /* allocate the new record */
279 rec = add_new_record(vmg_ obj);
280
281 /* if we successfully allocated a record, set it up */
282 if (rec != 0)
283 {
284 /* set the object */
285 rec->obj = obj;
286
287 /* set the key */
288 rec->id.prop = key;
289
290 /* set the value */
291 rec->oldval = *val;
292 }
293 }
294
295 /*
296 * Add a new record with an integer key
297 */
add_new_record_int_key(VMG_ vm_obj_id_t obj,uint32 key,const vm_val_t * val)298 void CVmUndo::add_new_record_int_key(VMG_ vm_obj_id_t obj, uint32 key,
299 const vm_val_t *val)
300 {
301 CVmUndoRecord *rec;
302
303 /* allocate the new record */
304 rec = add_new_record(vmg_ obj);
305
306 /* if we successfully allocated a record, set it up */
307 if (rec != 0)
308 {
309 /* set the object */
310 rec->obj = obj;
311
312 /* set the key */
313
314 rec->id.intval = key;
315
316 /* set the value */
317 rec->oldval = *val;
318 }
319 }
320
321 /*
322 * Add a new record with a pointer key
323 */
add_new_record_ptr_key(VMG_ vm_obj_id_t obj,void * key,const vm_val_t * val)324 int CVmUndo::add_new_record_ptr_key(VMG_ vm_obj_id_t obj, void *key,
325 const vm_val_t *val)
326 {
327 CVmUndoRecord *rec;
328
329 /* allocate the new record */
330 rec = add_new_record(vmg_ obj);
331
332 /* if we successfully allocated a record, set it up */
333 if (rec != 0)
334 {
335 /* set the object */
336 rec->obj = obj;
337
338 /* set the key */
339 rec->id.ptrval = key;
340
341 /* set the value */
342 rec->oldval = *val;
343 }
344
345 /* return an indication as to whether the record was created */
346 return (rec != 0);
347 }
348
349 /*
350 * Add a new undo record
351 */
add_new_record(VMG_ vm_obj_id_t controlling_obj)352 CVmUndoRecord *CVmUndo::add_new_record(VMG_ vm_obj_id_t controlling_obj)
353 {
354 CVmUndoMeta *meta;
355
356 /* if there is not an active savepoint, do not keep undo */
357 if (savept_cnt_ == 0)
358 return 0;
359
360 /*
361 * if the object was created after the current savepoint was created,
362 * there is no need to keep undo for it during this savepoint, since
363 * rolling back to the savepoint will roll back to a point at which
364 * the object didn't even exist
365 */
366 if (!G_obj_table->is_obj_in_undo(controlling_obj))
367 return 0;
368
369 /* allocate a new record */
370 meta = alloc_rec(vmg0_);
371
372 /* return the undo record, if we succeeded */
373 return (meta == 0 ? 0 : &meta->rec);
374 }
375
376 /*
377 * Apply undo to the most recent savepoint.
378 */
undo_to_savept(VMG0_)379 void CVmUndo::undo_to_savept(VMG0_)
380 {
381 CVmUndoMeta *meta;
382
383 /* if we don't have any savepoints, there's nothing to do */
384 if (savept_cnt_ == 0)
385 return;
386
387 /*
388 * Starting with the most recently-added record, apply each record
389 * in sequence until we reach the first savepoint in the undo list.
390 */
391 meta = next_free_;
392 for (;;)
393 {
394 /*
395 * move to the previous record, wrapping to the end of the array
396 * at the first record (since we treat the array as circular)
397 */
398 if (meta == rec_arr_)
399 meta = rec_arr_ + rec_arr_size_;
400 --meta;
401
402 /*
403 * if we're at the first record in the current savepoint, we're
404 * done
405 */
406 if (meta == cur_first_)
407 break;
408
409 /* apply this undo record */
410 G_obj_table->apply_undo(vmg_ &meta->rec);
411 }
412
413 /*
414 * Unwind the undo stack -- get the first record in the previous
415 * savepoint from the link pointer.
416 */
417 cur_first_ = cur_first_->link.prev_first;
418
419 /*
420 * there's nothing following the current savepoint any more -- the
421 * savepoint we just applied is gone now
422 */
423 if (cur_first_ != 0)
424 cur_first_->link.next_first = 0;
425 else
426 oldest_first_ = 0;
427
428 /* that's one less savepoint */
429 --savept_cnt_;
430
431 /* make the previous savepoint current */
432 --cur_savept_;
433 if (cur_savept_ == 0)
434 cur_savept_ = VM_SAVEPT_MAX;
435
436 /* the savepoint link we just removed is now the next free record */
437 next_free_ = meta;
438
439 /*
440 * notify objects that a new savepoint is in effect - the savepoint
441 * isn't new in the sense of being newly created, but in the sense of
442 * being a different savepoint than was previously in effect
443 */
444 G_obj_table->notify_new_savept();
445 }
446
447 /*
448 * Garbage collection: mark referenced objects. This goes through all
449 * of the undo records; for each undo record, we have the object that
450 * owns the undo record mark as referenced any object to which the
451 * record refers.
452 */
gc_mark_refs(VMG0_)453 void CVmUndo::gc_mark_refs(VMG0_)
454 {
455 CVmUndoMeta *cur;
456 CVmUndoMeta *next_link;
457
458 /* if we don't have any records, there's nothing to do */
459 if (oldest_first_ == 0)
460 return;
461
462 /* the first record is a linking record */
463 next_link = oldest_first_;
464
465 /* start at the first record */
466 cur = oldest_first_;
467
468 /*
469 * Go through all undo records, from the oldest to the newest. Note
470 * that we must keep track of each "link" record, because these are
471 * not ordinary undo records and must be handled differently.
472 */
473 for (;;)
474 {
475 /* check to see if this is a linking record or an ordinary record */
476 if (cur == next_link)
477 {
478 /*
479 * this is a linking record - simply note the next linking
480 * record and otherwise ignore this record
481 */
482 next_link = cur->link.next_first;
483 }
484 else if (cur->rec.obj != VM_INVALID_OBJ)
485 {
486 /*
487 * It's an ordinary undo record -- mark its references.
488 * Note that the fact that an object has undo records does
489 * not mean that the object is reachable -- this is
490 * effectively a weak link to the object, because if it's
491 * not reachable through other means, there's no need to
492 * keep any undo information for it; so, we don't mark the
493 * owner object itself as reachable at this point.
494 */
495 G_obj_table->mark_obj_undo_rec(vmg_ cur->rec.obj, &cur->rec);
496 }
497
498 /* advance to the next record, wrapping at the end of the array */
499 ++cur;
500 if (cur == rec_arr_ + rec_arr_size_)
501 cur = rec_arr_;
502
503 /* stop if we've reached the last record */
504 if (cur == next_free_)
505 break;
506 }
507 }
508
509 /*
510 * Garbage collection: delete obsolete weak references. This goes
511 * through all of the undo records; for each undo record, if the object
512 * that owns the record is unreachable, we'll delete the undo record;
513 * otherwise, we'll tell the object that owns the record to clean up the
514 * record if it contains an unreachable weak reference.
515 */
gc_remove_stale_weak_refs(VMG0_)516 void CVmUndo::gc_remove_stale_weak_refs(VMG0_)
517 {
518 CVmUndoMeta *cur;
519 CVmUndoMeta *next_link;
520
521 /* if we don't have any records, there's nothing to do */
522 if (oldest_first_ == 0)
523 return;
524
525 /* the first record is a linking record */
526 next_link = oldest_first_;
527
528 /* start at the first record */
529 cur = oldest_first_;
530
531 /*
532 * Go through all undo records, from the oldest to the newest. Note
533 * that we must keep track of each "link" record, because these are
534 * not ordinary undo records and must be handled differently.
535 */
536 for (;;)
537 {
538 /* check to see if this is a linking record or an ordinary record */
539 if (cur == next_link)
540 {
541 /*
542 * this is a linking record - simply note the next linking
543 * record and otherwise ignore this record
544 */
545 next_link = cur->link.next_first;
546 }
547 else if (cur->rec.obj != VM_INVALID_OBJ)
548 {
549 /*
550 * It's an ordinary undo record -- delete its stale
551 * references. If the record owner is itself about to be
552 * deleted, don't bother with the object, but rather delete
553 * the entire undo record -- undo records themselves only
554 * weakly reference their owning objects.
555 */
556 if (!G_obj_table->is_obj_deletable(cur->rec.obj))
557 {
558 /* it's not ready for deletion - clean up its weak refs */
559 G_obj_table->remove_obj_stale_undo_weak_ref(
560 vmg_ cur->rec.obj, &cur->rec);
561 }
562 else
563 {
564 /*
565 * it's no longer reachable - delete the undo record by
566 * setting the owning object to 'invalid'
567 */
568 cur->rec.obj = VM_INVALID_OBJ;
569 }
570 }
571
572 /* advance to the next record, wrapping at the end of the array */
573 ++cur;
574 if (cur == rec_arr_ + rec_arr_size_)
575 cur = rec_arr_;
576
577 /* stop if we've reached the last record */
578 if (cur == next_free_)
579 break;
580 }
581 }
582
583