aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/libexpr/eval.cc44
-rw-r--r--src/libexpr/get-drvs.cc42
-rw-r--r--src/libexpr/nixexpr.cc130
-rw-r--r--src/libexpr/nixexpr.hh39
-rw-r--r--src/libexpr/parser.cc6
-rw-r--r--src/libexpr/primops.cc33
-rw-r--r--src/libutil/Makefile.am3
-rw-r--r--src/libutil/aterm-map.cc312
-rw-r--r--src/libutil/aterm-map.hh114
-rw-r--r--src/nix-env/main.cc2
10 files changed, 500 insertions, 225 deletions
diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index 6d2b20e53..38f198fb8 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 78ccab7f3..19778c6ab 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<ATermMap> attrs(new ATermMap());
+ shared_ptr<ATermMap> 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 bfa7a9ed7..ebdef96d9 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 298a9f0b9..e3c7ee607 100644
--- a/src/libexpr/nixexpr.hh
+++ b/src/libexpr/nixexpr.hh
@@ -5,6 +5,7 @@
#include <aterm2.h>
+#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 2ca1cab4a..241a43734 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 8935b147e..262e3bec5 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 9d71b66e6..e10477deb 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 000000000..e0cfefa2d
--- /dev/null
+++ b/src/libutil/aterm-map.cc
@@ -0,0 +1,312 @@
+#include "aterm-map.hh"
+
+#include <assert.h>
+#include <stdlib.h>
+
+
+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 000000000..d7aed2ca2
--- /dev/null
+++ b/src/libutil/aterm-map.hh
@@ -0,0 +1,114 @@
+#ifndef __ATERM_MAP_H
+#define __ATERM_MAP_H
+
+#include <aterm2.h>
+#include <assert.h>
+
+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 ad3c1b5ce..e7f25c5ba 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<ATermMap>(new ATermMap()); /* ugh... */
+ elem.attrs = shared_ptr<ATermMap>(new ATermMap(0)); /* ugh... */
string name = baseNameOf(*i);
unsigned int dash = name.find('-');
if (dash != string::npos)
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-23 10:26:09 +0000