summaryrefslogtreecommitdiff
path: root/Build/source/utils/asymptote/entry.cc
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.cc
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.cc')
-rw-r--r--Build/source/utils/asymptote/entry.cc441
1 files changed, 341 insertions, 100 deletions
diff --git a/Build/source/utils/asymptote/entry.cc b/Build/source/utils/asymptote/entry.cc
index 325438f48d3..d133571f136 100644
--- a/Build/source/utils/asymptote/entry.cc
+++ b/Build/source/utils/asymptote/entry.cc
@@ -10,10 +10,12 @@
#include <iostream>
#include <cmath>
+#include <cstring>
#include <utility>
#include "entry.h"
#include "coder.h"
+using std::memset;
using types::ty;
using types::signature;
using types::overloaded;
@@ -121,7 +123,7 @@ bool tenv::add(symbol src, symbol dest,
return false;
}
-#ifdef NOHASH //{{{
+#if 0 //{{{
/*NOHASH*/ void venv::add(venv& source, varEntry *qualifier, coder &c)
/*NOHASH*/ {
/*NOHASH*/ // Enter each distinct (unshadowed) name,type pair.
@@ -205,38 +207,283 @@ bool tenv::add(symbol src, symbol dest,
// }}}
#else
-ostream& operator<< (ostream& out, const venv::key &k) {
- if(k.special)
- k.u.t->printVar(out, k.name);
- else {
- out << k.name;
- if (k.u.sig)
- out << *k.u.sig;
+// To avoid writing qualifiers everywhere.
+typedef core_venv::cell cell;
+
+void core_venv::initTable(size_t capacity) {
+ // Assert that capacity is a power of two.
+ assert((capacity & (capacity-1)) == 0);
+
+ this->capacity = capacity;
+ size = 0;
+ mask = capacity - 1;
+ table = new (UseGC) cell[capacity];
+ memset(table, 0, sizeof(cell) * capacity);
+}
+
+void core_venv::clear() {
+ if (size != 0) {
+ memset(table, 0, sizeof(cell) * capacity);
+ size = 0;
}
- return out;
}
-#if TEST_COLLISION
-bool venv::keyeq::operator()(const key k, const key l) const {
- keyhash kh;
- if (kh(k)==kh(l)) {
- if (base(k,l))
- return true;
- else {
- cerr << "collision: " << endl;
- cerr << " " << k << " -> " << kh(k) << endl;
- cerr << " " << l << " -> " << kh(l) << endl;
+void core_venv::resize() {
+ size_t oldCapacity = capacity;
+ size_t oldSize = size;
+ cell *oldTable = table;
+
+ initTable(capacity * 4);
+
+ for (size_t i = 0; i < oldCapacity; ++i) {
+ cell& b = oldTable[i];
+ if (!b.empty() && !b.isATomb()) {
+ varEntry *old = store(b.name, b.ent);
+
+ // We should not be shadowing anything when reconstructing the table.
+ DEBUG_CACHE_ASSERT(old == 0);
}
}
- return false;
+
+ assert(size == oldSize);
+
+#if DEBUG_CACHE
+ confirm_size();
+
+ for (size_t i = 0; i < oldCapacity; ++i) {
+ cell& b = oldTable[i];
+ if (!b.empty() && !b.isATomb()) {
+ assert(lookup(b.name, b.ent->getType()) == b.ent);
+ }
+ }
+#endif
+
+ //cout << "resized from " << oldCapacity << " to " << capacity << endl;
}
-#else
-bool venv::keyeq::operator()(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));
+
+cell& core_venv::cellByIndex(size_t i) {
+ return table[i & mask];
+}
+
+const cell& core_venv::cellByIndex(size_t i) const {
+ return table[i & mask];
+}
+
+void core_venv::confirm_size() {
+ size_t sum = 0;
+ for (size_t i = 0; i < capacity; ++i) {
+ cell& b = table[i];
+ if (!b.empty() && !b.isATomb())
+ ++sum;
+ }
+ assert(sum == size);
+}
+
+varEntry *core_venv::storeNew(cell& cell, symbol name, varEntry *ent) {
+ // Store the value into the cell.
+ cell.storeNew(name, ent);
+
+ // We now have a new entry. Update the size.
+ ++size;
+
+ // Check if the hash table has grown too big and needs to be expanded.
+ if (2*size > capacity)
+ resize();
+
+ // Nothing is shadowed.
+ return 0;
+}
+
+
+varEntry *core_venv::storeNonSpecialAfterTomb(size_t tombIndex,
+ symbol name, varEntry *ent) {
+ DEBUG_CACHE_ASSERT(name.notSpecial());
+ DEBUG_CACHE_ASSERT(ent);
+ DEBUG_CACHE_ASSERT(ent->getType());
+
+ signature *sig = ent->getSignature();
+
+ for (size_t i = tombIndex+1; ; ++i)
+ {
+ cell& b = cellByIndex(i);
+
+ if (b.empty())
+ return storeNew(cellByIndex(tombIndex), name, ent);
+
+ if (b.matches(name, sig))
+ return b.replaceWith(name, ent);
+ }
+}
+
+varEntry *core_venv::storeSpecialAfterTomb(size_t tombIndex,
+ symbol name, varEntry *ent) {
+ DEBUG_CACHE_ASSERT(name.special());
+ DEBUG_CACHE_ASSERT(ent);
+ DEBUG_CACHE_ASSERT(ent->getType());
+
+ ty *t = ent->getType();
+
+ for (size_t i = tombIndex+1; ; ++i)
+ {
+ cell& b = cellByIndex(i);
+
+ if (b.empty())
+ return storeNew(cellByIndex(tombIndex), name, ent);
+
+ if (b.matches(name, t))
+ return b.replaceWith(name, ent);
+ }
+}
+
+size_t hashSig(const signature *sig) {
+ return sig ? sig->hash() : 0;
+}
+size_t nonSpecialHash(symbol name, const signature *sig) {
+ return name.hash() * 107 + hashSig(sig);
+}
+size_t nonSpecialHash(symbol name, const ty *t) {
+ DEBUG_CACHE_ASSERT(t);
+ return nonSpecialHash(name, t->getSignature());
+}
+size_t specialHash(symbol name, const ty *t) {
+ DEBUG_CACHE_ASSERT(t);
+ return name.hash() * 107 + t->hash();
+}
+
+varEntry *core_venv::storeNonSpecial(symbol name, varEntry *ent) {
+ DEBUG_CACHE_ASSERT(name.notSpecial());
+ DEBUG_CACHE_ASSERT(ent);
+ DEBUG_CACHE_ASSERT(ent->getType());
+
+ signature *sig = ent->getSignature();
+
+ for (size_t i = nonSpecialHash(name, sig); ; ++i)
+ {
+ cell& b = cellByIndex(i);
+
+ if (b.empty())
+ return storeNew(b, name, ent);
+
+ if (b.matches(name, sig))
+ return b.replaceWith(name, ent);
+
+ if (b.isATomb())
+ return storeNonSpecialAfterTomb(i, name, ent);
+ }
+}
+
+varEntry *core_venv::storeSpecial(symbol name, varEntry *ent) {
+ DEBUG_CACHE_ASSERT(name.special());
+ DEBUG_CACHE_ASSERT(ent);
+ DEBUG_CACHE_ASSERT(ent->getType());
+
+ ty *t = ent->getType();
+
+ for (size_t i = specialHash(name, t); ; ++i)
+ {
+ cell& b = cellByIndex(i);
+
+ if (b.empty())
+ return storeNew(b, name, ent);
+
+ if (b.matches(name, t))
+ return b.replaceWith(name, ent);
+
+ if (b.isATomb())
+ return storeSpecialAfterTomb(i, name, ent);
+ }
+}
+
+varEntry *core_venv::store(symbol name, varEntry *ent) {
+ DEBUG_CACHE_ASSERT(ent);
+ DEBUG_CACHE_ASSERT(ent->getType());
+
+ return name.special() ? storeSpecial(name, ent) :
+ storeNonSpecial(name, ent);
+}
+
+varEntry *core_venv::lookupSpecial(symbol name, const ty *t) {
+ DEBUG_CACHE_ASSERT(name.special());
+ DEBUG_CACHE_ASSERT(t);
+
+ for (size_t i = specialHash(name, t); ; ++i)
+ {
+ cell& b = cellByIndex(i);
+
+ if (b.matches(name, t))
+ return b.ent;
+
+ if (b.empty())
+ return 0;
+ }
+}
+
+varEntry *core_venv::lookupNonSpecial(symbol name, const signature *sig) {
+ DEBUG_CACHE_ASSERT(name.notSpecial());
+
+ for (size_t i = nonSpecialHash(name, sig); ; ++i)
+ {
+ cell& b = cellByIndex(i);
+
+ if (b.matches(name, sig))
+ return b.ent;
+
+ if (b.empty())
+ return 0;
+ }
+}
+
+varEntry *core_venv::lookup(symbol name, const ty *t) {
+ DEBUG_CACHE_ASSERT(t);
+
+ return name.special() ? lookupSpecial(name, t) :
+ lookupNonSpecial(name, t->getSignature());
+}
+
+void core_venv::removeNonSpecial(symbol name, const signature *sig) {
+ DEBUG_CACHE_ASSERT(name.notSpecial());
+
+ for (size_t i = nonSpecialHash(name, sig); ; ++i)
+ {
+ cell& b = cellByIndex(i);
+
+ if (b.matches(name, sig)) {
+ b.remove();
+ --size;
+ return;
+ }
+
+ DEBUG_CACHE_ASSERT(!b.empty());
+ }
}
-#endif
+
+void core_venv::removeSpecial(symbol name, const ty *t) {
+ DEBUG_CACHE_ASSERT(name.special());
+ DEBUG_CACHE_ASSERT(t);
+
+ for (size_t i = specialHash(name, t); ; ++i)
+ {
+ cell& b = cellByIndex(i);
+
+ if (b.matches(name, t)) {
+ b.remove();
+ --size;
+ return;
+ }
+
+ DEBUG_CACHE_ASSERT(!b.empty());
+ }
+}
+
+void core_venv::remove(symbol name, const ty *t) {
+ DEBUG_CACHE_ASSERT(t);
+
+ if (name.special())
+ removeSpecial(name, t);
+ else
+ removeNonSpecial(name, t->getSignature());
+}
+
#ifdef CALLEE_SEARCH
size_t numFormals(ty *t) {
@@ -247,7 +494,10 @@ size_t numFormals(ty *t) {
void venv::checkName(symbol name)
{
- // TODO: test maxFormals
+#if 0
+ // This size test is too slow, even for DEBUG_CACHE.
+ core.confirm_size();
+#endif
// Get the type, and make it overloaded if it is not (for uniformity).
overloaded o;
@@ -260,8 +510,11 @@ void venv::checkName(symbol name)
}
assert(t->isOverloaded());
+ size_t maxFormals = names[name].maxFormals;
+
size_t size = 0;
for (ty_iterator i = t->begin(); i != t->end(); ++i) {
+ assert(numFormals(*i) <= maxFormals);
varEntry *v = lookByType(name, *i);
assert(v);
assert(equivalent(v->getType(), *i));
@@ -269,11 +522,12 @@ void venv::checkName(symbol name)
}
size_t matches = 0;
- for (keymap::iterator p = all.begin(); p != all.end(); ++p) {
- if (p->first.name == name) {
+ core_venv::const_iterator end = core.end();
+ for (core_venv::const_iterator p = core.begin(); p != end; ++p) {
+ if (p->name == name) {
++matches;
- varEntry *v=p->second.v;
+ varEntry *v=p->ent;
assert(v);
assert(equivalent(t, v->getType()));
}
@@ -334,6 +588,8 @@ void venv::namevalue::replaceType(ty *new_t, ty *old_t) {
assert(t != 0);
RIGHTKIND(t);
#endif
+
+ // TODO: Test for equivalence.
if (t->isOverloaded()) {
for (ty_iterator i = t->begin(); i != t->end(); ++i) {
@@ -399,33 +655,34 @@ void venv::namevalue::popType()
}
void venv::remove(const addition& a) {
- CHECKNAME(a.k.name);
+ CHECKNAME(a.name);
- value &val=all[a.k];
+ if (a.shadowed) {
+ varEntry *popEnt = core.store(a.name, a.shadowed);
-#ifdef DEBUG_CACHE
- assert(val);
-#endif
+ DEBUG_CACHE_ASSERT(popEnt);
- if (a.shadowed) {
// Unshadow the previously shadowed varEntry.
- names[a.k.name].replaceType(a.shadowed->getType(), val.v->getType());
- val.v = a.shadowed;
- } else {
+ names[a.name].replaceType(a.shadowed->getType(), popEnt->getType());
+ }
+ else {
// Remove the (name,sig) key completely.
#if DEBUG_CACHE
- names[a.k.name].popType(val.v->getType());
+ varEntry *popEnt = core.lookup(a.name, a.t);
+ assert(popEnt);
+ names[a.name].popType(popEnt->getType());
#else
- names[a.k.name].popType();
+ names[a.name].popType();
#endif
- all.erase(a.k);
+
+ core.remove(a.name, a.t);
}
- CHECKNAME(a.k.name);
+ CHECKNAME(a.name);
}
void venv::beginScope() {
- if (all.empty()) {
+ if (core.empty()) {
assert(scopesizes.empty());
++empty_scopes;
} else {
@@ -437,7 +694,7 @@ void venv::endScope() {
if (scopesizes.empty()) {
// The corresponding beginScope happened when the venv was empty, so
// clear the hash tables to return to that state.
- all.clear();
+ core.clear();
names.clear();
assert(empty_scopes > 0);
@@ -461,6 +718,9 @@ void venv::collapseScope() {
assert(empty_scopes > 0);
--empty_scopes;
} else {
+ // As scopes are stored solely by the number of entries at the beginning
+ // of the scope, popping the top size will put all of the entries into the
+ // next scope down.
scopesizes.pop();
}
}
@@ -470,30 +730,24 @@ void venv::enter(symbol name, varEntry *v)
{
CHECKNAME(name);
- key k(name, v);
+ // Store the new variable. If it shadows an older variable, that varEntry
+ // will be returned.
+ varEntry *shadowed = core.store(name, v);
- value &slot=all[k];
- if (slot.v) {
+ ty *t = v->getType();
+
+ // Record the addition, so it can be undone during endScope.
+ if (!scopesizes.empty())
+ additions.push(addition(name, t, shadowed));
+
+ if (shadowed)
// The new value shadows an old value. They have the same signature, but
// possibly different return types. If necessary, update the type stored
// by name.
- names[name].replaceType(v->getType(), slot.v->getType());
-
- // Replace the old value, but store its now-shadowed varEntry.
- if (!scopesizes.empty())
- additions.push(addition(k, slot.v));
-
- slot.v = v;
-
- } else {
+ names[name].replaceType(t, shadowed->getType());
+ else
// Add to the names hash table.
- names[name].addType(v->getType());
-
- if (!scopesizes.empty())
- additions.push(addition(k, 0));
-
- slot.v=v;
- }
+ names[name].addType(t);
CHECKNAME(name);
}
@@ -502,58 +756,41 @@ void venv::enter(symbol name, varEntry *v)
varEntry *venv::lookBySignature(symbol name, signature *sig) {
#ifdef CALLEE_SEARCH
// Rest arguments are complicated and rare. Don't handle them here.
- if (sig->hasRest()) {
-#if 0
- if (lookByType(key(name, sig)))
- cout << "FAIL BY REST ARG" << endl;
- else
- cout << "FAIL BY REST ARG AND NO-MATCH" << endl;
-#endif
+ if (sig->hasRest())
return 0;
- }
// Likewise with the special operators.
- if (name.special()) {
- //cout << "FAIL BY SPECIAL" << endl;
+ if (name.special())
return 0;
- }
namevalue& nv = names[name];
// Avoid ambiguities with default parameters.
- if (nv.maxFormals != sig->getNumFormals()) {
-#if 0
- if (lookByType(key(name, sig)))
- cout << "FAIL BY NUMARGS" << endl;
- else
- cout << "FAIL BY NUMARGS AND NO-MATCH" << endl;
-#endif
+ if (nv.maxFormals != sig->getNumFormals())
return 0;
- }
// At this point, any function with an equivalent an signature will be equal
// to the result of the normal overloaded function resolution. We may
// safely return it.
- varEntry *result = lookByType(key(name, sig));
-#if 0
- if (!result) {
- cout << "FAIL BY NO-MATCH" << endl;
- }
-#endif
- return result;
+ return core.lookupNonSpecial(name, sig);
+
#else
- // The maxFormals field is necessary for this optimization.
+ // If the optimization is disabled, always return 0.
return 0;
#endif
}
void venv::add(venv& source, varEntry *qualifier, coder &c)
{
- // Enter each distinct (unshadowed) name,type pair.
- for(keymap::iterator p = source.all.begin(); p != source.all.end(); ++p) {
- varEntry *v=p->second.v;
- if (v->checkPerm(READ, c))
- enter(p->first.name, qualifyVarEntry(qualifier, v));
+ core_venv::const_iterator end = source.core.end();
+ for (core_venv::const_iterator p = source.core.begin(); p != end; ++p)
+ {
+ DEBUG_CACHE_ASSERT(p->filled());
+
+ varEntry *v=p->ent;
+ if (v->checkPerm(READ, c)) {
+ enter(p->name, qualifyVarEntry(qualifier, v));
+ }
}
}
@@ -561,11 +798,14 @@ bool venv::add(symbol src, symbol dest,
venv& source, varEntry *qualifier, coder &c)
{
ty *t=source.getType(src);
+
if (!t)
return false;
- else if (t->isOverloaded()) {
+
+ if (t->isOverloaded()) {
bool added=false;
- for (ty_iterator i = t->begin(); i != t->end(); ++i) {
+ for (ty_iterator i = t->begin(); i != t->end(); ++i)
+ {
varEntry *v=source.lookByType(src, *i);
if (v->checkPerm(READ, c)) {
enter(dest, qualifyVarEntry(qualifier, v));
@@ -573,7 +813,8 @@ bool venv::add(symbol src, symbol dest,
}
}
return added;
- } else {
+ }
+ else {
varEntry *v=source.lookByType(src, t);
if (v->checkPerm(READ, c)) {
enter(dest, qualifyVarEntry(qualifier, v));
@@ -629,6 +870,6 @@ void venv::completions(mem::list<symbol >& l, string start)
l.push_back(N->first);
}
-#endif
+#endif /* not NOHASH */
} // namespace trans