diff options
| -rw-r--r-- | gc.cpp | 16 | ||||
| -rw-r--r-- | model.cpp | 41 | ||||
| -rw-r--r-- | model.h | 71 | ||||
| -rw-r--r-- | types.h | 1 |
4 files changed, 90 insertions, 39 deletions
@@ -25,12 +25,12 @@ GarbageCollector::PendingEntry::PendingEntry( void GarbageCollector::expose(EvalObj *ptr) { - if (ptr == NULL || ptr->gc_obj == NULL) return; + if (ptr == NULL || ptr->gc_rec == NULL) return; #ifdef GC_DEBUG fprintf(stderr, "GC: 0x%llx exposed. count = %lu \"%s\"\n", - (ull)ptr, ptr->gc_obj->gc_cnt - 1, ptr->ext_repr().c_str()); + (ull)ptr, ptr->gc_rec->gc_cnt - 1, ptr->ext_repr().c_str()); #endif - if (--ptr->gc_obj->gc_cnt == 0) + if (--ptr->gc_rec->gc_cnt == 0) { #ifdef GC_DEBUG fprintf(stderr, "GC: 0x%llx pending. \n", (ull)ptr); @@ -45,7 +45,7 @@ void GarbageCollector::force() { { np = p->next; EvalObj *obj = p->obj; - if (obj->gc_obj && !obj->gc_obj->gc_cnt) + if (obj->gc_rec && !obj->gc_rec->gc_cnt) *r++ = obj; delete p; } // fetch the pending pointers in the list @@ -99,10 +99,10 @@ EvalObj *GarbageCollector::attach(EvalObj *ptr) { if (flag) mapping[ptr]++; else mapping[ptr] = 1; */ - ptr->gc_obj->gc_cnt++; + ptr->gc_rec->gc_cnt++; #ifdef GC_DEBUG fprintf(stderr, "GC: 0x%llx attached. count = %lu \"%s\"\n", - (ull)ptr, ptr->gc_obj->gc_cnt, ptr->ext_repr().c_str()); + (ull)ptr, ptr->gc_rec->gc_cnt, ptr->ext_repr().c_str()); #endif /* if (mapping.size() > GC_QUEUE_SIZE >> 1) force();*/ @@ -174,10 +174,10 @@ ObjEntry *GarbageCollector::join(EvalObj *ptr) { } void GarbageCollector::quit(EvalObj *ptr) { - ObjEntry *p = ptr->gc_obj; + ObjEntry *p = ptr->gc_rec; p->prev->next = p->next; p->next->prev = p->prev; - ptr->gc_obj = NULL; + ptr->gc_rec = NULL; delete p; joined_size--; } @@ -6,11 +6,14 @@ #include "types.h" #include "gc.h" -const int REPR_STACK_SIZE = 262144; +static const int REPR_STACK_SIZE = 262144; extern EmptyList *empty_list; extern GarbageCollector gc; +typedef set<EvalObj*> EvalObjAddrHash; +/** Maintain the current in-stack objects to detect circular structures */ static EvalObjAddrHash hash; +/** The stack for building external representation string */ static ReprCons *repr_stack[REPR_STACK_SIZE]; FrameObj::FrameObj(FrameType _ftype) : ftype(_ftype) {} @@ -25,10 +28,12 @@ bool FrameObj::is_parse_bracket() { EvalObj::EvalObj(int _otype) : FrameObj(CLS_EVAL_OBJ), otype(_otype) { - gc_obj = gc.join(this); + /** To notify GC when an EvalObj is constructed */ + gc_rec = gc.join(this); } EvalObj::~EvalObj() { + /** To notify GC when an EvalObj is destructed */ gc.quit(this); } @@ -51,10 +56,10 @@ bool EvalObj::is_opt_obj() { } bool EvalObj::is_pair_obj() { + /** an empty list is not a pair obj */ return this != empty_list && (otype & CLS_PAIR_OBJ); } - bool EvalObj::is_num_obj() { return otype & CLS_NUM_OBJ; } @@ -80,13 +85,16 @@ int EvalObj::get_otype() { } bool EvalObj::is_true() { + /** will be override by `BoolObj` */ return true; } string EvalObj::ext_repr() { - hash.clear(); // TODO: Performance improvement // (from possibly O(n^2logn) to strictly O(nlogn)) + // O(n^2logn) because the potential string concatenate + // cost + hash.clear(); ReprCons **top_ptr = repr_stack; *top_ptr++ = this->get_repr_cons(); EvalObj *obj; @@ -97,6 +105,7 @@ string EvalObj::ext_repr() { { top_ptr -= 2; obj = (*top_ptr)->next((*(top_ptr + 1))->repr); + delete *(top_ptr + 1); if (obj) { *(++top_ptr) = obj->get_repr_cons(); @@ -104,14 +113,19 @@ string EvalObj::ext_repr() { if (ptr) { if (hash.count(ptr)) + { + delete *top_ptr; *top_ptr = new ReprStr("#inf#"); + } else hash.insert(ptr); } } else { - hash.erase((*top_ptr)->ori); - *top_ptr = new ReprStr((*top_ptr)->repr); + hash.erase((*top_ptr)->ori); // poping from stack + ReprCons *p = *top_ptr; + *top_ptr = new ReprStr(p->repr); + delete p; } } else @@ -125,17 +139,26 @@ string EvalObj::ext_repr() { if (ptr) { if (hash.count(ptr)) + { + delete *top_ptr; *top_ptr = new ReprStr("#inf#"); - else hash.insert(ptr); + } + else hash.insert(ptr); // push into stack } } - else *top_ptr = new ReprStr((*top_ptr)->repr); + else + { + ReprCons *p = *top_ptr; + *top_ptr = new ReprStr(p->repr); + delete p; + } } top_ptr++; } - string &res = (*repr_stack)->repr; + string res = (*repr_stack)->repr; if (this->is_pair_obj()) res = "(" + res + ")"; + delete *repr_stack; return res; } @@ -10,7 +10,6 @@ using std::string; typedef unsigned char FrameType; typedef unsigned char NumLvl; -const int CLS_RET_ADDR = 1 << 0; const int CLS_EVAL_OBJ = 1 << 1; const int CLS_PAR_BRA = 1 << 2; @@ -21,11 +20,10 @@ const int CLS_CONTAINER = 1 << 20; #define TO_PAIR(ptr) \ (static_cast<Pair*>(ptr)) - /** @class FrameObj - * Objects that can be held in the evaluation stack + * Objects that can be held in the parsing stack */ -class FrameObj { +class FrameObj {/*{{{*/ protected: /** * Report the type of the FrameObj, which can avoid the use of @@ -34,19 +32,21 @@ class FrameObj { FrameType ftype; public: /** - * Construct an EvalObj - * @param ftype the type of the FrameObj (CLS_EVAL_OBJ for an EvalObj, - * CLS_RET_ADDR for a return address) + * Construct a FrameObj + * @param ftype describes the type of the FrameObj (CLS_EVAL_OBJ for an EvalObj, + * CLS_PAR_BRA for a bracket) */ FrameObj(FrameType ftype); + /** + * The destructor + */ virtual ~FrameObj() {} /** * Tell whether the object is a bracket, according to ftype * @return true for yes */ bool is_parse_bracket(); -}; - +};/*}}}*/ class ObjEntry; class Pair; @@ -54,7 +54,7 @@ class ReprCons; /** @class EvalObj * Objects that represents a value in evaluation */ -class EvalObj : public FrameObj { +class EvalObj : public FrameObj {/*{{{*/ protected: /** * Report the type of the EvalObj, which can avoid the use of @@ -62,25 +62,31 @@ class EvalObj : public FrameObj { */ int otype; public: - ObjEntry *gc_obj; + /** + * The pointer to the corresponding record in GC + */ + ObjEntry *gc_rec; /** * Construct an EvalObj - * @param otype the type of the EvalObj (CLS_PAIR_OBJ for a - * construction, CLS_SIM_OBJ for a simple object), which defaults to - * CLS_SIM_OBJ + * @param otype the type of the EvalObj (CLS_PAIR_OBJ for a pair, + * CLS_SIM_OBJ for a simple object), which defaults to CLS_SIM_OBJ, etc. */ EvalObj(int otype = CLS_SIM_OBJ); + /** + * The destructor + */ ~EvalObj(); /** Check if the object is a simple object (instead of a call * invocation) - * @return true if the object is not a construction (Pair) + * @return true if the object is not a pair or an empty list * */ bool is_simple_obj(); /** Check if the object is a symobl */ bool is_sym_obj(); /** Check if the object is an operator */ bool is_opt_obj(); - /** Check if the object is a Pair */ + /** Check if the object is a pair (notice that an empty list does + * not counts as a pair here) */ bool is_pair_obj(); /** Check if the object is a number */ bool is_num_obj(); @@ -92,34 +98,57 @@ class EvalObj : public FrameObj { bool is_prom_obj(); /** Check if the object is a vector */ bool is_vect_obj(); + /** Check if the object is a container */ bool is_container(); + /** Get `otype`, used by some routines for efficiency issues */ int get_otype(); + /** Dummy function, actually used by OptObj, called before the actual + * invocation */ virtual void prepare(Pair *pc); /** Any EvalObj has its external representation */ string ext_repr(); - /** Always true for all EvalObjs except BoolObj */ + /** Always true for all other EvalObjs except BoolObj */ virtual bool is_true(); - /** External representation construction */ + /** External representation construction, used by `ext_repr()` */ virtual ReprCons *get_repr_cons() = 0; -}; +};/*}}}*/ /** @class ParseBracket * To indiate a left bracket when parsing, used in the parse_stack */ class ParseBracket : public FrameObj {/*{{{*/ public: - unsigned char btype; /**< The type of the bracket */ + /** The type of the bracket */ + unsigned char btype; /** Construct a ParseBracket object */ ParseBracket(unsigned char btype); };/*}}}*/ +/** @class Container + * Describes the kind of EvalObjs which may cause circular reference issue, + * different from some "direct" objects, such as BoolObj, NumberObj... + */ class Container: public EvalObj {/*{{{*/ public: - bool keep; + /** true if the object is still in use, its value is set and read temporarily, + * check `gc.cpp` */ + bool keep; + /** the counter used when resolving circular references, see `gc.cpp` */ size_t gc_refs; + /** Constructor, does an "or" bit operation on the otype provided by + * its subclasses, i.e. to mark CLS_CONTAINER. + * The mark will not be not enforced if the `override` is + * true. */ Container(int otype = 0, bool override = false); + /** + * Decrease the gc_refs of the objects referenced by this container. + * Used by circular ref resolver to detect the cycle. + */ virtual void gc_decrement() = 0; + /** Push the objects referenced by this container to the queue via the pointer `tail`. Used in the phase of + * marking `keep`. + */ virtual void gc_trigger(EvalObj ** &tail) = 0; };/*}}}*/ @@ -33,7 +33,6 @@ static const int NUM_LVL_REAL = 1; static const int NUM_LVL_RAT = 2; static const int NUM_LVL_INT = 3; -typedef set<EvalObj*> EvalObjAddrHash; typedef vector<EvalObj*> EvalObjVec; typedef map<string, EvalObj*> Str2EvalObj; typedef EvalObj* (*BuiltinProc)(Pair *, const string &); |