aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--gc.cpp16
-rw-r--r--model.cpp41
-rw-r--r--model.h71
-rw-r--r--types.h1
4 files changed, 90 insertions, 39 deletions
diff --git a/gc.cpp b/gc.cpp
index 0e4fc3d..05f70cc 100644
--- a/gc.cpp
+++ b/gc.cpp
@@ -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--;
}
diff --git a/model.cpp b/model.cpp
index a56e530..3e5c9fa 100644
--- a/model.cpp
+++ b/model.cpp
@@ -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;
}
diff --git a/model.h b/model.h
index 797631d..ab5dcc6 100644
--- a/model.h
+++ b/model.h
@@ -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;
};/*}}}*/
diff --git a/types.h b/types.h
index 3b948e4..6c3ae54 100644
--- a/types.h
+++ b/types.h
@@ -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 &);