/* 

 *   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

  vmlst.h - VM dynamic list implementation

Function

Notes

Modified

  10/29/98 MJRoberts  - Creation

*/

#ifndef VMLST_H

#define VMLST_H

#include <stdlib.h>

#include "vmtype.h"

#include "vmobj.h"

#include "vmcoll.h"

#include "vmglob.h"

#include "vmstack.h"

class CVmObjList: public CVmObjCollection

{

    friend class CVmMetaclassList;

public:

    /* metaclass registration object */

    static class CVmMetaclass *metaclass_reg_;

    class CVmMetaclass *get_metaclass_reg() const { return metaclass_reg_; }

    /* am I of the given metaclass? */

    virtual int is_of_metaclass(class CVmMetaclass *meta) const

    {

        /* try my own metaclass and my base class */

        return (meta == metaclass_reg_

                || CVmObjCollection::is_of_metaclass(meta));

    }

    /* create dynamically using stack arguments */

    static vm_obj_id_t create_from_stack(VMG_ const uchar **pc_ptr,

                                         uint argc);

    /* 

     *   Create dynamically from parameters in the stack; we do not remove

     *   the elements from the stack, but simply create a list from the

     *   parameters.  'idx' is the parameter index of the first parameter,

     *   and 'cnt' is the number of parameters to use.  

     */

    static vm_obj_id_t create_from_params(VMG_ uint idx, uint cnt);

    /* 

     *   call a static property - we don't have any of our own, so simply

     *   "inherit" the base class handling 

     */

    static int call_stat_prop(VMG_ vm_val_t *result,

                              const uchar **pc_ptr, uint *argc,

                              vm_prop_id_t prop)

    {

        return CVmObjCollection::

            call_stat_prop(vmg_ result, pc_ptr, argc, prop);

    }

    /* reserve constant data */

    virtual void reserve_const_data(VMG_ class CVmConstMapper *mapper,

                                    vm_obj_id_t self);

    /* convert to constant data */

    virtual void convert_to_const_data(VMG_ class CVmConstMapper *mapper,

                                       vm_obj_id_t self);

    /* get my datatype when converted to constant data */

    virtual vm_datatype_t get_convert_to_const_data_type() const

      { return VM_LIST; }

    /* create a list with no initial contents */

    static vm_obj_id_t create(VMG_ int in_root_set);

    /* 

     *   create a list with a given number of elements, for construction

     *   of the list element-by-element 

     */

    static vm_obj_id_t create(VMG_ int in_root_set, size_t element_count);

    /* 

     *   create a list from a constant list, for construction of the list

     *   as a modified copy of an original list 

     */

    static vm_obj_id_t create(VMG_ int in_root_set, const char *lst);

    /*

     *   List construction: set an element.  List contents are immutable,

     *   so they cannot be changed after the list is constructed.

     *   However, it is often convenient to construct a list one element

     *   at a time, so a caller can create the list with the appropriate

     *   number of elements, then use this routine to set each element of

     *   the list individually.

     *   

     *   idx is the index of the element in the list; the first element is

     *   at index zero.  Note that this routine does *not* allocate

     *   memory; the list must be pre-allocated to its full number of

     *   elements.

     */

    void cons_set_element(size_t idx, const vm_val_t *val);

    /* update the list in place so that each value is unique */

    void cons_uniquify(VMG0_);

    /* 

     *   Copy an existing list into our list, starting at a given index.  The

     *   caller must ensure that our list buffer is large enough to

     *   accommodate the new elements.  The 'orig_list' value must point to a

     *   standard list constant value: a UINT2 element count prefix followed

     *   by DATAHOLDER elements.  

     */

    void cons_copy_elements(size_t start_idx, const char *orig_list);

    /*

     *   Copy existing list elements into our list, starting at the given

     *   index.  The caller must ensure that our list buffer is large enough

     *   to accommodate the new elements.  The 'ele_array' is an array of

     *   DATAHOLDER values.  

     */

    void cons_copy_data(size_t start_idx, const char *ele_array,

                        size_t ele_count);

    /*

     *   Set the length of the list.  This can be used when constructing a

     *   list, and the actual number of elements is unknown before

     *   construction is complete (however, the maximum number of elements

     *   must be known in advance, since this merely sets the length, and

     *   does NOT reallocate the list -- hence, this call can only be used

     *   to shrink the list below its allocated size, never to expand it).

     */

    void cons_set_len(size_t len)

        { vmb_put_len(ext_, len); }

    /* notify of deletion */

    void notify_delete(VMG_ int in_root_set);

    /* set a property */

    void set_prop(VMG_ class CVmUndo *undo,

                  vm_obj_id_t self, vm_prop_id_t prop, const vm_val_t *val);

    /* get a property */

    int get_prop(VMG_ vm_prop_id_t prop, vm_val_t *val,

                 vm_obj_id_t self, vm_obj_id_t *source_obj, uint *argc);

    /* undo operations - lists are immutable and hence keep no undo */

    void notify_new_savept() { }

    void apply_undo(VMG_ struct CVmUndoRecord *) { }

    void mark_undo_ref(VMG_ struct CVmUndoRecord *) { }

    void remove_stale_undo_weak_ref(VMG_ struct CVmUndoRecord *) { }    

    /* mark references */

    void mark_refs(VMG_ uint state);

    /* 

     *   remove weak references - we keep only normal (strong) references,

     *   so this routine doesn't need to do anything 

     */

    void remove_stale_weak_refs(VMG0_) { }

    /* load from an image file */

    void load_from_image(VMG_ vm_obj_id_t, const char *ptr, size_t)

        { ext_ = (char *)ptr; }

    /* rebuild for image file */

    virtual ulong rebuild_image(VMG_ char *buf, ulong buflen);

    /* save to a file */

    void save_to_file(VMG_ class CVmFile *fp);

    /* restore from a file */

    void restore_from_file(VMG_ vm_obj_id_t self,

                           class CVmFile *fp, class CVmObjFixup *fixups);

    /* 

     *   Add a value to the list.  If the value to add is a list (constant

     *   or object), we'll append each element of the list to this list;

     *   otherwise, we'll just append the value itself to the list.  In

     *   any case, we don't modify this list itself, but create a new list

     *   object to hold the result.

     */

    void add_val(VMG_ vm_val_t *result,

                 vm_obj_id_t self, const vm_val_t *val);

    /*

     *   Index the list 

     */

    void index_val(VMG_ vm_val_t *result, vm_obj_id_t self,

                   const vm_val_t *index_val);

    /*

     *   Set an indexed element of the list.  Since the contents of a list

     *   object cannot be changed, we'll return in *new_container a new

     *   list object that we create with the modified contents.  

     */

    void set_index_val(VMG_ vm_val_t *new_container, vm_obj_id_t self,

                       const vm_val_t *index_val, const vm_val_t *new_val);

    /* 

     *   Subtract a value from the list.  This creates a new list with the

     *   element matching the given value removed from the original list.

     *   We do not modify the original list; instead, we create a new list

     *   object with the new value.  

     */

    void sub_val(VMG_ vm_val_t *result,

                 vm_obj_id_t self, const vm_val_t *val);

    /* 

     *   get as a list - simply return our extension, which is in the

     *   required portable list format 

     */

    const char *get_as_list() const { return ext_; }

    /* 

     *   Check a value for equality.  We will match any constant list that

     *   contains the same data as our list, and any other list object

     *   with the same underlying data.  

     */

    int equals(VMG_ vm_obj_id_t self, const vm_val_t *val, int depth) const;

    /*

     *   Static list adder.  This creates a new list object that results

     *   from appending the given value to the given list constant.  This

     *   is defined statically so that this code can be shared for adding

     *   to constant pool lists and adding to CVmObjList objects.

     *   

     *   'lstval' must point to a constant list.  The first two bytes of

     *   the list are stored in portable UINT2 format and give the number

     *   of elements in the list; this is immediately followed by a packed

     *   array of data holders in portable format.  

     */

    static void add_to_list(VMG_ vm_val_t *result,

                            vm_obj_id_t self, const char *lstval,

                            const vm_val_t *val);

    /*

     *   Static list subtraction routine. This creates a new list object

     *   that results from removing the given value from the list

     *   constant.  This is defined statically so that this code can be

     *   shared for subtracting from constant pool lists and subtracting

     *   from CVmObjList objects.

     *   

     *   'lstmem' must point to a constant list in the same format as

     *   required for add_to_list.  If 'lstmem' comes from the constant

     *   pool, then 'lstval' must be provided to give us the constant pool

     *   address; otherwise, 'lstval' should be null.  

     */

    static void sub_from_list(VMG_ vm_val_t *result,

                              const vm_val_t *lstval, const char *lstmem,

                              const vm_val_t *val);

    /*

     *   Constant list comparison routine.  Compares the given list

     *   constant (in portable format, with leading UINT2 element count

     *   prefix followed by the list's elements in portable data holder

     *   format) to the other value.  Returns true if the other value is a

     *   list constant or object whose contents match the list constant,

     *   false if not.

     *   

     *   If 'lstmem' comes from the constant pool, then 'lstval' must be

     *   provided to give us the constant pool address; otherwise,

     *   'lstval' should be null.  

     */

    static int const_equals(VMG_ const vm_val_t *lstval, const char *lstmem,

                            const vm_val_t *val, int depth);

    /*

     *   Calculate a hash value for the list 

     */

    uint calc_hash(VMG_ vm_obj_id_t self, int depth) const;

    /*

     *   Constant list hash value calculation

     */

    static uint const_calc_hash(VMG_ const vm_val_t *self_val,

                                const char *lst, int depth);

    /*

     *   When we're the right-hand side of a '+' or '-' operation whose

     *   left-hand side is another collection type that treats these

     *   operators as concatenation/set subtraction, add/subtract our

     *   elements individually.  

     */

    size_t get_coll_addsub_rhs_ele_cnt(VMG0_) const

        { return vmb_get_len(ext_); }

    void get_coll_addsub_rhs_ele(VMG_ vm_val_t *result,

                                 vm_obj_id_t self, size_t idx)

        { index_list(vmg_ result, ext_, idx); }

    /*

     *   Constant list indexing routine.  Indexes the given constant list

     *   (which must be in portable format, with leading UINT2 element

     *   count followed by the list's elements in portable data holder

     *   format), looking up the value at the index number given by the

     *   index value, and puts the result in *result. 

     */

    static void index_list(VMG_ vm_val_t *result,

                           const char *lst, const vm_val_t *index_val);

    /* index a list, using a 1-based index */

    static void index_list(VMG_ vm_val_t *result, const char *lst, uint idx);

    /* push the indexed element, using a 1-based index */

    static void index_and_push(VMG_ const char *lst, uint idx)

    {

        vm_val_t *p;

        /* push a new stack element */

        p = G_stk->push();

        /* index the list and store the value directly in the stack */

        index_list(vmg_ p, lst, idx);

    }

    /*

     *   Constant list set-index routine.  Creates a new list object as a

     *   copy of this list, with the element at the given index set to the

     *   given new value. 

     */

    static void set_index_list(VMG_ vm_val_t *result,

                               const char *lst, const vm_val_t *index_val,

                               const vm_val_t *new_val);

    /*

     *   Find a value within a list.  If we find the value, we'll set

     *   *idxp to the index (starting at zero for the first element) of

     *   the item we found, and we'll return true; if we don't find the

     *   value, we'll return false.  

     */

    static int find_in_list(VMG_ const vm_val_t *lst,

                            const vm_val_t *val, size_t *idxp);

    /* find the last match for a value */

    static int find_last_in_list(VMG_ const vm_val_t *lst,

                                 const vm_val_t *val, size_t *idxp);

    /*

     *   Evaluate a property of a constant list value.  Returns true if we

     *   successfully evaluated the property, false if the property is not

     *   one of the properties that the list class defines.  

     */

    static int const_get_prop(VMG_ vm_val_t *retval, const vm_val_t *self_val,

                              const char *lst, vm_prop_id_t prop, 

                              vm_obj_id_t *srcobj, uint *argc);

    /* property evaluator - undefined property */

    static int getp_undef(VMG_ vm_val_t *, const vm_val_t *,

                          const char *, uint *)

        { return FALSE; }

    /* property evaluator - select a subset through a callback */

    static int getp_subset(VMG_ vm_val_t *retval, const vm_val_t *self_val,

                           const char *lst, uint *argc);

    /* property evaluator - apply a callback to each element */

    static int getp_map(VMG_ vm_val_t *retval, const vm_val_t *self_val,

                        const char *lst, uint *argc);

    /* get the length */

    static int getp_len(VMG_ vm_val_t *retval, const vm_val_t *self_val,

                        const char *lst, uint *argc);

    /* sublist */

    static int getp_sublist(VMG_ vm_val_t *retval, const vm_val_t *self_val,

                            const char *lst, uint *argc);

    /* intersect */

    static int getp_intersect(VMG_ vm_val_t *retval,

                              const vm_val_t *self_val,

                              const char *lst, uint *argc);

    /* indexOf */

    static int getp_index_of(VMG_ vm_val_t *retval, const vm_val_t *self_val,

                             const char *lst, uint *argc);

    /* car */

    static int getp_car(VMG_ vm_val_t *retval, const vm_val_t *self_val,

                        const char *lst, uint *argc);

    /* cdr */

    static int getp_cdr(VMG_ vm_val_t *retval, const vm_val_t *self_val,

                        const char *lst, uint *argc);

    /* indexWhich */

    static int getp_index_which(VMG_ vm_val_t *retval,

                                const vm_val_t *self_val,

                                const char *lst, uint *argc);

    /* forEach */

    static int getp_for_each(VMG_ vm_val_t *retval, const vm_val_t *self_val,

                             const char *lst, uint *argc);

    /* forEachAssoc */

    static int getp_for_each_assoc(VMG_ vm_val_t *retval,

                                   const vm_val_t *self_val,

                                   const char *lst, uint *argc);

    /* valWhich */

    static int getp_val_which(VMG_ vm_val_t *retval,

                              const vm_val_t *self_val,

                              const char *lst, uint *argc);

    /* lastIndexOf */

    static int getp_last_index_of(VMG_ vm_val_t *retval,

                                  const vm_val_t *self_val,

                                  const char *lst, uint *argc);

    /* lastIndexWhich */

    static int getp_last_index_which(VMG_ vm_val_t *retval,

                                     const vm_val_t *self_val,

                                     const char *lst, uint *argc);

    /* lastValWhich */

    static int getp_last_val_which(VMG_ vm_val_t *retval,

                                   const vm_val_t *self_val,

                                   const char *lst, uint *argc);

    /* countOf */

    static int getp_count_of(VMG_ vm_val_t *retval,

                             const vm_val_t *self_val,

                             const char *lst, uint *argc);

    /* countWhich */

    static int getp_count_which(VMG_ vm_val_t *retval,

                                const vm_val_t *self_val,

                                const char *lst, uint *argc);

    /* general routine for indexWhich and lastIndexWhich */

    static int gen_index_which(VMG_ vm_val_t *retval,

                               const vm_val_t *self_val,

                               const char *lst, uint *argc,

                               int forward);

    /* getUnique */

    static int getp_get_unique(VMG_ vm_val_t *retval,

                               const vm_val_t *self_val,

                               const char *lst, uint *argc);

    /* appendUnique */

    static int getp_append_unique(VMG_ vm_val_t *retval,

                                  const vm_val_t *self_val,

                                  const char *lst, uint *argc);

    /* append */

    static int getp_append(VMG_ vm_val_t *retval,

                           const vm_val_t *self_val,

                           const char *lst, uint *argc);

    /* sort */

    static int getp_sort(VMG_ vm_val_t *retval,

                         const vm_val_t *self_val,

                         const char *lst, uint *argc);

    /* insertAt */

    static int getp_insert_at(VMG_ vm_val_t *retval,

                              const vm_val_t *self_val,

                              const char *lst, uint *argc);

    /* prepend */

    static int getp_prepend(VMG_ vm_val_t *retval,

                            const vm_val_t *self_val,

                            const char *lst, uint *argc);

    /* property evaluator - remove a single element at a given index */

    static int getp_remove_element_at(VMG_ vm_val_t *retval,

                                      const vm_val_t *self_val,

                                      const char *lst, uint *argc);

    /* property evaluator - removeRange */

    static int getp_remove_range(VMG_ vm_val_t *retval,

                                 const vm_val_t *self_val,

                                 const char *lst, uint *argc);

protected:

    /* general processor for forEach and forEachAssoc */

    static int for_each_gen(VMG_ vm_val_t *retval,

                            const vm_val_t *self_val,

                            const char *lst, uint *argc,

                            int send_idx_to_cb);

    /*

     *   Compute the intersection of two lists.  Returns a new list with the

     *   elements that occur in both lists.  

     */

    static vm_obj_id_t intersect(VMG_ const vm_val_t *lst1,

                                 const vm_val_t *lst2);

    /* insert the arguments into the list at the given index */

    static void insert_elements(VMG_ vm_val_t *retval,

                                const vm_val_t *self_val,

                                const char *lst, uint argc, int idx);

    /* remove elements */

    static void remove_range(VMG_ vm_val_t *retval,

                             const vm_val_t *self_val,

                             const char *lst, int start_idx, int del_cnt);

    /* create an iterator */

    virtual void new_iterator(VMG_ vm_val_t *retval,

                              const vm_val_t *self_val);

    /* 

     *   create a live iterator - for a list, there is no difference

     *   between snapshot and live iterators, since a list is immutable 

     */

    virtual void new_live_iterator(VMG_ vm_val_t *retval,

                                   const vm_val_t *self_val)

        { new_iterator(vmg_ retval, self_val); }

    /* get the number of elements in the list */

    size_t get_ele_count() const { return vmb_get_len(ext_); }

    /* get an element, given a zero-based index */

    void get_element(size_t idx, vm_val_t *val) const

    {

        /* get the data from the data holder in our extension */

        vmb_get_dh(get_element_ptr(idx), val);

    }

    /* get the number of elements in a constant list */

    static size_t get_ele_count_const(const char *lstval)

        { return vmb_get_len(lstval); }

    /* get an element from a constant list, given a zero-based index */

    static void get_element_const(const char *lstval, size_t idx,

                                  vm_val_t *val)

    {

        /* get the data from the data holder in the constant list */

        vmb_get_dh(get_element_ptr_const(lstval, idx), val);

    }

    /* given an index, get a pointer to the element's data in the list */

    char *get_element_ptr(size_t idx) const

    {

        /* 

         *   figure out where this element's data holder is by skipping

         *   the count prefix, then skipping past preceding data holders 

         */

        return ext_ + VMB_LEN + (idx * VMB_DATAHOLDER);

    }

    /* 

     *   given an index, and a pointer to a constant list, get a pointer

     *   to the element's data in the list constant 

     */

    static const char *get_element_ptr_const(const char *lstval, size_t idx)

    {

        /* 

         *   figure out where this element's data holder is by skipping

         *   the count prefix, then skipping past preceding data holders 

         */

        return lstval + VMB_LEN + (idx * VMB_DATAHOLDER);

    }

    /* 

     *   given a pointer to a list element, increment the pointer so that

     *   it points to the next element 

     */

    static void inc_element_ptr(char **p)

    {

        /* add the size of a data holder to the current pointer */

        *p += VMB_DATAHOLDER;

    }

    /* increment a constant element pointer */

    static void inc_const_element_ptr(const char **p)

    {

        /* add the size of a data holder to the current pointer */

        *p += VMB_DATAHOLDER;

    }

    /* create a list with no initial contents */

    CVmObjList() { ext_ = 0; }

    /* 

     *   create a list with a given number of elements, for construction

     *   of the list element-by-element 

     */

    CVmObjList(VMG_ size_t element_count);

    /* create a list from a constant list */

    CVmObjList(VMG_ const char *lst);

    /*

     *   Calculate the amount of space we need to store a list of a given

     *   length.  We require two bytes for the length prefix, plus the

     *   space for each element.

     */

    static size_t calc_alloc(size_t elecnt)

        { return (VMB_LEN + (elecnt * VMB_DATAHOLDER)); }

    /* allocate space for the list, given the number of elements */

    void alloc_list(VMG_ size_t element_count);

    /* property evaluation function table */

    static int (*func_table_[])(VMG_ vm_val_t *retval,

                                const vm_val_t *self_val,

                                const char *lst, uint *argc);

};

/* ------------------------------------------------------------------------ */

/*

 *   A constant list is exactly like an ordinary list, except that our

 *   contents come from the constant pool.  We store a pointer directly to

 *   our constant pool data rather than making a separate copy.  The only

 *   thing we have to do differently from an ordinary list is that we don't

 *   delete our extension when we're deleted, since our extension is really

 *   just a pointer into the constant pool.  

 */

class CVmObjListConst: public CVmObjList

{

public:

    /* notify of deletion */

    void notify_delete(VMG_ int /*in_root_set*/)

    {

        /* 

         *   do nothing, since our extension is just a pointer into the

         *   constant pool 

         */

    }

    /* create from constant pool data */

    static vm_obj_id_t create(VMG_ const char *const_ptr);

protected:

    /* construct from constant pool data */

    CVmObjListConst(VMG_ const char *const_ptr)

    {

        /* point our extension directly to the constant pool data */

        ext_ = (char *)const_ptr;

    }

};

/* ------------------------------------------------------------------------ */

/*

 *   Registration table object 

 */

class CVmMetaclassList: public CVmMetaclass

{

public:

    /* get the global name */

    const char *get_meta_name() const { return "list/030007"; }

    /* create from image file */

    void create_for_image_load(VMG_ vm_obj_id_t id)

    {

        new (vmg_ id) CVmObjList();

        G_obj_table->set_obj_gc_characteristics(id, TRUE, FALSE);

    }

    /* create from restoring from saved state */

    void create_for_restore(VMG_ vm_obj_id_t id)

    {

        new (vmg_ id) CVmObjList();

        G_obj_table->set_obj_gc_characteristics(id, TRUE, FALSE);

    }

    /* create dynamically using stack arguments */

    vm_obj_id_t create_from_stack(VMG_ const uchar **pc_ptr, uint argc)

        { return CVmObjList::create_from_stack(vmg_ pc_ptr, argc); }

    /* call a static property */

    int call_stat_prop(VMG_ vm_val_t *result,

                       const uchar **pc_ptr, uint *argc,

                       vm_prop_id_t prop)

    {

        return CVmObjList::call_stat_prop(vmg_ result, pc_ptr, argc, prop);

    }

    /* I'm a Collection object */

    CVmMetaclass *get_supermeta_reg() const

        { return CVmObjCollection::metaclass_reg_; }

};

#endif /* VMLST_H */

/*

 *   Register the class 

 */

VM_REGISTER_METACLASS(CVmObjList)