summaryrefslogtreecommitdiff
path: root/Build/source/utils/asymptote/symbol.cc
diff options
context:
space:
mode:
authorKarl Berry <karl@freefriends.org>2010-06-14 23:14:16 +0000
committerKarl Berry <karl@freefriends.org>2010-06-14 23:14:16 +0000
commitc2175edc7aa44ca0b526f008d473d6f8a8ac4933 (patch)
treed6c491676b413ad1922481f8c3fc7b64c3afc0a5 /Build/source/utils/asymptote/symbol.cc
parent5d08e9ff4fe5fc836d237ea08e82c82b27d558a2 (diff)
asy 1.98
git-svn-id: svn://tug.org/texlive/trunk@18982 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Build/source/utils/asymptote/symbol.cc')
-rw-r--r--Build/source/utils/asymptote/symbol.cc324
1 files changed, 314 insertions, 10 deletions
diff --git a/Build/source/utils/asymptote/symbol.cc b/Build/source/utils/asymptote/symbol.cc
index 94089223417..0c6e225af88 100644
--- a/Build/source/utils/asymptote/symbol.cc
+++ b/Build/source/utils/asymptote/symbol.cc
@@ -3,35 +3,339 @@
* Andy Hammerlindl 2002/06/18
*
* Creates symbols from strings so that multiple calls for a symbol of
- * the same string will return a pointer to the same object.
+ * the same string will return an identical object.
*****/
-#include <cstdio>
-#include "symbol.h"
+#include <cstring>
+#include <cstdlib>
+
+using std::strlen;
+#include "settings.h"
+#include "symbol.h"
namespace sym {
+const char USED = 1;
+const char SKIP = 2;
+
+struct symbolRecord {
+ // When a symbol is entered into the table, its hash is computed. If the
+ // corresponding entry in the table is full, this value is incremented until
+ // an empty slot is found. hashplus stores the end value. As entries are
+ // removed, each symbol has a unique hashplus value, even if there is a
+ // collision in the original hashing function.
+ uint hashplus;
+ unsigned char flag;
+ char *s;
+};
+
+// The table size must be a power of two so that (h % tableSize) can be
+// replaced by (h & tableMask). 1 << 15 was chosen based on the number of
+// unique symbols (roughly 4000) which occured in all of the base modules.
+const size_t SYMBOL_TABLE_BASE_CAPACITY = 1 << 15;
+symbolRecord baseSymbolTable[SYMBOL_TABLE_BASE_CAPACITY];
+
+symbolRecord *table = baseSymbolTable;
+size_t tableCapacity = SYMBOL_TABLE_BASE_CAPACITY;
+uint tableMask = 0;
+size_t tableSize = 0;
+
+symbolRecord &recordByHashplus(uint h)
+{
+ return table[h & tableMask];
+}
+
GCInit symbol::initialize;
+symbol symbol::nullsym;
+symbol symbol::initsym;
+symbol symbol::castsym;
+symbol symbol::ecastsym;
+
+const char *nullsymstr = "<nullsym>";
+
+void initTable() {
+ tableMask = (uint)(tableCapacity - 1);
+ tableSize = 0;
+
+ // Set every entry to empty. (Is this faster than memsetting the whole
+ // thing?)
+ for (size_t i = 0; i < tableCapacity; ++i)
+ table[i].flag = 0;
+
+ // The zeroth entry is reserved for the "null" symbol.
+ if (table == baseSymbolTable) {
+ table[0].flag = USED;
+ table[0].s = new char[strlen(nullsymstr) + 1];
+ strcpy(table[0].s, nullsymstr);
+ ++tableSize;
+
+ symbol::nullsym.hashplus = 0;
+
+ symbol::initsym = symbol::opTrans("init");
+ symbol::castsym = symbol::opTrans("cast");
+ symbol::ecastsym = symbol::opTrans("ecast");
+ }
+}
+
+// Hashing constants found experimentally to reduce collision (a little).
+const uint A = 25191, B = 16342, C = 1746, D = 18326;
+
+// Hash the string into an integer. Experimental testing has shown that
+// hashing only the first few letters seems to be faster than hashing deeper
+// into the string, even though this approach causes more hash collisions.
+uint hash(const char *s, size_t len)
+{
+ uint h = s[0];
+ if (len == 2)
+ return h;
+ h += A*s[1];
+ if (len == 3)
+ return h;
+ h += B*s[2];
+ if (len == 4)
+ return h;
+ h += C*s[3];
+ if (len == 5)
+ return h;
+ h += D*s[4];
+ return h+len;
+}
+
+/* Under normal circumstances, the initial table should be large enough for
+ * all of the symbols used and will never be resized. Just in case the
+ * program encounters a large number of distinct symbols, we implement
+ * resizing of the table.
+ */
+void resizeTable() {
+ symbolRecord *oldTable = table;
+ size_t oldSize = tableSize;
+ size_t oldCapacity = tableCapacity;
+
+ tableCapacity *= 4;
+ table = new symbolRecord[tableCapacity];
+ initTable();
+
+ // The null symbol is a special case.
+ table[0] = oldTable[0];
+ ++tableSize;
+
+#if 0
+ printf("old:\n");
+ for (size_t i = 0; i < oldCapacity; ++i) {
+ symbolRecord &r = oldTable[i];
+
+ if (r.flag != USED)
+ continue;
+
+ printf(" %u -> %s\n", r.hashplus, r.s);
+ }
+#endif
+
+ for (size_t i = 1; i < oldCapacity; ++i) {
+ symbolRecord &r = oldTable[i];
+
+ if (r.flag != USED)
+ continue;
+
+ // Entries that were skipped over when this symbol was entered into the
+ // old hash table may not appear in the same spot in the new hash table.
+ // Put "SKIP" entries in their place, so that the symbol will still be
+ // found.
+ for (uint h = hash(r.s, strlen(r.s)+1); h < r.hashplus; ++h) {
+ symbolRecord &skipr = recordByHashplus(h);
+ if (skipr.flag == 0)
+ skipr.flag = SKIP;
+ }
+
+ // Enter the symbol in its spot.
+ symbolRecord &newr = recordByHashplus(r.hashplus);
+ assert(newr.flag != USED);
+ newr.flag = USED;
+ newr.hashplus = r.hashplus;
+ newr.s = r.s;
+ ++tableSize;
+ }
+
+#if 0
+ printf("new:\n");
+ for (size_t i = 0; i < tableCapacity; ++i) {
+ symbolRecord &r = table[i];
+
+ if (r.flag != USED)
+ continue;
+
+ printf(" %u -> %s\n", r.hashplus, r.s);
+ }
+#endif
+
+ assert(tableSize == oldSize);
+
+ // Debugging resize.
+ for (size_t i = 1; i < oldCapacity; ++i) {
+ symbolRecord &r = oldTable[i];
+
+ if (r.flag != USED)
+ continue;
+
+ symbolRecord &newr = recordByHashplus(r.hashplus);
+ assert(newr.hashplus == r.hashplus);
+ assert(newr.flag != 0);
+ assert(newr.flag != SKIP);
+ assert(newr.flag == USED);
+ assert(newr.s = r.s);
+ if (strncmp(r.s, "gensym", 6) != 0)
+ assert(symbol::rawTrans(r.s, strlen(r.s)+1).hashplus == r.hashplus);
+ }
+
+#if 0
+ // Diagnostics.
+ uint empty=0, used=0, skip=0;
+ for (size_t i = 0; i < tableCapacity; ++i) {
+ symbolRecord &r = table[i];
+ if (r.flag == 0) ++empty;
+ else if (r.flag == USED) ++used;
+ else if (r.flag == SKIP) ++skip;
+ else assert("Unknown flag" == 0);
+ }
+
+ cout << "Resized symbol table. "
+ << "empty: " << empty
+ << "used: " << used
+ << "skip: " << skip
+ << endl;
+#endif
+}
+
+symbol symbolize(uint h) {
+ symbol s;
+ s.hashplus = h;
+ return s;
+}
+
+// Handles the insertion of a new symbol into a table the has been resized (or
+// needs resizing).
+symbol advancedInsert(const char *s, size_t len)
+{
+ if (2*tableSize >= tableCapacity)
+ resizeTable();
+
+ uint hashplus = hash(s, len);
+
+#if 1
+ assert(s != 0);
+ assert(len > 0);
+ assert(2*tableSize <= tableCapacity);
+#endif
+
+ // We know the symbol is not in the table. Just search for the first unused
+ // entry (either empty or a skip entry) and insert there.
+ for (;;) {
+ symbolRecord &r = recordByHashplus(hashplus);
+
+ if (r.flag != USED) {
+ r.flag = USED;
+ r.s = new char[len];
+ memcpy(r.s, s, len);
+ assert(r.s[len-1] == '\0');
+ r.hashplus = hashplus;
+
+ ++tableSize;
+ assert(2*tableSize <= tableCapacity);
+
+ return symbolize(hashplus);
+ }
+
+ ++hashplus;
+ }
+
+ assert("Unreachable code" == 0);
+ return symbol::nullsym;
+}
+
+symbol symbol::gensym(string s) {
+ // Gensym can be inserted as if it were a normal string not already in the
+ // table. advancedInsert handles this.
+ s = "gensym " + s;
+ return advancedInsert(s.c_str(), s.size() + 1);
+}
+
+symbol symbol::rawTrans(const char *s, size_t len)
+{
+ uint hashplus = sym::hash(s, len);
+
+#if 1
+ assert(s != 0);
+ assert(len > 0);
+ assert(2*tableSize <= tableCapacity);
+#endif
+
+ // Search through the table till we find the symbol already translated or
+ // an empty field.
+ for (;;) {
+ symbolRecord &r = recordByHashplus(hashplus);
+
+ // Translating pre-existing symbols is more common, so check for it first.
+ if (r.hashplus == hashplus &&
+ r.flag == USED &&
+ strncmp(r.s, s, len) == 0) {
+ return symbolize(hashplus);
+ }
+
+ // Then check for an empty entry, in which case the entry is added.
+ if (r.flag == 0) {
+ // Test if the table needs resizing before entering a new symbol, or if
+ // the table has already been resized. In either case, the symbol will
+ // be added to a resized table which may contain skip entries, and a
+ // more involved insertion routine is needed.
+ if (2*tableSize >= SYMBOL_TABLE_BASE_CAPACITY)
+ return advancedInsert(s, len);
+
+ r.flag = USED;
+ r.s = new char[len];
+ memcpy(r.s, s, len);
+ assert(r.s[len-1] == '\0');
+ r.hashplus = hashplus;
+
+ ++tableSize;
+ assert(2*tableSize <= tableCapacity);
+
+ return symbolize(hashplus);
+ }
+
+ // A case where a different symbol is in the spot, continue along the
+ // table.
+ ++hashplus;
+ }
+
+ assert("Unreachable code" == 0);
+ return symbol::nullsym;
+}
+
+symbol::operator string () const {
+ symbolRecord &r = recordByHashplus(this->hashplus);
+ return (string)r.s;
+}
-mem::map<CONST string,symbol> symbol::dict;
-symbol *symbol::initsym=symbol::specialTrans(string("operator init"));
-symbol *symbol::castsym=symbol::specialTrans(string("operator cast"));
-symbol *symbol::ecastsym=symbol::specialTrans(string("operator ecast"));
+ostream& operator<< (ostream& out, const symbol sym)
+{
+ symbolRecord &r = recordByHashplus(sym.hashplus);
+ return out << r.s;
+}
-} // namespace sym
+} // end namespace sym
#ifdef PRESYM
/* Define all of operator symbols SYM_PLUS, etc. */
#define OPSYMBOL(str, name) \
- sym::symbol *name = sym::symbol::opTrans(str)
+ sym::symbol name = sym::symbol::opTrans(str)
#include "opsymbols.h"
#undef OPSYMBOL
/* Define all of the symbols of the type SYM(name) in selected files. */
#define ADDSYMBOL(name) \
- sym::symbol *PRETRANSLATED_SYMBOL_##name = sym::symbol::literalTrans(#name)
+ sym::symbol PRETRANSLATED_SYMBOL_##name = sym::symbol::literalTrans(#name)
#include "allsymbols.h"
#undef ADDSYMBOL
#endif