diff options
Diffstat (limited to 'src/libutil')
| -rw-r--r-- | src/libutil/Makefile.am | 6 | ||||
| -rw-r--r-- | src/libutil/aterm-map.cc | 332 | ||||
| -rw-r--r-- | src/libutil/aterm-map.hh | 129 | ||||
| -rw-r--r-- | src/libutil/aterm.cc | 55 | ||||
| -rw-r--r-- | src/libutil/aterm.hh | 55 | ||||
| -rw-r--r-- | src/libutil/util.cc | 88 | ||||
| -rw-r--r-- | src/libutil/util.hh | 42 |
7 files changed, 57 insertions, 650 deletions
diff --git a/src/libutil/Makefile.am b/src/libutil/Makefile.am index bd0996543344..aa862208c6f9 100644 --- a/src/libutil/Makefile.am +++ b/src/libutil/Makefile.am @@ -1,16 +1,16 @@ pkglib_LTLIBRARIES = libutil.la libutil_la_SOURCES = util.cc hash.cc serialise.cc \ - archive.cc aterm.cc aterm-map.cc xml-writer.cc + archive.cc xml-writer.cc libutil_la_LIBADD = ../boost/format/libformat.la pkginclude_HEADERS = util.hh hash.hh serialise.hh \ - archive.hh aterm.hh aterm-map.hh xml-writer.hh types.hh + archive.hh xml-writer.hh types.hh if !HAVE_OPENSSL libutil_la_SOURCES += \ md5.c md5.h sha1.c sha1.h sha256.c sha256.h md32_common.h endif -AM_CXXFLAGS = -Wall -I$(srcdir)/.. ${aterm_include} +AM_CXXFLAGS = -Wall -I$(srcdir)/.. diff --git a/src/libutil/aterm-map.cc b/src/libutil/aterm-map.cc deleted file mode 100644 index c31fcdba3966..000000000000 --- a/src/libutil/aterm-map.cc +++ /dev/null @@ -1,332 +0,0 @@ -#include "aterm-map.hh" - -#include <iostream> - -#include <assert.h> -#include <stdlib.h> - -#include <aterm2.h> - - -namespace nix { - - -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); -} - - -/* !!! use a bigger shift for 64-bit platforms? */ -static const unsigned int shift = 16; -static const unsigned long knuth = (unsigned long) (0.6180339887 * (1 << shift)); - - -unsigned long ATermMap::hash1(ATerm key) const -{ - /* Don't care about the least significant bits of the ATerm - pointer since they're always 0. */ - unsigned long key2 = ((unsigned long) key) >> 2; - - /* Approximately equal to: - double d = key2 * 0.6180339887; - unsigned int h = (int) (capacity * (d - floor(d))); - */ - - unsigned long h = (capacity * ((key2 * knuth) & ((1 << shift) - 1))) >> shift; - - return h; -} - - -unsigned long ATermMap::hash2(ATerm key) const -{ - unsigned long key2 = ((unsigned long) 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 long 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 */ -} - - -void printATermMapStats() -{ - using std::cerr; - using std::endl; - - cerr << "RESIZES: " << nrResizes << " " - << sizeTotalAlloc << " " - << sizeCurAlloc << " " - << sizeMaxAlloc << endl; - - cerr << "SET: " - << nrItemsSet << " " - << nrSetProbes << " " - << (double) nrSetProbes / nrItemsSet << endl; - - cerr << "GET: " - << nrItemsGet << " " - << nrGetProbes << " " - << (double) nrGetProbes / nrItemsGet << endl; -} - - -#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()); - - } - - printATermMapStats(); -} -#endif - - -} diff --git a/src/libutil/aterm-map.hh b/src/libutil/aterm-map.hh deleted file mode 100644 index b732453a7600..000000000000 --- a/src/libutil/aterm-map.hh +++ /dev/null @@ -1,129 +0,0 @@ -#ifndef __ATERM_MAP_H -#define __ATERM_MAP_H - -#include <aterm1.h> -#include <assert.h> - - -namespace nix { - - -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 = 16); - - ATermMap(const ATermMap & map); - - ~ATermMap(); - - ATermMap & operator = (const ATermMap & map); - - void set(ATerm key, ATerm value); - - ATerm get(ATerm key) const; - - ATerm operator [](ATerm key) const - { - return get(key); - } - - 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]; - } - }; - - friend class ATermMap::const_iterator; - - 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 long hash1(ATerm key) const; - inline unsigned long hash2(ATerm key) const; -}; - - -/* Hack. */ -void printATermMapStats(); - - -} - - -#endif /* !__ATERM_MAP_H */ diff --git a/src/libutil/aterm.cc b/src/libutil/aterm.cc deleted file mode 100644 index 25d70478573d..000000000000 --- a/src/libutil/aterm.cc +++ /dev/null @@ -1,55 +0,0 @@ -#include "aterm.hh" - -#include <cstring> - -using std::string; - - -string nix::atPrint(ATerm t) -{ - if (!t) throw Error("attempt to print null aterm"); - char * s = ATwriteToString(t); - if (!s) throw Error("cannot print term"); - return s; -} - - -std::ostream & operator << (std::ostream & stream, ATerm e) -{ - return stream << nix::atPrint(e); -} - - -nix::Error nix::badTerm(const format & f, ATerm t) -{ - char * s = ATwriteToString(t); - if (!s) throw Error("cannot print term"); - if (strlen(s) > 1000) { - int len; - s = ATwriteToSharedString(t, &len); - if (!s) throw Error("cannot print term"); - } - return Error(format("%1%, in `%2%'") % f.str() % (string) s); -} - - -ATerm nix::toATerm(const char * s) -{ - return (ATerm) ATmakeAppl0(ATmakeAFun((char *) s, 0, ATtrue)); -} - - -ATerm nix::toATerm(const string & s) -{ - return toATerm(s.c_str()); -} - - -ATermList nix::toATermList(const StringSet & ss) -{ - ATermList l = ATempty; - for (StringSet::const_reverse_iterator i = ss.rbegin(); - i != ss.rend(); ++i) - l = ATinsert(l, toATerm(*i)); - return l; -} diff --git a/src/libutil/aterm.hh b/src/libutil/aterm.hh deleted file mode 100644 index b1cbc3b6d895..000000000000 --- a/src/libutil/aterm.hh +++ /dev/null @@ -1,55 +0,0 @@ -#ifndef __ATERM_H -#define __ATERM_H - -#include <aterm2.h> - -#include "types.hh" - - -namespace nix { - - -/* Print an ATerm. */ -string atPrint(ATerm t); - -class ATermIterator -{ - ATermList t; - -public: - ATermIterator(ATermList _t) : t(_t) { } - ATermIterator & operator ++ () - { - t = ATgetNext(t); - return *this; - } - ATerm operator * () - { - return ATgetFirst(t); - } - operator bool () - { - return t != ATempty; - } -}; - - -/* Throw an exception with an error message containing the given - aterm. */ -Error badTerm(const format & f, ATerm t); - - -/* Convert strings to ATerms. */ -ATerm toATerm(const char * s); -ATerm toATerm(const string & s); - -ATermList toATermList(const StringSet & ss); - -} - - -/* Write an ATerm to an output stream. */ -std::ostream & operator << (std::ostream & stream, ATerm e); - - -#endif /* !__ATERM_H */ diff --git a/src/libutil/util.cc b/src/libutil/util.cc index 790c2576802e..98912e7a002c 100644 --- a/src/libutil/util.cc +++ b/src/libutil/util.cc @@ -951,53 +951,6 @@ void _interrupted() ////////////////////////////////////////////////////////////////////// -string packStrings(const Strings & strings) -{ - string d; - for (Strings::const_iterator i = strings.begin(); - i != strings.end(); ++i) - { - unsigned int len = i->size(); - d += len & 0xff; - d += (len >> 8) & 0xff; - d += (len >> 16) & 0xff; - d += (len >> 24) & 0xff; - d += *i; - } - return d; -} - - -Strings unpackStrings(const string & s) -{ - Strings strings; - - string::const_iterator i = s.begin(); - - while (i != s.end()) { - - if (i + 4 > s.end()) - throw Error(format("short db entry: `%1%'") % s); - - unsigned int len; - len = (unsigned char) *i++; - len |= ((unsigned char) *i++) << 8; - len |= ((unsigned char) *i++) << 16; - len |= ((unsigned char) *i++) << 24; - - if (len == 0xffffffff) return strings; /* explicit end-of-list */ - - if (i + len > s.end()) - throw Error(format("short db entry: `%1%'") % s); - - strings.push_back(string(i, i + len)); - i += len; - } - - return strings; -} - - Strings tokenizeString(const string & s, const string & separators) { Strings result; @@ -1053,6 +1006,47 @@ bool hasSuffix(const string & s, const string & suffix) } +void expect(std::istream & str, const string & s) +{ + char s2[s.size()]; + str.read(s2, s.size()); + if (string(s2, s.size()) != s) + throw Error(format("expected string `%1%'") % s); +} + + +string parseString(std::istream & str) +{ + string res; + expect(str, "\""); + int c; + while ((c = str.get()) != '"') + if (c == '\\') { + c = str.get(); + if (c == 'n') res += '\n'; + else if (c == 'r') res += '\r'; + else if (c == 't') res += '\t'; + else res += c; + } + else res += c; + return res; +} + + +bool endOfList(std::istream & str) +{ + if (str.peek() == ',') { + str.get(); + return false; + } + if (str.peek() == ']') { + str.get(); + return true; + } + return false; +} + + void ignoreException() { try { diff --git a/src/libutil/util.hh b/src/libutil/util.hh index f609e8944ba8..ff710077ceaa 100644 --- a/src/libutil/util.hh +++ b/src/libutil/util.hh @@ -15,7 +15,7 @@ namespace nix { #define foreach(it_type, it, collection) \ - for (it_type it = collection.begin(); it != collection.end(); ++it) + for (it_type it = (collection).begin(); it != (collection).end(); ++it) /* Return an environment variable. */ @@ -276,11 +276,6 @@ void inline checkInterrupt() MakeError(Interrupted, BaseError) -/* String packing / unpacking. */ -string packStrings(const Strings & strings); -Strings unpackStrings(const string & s); - - /* String tokenizer. */ Strings tokenizeString(const string & s, const string & separators = " \t\n\r"); @@ -307,32 +302,21 @@ string int2String(int n); bool hasSuffix(const string & s, const string & suffix); -/* Exception handling in destructors: print an error message, then - ignore the exception. */ -void ignoreException(); +/* Read string `s' from stream `str'. */ +void expect(std::istream & str, const string & s); -/* STL functions such as sort() pass a binary function object around - by value, so it gets cloned a lot. This is bad if the function - object has state or is simply large. This adapter wraps the - function object to simulate passing by reference. */ -template<class F> -struct binary_function_ref_adapter -{ - F * p; +/* Read a C-style string from stream `str'. */ +string parseString(std::istream & str); - binary_function_ref_adapter(F * _p) - { - p = _p; - } - - typename F::result_type operator () ( - const typename F::first_argument_type & x, - const typename F::second_argument_type & y) - { - return (*p)(x, y); - } -}; + +/* Utility function used to parse legacy ATerms. */ +bool endOfList(std::istream & str); + + +/* Exception handling in destructors: print an error message, then + ignore the exception. */ +void ignoreException(); } |