From 0832956089516d32371060c98df4f8d0cbff2b0f Mon Sep 17 00:00:00 2001 From: Eelco Dolstra Date: Thu, 4 May 2006 12:21:08 +0000 Subject: * Use the new ATermMap. --- src/libexpr/eval.cc | 44 +++-- src/libexpr/get-drvs.cc | 42 ++--- src/libexpr/nixexpr.cc | 130 +-------------- src/libexpr/nixexpr.hh | 39 +---- src/libexpr/parser.cc | 6 +- src/libexpr/primops.cc | 33 ++-- src/libutil/Makefile.am | 3 +- src/libutil/aterm-map.cc | 312 +++++++++++++++++++++++++++++++++++ src/libutil/aterm-map.hh | 114 +++++++++++++ src/nix-env/main.cc | 2 +- table/aterm-map.cc | 417 ----------------------------------------------- 11 files changed, 500 insertions(+), 642 deletions(-) create mode 100644 src/libutil/aterm-map.cc create mode 100644 src/libutil/aterm-map.hh delete mode 100644 table/aterm-map.cc diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc index 6d2b20e53946..38f198fb86ca 100644 --- a/src/libexpr/eval.cc +++ b/src/libexpr/eval.cc @@ -4,7 +4,7 @@ EvalState::EvalState() - : normalForms(32768, 50) + : normalForms(32768), primOps(128) { nrEvaluated = nrCached = 0; @@ -17,7 +17,7 @@ EvalState::EvalState() void EvalState::addPrimOp(const string & name, unsigned int arity, PrimOp primOp) { - primOps.set(name, makePrimOpDef(arity, ATmakeBlob(0, (void *) primOp))); + primOps.set(toATerm(name), makePrimOpDef(arity, ATmakeBlob(0, (void *) primOp))); } @@ -25,7 +25,6 @@ void EvalState::addPrimOp(const string & name, static Expr substArgs(Expr body, ATermList formals, Expr arg) { ATermMap subs(ATgetLength(formals) * 2); - Expr undefined = makeUndefined(); /* ({x ? E1; y ? E2, z}: E3) {x = E4; z = E5;} @@ -44,7 +43,7 @@ static Expr substArgs(Expr body, ATermList formals, Expr arg) for (ATermIterator i(formals); i; ++i) { Expr name, def; if (matchNoDefFormal(*i, name)) - subs.set(name, undefined); + subs.set(name, makeUndefined()); else if (matchDefFormal(*i, name, def)) subs.set(name, def); else abort(); /* can't happen */ @@ -52,22 +51,21 @@ static Expr substArgs(Expr body, ATermList formals, Expr arg) /* Get the actual arguments, and check that they match with the formals. */ - ATermMap args; + ATermMap args(128); /* !!! fix */ queryAllAttrs(arg, args); - for (ATermIterator i(args.keys()); i; ++i) { - Expr key = *i; - Expr cur = subs.get(key); - if (!cur) + for (ATermMap::const_iterator i = args.begin(); i != args.end(); ++i) { + Expr cur = subs.get(i->key); + if (!subs.get(i->key)) throw Error(format("unexpected function argument `%1%'") - % aterm2String(key)); - subs.set(key, args.get(key)); + % aterm2String(i->key)); + subs.set(i->key, i->value); } /* Check that all arguments are defined. */ - for (ATermIterator i(subs.keys()); i; ++i) - if (subs.get(*i) == undefined) + for (ATermMap::const_iterator i = subs.begin(); i != subs.end(); ++i) + if (i->value == makeUndefined()) throw Error(format("required function argument `%1%' missing") - % aterm2String(*i)); + % aterm2String(i->key)); return substitute(Substitution(0, &subs), body); } @@ -85,7 +83,7 @@ ATerm expandRec(ATerm e, ATermList rbnds, ATermList nrbnds) Pos pos; /* Create the substitution list. */ - ATermMap subs; + ATermMap subs(ATgetLength(rbnds) + ATgetLength(nrbnds)); for (ATermIterator i(rbnds); i; ++i) { if (!matchBind(*i, name, e2, pos)) abort(); /* can't happen */ subs.set(name, makeSelect(e, name)); @@ -98,7 +96,7 @@ ATerm expandRec(ATerm e, ATermList rbnds, ATermList nrbnds) Substitution subs_(0, &subs); /* Create the non-recursive set. */ - ATermMap as; + ATermMap as(ATgetLength(rbnds) + ATgetLength(nrbnds)); for (ATermIterator i(rbnds); i; ++i) { if (!matchBind(*i, name, e2, pos)) abort(); /* can't happen */ as.set(name, makeAttrRHS(substitute(subs_, e2), pos)); @@ -118,7 +116,7 @@ static Expr updateAttrs(Expr e1, Expr e2) { /* Note: e1 and e2 should be in normal form. */ - ATermMap attrs; + ATermMap attrs(128); /* !!! */ queryAllAttrs(e1, attrs, true); queryAllAttrs(e2, attrs, true); @@ -217,12 +215,12 @@ string coerceToStringWithContext(EvalState & state, } if (matchAttrs(e, es)) { - ATermMap attrs; + ATermMap attrs(128); /* !!! */ queryAllAttrs(e, attrs, false); - Expr a = attrs.get("type"); + Expr a = attrs.get(toATerm("type")); if (a && evalString(state, a) == "derivation") { - a = attrs.get("outPath"); + a = attrs.get(toATerm("outPath")); if (!a) throw Error("output path missing from derivation"); context = ATinsert(context, e); return evalPath(state, a); @@ -342,7 +340,7 @@ Expr evalExpr2(EvalState & state, Expr e) else if (matchFunction1(e1, name, e4, pos)) { try { - ATermMap subs; + ATermMap subs(1); subs.set(name, e2); return evalExpr(state, substitute(Substitution(0, &subs), e4)); } catch (Error & e) { @@ -392,7 +390,7 @@ Expr evalExpr2(EvalState & state, Expr e) /* Withs. */ if (matchWith(e, e1, e2, pos)) { - ATermMap attrs; + ATermMap attrs(128); /* !!! */ try { e1 = evalExpr(state, e1); queryAllAttrs(e1, attrs); @@ -442,7 +440,7 @@ Expr evalExpr2(EvalState & state, Expr e) /* Attribute existence test (?). */ if (matchOpHasAttr(e, e1, name)) { - ATermMap attrs; + ATermMap attrs(128); /* !!! */ queryAllAttrs(evalExpr(state, e1), attrs); return makeBool(attrs.get(name) != 0); } diff --git a/src/libexpr/get-drvs.cc b/src/libexpr/get-drvs.cc index 78ccab7f32a7..19778c6abeda 100644 --- a/src/libexpr/get-drvs.cc +++ b/src/libexpr/get-drvs.cc @@ -5,7 +5,7 @@ string DrvInfo::queryDrvPath(EvalState & state) const { if (drvPath == "") { - Expr a = attrs->get("drvPath"); + Expr a = attrs->get(toATerm("drvPath")); (string &) drvPath = a ? evalPath(state, a) : ""; } return drvPath; @@ -15,7 +15,7 @@ string DrvInfo::queryDrvPath(EvalState & state) const string DrvInfo::queryOutPath(EvalState & state) const { if (outPath == "") { - Expr a = attrs->get("outPath"); + Expr a = attrs->get(toATerm("outPath")); if (!a) throw Error("output path missing"); (string &) outPath = evalPath(state, a); } @@ -27,16 +27,16 @@ MetaInfo DrvInfo::queryMetaInfo(EvalState & state) const { MetaInfo meta; - Expr a = attrs->get("meta"); + Expr a = attrs->get(toATerm("meta")); if (!a) return meta; /* fine, empty meta information */ - ATermMap attrs2; + ATermMap attrs2(16); /* !!! */ queryAllAttrs(evalExpr(state, a), attrs2); - for (ATermIterator i(attrs2.keys()); i; ++i) { - ATerm s = coerceToString(evalExpr(state, attrs2.get(*i))); + for (ATermMap::const_iterator i = attrs2.begin(); i != attrs2.end(); ++i) { + ATerm s = coerceToString(evalExpr(state, i->value)); if (s) - meta[aterm2String(*i)] = aterm2String(s); + meta[aterm2String(i->key)] = aterm2String(s); /* For future compatibility, ignore attribute values that are not strings. */ } @@ -66,10 +66,10 @@ static bool getDerivation(EvalState & state, Expr e, e = evalExpr(state, e); if (!matchAttrs(e, es)) return true; - shared_ptr attrs(new ATermMap()); + shared_ptr attrs(new ATermMap(32)); /* !!! */ queryAllAttrs(e, *attrs, false); - Expr a = attrs->get("type"); + Expr a = attrs->get(toATerm("type")); if (!a || evalString(state, a) != "derivation") return true; /* Remove spurious duplicates (e.g., an attribute set like @@ -79,11 +79,11 @@ static bool getDerivation(EvalState & state, Expr e, DrvInfo drv; - a = attrs->get("name"); + a = attrs->get(toATerm("name")); if (!a) throw badTerm("derivation name missing", e); drv.name = evalString(state, a); - a = attrs->get("system"); + a = attrs->get(toATerm("system")); if (!a) drv.system = "unknown"; else @@ -128,7 +128,7 @@ static void getDerivations(EvalState & state, Expr e, abort(); /* can't happen */ } getDerivations(state, - makeCall(e, makeAttrs(ATermMap())), + makeCall(e, makeAttrs(ATermMap(0))), drvs, doneExprs, attrPath); return; } @@ -169,30 +169,30 @@ static void getDerivations(EvalState & state, Expr e, if (matchAttrs(e, es)) { if (apType != apNone && apType != apAttr) throw attrError; - ATermMap drvMap; + ATermMap drvMap(ATgetLength(es)); queryAllAttrs(e, drvMap); if (apType == apNone) { - for (ATermIterator i(drvMap.keys()); i; ++i) { + for (ATermMap::const_iterator i = drvMap.begin(); i != drvMap.end(); ++i) { startNest(nest, lvlDebug, - format("evaluating attribute `%1%'") % aterm2String(*i)); - if (getDerivation(state, drvMap.get(*i), drvs, doneExprs)) { + format("evaluating attribute `%1%'") % aterm2String(i->key)); + if (getDerivation(state, i->value, drvs, doneExprs)) { /* If the value of this attribute is itself an attribute set, should we recurse into it? => Only if it has a `recurseForDerivations = true' attribute. */ ATermList es; - Expr e = evalExpr(state, drvMap.get(*i)); + Expr e = evalExpr(state, i->value); if (matchAttrs(e, es)) { - ATermMap attrs; + ATermMap attrs(ATgetLength(es)); queryAllAttrs(e, attrs, false); - if (attrs.get("recurseForDerivations") && - evalBool(state, attrs.get("recurseForDerivations"))) + Expr e2 = attrs.get(toATerm("recurseForDerivations")); + if (e2 && evalBool(state, e2)) getDerivations(state, e, drvs, doneExprs, attrPathRest); } } } } else { - Expr e2 = drvMap.get(attr); + Expr e2 = drvMap.get(toATerm(attr)); if (!e2) throw Error(format("attribute `%1%' in selection path not found") % attr); startNest(nest, lvlDebug, format("evaluating attribute `%1%'") % attr); diff --git a/src/libexpr/nixexpr.cc b/src/libexpr/nixexpr.cc index bfa7a9ed76e6..ebdef96d9ce5 100644 --- a/src/libexpr/nixexpr.cc +++ b/src/libexpr/nixexpr.cc @@ -6,124 +6,6 @@ #include "nixexpr-ast.cc" -ATermMap::ATermMap(unsigned int initialSize, unsigned int maxLoadPct) - : table(0) -{ - this->maxLoadPct = maxLoadPct; - table = ATtableCreate(initialSize, maxLoadPct); - if (!table) throw Error("cannot create ATerm table"); -} - - -ATermMap::ATermMap(const ATermMap & map) - : table(0) -{ - copy(map); -} - - -ATermMap::~ATermMap() -{ - free(); -} - - -ATermMap & ATermMap::operator = (const ATermMap & map) -{ - if (this == &map) return *this; - free(); - copy(map); - return *this; -} - - -void ATermMap::free() -{ - if (table) { - ATtableDestroy(table); - table = 0; - } -} - - -void ATermMap::copy(const ATermMap & map) -{ - ATermList keys = map.keys(); - - /* !!! We adjust for the maximum load pct by allocating twice as - much. Probably a bit too much. */ - maxLoadPct = map.maxLoadPct; - table = ATtableCreate(ATgetLength(keys) * 2, maxLoadPct); - if (!table) throw Error("cannot create ATerm table"); - - add(map, keys); -} - - -void ATermMap::set(ATerm key, ATerm value) -{ - return ATtablePut(table, key, value); -} - - -void ATermMap::set(const string & key, ATerm value) -{ - set(toATerm(key), value); -} - - -ATerm ATermMap::get(ATerm key) const -{ - return ATtableGet(table, key); -} - - -ATerm ATermMap::get(const string & key) const -{ - return get(toATerm(key)); -} - - -void ATermMap::remove(ATerm key) -{ - ATtableRemove(table, key); -} - - -void ATermMap::remove(const string & key) -{ - remove(toATerm(key)); -} - - -ATermList ATermMap::keys() const -{ - ATermList keys = ATtableKeys(table); - if (!keys) throw Error("cannot query aterm map keys"); - return keys; -} - - -void ATermMap::add(const ATermMap & map) -{ - ATermList keys = map.keys(); - add(map, keys); -} - - -void ATermMap::add(const ATermMap & map, ATermList & keys) -{ - for (ATermIterator i(keys); i; ++i) - set(*i, map.get(*i)); -} - - -void ATermMap::reset() -{ - ATtableReset(table); -} - - string showPos(ATerm pos) { ATerm path; @@ -211,12 +93,12 @@ Expr queryAttr(Expr e, const string & name, ATerm & pos) Expr makeAttrs(const ATermMap & attrs) { ATermList bnds = ATempty; - for (ATermIterator i(attrs.keys()); i; ++i) { + for (ATermMap::const_iterator i = attrs.begin(); i != attrs.end(); ++i) { Expr e; ATerm pos; - if (!matchAttrRHS(attrs.get(*i), e, pos)) + if (!matchAttrRHS(i->value, e, pos)) abort(); /* can't happen */ - bnds = ATinsert(bnds, makeBind(*i, e, pos)); + bnds = ATinsert(bnds, makeBind(i->key, e, pos)); } return makeAttrs(bnds); } @@ -250,7 +132,7 @@ Expr substitute(const Substitution & subs, Expr e) ATermList formals; ATerm body, def; if (matchFunction(e, formals, body, pos)) { - ATermMap map; + ATermMap map(ATgetLength(formals)); for (ATermIterator i(formals); i; ++i) { if (!matchNoDefFormal(*i, name) && !matchDefFormal(*i, name, def)) @@ -264,7 +146,7 @@ Expr substitute(const Substitution & subs, Expr e) } if (matchFunction1(e, name, body, pos)) { - ATermMap map; + ATermMap map(1); map.set(name, makeRemoved()); return makeFunction1(name, substitute(Substitution(&subs, &map), body), pos); } @@ -272,7 +154,7 @@ Expr substitute(const Substitution & subs, Expr e) /* Idem for a mutually recursive attribute set. */ ATermList rbnds, nrbnds; if (matchRec(e, rbnds, nrbnds)) { - ATermMap map; + ATermMap map(ATgetLength(rbnds) + ATgetLength(nrbnds)); for (ATermIterator i(rbnds); i; ++i) if (matchBind(*i, name, e2, pos)) map.set(name, makeRemoved()); else abort(); /* can't happen */ diff --git a/src/libexpr/nixexpr.hh b/src/libexpr/nixexpr.hh index 298a9f0b949b..e3c7ee60745c 100644 --- a/src/libexpr/nixexpr.hh +++ b/src/libexpr/nixexpr.hh @@ -5,6 +5,7 @@ #include +#include "aterm-map.hh" #include "util.hh" @@ -16,44 +17,6 @@ typedef ATerm Expr; typedef ATerm Pos; -/* Mappings from ATerms to ATerms. This is just a wrapper around - ATerm tables. */ -class ATermMap -{ -private: - unsigned int maxLoadPct; - ATermTable table; - -public: - ATermMap(unsigned int initialSize = 64, unsigned int maxLoadPct = 75); - ATermMap(const ATermMap & map); - ~ATermMap(); - - ATermMap & operator = (const ATermMap & map); - - void set(ATerm key, ATerm value); - void set(const string & key, ATerm value); - - ATerm get(ATerm key) const; - ATerm get(const string & key) const; - - void remove(ATerm key); - void remove(const string & key); - - ATermList keys() const; - - void add(const ATermMap & map); - - void reset(); - -private: - void add(const ATermMap & map, ATermList & keys); - - void free(); - void copy(const ATermMap & map); -}; - - /* A STL vector of ATerms. Should be used with great care since it's stored on the heap, and the elements are therefore not roots to the ATerm garbage collector. */ diff --git a/src/libexpr/parser.cc b/src/libexpr/parser.cc index 2ca1cab4afcb..241a437345fc 100644 --- a/src/libexpr/parser.cc +++ b/src/libexpr/parser.cc @@ -115,7 +115,7 @@ static void checkAttrSets(ATerm e) ATermList formals; ATerm body, pos; if (matchFunction(e, formals, body, pos)) { - ATermMap names; + ATermMap names(ATgetLength(formals)); for (ATermIterator i(formals); i; ++i) { ATerm name; Expr deflt; @@ -131,13 +131,13 @@ static void checkAttrSets(ATerm e) ATermList bnds; if (matchAttrs(e, bnds)) { - ATermMap names; + ATermMap names(ATgetLength(bnds)); checkAttrs(names, bnds); } ATermList rbnds, nrbnds; if (matchRec(e, rbnds, nrbnds)) { - ATermMap names; + ATermMap names(ATgetLength(rbnds) + ATgetLength(nrbnds)); checkAttrs(names, rbnds); checkAttrs(names, nrbnds); } diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc index 8935b147e559..262e3bec542b 100644 --- a/src/libexpr/primops.cc +++ b/src/libexpr/primops.cc @@ -234,11 +234,11 @@ static Expr primDerivationStrict(EvalState & state, const ATermVector & args) { startNest(nest, lvlVomit, "evaluating derivation"); - ATermMap attrs; + ATermMap attrs(128); /* !!! */ queryAllAttrs(evalExpr(state, args[0]), attrs, true); /* Figure out the name already (for stack backtraces). */ - Expr eDrvName = attrs.get("name"); + Expr eDrvName = attrs.get(toATerm("name")); if (!eDrvName) throw Error("required attribute `name' missing"); ATerm posDrvName; @@ -252,11 +252,11 @@ static Expr primDerivationStrict(EvalState & state, const ATermVector & args) string outputHashAlgo; bool outputHashRecursive = false; - for (ATermIterator i(attrs.keys()); i; ++i) { - string key = aterm2String(*i); + for (ATermMap::const_iterator i = attrs.begin(); i != attrs.end(); ++i) { + string key = aterm2String(i->key); ATerm value; Expr pos; - ATerm rhs = attrs.get(key); + ATerm rhs = i->value; if (!matchAttrRHS(rhs, value, pos)) abort(); startNest(nest, lvlVomit, format("processing attribute `%1%'") % key); @@ -363,9 +363,11 @@ static Expr primDerivationStrict(EvalState & state, const ATermVector & args) state.drvHashes[drvPath] = hashDerivationModulo(state, drv); /* !!! assumes a single output */ - ATermMap outAttrs; - outAttrs.set("outPath", makeAttrRHS(makePath(toATerm(outPath)), makeNoPos())); - outAttrs.set("drvPath", makeAttrRHS(makePath(toATerm(drvPath)), makeNoPos())); + ATermMap outAttrs(2); + outAttrs.set(toATerm("outPath"), + makeAttrRHS(makePath(toATerm(outPath)), makeNoPos())); + outAttrs.set(toATerm("drvPath"), + makeAttrRHS(makePath(toATerm(drvPath)), makeNoPos())); return makeAttrs(outAttrs); } @@ -374,15 +376,18 @@ static Expr primDerivationStrict(EvalState & state, const ATermVector & args) static Expr primDerivationLazy(EvalState & state, const ATermVector & args) { Expr eAttrs = evalExpr(state, args[0]); - ATermMap attrs; + ATermMap attrs(128); /* !!! */ queryAllAttrs(eAttrs, attrs, true); - attrs.set("type", makeAttrRHS(makeStr(toATerm("derivation")), makeNoPos())); + attrs.set(toATerm("type"), + makeAttrRHS(makeStr(toATerm("derivation")), makeNoPos())); Expr drvStrict = makeCall(makeVar(toATerm("derivation!")), eAttrs); - attrs.set("outPath", makeAttrRHS(makeSelect(drvStrict, toATerm("outPath")), makeNoPos())); - attrs.set("drvPath", makeAttrRHS(makeSelect(drvStrict, toATerm("drvPath")), makeNoPos())); + attrs.set(toATerm("outPath"), + makeAttrRHS(makeSelect(drvStrict, toATerm("outPath")), makeNoPos())); + attrs.set(toATerm("drvPath"), + makeAttrRHS(makeSelect(drvStrict, toATerm("drvPath")), makeNoPos())); return makeAttrs(attrs); } @@ -627,14 +632,14 @@ static Expr primCurrentTime(EvalState & state, const ATermVector & args) static Expr primRemoveAttrs(EvalState & state, const ATermVector & args) { - ATermMap attrs; + ATermMap attrs(128); /* !!! */ queryAllAttrs(evalExpr(state, args[0]), attrs, true); ATermList list = evalList(state, args[1]); for (ATermIterator i(list); i; ++i) /* It's not an error for *i not to exist. */ - attrs.remove(evalString(state, *i)); + attrs.remove(toATerm(evalString(state, *i))); return makeAttrs(attrs); } diff --git a/src/libutil/Makefile.am b/src/libutil/Makefile.am index 9d71b66e6287..e10477deb706 100644 --- a/src/libutil/Makefile.am +++ b/src/libutil/Makefile.am @@ -1,7 +1,8 @@ lib_LTLIBRARIES = libutil.la libutil_la_SOURCES = util.cc util.hh hash.cc hash.hh \ - archive.cc archive.hh aterm.cc aterm.hh + archive.cc archive.hh aterm.cc aterm.hh \ + aterm-map.cc aterm-map.hh if !HAVE_OPENSSL libutil_la_SOURCES += \ diff --git a/src/libutil/aterm-map.cc b/src/libutil/aterm-map.cc new file mode 100644 index 000000000000..e0cfefa2d5f4 --- /dev/null +++ b/src/libutil/aterm-map.cc @@ -0,0 +1,312 @@ +#include "aterm-map.hh" + +#include +#include + + +static const unsigned int maxLoadFactor = /* 1 / */ 3; +static unsigned int nrResizes = 0; +static unsigned int sizeTotalAlloc = 0; +static unsigned int sizeCurAlloc = 0; +static unsigned int sizeMaxAlloc = 0; + + +ATermMap::ATermMap(unsigned int expectedCount) +{ + init(expectedCount); +} + + +ATermMap::ATermMap(const ATermMap & map) +{ + init(map.maxCount); + copy(map.hashTable, map.capacity); +} + + +ATermMap & ATermMap::operator = (const ATermMap & map) +{ + if (this == &map) return *this; + free(); + init(map.maxCount); + copy(map.hashTable, map.capacity); + return *this; +} + + +ATermMap::~ATermMap() +{ + free(); +} + + +void ATermMap::init(unsigned int expectedCount) +{ + assert(sizeof(ATerm) * 2 == sizeof(KeyValue)); + capacity = 0; + count = 0; + maxCount = 0; + hashTable = 0; + resizeTable(expectedCount); +} + + +void ATermMap::free() +{ + if (hashTable) { + ATunprotectArray((ATerm *) hashTable); + ::free(hashTable); + sizeCurAlloc -= sizeof(KeyValue) * capacity; + hashTable = 0; + } +} + + +static unsigned int roundToPowerOf2(unsigned int x) +{ + x--; + x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16; + x++; + return x; +} + + +void ATermMap::resizeTable(unsigned int expectedCount) +{ + if (expectedCount == 0) expectedCount = 1; +// cout << maxCount << " -> " << expectedCount << endl; +// cout << maxCount << " " << size << endl; +// cout << (double) size / maxCount << endl; + + unsigned int oldCapacity = capacity; + KeyValue * oldHashTable = hashTable; + + maxCount = expectedCount; + capacity = roundToPowerOf2(maxCount * maxLoadFactor); + hashTable = (KeyValue *) calloc(sizeof(KeyValue), capacity); + sizeTotalAlloc += sizeof(KeyValue) * capacity; + sizeCurAlloc += sizeof(KeyValue) * capacity; + if (sizeCurAlloc > sizeMaxAlloc) sizeMaxAlloc = sizeCurAlloc; + ATprotectArray((ATerm *) hashTable, capacity * 2); + +// cout << capacity << endl; + + /* Re-hash the elements in the old table. */ + if (oldCapacity != 0) { + count = 0; + copy(oldHashTable, oldCapacity); + ATunprotectArray((ATerm *) oldHashTable); + ::free(oldHashTable); + sizeCurAlloc -= sizeof(KeyValue) * oldCapacity; + nrResizes++; + } +} + + +void ATermMap::copy(KeyValue * elements, unsigned int capacity) +{ + for (unsigned int i = 0; i < capacity; ++i) + if (elements[i].value) /* i.e., non-empty, non-deleted element */ + set(elements[i].key, elements[i].value); +} + + +static const unsigned int shift = 16; +static const unsigned int knuth = (unsigned int) (0.6180339887 * (1 << shift)); + + +unsigned int ATermMap::hash1(ATerm key) const +{ + /* Don't care about the least significant bits of the ATerm + pointer since they're always 0. */ + unsigned int key2 = ((unsigned int) key) >> 2; + + /* Approximately equal to: + double d = key2 * 0.6180339887; + unsigned int h = (int) (capacity * (d - floor(d))); + */ + + unsigned int h = (capacity * ((key2 * knuth) & ((1 << shift) - 1))) >> shift; + + return h; +} + + +unsigned int ATermMap::hash2(ATerm key) const +{ + unsigned int key2 = ((unsigned int) key) >> 2; + /* Note: the result must be relatively prime to `capacity' (which + is a power of 2), so we make sure that the result is always + odd. */ + unsigned int h = ((key2 * 134217689) & (capacity - 1)) | 1; + return h; +} + + +static unsigned int nrItemsSet = 0; +static unsigned int nrSetProbes = 0; + + +void ATermMap::set(ATerm key, ATerm value) +{ + if (count == maxCount) resizeTable(capacity * 2 / maxLoadFactor); + + nrItemsSet++; + for (unsigned int i = 0, h = hash1(key); i < capacity; + ++i, h = (h + hash2(key)) & (capacity - 1)) + { + // assert(h < capacity); + nrSetProbes++; + /* Note: to see whether a slot is free, we check + hashTable[h].value, not hashTable[h].key, since we use + value == 0 to mark deleted slots. */ + if (hashTable[h].value == 0 || hashTable[h].key == key) { + if (hashTable[h].value == 0) count++; + hashTable[h].key = key; + hashTable[h].value = value; + return; + } + } + + abort(); +} + + +static unsigned int nrItemsGet = 0; +static unsigned int nrGetProbes = 0; + + +ATerm ATermMap::get(ATerm key) const +{ + nrItemsGet++; + for (unsigned int i = 0, h = hash1(key); i < capacity; + ++i, h = (h + hash2(key)) & (capacity - 1)) + { + nrGetProbes++; + if (hashTable[h].key == 0) return 0; + if (hashTable[h].key == key) return hashTable[h].value; + } + return 0; +} + + +void ATermMap::remove(ATerm key) +{ + for (unsigned int i = 0, h = hash1(key); i < capacity; + ++i, h = (h + hash2(key)) & (capacity - 1)) + { + if (hashTable[h].key == 0) return; + if (hashTable[h].key == key) { + if (hashTable[h].value != 0) { + hashTable[h].value = 0; + count--; + } + return; + } + } +} + + +unsigned int ATermMap::size() +{ + return count; /* STL nomenclature */ +} + + +#if 0 +int main(int argc, char * * argv) +{ + ATerm bottomOfStack; + ATinit(argc, argv, &bottomOfStack); + + /* Make test terms. */ + int nrTestTerms = 100000; + ATerm testTerms[nrTestTerms]; + + for (int i = 0; i < nrTestTerms; ++i) { + char name[10]; + sprintf(name, "%d", (int) random() % 37); + + int arity = i == 0 ? 0 : (random() % 37); + ATerm kids[arity]; + for (int j = 0; j < arity; ++j) + kids[j] = testTerms[random() % i]; + + testTerms[i] = (ATerm) ATmakeApplArray(ATmakeAFun(name, arity, ATfalse), kids); +// ATwriteToSharedTextFile(testTerms[i], stdout); +// printf("\n"); + } + + + cout << "testing...\n"; + + + #define someTerm() (testTerms[(int) random() % nrTestTerms]) + + + for (int test = 0; test < 100000; ++test) { + //cerr << test << endl; + unsigned int n = 300; + ATermMap map(300); + ATerm keys[n], values[n]; + for (unsigned int i = 0; i < n; ++i) { + keys[i] = someTerm(); + values[i] = someTerm(); + map.set(keys[i], values[i]); + //cerr << "INSERT: " << keys[i] << " " << values[i] << endl; + } + + unsigned int size = map.size(); + assert(size <= n); + values[n - 1] = 0; + map.remove(keys[n - 1]); + assert(map.size() == size - 1); + + unsigned int checksum; + unsigned int count = 0; + for (ATermMap::const_iterator i = map.begin(); i != map.end(); ++i, ++count) { + assert(i->key); + assert(i->value); + checksum += (unsigned int) (*i).key; + checksum += (unsigned int) (*i).value; + // cout << (*i).key << " " << (*i).value << endl; + } + assert(count == size - 1); + + for (unsigned int i = 0; i < n; ++i) { + for (unsigned int j = i + 1; j < n; ++j) + if (keys[i] == keys[j]) goto x; + if (map.get(keys[i]) != values[i]) { + cerr << "MISMATCH: " << keys[i] << " " << values[i] << " " << map.get(keys[i]) << " " << i << endl; + abort(); + } + if (values[i] != 0) { + checksum -= (unsigned int) keys[i]; + checksum -= (unsigned int) values[i]; + } + x: ; + } + + assert(checksum == 0); + + for (unsigned int i = 0; i < 100; ++i) + map.get(someTerm()); + + } + + cout << "RESIZES: " << nrResizes << " " + << sizeTotalAlloc << " " + << sizeCurAlloc << " " + << sizeMaxAlloc << endl; + + cout << "SET: " + << nrItemsSet << " " + << nrSetProbes << " " + << (double) nrSetProbes / nrItemsSet << endl; + + cout << "GET: " + << nrItemsGet << " " + << nrGetProbes << " " + << (double) nrGetProbes / nrItemsGet << endl; +} +#endif diff --git a/src/libutil/aterm-map.hh b/src/libutil/aterm-map.hh new file mode 100644 index 000000000000..d7aed2ca21ac --- /dev/null +++ b/src/libutil/aterm-map.hh @@ -0,0 +1,114 @@ +#ifndef __ATERM_MAP_H +#define __ATERM_MAP_H + +#include +#include + +using namespace std; + + +class ATermMap +{ +public: + + struct KeyValue + { + ATerm key; + ATerm value; + }; + +private: + + /* Hash table for the map. We use open addressing, i.e., all + key/value pairs are stored directly in the table, and there are + no pointers. Collisions are resolved through probing. */ + KeyValue * hashTable; + + /* Current size of the hash table. */ + unsigned int capacity; + + /* Number of elements in the hash table. */ + unsigned int count; + + /* Maximum number of elements in the hash table. If `count' + exceeds this number, the hash table is expanded. */ + unsigned int maxCount; + +public: + + /* Create a map. `expectedCount' is the number of elements the + map is expected to hold. */ + ATermMap(unsigned int expectedCount); + + ATermMap(const ATermMap & map); + + ~ATermMap(); + + ATermMap & operator = (const ATermMap & map); + + void set(ATerm key, ATerm value); + + ATerm get(ATerm key) const; + + void remove(ATerm key); + + unsigned int size(); + + struct const_iterator + { + const ATermMap & map; + unsigned int pos; + const_iterator(const ATermMap & map, int pos) : map(map) + { + this->pos = pos; + } + bool operator !=(const const_iterator & i) + { + return pos != i.pos; + } + void operator ++() + { + if (pos == map.capacity) return; + do { ++pos; + } while (pos < map.capacity && map.hashTable[pos].value == 0); + } + const KeyValue & operator *() + { + assert(pos < map.capacity); + return map.hashTable[pos]; + } + const KeyValue * operator ->() + { + assert(pos < map.capacity); + return &map.hashTable[pos]; + } + }; + + const_iterator begin() const + { + unsigned int i = 0; + while (i < capacity && hashTable[i].value == 0) ++i; + return const_iterator(*this, i); + } + + const_iterator end() const + { + return const_iterator(*this, capacity); + } + +private: + + void init(unsigned int expectedCount); + + void free(); + + void resizeTable(unsigned int expectedCount); + + void copy(KeyValue * elements, unsigned int capacity); + + inline unsigned int hash1(ATerm key) const; + inline unsigned int hash2(ATerm key) const; +}; + + +#endif /* !__ATERM_MAP_H */ diff --git a/src/nix-env/main.cc b/src/nix-env/main.cc index ad3c1b5ce329..e7f25c5ba2f1 100644 --- a/src/nix-env/main.cc +++ b/src/nix-env/main.cc @@ -348,7 +348,7 @@ static void queryInstSources(EvalState & state, assertStorePath(*i); DrvInfo elem; - elem.attrs = shared_ptr(new ATermMap()); /* ugh... */ + elem.attrs = shared_ptr(new ATermMap(0)); /* ugh... */ string name = baseNameOf(*i); unsigned int dash = name.find('-'); if (dash != string::npos) diff --git a/table/aterm-map.cc b/table/aterm-map.cc deleted file mode 100644 index b619ead3668a..000000000000 --- a/table/aterm-map.cc +++ /dev/null @@ -1,417 +0,0 @@ -#include -#include -#include -#include -#include - -using namespace std; - - -class ATermMap -{ -public: - - struct KeyValue - { - ATerm key; - ATerm value; - }; - -private: - - /* Hash table for the map. We use open addressing, i.e., all - key/value pairs are stored directly in the table, and there are - no pointers. Collisions are resolved through probing. */ - KeyValue * hashTable; - - /* Current size of the hash table. */ - unsigned int capacity; - - /* Number of elements in the hash table. */ - unsigned int count; - - /* Maximum number of elements in the hash table. If `count' - exceeds this number, the hash table is expanded. */ - unsigned int maxCount; - -public: - - /* Create a map. `expectedCount' is the number of elements the - map is expected to hold. */ - ATermMap(unsigned int expectedCount); - - ATermMap(const ATermMap & map); - - ~ATermMap(); - - ATermMap & operator = (const ATermMap & map); - - void set(ATerm key, ATerm value); - - ATerm get(ATerm key) const; - - void remove(ATerm key); - - unsigned int size(); - - struct const_iterator - { - const ATermMap & map; - unsigned int pos; - const_iterator(const ATermMap & map, int pos) : map(map) - { - this->pos = pos; - } - bool operator !=(const const_iterator & i) - { - return pos != i.pos; - } - void operator ++() - { - if (pos == map.capacity) return; - do { ++pos; - } while (pos < map.capacity && map.hashTable[pos].value == 0); - } - const KeyValue & operator *() - { - assert(pos < map.capacity); - return map.hashTable[pos]; - } - const KeyValue * operator ->() - { - assert(pos < map.capacity); - return &map.hashTable[pos]; - } - }; - - const_iterator begin() const - { - unsigned int i = 0; - while (i < capacity && hashTable[i].value == 0) ++i; - return const_iterator(*this, i); - } - - const_iterator end() const - { - return const_iterator(*this, capacity); - } - -private: - - void init(unsigned int expectedCount); - - void free(); - - void resizeTable(unsigned int expectedCount); - - void copy(KeyValue * elements, unsigned int capacity); - - inline unsigned int hash1(ATerm key) const; - inline unsigned int hash2(ATerm key) const; -}; - - -static const unsigned int maxLoadFactor = /* 1 / */ 3; -static unsigned int nrResizes = 0; -static unsigned int sizeTotalAlloc = 0; -static unsigned int sizeCurAlloc = 0; -static unsigned int sizeMaxAlloc = 0; - - -ATermMap::ATermMap(unsigned int expectedCount) -{ - init(expectedCount * 10 / 9); /* slight adjustment */ -} - - -ATermMap::ATermMap(const ATermMap & map) -{ - init(map.maxCount); - copy(map.hashTable, map.capacity); -} - - -ATermMap & ATermMap::operator = (const ATermMap & map) -{ - if (this == &map) return *this; - free(); - init(map.maxCount); - copy(map.hashTable, map.capacity); - return *this; -} - - -ATermMap::~ATermMap() -{ - free(); -} - - -void ATermMap::init(unsigned int expectedCount) -{ - assert(sizeof(ATerm) * 2 == sizeof(KeyValue)); - capacity = 0; - count = 0; - maxCount = 0; - hashTable = 0; - resizeTable(expectedCount); -} - - -void ATermMap::free() -{ - if (hashTable) { - ATunprotectArray((ATerm *) hashTable); - ::free(hashTable); - sizeCurAlloc -= sizeof(KeyValue) * capacity; - hashTable = 0; - } -} - - -static unsigned int roundToPowerOf2(unsigned int x) -{ - x--; - x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16; - x++; - return x; -} - - -void ATermMap::resizeTable(unsigned int expectedCount) -{ - if (expectedCount == 0) expectedCount = 1; -// cout << maxCount << " -> " << expectedCount << endl; -// cout << maxCount << " " << size << endl; -// cout << (double) size / maxCount << endl; - - unsigned int oldCapacity = capacity; - KeyValue * oldHashTable = hashTable; - - maxCount = expectedCount; - capacity = roundToPowerOf2(maxCount * maxLoadFactor); - hashTable = (KeyValue *) calloc(sizeof(KeyValue), capacity); - sizeTotalAlloc += sizeof(KeyValue) * capacity; - sizeCurAlloc += sizeof(KeyValue) * capacity; - if (sizeCurAlloc > sizeMaxAlloc) sizeMaxAlloc = sizeCurAlloc; - ATprotectArray((ATerm *) hashTable, capacity * 2); - -// cout << capacity << endl; - - /* Re-hash the elements in the old table. */ - if (oldCapacity != 0) { - count = 0; - copy(oldHashTable, oldCapacity); - ATunprotectArray((ATerm *) oldHashTable); - ::free(oldHashTable); - sizeCurAlloc -= sizeof(KeyValue) * oldCapacity; - nrResizes++; - } -} - - -void ATermMap::copy(KeyValue * elements, unsigned int capacity) -{ - for (unsigned int i = 0; i < capacity; ++i) - if (elements[i].value) /* i.e., non-empty, non-deleted element */ - set(elements[i].key, elements[i].value); -} - - -static const unsigned int shift = 16; -static const unsigned int knuth = (unsigned int) (0.6180339887 * (1 << shift)); - - -unsigned int ATermMap::hash1(ATerm key) const -{ - /* Don't care about the least significant bits of the ATerm - pointer since they're always 0. */ - unsigned int key2 = ((unsigned int) key) >> 2; - - /* Approximately equal to: - double d = key2 * 0.6180339887; - unsigned int h = (int) (capacity * (d - floor(d))); - */ - - unsigned int h = (capacity * ((key2 * knuth) & ((1 << shift) - 1))) >> shift; - - return h; -} - - -unsigned int ATermMap::hash2(ATerm key) const -{ - unsigned int key2 = ((unsigned int) key) >> 2; - /* Note: the result must be relatively prime to `capacity' (which - is a power of 2), so we make sure that the result is always - odd. */ - unsigned int h = ((key2 * 134217689) & (capacity - 1)) | 1; - return h; -} - - -static unsigned int nrItemsSet = 0; -static unsigned int nrSetProbes = 0; - - -void ATermMap::set(ATerm key, ATerm value) -{ - if (count == maxCount) resizeTable(capacity * 2 / maxLoadFactor); - - nrItemsSet++; - for (unsigned int i = 0, h = hash1(key); i < capacity; - ++i, h = (h + hash2(key)) & (capacity - 1)) - { - // assert(h < capacity); - nrSetProbes++; - /* Note: to see whether a slot is free, we check - hashTable[h].value, not hashTable[h].key, since we use - value == 0 to mark deleted slots. */ - if (hashTable[h].value == 0 || hashTable[h].key == key) { - if (hashTable[h].value == 0) count++; - hashTable[h].key = key; - hashTable[h].value = value; - return; - } - } - - abort(); -} - - -static unsigned int nrItemsGet = 0; -static unsigned int nrGetProbes = 0; - - -ATerm ATermMap::get(ATerm key) const -{ - nrItemsGet++; - for (unsigned int i = 0, h = hash1(key); i < capacity; - ++i, h = (h + hash2(key)) & (capacity - 1)) - { - nrGetProbes++; - if (hashTable[h].key == 0) return 0; - if (hashTable[h].key == key) return hashTable[h].value; - } - return 0; -} - - -void ATermMap::remove(ATerm key) -{ - for (unsigned int i = 0, h = hash1(key); i < capacity; - ++i, h = (h + hash2(key)) & (capacity - 1)) - { - if (hashTable[h].key == 0) return; - if (hashTable[h].key == key) { - if (hashTable[h].value != 0) { - hashTable[h].value = 0; - count--; - } - return; - } - } -} - - -unsigned int ATermMap::size() -{ - return count; /* STL nomenclature */ -} - - -int main(int argc, char * * argv) -{ - ATerm bottomOfStack; - ATinit(argc, argv, &bottomOfStack); - - /* Make test terms. */ - int nrTestTerms = 100000; - ATerm testTerms[nrTestTerms]; - - for (int i = 0; i < nrTestTerms; ++i) { - char name[10]; - sprintf(name, "%d", (int) random() % 37); - - int arity = i == 0 ? 0 : (random() % 37); - ATerm kids[arity]; - for (int j = 0; j < arity; ++j) - kids[j] = testTerms[random() % i]; - - testTerms[i] = (ATerm) ATmakeApplArray(ATmakeAFun(name, arity, ATfalse), kids); -// ATwriteToSharedTextFile(testTerms[i], stdout); -// printf("\n"); - } - - - cout << "testing...\n"; - - - #define someTerm() (testTerms[(int) random() % nrTestTerms]) - - - for (int test = 0; test < 100000; ++test) { - //cerr << test << endl; - unsigned int n = 300; - ATermMap map(300); - ATerm keys[n], values[n]; - for (unsigned int i = 0; i < n; ++i) { - keys[i] = someTerm(); - values[i] = someTerm(); - map.set(keys[i], values[i]); - //cerr << "INSERT: " << keys[i] << " " << values[i] << endl; - } - - unsigned int size = map.size(); - assert(size <= n); - values[n - 1] = 0; - map.remove(keys[n - 1]); - assert(map.size() == size - 1); - - unsigned int checksum; - unsigned int count = 0; - for (ATermMap::const_iterator i = map.begin(); i != map.end(); ++i, ++count) { - assert(i->key); - assert(i->value); - checksum += (unsigned int) (*i).key; - checksum += (unsigned int) (*i).value; - // cout << (*i).key << " " << (*i).value << endl; - } - assert(count == size - 1); - - for (unsigned int i = 0; i < n; ++i) { - for (unsigned int j = i + 1; j < n; ++j) - if (keys[i] == keys[j]) goto x; - if (map.get(keys[i]) != values[i]) { - cerr << "MISMATCH: " << keys[i] << " " << values[i] << " " << map.get(keys[i]) << " " << i << endl; - abort(); - } - if (values[i] != 0) { - checksum -= (unsigned int) keys[i]; - checksum -= (unsigned int) values[i]; - } - x: ; - } - - assert(checksum == 0); - - for (unsigned int i = 0; i < 100; ++i) - map.get(someTerm()); - - } - - cout << "RESIZES: " << nrResizes << " " - << sizeTotalAlloc << " " - << sizeCurAlloc << " " - << sizeMaxAlloc << endl; - - cout << "SET: " - << nrItemsSet << " " - << nrSetProbes << " " - << (double) nrSetProbes / nrItemsSet << endl; - - cout << "GET: " - << nrItemsGet << " " - << nrGetProbes << " " - << (double) nrGetProbes / nrItemsGet << endl; -} -- cgit 1.4.1