static char RCSid[] =

"$Header: d:/cvsroot/tads/tads3/VMUNDO.CPP,v 1.3 1999/07/11 00:46:58 MJRoberts Exp $";

#endif

/* 

 *   Copyright (c) 1998, 2002 Michael J. Roberts.  All Rights Reserved.

 *   

 *   Please see the accompanying license file, LICENSE.TXT, for information

 *   on using and copying this software.  

 */

/*

Name

  vmundo.cpp - undo manager

Function

Notes

Modified

  10/29/98 MJRoberts  - Creation

*/

#include "t3std.h"

#include "vmtype.h"

#include "vmobj.h"

#include "vmundo.h"

/*

 *   create the undo manager 

 */

CVmUndo::CVmUndo(size_t undo_record_cnt, uint max_savepts)

{

    /* remember the maximum number of savepoints */

    max_savepts_ = (vm_savept_t)max_savepts;

    /* 

     *   initialize the savepoint to number 0 (this is arbitrary, but we

     *   might as well start here) 

     */

    cur_savept_ = 0;

    /* no savepoints have been created yet */

    savept_cnt_ = 0;

    /* create the undo record array */

    rec_arr_size_ = undo_record_cnt;

    rec_arr_ = (CVmUndoMeta *)t3malloc(rec_arr_size_

                                       * sizeof(rec_arr_[0]));

    /* we have no records at all yet, so we have no "firsts" */

    cur_first_ = 0;

    oldest_first_ = 0;

    /* start allocating from the first entry in the array */

    next_free_ = rec_arr_;

}

/*

 *   delete the undo manager 

 */

CVmUndo::~CVmUndo()

{

    /* delete the array of undo records */

    t3free(rec_arr_);

}

/*

 *   create a savepoint 

 */

void CVmUndo::create_savept(VMG0_)

{

    CVmUndoMeta *rec;

    /* 

     *   Allocate an undo record to serve as the link pointer for this

     *   savepoint.  If this fails, we cannot create a savepoint; we won't

     *   need to do anything else in this case, since we will have deleted

     *   all existing savepoints if we ran out of records.  

     */

    rec = alloc_rec(vmg0_);

    if (rec == 0)

        return;

    /* if we have an old savepoint, the new record starts the next one */

    if (cur_first_ != 0)

        cur_first_->link.next_first = rec;

    /* the old savepoint (if any) is our previous savepoint */

    rec->link.prev_first = cur_first_;

    /* there's nothing after us yet */

    rec->link.next_first = 0;

    /* this record is now the current savepoint's first record */

    cur_first_ = rec;

    /* 

     *   if we didn't have any savepoints recorded yet, this is now the

     *   first record in the oldest savepoint 

     */

    if (oldest_first_ == 0)

        oldest_first_ = rec;

    /* 

     *   increment the savepoint number, wrapping to zero if we reach the

     *   highest value we can store 

     */

    if (cur_savept_ == VM_SAVEPT_MAX)

        cur_savept_ = 0;

    else

        ++cur_savept_;

    /* 

     *   if we're already storing the maximum number of savepoints we're

     *   allowed to store simultaneously, drop the oldest savepoint;

     *   otherwise, simply increment the savepoint counter 

     */

    if (savept_cnt_ == max_savepts_)

    {

        /* we have the maximum number of savepoints; discard the oldest */

        drop_oldest_savept(vmg0_);

    }

    /* count the new savepoint */

    ++savept_cnt_;

    /* notify the objects that we're starting a new savepoint */

    G_obj_table->notify_new_savept();

}

/*

 *   Discard the oldest savepoint 

 */

void CVmUndo::drop_oldest_savept(VMG0_)

{

    vm_savept_t oldest;

    /* if there are no savepoints, there's nothing to do */

    if (savept_cnt_ == 0)

        return;

    /* 

     *   The oldest savepoint number is (cur - cnt), adjusted for wrapping

     *   if we go below zero.  

     */

    if (cur_savept_ >= savept_cnt_)

        oldest = cur_savept_ - savept_cnt_;

    else

        oldest = VM_SAVEPT_MAX - (savept_cnt_ - cur_savept_) + 1;

    /* decrement the savepoint count, now that this one is gone */

    --savept_cnt_;

    /* forget the oldest lead pointer */

    if (oldest_first_ != 0)

    {

        CVmUndoMeta *meta;

        /* 

         *   discard records from the oldest lead pointer to the next

         *   oldest lead pointer 

         */

        for (meta = oldest_first_, inc_rec_ptr(&meta) ;

             meta != oldest_first_->link.next_first && meta != next_free_ ; )

        {

            /* discard this entry, if it still exists */

            if (meta->rec.obj != VM_INVALID_OBJ)

                vm_objp(vmg_ meta->rec.obj)->discard_undo(vmg_ &meta->rec);

            /* advance to the next record */

            inc_rec_ptr(&meta);

        }

        /* advance the oldest pointer to the next savepoint's first record */

        oldest_first_ = oldest_first_->link.next_first;

        /* there's now nothing before this one */

        if (oldest_first_ != 0)

            oldest_first_->link.prev_first = 0;

    }

    /* if we don't have an oldest, we also don't have a current */

    if (oldest_first_ == 0)

        cur_first_ = 0;

}

/*

 *   Drop all undo information

 */

void CVmUndo::drop_undo(VMG0_)

{

    /* delete each savepoint until we have none left */

    while (savept_cnt_ != 0)

        drop_oldest_savept(vmg0_);

    /* reset the savepoint number */

    cur_savept_ = 0;

    /* we have no "firsts" */

    cur_first_ = 0;

    oldest_first_ = 0;

    /* start allocating from the start of the array */

    next_free_ = rec_arr_;

}

/*

 *   Allocate an undo record.  If we run out of free records, delete

 *   savepoints, starting with the oldest savepoint, until we have a free

 *   record.  

 */

CVmUndoMeta *CVmUndo::alloc_rec(VMG0_)

{

    /* 

     *   keep trying until we find an entry or run out of savepoints to

     *   delete 

     */

    for (;;)

    {

        /*

         *   If we have no savepoints at all, all records are free.

         *   Otherwise, if the next free pointer hasn't bumped up against

         *   the oldest allocated record yet, we can allocate another

         *   record.  

         */

        if (savept_cnt_ == 0 || next_free_ != oldest_first_)

        {

            CVmUndoMeta *ret;

            /* remember the current free record */

            ret = next_free_;

            /* 

             *   advance to the next record, wrapping if we reach the end

             *   of the array (since we treat the array as circular) 

             */

            inc_rec_ptr(&next_free_);

            /* return the record */

            return ret;

        }

        /* 

         *   If we have at least one old savepoint, discard the oldest

         *   savepoint, which may free up some records, and try again;

         *   otherwise, give up.  

         */

        if (savept_cnt_ > 1)

        {

            /* 

             *   we have at least one old savepoint we can discard - get

             *   rid of it and try again 

             */

            drop_oldest_savept(vmg0_);

        }

        else

        {

            /* 

             *   we are down to our last savepoint (or none at all) - it's

             *   no longer valid (since we can't keep it complete due to

             *   the lack of available records), so delete it and return

             *   failure 

             */

            drop_oldest_savept(vmg0_);

            return 0;

        }

    }

}

/*

 *   Add a new record with a property ID key 

 */

void CVmUndo::add_new_record_prop_key(VMG_ vm_obj_id_t obj, vm_prop_id_t key,

                                      const vm_val_t *val)

{

    CVmUndoRecord *rec;

    /* allocate the new record */

    rec = add_new_record(vmg_ obj);

    /* if we successfully allocated a record, set it up */

    if (rec != 0)

    {

        /* set the object */

        rec->obj = obj;

        /* set the key */

        rec->id.prop = key;

        /* set the value */

        rec->oldval = *val;

    }

}

/*

 *   Add a new record with an integer key 

 */

void CVmUndo::add_new_record_int_key(VMG_ vm_obj_id_t obj, uint32 key,

                                     const vm_val_t *val)

{

    CVmUndoRecord *rec;

    /* allocate the new record */

    rec = add_new_record(vmg_ obj);

    /* if we successfully allocated a record, set it up */

    if (rec != 0)

    {

        /* set the object */

        rec->obj = obj;

        /* set the key */

        rec->id.intval = key;

        /* set the value */

        rec->oldval = *val;

    }

}

/*

 *   Add a new record with a pointer key

 */

int CVmUndo::add_new_record_ptr_key(VMG_ vm_obj_id_t obj, void *key,

                                    const vm_val_t *val)

{

    CVmUndoRecord *rec;

    /* allocate the new record */

    rec = add_new_record(vmg_ obj);

    /* if we successfully allocated a record, set it up */

    if (rec != 0)

    {

        /* set the object */

        rec->obj = obj;

        /* set the key */

        rec->id.ptrval = key;

        /* set the value */

        rec->oldval = *val;

    }

    /* return an indication as to whether the record was created */

    return (rec != 0);

}

/*

 *   Add a new undo record 

 */

CVmUndoRecord *CVmUndo::add_new_record(VMG_ vm_obj_id_t controlling_obj)

{

    CVmUndoMeta *meta;

    /* if there is not an active savepoint, do not keep undo */

    if (savept_cnt_ == 0)

        return 0;

    /* 

     *   if the object was created after the current savepoint was created,

     *   there is no need to keep undo for it during this savepoint, since

     *   rolling back to the savepoint will roll back to a point at which

     *   the object didn't even exist 

     */

    if (!G_obj_table->is_obj_in_undo(controlling_obj))

        return 0;

    /* allocate a new record */

    meta = alloc_rec(vmg0_);

    /* return the undo record, if we succeeded */

    return (meta == 0 ? 0 : &meta->rec);

}

/*

 *   Apply undo to the most recent savepoint.

 */

void CVmUndo::undo_to_savept(VMG0_)

{

    CVmUndoMeta *meta;

    /* if we don't have any savepoints, there's nothing to do */

    if (savept_cnt_ == 0)

        return;

    /* 

     *   Starting with the most recently-added record, apply each record

     *   in sequence until we reach the first savepoint in the undo list.  

     */

    meta = next_free_;

    for (;;)

    {

        /* 

         *   move to the previous record, wrapping to the end of the array

         *   at the first record (since we treat the array as circular) 

         */

        if (meta == rec_arr_)

            meta = rec_arr_ + rec_arr_size_;

        --meta;

        /* 

         *   if we're at the first record in the current savepoint, we're

         *   done 

         */

        if (meta == cur_first_)

            break;

        /* apply this undo record */

        G_obj_table->apply_undo(vmg_ &meta->rec);

    }

    /*

     *   Unwind the undo stack -- get the first record in the previous

     *   savepoint from the link pointer. 

     */

    cur_first_ = cur_first_->link.prev_first;

    /* 

     *   there's nothing following the current savepoint any more -- the

     *   savepoint we just applied is gone now 

     */

    if (cur_first_ != 0)

        cur_first_->link.next_first = 0;

    else

        oldest_first_ = 0;

    /* that's one less savepoint */

    --savept_cnt_;

    /* make the previous savepoint current */

    --cur_savept_;

    if (cur_savept_ == 0)

        cur_savept_ = VM_SAVEPT_MAX;

    /* the savepoint link we just removed is now the next free record */

    next_free_ = meta;

    /* 

     *   notify objects that a new savepoint is in effect - the savepoint

     *   isn't new in the sense of being newly created, but in the sense of

     *   being a different savepoint than was previously in effect 

     */

    G_obj_table->notify_new_savept();

}

/*

 *   Garbage collection: mark referenced objects.  This goes through all

 *   of the undo records; for each undo record, we have the object that

 *   owns the undo record mark as referenced any object to which the

 *   record refers.  

 */

void CVmUndo::gc_mark_refs(VMG0_)

{

    CVmUndoMeta *cur;

    CVmUndoMeta *next_link;

    /* if we don't have any records, there's nothing to do */

    if (oldest_first_ == 0)

        return;

    /* the first record is a linking record */

    next_link = oldest_first_;

    /* start at the first record */

    cur = oldest_first_;

    /* 

     *   Go through all undo records, from the oldest to the newest.  Note

     *   that we must keep track of each "link" record, because these are

     *   not ordinary undo records and must be handled differently.  

     */

    for (;;)

    {

        /* check to see if this is a linking record or an ordinary record */

        if (cur == next_link)

        {

            /* 

             *   this is a linking record - simply note the next linking

             *   record and otherwise ignore this record 

             */

            next_link = cur->link.next_first;

        }

        else if (cur->rec.obj != VM_INVALID_OBJ)

        {

            /* 

             *   It's an ordinary undo record -- mark its references.

             *   Note that the fact that an object has undo records does

             *   not mean that the object is reachable -- this is

             *   effectively a weak link to the object, because if it's

             *   not reachable through other means, there's no need to

             *   keep any undo information for it; so, we don't mark the

             *   owner object itself as reachable at this point.  

             */

            G_obj_table->mark_obj_undo_rec(vmg_ cur->rec.obj, &cur->rec);

        }

        /* advance to the next record, wrapping at the end of the array */

        ++cur;

        if (cur == rec_arr_ + rec_arr_size_)

            cur = rec_arr_;

        /* stop if we've reached the last record */

        if (cur == next_free_)

            break;

    }

}

/*

 *   Garbage collection: delete obsolete weak references.  This goes

 *   through all of the undo records; for each undo record, if the object

 *   that owns the record is unreachable, we'll delete the undo record;

 *   otherwise, we'll tell the object that owns the record to clean up the

 *   record if it contains an unreachable weak reference.

 */

void CVmUndo::gc_remove_stale_weak_refs(VMG0_)

{

    CVmUndoMeta *cur;

    CVmUndoMeta *next_link;

    /* if we don't have any records, there's nothing to do */

    if (oldest_first_ == 0)

        return;

    /* the first record is a linking record */

    next_link = oldest_first_;

    /* start at the first record */

    cur = oldest_first_;

    /* 

     *   Go through all undo records, from the oldest to the newest.  Note

     *   that we must keep track of each "link" record, because these are

     *   not ordinary undo records and must be handled differently.  

     */

    for (;;)

    {

        /* check to see if this is a linking record or an ordinary record */

        if (cur == next_link)

        {

            /* 

             *   this is a linking record - simply note the next linking

             *   record and otherwise ignore this record 

             */

            next_link = cur->link.next_first;

        }

        else if (cur->rec.obj != VM_INVALID_OBJ)

        {

            /* 

             *   It's an ordinary undo record -- delete its stale

             *   references.  If the record owner is itself about to be

             *   deleted, don't bother with the object, but rather delete

             *   the entire undo record -- undo records themselves only

             *   weakly reference their owning objects.  

             */

            if (!G_obj_table->is_obj_deletable(cur->rec.obj))

            {

                /* it's not ready for deletion - clean up its weak refs */

                G_obj_table->remove_obj_stale_undo_weak_ref(

                    vmg_ cur->rec.obj, &cur->rec);

            }

            else

            {

                /* 

                 *   it's no longer reachable - delete the undo record by

                 *   setting the owning object to 'invalid' 

                 */

                cur->rec.obj = VM_INVALID_OBJ;

            }

        }

        /* advance to the next record, wrapping at the end of the array */

        ++cur;

        if (cur == rec_arr_ + rec_arr_size_)

            cur = rec_arr_;

        /* stop if we've reached the last record */

        if (cur == next_free_)

            break;

    }

}