summaryrefslogtreecommitdiff
path: root/Build/source/utils/asymptote/entry.h
diff options
context:
space:
mode:
authorKarl Berry <karl@freefriends.org>2010-07-11 22:39:53 +0000
committerKarl Berry <karl@freefriends.org>2010-07-11 22:39:53 +0000
commit4e8485b0ddecb55f72929dd6233f254a1e7bf5b0 (patch)
tree354324ee6f54d46053b3ce88fe9dc4acf8e2ed81 /Build/source/utils/asymptote/entry.h
parent713bb91ad0467fb3b12acad03cae2fa105ed2caa (diff)
asy 2.02
git-svn-id: svn://tug.org/texlive/trunk@19378 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Build/source/utils/asymptote/entry.h')
-rw-r--r--Build/source/utils/asymptote/entry.h276
1 files changed, 194 insertions, 82 deletions
diff --git a/Build/source/utils/asymptote/entry.h b/Build/source/utils/asymptote/entry.h
index c9eeb2e54ff..c543a5df2c6 100644
--- a/Build/source/utils/asymptote/entry.h
+++ b/Build/source/utils/asymptote/entry.h
@@ -179,7 +179,7 @@ public:
tenv& source, varEntry *qualifier, coder &c);
};
-#ifdef NOHASH //{{{
+#if 0 //{{{
/* This version of venv is provided for compiling on systems which do not
* have some form of STL hash table. It will eventually be removed.
* See the hash version below for documentation on the functions.
@@ -214,99 +214,189 @@ public:
//}}}
#else
-// venv implemented with a hash table.
-class venv {
- struct key : public gc {
+// For speed reasons, many asserts are only tested when DEBUG_CACHE is set.
+#ifdef DEBUG_CACHE
+#define DEBUG_CACHE_ASSERT(x) assert(x)
+#else
+#define DEBUG_CACHE_ASSERT(x) (void)(x)
+#endif
+
+// The hash table which is at the core of the variable environment venv.
+class core_venv : public gc {
+
+public:
+ // The cells of the table
+ struct cell {
symbol name;
- bool special;
- union {
- ty *t;
- signature *sig;
- } u;
+ varEntry *ent;
- //key(key& k) : name(k.name), special(k.special), u(k.u) {}
+ bool empty() const {
+ return name == 0;
+ }
- key(symbol name, ty *t)
- : name(name), special(name.special())
- {
- if (special)
- u.t = t;
- else
- u.sig = t->getSignature();
+ bool isATomb() const {
+ DEBUG_CACHE_ASSERT(!empty());
+ return ent == 0;
}
- /* A fake key used for searching just based on a signature. */
- key(symbol name, signature *sig)
- : name(name), special(false)
- {
- assert(!name.special());
- u.sig = sig;
+ bool filled() const {
+ return !empty() and !isATomb();
}
- key(symbol name, varEntry *v)
- : name(name), special(name.special())
- {
- ty *t = v->getType();
- if (special)
- u.t = t;
- else
- u.sig = t->getSignature();
+ bool matches(symbol name, const ty *t) {
+ DEBUG_CACHE_ASSERT(name.special());
+ DEBUG_CACHE_ASSERT(t);
+
+ if (this->name != name)
+ return false;
+ if (!this->ent)
+ return false;
+ return equivalent(this->ent->getType(), t);
}
- };
- friend ostream& operator<< (ostream& out, const venv::key &k);
- struct value : public gc {
- varEntry *v;
- value(varEntry *v)
- : v(v) {}
- value() : v(0) {}
- };
+ bool matches(symbol name, const signature *sig) {
+ DEBUG_CACHE_ASSERT(!name.special());
- struct namehash {
- size_t operator()(const symbol name) const {
- return name.hash();
+ if (this->name != name)
+ return false;
+ if (!this->ent)
+ return false;
+ return equivalent(this->ent->getSignature(), sig);
}
- };
- struct nameeq {
- bool operator()(const symbol s, const symbol t) const {
- return s==t;
+
+ void storeNew(symbol name, varEntry *ent) {
+ DEBUG_CACHE_ASSERT(empty() || isATomb());
+
+ this->name = name;
+ this->ent = ent;
}
- };
- struct keyhash {
- size_t hashSig(signature *sig) const {
- return sig ? sig->hash() : 0;
+
+ varEntry *replaceWith(symbol name, varEntry *ent) {
+ this->name = name;
+
+ varEntry *old = this->ent;
+ this->ent = ent;
+ return old;
}
- size_t operator()(const key k) const {
- return k.name.hash() * 107 +
- (k.special ? k.u.t->hash() : hashSig(k.u.sig));
+
+ void remove() {
+ this->ent = 0;
}
};
- struct keyeq {
-#define TEST_COLLISION 0
-#if TEST_COLLISION
- bool base(const key k, const key l) const {
- return k.name==l.name &&
- (k.special ? equivalent(k.u.t, l.u.t) :
- equivalent(k.u.sig, l.u.sig));
+
+private:
+ size_t capacity;
+ size_t size;
+ size_t mask;
+ cell *table;
+
+ void initTable(size_t capacity);
+
+ void resize();
+
+ cell& cellByIndex(size_t i);
+
+ const cell& cellByIndex(size_t i) const;
+
+ varEntry *storeNew(cell& cell, symbol name, varEntry *ent);
+
+ varEntry *storeNonSpecialAfterTomb(size_t tombIndex,
+ symbol name, varEntry *ent);
+ varEntry *storeSpecialAfterTomb(size_t tombIndex,
+ symbol name, varEntry *ent);
+
+public:
+ core_venv(size_t capacity) {
+ initTable(capacity);
+ }
+
+ bool empty() const { return size == 0; }
+ void clear();
+
+ void confirm_size();
+
+ // Store an entry into the table. If this shadows a previous entry, the old
+ // entry is returned, otherwise 0 is returned.
+ varEntry *storeNonSpecial(symbol name, varEntry *ent);
+ varEntry *storeSpecial(symbol name, varEntry *ent);
+ varEntry *store(symbol name, varEntry *ent);
+
+ // Lookup an entry in the table.
+ varEntry *lookupNonSpecial(symbol name, const signature *sig);
+ varEntry *lookupSpecial(symbol name, const ty *t);
+ varEntry *lookup(symbol name, const ty *t);
+
+ // Remove an entry from the table.
+ void removeNonSpecial(symbol name, const signature *sig);
+ void removeSpecial(symbol name, const ty *t);
+ void remove(symbol name, const ty *t);
+
+ // Features for iterating over the entire table.
+ class const_iterator {
+ const core_venv& core;
+ size_t index;
+
+ public:
+ const_iterator(const core_venv& core, size_t index)
+ : core(core), index(index) {}
+
+ const cell& operator * () const {
+ return core.cellByIndex(index);
+ }
+ const cell* operator -> () const {
+ return &core.cellByIndex(index);
+ }
+
+ const_iterator& operator ++ () {
+ // Advance to the next filled cell, or stop at the end of the array.
+ do {
+ ++index;
+ } while (!(*this)->filled() && index < core.capacity);
+
+ DEBUG_CACHE_ASSERT((*this)->filled() || (*this) == core.end());
+
+ return *this;
+ }
+
+ friend bool operator == (const const_iterator& a, const const_iterator& b)
+ {
+ // For speed, we don't compare the hashtables.
+ return a.index == b.index;
+ }
+ friend bool operator != (const const_iterator& a, const const_iterator& b)
+ {
+ // For speed, we don't compare the hashtables.
+ return a.index != b.index;
}
- bool operator()(const key k, const key l) const;
-#else
- bool operator()(const key k, const key l) const;
-#endif
};
+ const_iterator begin() const {
+ size_t index = 0;
+ while (index < capacity && !cellByIndex(index).filled())
+ ++index;
+ return const_iterator(*this, index);
+ }
+ const_iterator end() const {
+ return const_iterator(*this, capacity);
+ }
+};
+
+
+// venv implemented with a hash table.
+class venv {
// A hash table used to quickly look up a variable once its name and type are
// known. Includes all scopes.
- typedef mem::unordered_map<key, value, keyhash, keyeq> keymap;
- keymap all;
+ core_venv core;
// Record of added variables in the order they were added.
struct addition {
- key k;
+ symbol name;
+ ty *t;
varEntry *shadowed;
- addition(key k, varEntry *shadowed) : k(k), shadowed(shadowed) {}
+ addition(symbol name, ty *t, varEntry *shadowed)
+ : name(name), t(t), shadowed(shadowed) {}
};
typedef mem::stack<addition> addstack;
addstack additions;
@@ -316,6 +406,18 @@ class venv {
typedef mem::stack<size_t> scopestack;
scopestack scopesizes;
+
+ struct namehash {
+ size_t operator()(const symbol name) const {
+ return name.hash();
+ }
+ };
+ struct nameeq {
+ bool operator()(const symbol s, const symbol t) const {
+ return s==t;
+ }
+ };
+
struct namevalue {
#ifdef CALLEE_SEARCH
size_t maxFormals;
@@ -335,37 +437,51 @@ class venv {
#endif
};
- // A hash table indexed solely on the name, storing for each name the
+ // A dictionary indexed solely on the name, storing for each name the
// current (possibly overloaded) type of the name.
+ // The hash table implementation is slightly faster than the std::map binary
+ // tree implementation, so we use it if we can.
+#ifdef NOHASH
+ typedef mem::map<symbol CONST, namevalue> namemap;
+#else
typedef mem::unordered_map<symbol, namevalue, namehash, nameeq> namemap;
+#endif
namemap names;
+
// A sanity check. For a given name, it checks that the type stored in the
// names hash table exactly matches with all of the entries of that name
// stored in the full hash table.
void checkName(symbol name);
- void listValues(symbol name, /*values &vals,*/ record *module);
+ void listValues(symbol name, record *module);
+
// Helper function for endScope.
void remove(const addition& a);
// These are roughly the size the hashtables will be after loading the
// builtin functions and plain module.
- static const size_t fileAllSize=2000;
- static const size_t namesAllSize=1000;
+ static const size_t fileCoreSize=1 << 13;
+ static const size_t fileNamesSize=1000;
// The number of scopes begun (but not yet ended) when the venv was empty.
size_t empty_scopes;
public:
- venv() : empty_scopes(0) {}
+ venv() :
+ core(1 << 2), empty_scopes(0) {}
// Most file level modules automatically import plain, so allocate hashtables
// big enough to hold it in advance.
struct file_env_tag {};
venv(file_env_tag)
- : all(fileAllSize), names(namesAllSize), empty_scopes(0) {}
+ : core(fileCoreSize),
+#ifndef NOHASH
+ names(fileNamesSize),
+#endif
+ empty_scopes(0) {}
+ // Add a new variable definition.
void enter(symbol name, varEntry *v);
// Add the entries in one environment to another, if qualifier is
@@ -379,14 +495,9 @@ public:
bool add(symbol src, symbol dest,
venv& source, varEntry *qualifier, coder &c);
- varEntry *lookByType(key k) {
- keymap::const_iterator p=all.find(k);
- return p!=all.end() ? p->second.v : 0;
- }
-
// Look for a function that exactly matches the type given.
varEntry *lookByType(symbol name, ty *t) {
- return lookByType(key(name, t));
+ return core.lookup(name, t);
}
// An optimization heuristic. Try to guess the signature of a variable and
@@ -403,13 +514,14 @@ public:
// avoid such ambiguities.
varEntry *lookBySignature(symbol name, signature *sig);
+ // Get the (possibly overloaded) type of all variables associated to a
+ // particular name.
ty *getType(symbol name);
void beginScope();
void endScope();
- // Adds the definitions of the top-level scope to the level underneath,
- // and then removes the top scope.
+ // Merges the top-level scope with the level immediately underneath it.
void collapseScope();
// Prints a list of the variables to the standard output.