about summary refs log tree commit diff
path: root/src/libutil
diff options
context:
space:
mode:
Diffstat (limited to 'src/libutil')
-rw-r--r--src/libutil/hash.cc185
-rw-r--r--src/libutil/hash.hh51
-rw-r--r--src/libutil/thread-pool.hh75
3 files changed, 160 insertions, 151 deletions
diff --git a/src/libutil/hash.cc b/src/libutil/hash.cc
index e6f8aa85c6d8..817ddc0b8bc9 100644
--- a/src/libutil/hash.cc
+++ b/src/libutil/hash.cc
@@ -16,17 +16,8 @@
 namespace nix {
 
 
-Hash::Hash()
+void Hash::init()
 {
-    type = htUnknown;
-    hashSize = 0;
-    memset(hash, 0, maxHashSize);
-}
-
-
-Hash::Hash(HashType type)
-{
-    this->type = type;
     if (type == htMD5) hashSize = md5HashSize;
     else if (type == htSHA1) hashSize = sha1HashSize;
     else if (type == htSHA256) hashSize = sha256HashSize;
@@ -64,16 +55,10 @@ bool Hash::operator < (const Hash & h) const
 }
 
 
-std::string Hash::to_string(bool base32) const
-{
-    return printHashType(type) + ":" + (base32 ? printHash32(*this) : printHash(*this));
-}
-
-
 const string base16Chars = "0123456789abcdef";
 
 
-string printHash(const Hash & hash)
+static string printHash16(const Hash & hash)
 {
     char buf[hash.hashSize * 2];
     for (unsigned int i = 0; i < hash.hashSize; i++) {
@@ -84,42 +69,11 @@ string printHash(const Hash & hash)
 }
 
 
-Hash parseHash(const string & s)
-{
-    string::size_type colon = s.find(':');
-    if (colon == string::npos)
-        throw BadHash(format("invalid hash ‘%s’") % s);
-    string hts = string(s, 0, colon);
-    HashType ht = parseHashType(hts);
-    if (ht == htUnknown)
-        throw BadHash(format("unknown hash type ‘%s’") % hts);
-    return parseHash16or32(ht, string(s, colon + 1));
-}
-
-
-Hash parseHash(HashType ht, const string & s)
-{
-    Hash hash(ht);
-    if (s.length() != hash.hashSize * 2)
-        throw BadHash(format("invalid hash ‘%1%’") % s);
-    for (unsigned int i = 0; i < hash.hashSize; i++) {
-        string s2(s, i * 2, 2);
-        if (!isxdigit(s2[0]) || !isxdigit(s2[1]))
-            throw BadHash(format("invalid hash ‘%1%’") % s);
-        istringstream_nocopy str(s2);
-        int n;
-        str >> std::hex >> n;
-        hash.hash[i] = n;
-    }
-    return hash;
-}
-
-
 // omitted: E O U T
 const string base32Chars = "0123456789abcdfghijklmnpqrsvwxyz";
 
 
-string printHash32(const Hash & hash)
+static string printHash32(const Hash & hash)
 {
     assert(hash.hashSize);
     size_t len = hash.base32Len();
@@ -144,66 +98,103 @@ string printHash32(const Hash & hash)
 
 string printHash16or32(const Hash & hash)
 {
-    return hash.type == htMD5 ? printHash(hash) : printHash32(hash);
+    return hash.to_string(hash.type == htMD5 ? Base16 : Base32);
 }
 
 
-Hash parseHash32(HashType ht, const string & s)
+std::string Hash::to_string(Base base, bool includeType) const
 {
-    Hash hash(ht);
-    size_t len = hash.base32Len();
-    assert(s.size() == len);
-
-    for (unsigned int n = 0; n < len; ++n) {
-        char c = s[len - n - 1];
-        unsigned char digit;
-        for (digit = 0; digit < base32Chars.size(); ++digit) /* !!! slow */
-            if (base32Chars[digit] == c) break;
-        if (digit >= 32)
-            throw BadHash(format("invalid base-32 hash ‘%1%’") % s);
-        unsigned int b = n * 5;
-        unsigned int i = b / 8;
-        unsigned int j = b % 8;
-        hash.hash[i] |= digit << j;
-
-        if (i < hash.hashSize - 1) {
-            hash.hash[i + 1] |= digit >> (8 - j);
-        } else {
-            if (digit >> (8 - j))
-                throw BadHash(format("invalid base-32 hash ‘%1%’") % s);
-        }
+    std::string s;
+    if (includeType) {
+        s += printHashType(type);
+        s += ':';
     }
-
-    return hash;
+    switch (base) {
+    case Base16:
+        s += printHash16(*this);
+        break;
+    case Base32:
+        s += printHash32(*this);
+        break;
+    case Base64:
+        s += base64Encode(std::string((const char *) hash, hashSize));
+        break;
+    }
+    return s;
 }
 
 
-Hash parseHash16or32(HashType ht, const string & s)
+Hash::Hash(const std::string & s, HashType type)
+    : type(type)
 {
-    Hash hash(ht);
-    if (s.size() == hash.hashSize * 2)
-        /* hexadecimal representation */
-        hash = parseHash(ht, s);
-    else if (s.size() == hash.base32Len())
-        /* base-32 representation */
-        hash = parseHash32(ht, s);
-    else
-        throw BadHash(format("hash ‘%1%’ has wrong length for hash type ‘%2%’")
-            % s % printHashType(ht));
-    return hash;
-}
+    auto colon = s.find(':');
+
+    size_t pos = 0;
+
+    if (colon == string::npos) {
+        if (type == htUnknown)
+            throw BadHash("hash ‘%s’ does not include a type", s);
+    } else {
+        string hts = string(s, 0, colon);
+        this->type = parseHashType(hts);
+        if (this->type == htUnknown)
+            throw BadHash("unknown hash type ‘%s’", hts);
+        if (type != htUnknown && type != this->type)
+            throw BadHash("hash ‘%s’ should have type ‘%s’", s, printHashType(type));
+        pos = colon + 1;
+    }
 
+    init();
 
-bool isHash(const string & s)
-{
-    if (s.length() != 32) return false;
-    for (int i = 0; i < 32; i++) {
-        char c = s[i];
-        if (!((c >= '0' && c <= '9') ||
-              (c >= 'a' && c <= 'f')))
-            return false;
+    size_t size = s.size() - pos;
+
+    if (size == base16Len()) {
+
+        auto parseHexDigit = [&](char c) {
+            if (c >= '0' && c <= '9') return c - '0';
+            if (c >= 'A' && c <= 'F') return c - 'A' + 10;
+            if (c >= 'a' && c <= 'f') return c - 'a' + 10;
+            throw BadHash("invalid base-16 hash ‘%s’", s);
+        };
+
+        for (unsigned int i = 0; i < hashSize; i++) {
+            hash[i] =
+                parseHexDigit(s[pos + i * 2]) << 4
+                | parseHexDigit(s[pos + i * 2 + 1]);
+        }
     }
-    return true;
+
+    else if (size == base32Len()) {
+
+        for (unsigned int n = 0; n < size; ++n) {
+            char c = s[pos + size - n - 1];
+            unsigned char digit;
+            for (digit = 0; digit < base32Chars.size(); ++digit) /* !!! slow */
+                if (base32Chars[digit] == c) break;
+            if (digit >= 32)
+                throw BadHash("invalid base-32 hash ‘%s’", s);
+            unsigned int b = n * 5;
+            unsigned int i = b / 8;
+            unsigned int j = b % 8;
+            hash[i] |= digit << j;
+
+            if (i < hashSize - 1) {
+                hash[i + 1] |= digit >> (8 - j);
+            } else {
+                if (digit >> (8 - j))
+                    throw BadHash("invalid base-32 hash ‘%s’", s);
+            }
+        }
+    }
+
+    else if (size == base64Len()) {
+        auto d = base64Decode(std::string(s, pos));
+        assert(d.size() == hashSize);
+        memcpy(hash, d.data(), hashSize);
+    }
+
+    else
+        throw BadHash("hash ‘%s’ has wrong length for hash type ‘%s’", s, printHashType(type));
 }
 
 
diff --git a/src/libutil/hash.hh b/src/libutil/hash.hh
index 02e213fc7b35..b8b432256c97 100644
--- a/src/libutil/hash.hh
+++ b/src/libutil/hash.hh
@@ -20,20 +20,30 @@ const int sha512HashSize = 64;
 
 extern const string base32Chars;
 
+enum Base : int { Base64, Base32, Base16 };
+
 
 struct Hash
 {
     static const unsigned int maxHashSize = 64;
-    unsigned int hashSize;
-    unsigned char hash[maxHashSize];
+    unsigned int hashSize = 0;
+    unsigned char hash[maxHashSize] = {};
 
-    HashType type;
+    HashType type = htUnknown;
 
     /* Create an unset hash object. */
-    Hash();
+    Hash() { };
 
     /* Create a zero-filled hash object. */
-    Hash(HashType type);
+    Hash(HashType type) : type(type) { init(); };
+
+    /* Initialize the hash from a string representation, in the format
+       "[<type>:]<base16|base32|base64>". If the ‘type’ argument is
+       htUnknown, then the hash type must be specified in the
+       string. */
+    Hash(const std::string & s, HashType type = htUnknown);
+
+    void init();
 
     /* Check whether a hash is set. */
     operator bool () const { return type != htUnknown; }
@@ -59,33 +69,22 @@ struct Hash
         return (hashSize * 8 - 1) / 5 + 1;
     }
 
-    std::string to_string(bool base32 = true) const;
-};
-
-
-/* Convert a hash to a hexadecimal representation. */
-string printHash(const Hash & hash);
-
-Hash parseHash(const string & s);
+    /* Returns the length of a base-64 representation of this hash. */
+    size_t base64Len() const
+    {
+        return ((4 * hashSize / 3) + 3) & ~3;
+    }
 
-/* Parse a hexadecimal representation of a hash code. */
-Hash parseHash(HashType ht, const string & s);
+    /* Return a string representation of the hash, in base-16, base-32
+       or base-64. By default, this is prefixed by the hash type
+       (e.g. "sha256:"). */
+    std::string to_string(Base base = Base32, bool includeType = true) const;
+};
 
-/* Convert a hash to a base-32 representation. */
-string printHash32(const Hash & hash);
 
 /* Print a hash in base-16 if it's MD5, or base-32 otherwise. */
 string printHash16or32(const Hash & hash);
 
-/* Parse a base-32 representation of a hash code. */
-Hash parseHash32(HashType ht, const string & s);
-
-/* Parse a base-16 or base-32 representation of a hash code. */
-Hash parseHash16or32(HashType ht, const string & s);
-
-/* Verify that the given string is a valid hash code. */
-bool isHash(const string & s);
-
 /* Compute the hash of the given string. */
 Hash hashString(HashType ht, const string & s);
 
diff --git a/src/libutil/thread-pool.hh b/src/libutil/thread-pool.hh
index b64dc52d473e..361a9d33a732 100644
--- a/src/libutil/thread-pool.hh
+++ b/src/libutil/thread-pool.hh
@@ -70,50 +70,69 @@ void processGraph(
     struct Graph {
         std::set<T> left;
         std::map<T, std::set<T>> refs, rrefs;
-        std::function<void(T)> wrap;
     };
 
-    ref<Sync<Graph>> graph_ = make_ref<Sync<Graph>>();
+    Sync<Graph> graph_(Graph{nodes, {}, {}});
 
-    auto wrapWork = [&pool, graph_, processNode](const T & node) {
+    std::function<void(const T &)> worker;
+
+    worker = [&](const T & node) {
+
+        {
+            auto graph(graph_.lock());
+            auto i = graph->refs.find(node);
+            if (i == graph->refs.end())
+                goto getRefs;
+            goto doWork;
+        }
+
+    getRefs:
+        {
+            auto refs = getEdges(node);
+            refs.erase(node);
+
+            {
+                auto graph(graph_.lock());
+                for (auto & ref : refs)
+                    if (graph->left.count(ref)) {
+                        graph->refs[node].insert(ref);
+                        graph->rrefs[ref].insert(node);
+                    }
+                if (graph->refs[node].empty())
+                    goto doWork;
+            }
+        }
+
+        return;
+
+    doWork:
         processNode(node);
 
-        /* Enqueue work for all nodes that were waiting on this one. */
+        /* Enqueue work for all nodes that were waiting on this one
+           and have no unprocessed dependencies. */
         {
-            auto graph(graph_->lock());
-            graph->left.erase(node);
+            auto graph(graph_.lock());
             for (auto & rref : graph->rrefs[node]) {
                 auto & refs(graph->refs[rref]);
                 auto i = refs.find(node);
                 assert(i != refs.end());
                 refs.erase(i);
                 if (refs.empty())
-                    pool.enqueue(std::bind(graph->wrap, rref));
+                    pool.enqueue(std::bind(worker, rref));
             }
+            graph->left.erase(node);
+            graph->refs.erase(node);
+            graph->rrefs.erase(node);
         }
     };
 
-    {
-        auto graph(graph_->lock());
-        graph->left = nodes;
-        graph->wrap = wrapWork;
-    }
-
-    /* Build the dependency graph; enqueue all nodes with no
-       dependencies. */
-    for (auto & node : nodes) {
-        auto refs = getEdges(node);
-        {
-            auto graph(graph_->lock());
-            for (auto & ref : refs)
-                if (ref != node && graph->left.count(ref)) {
-                    graph->refs[node].insert(ref);
-                    graph->rrefs[ref].insert(node);
-                }
-            if (graph->refs[node].empty())
-                pool.enqueue(std::bind(graph->wrap, node));
-        }
-    }
+    for (auto & node : nodes)
+        pool.enqueue(std::bind(worker, std::ref(node)));
+
+    pool.process();
+
+    if (!graph_.lock()->left.empty())
+        throw Error("graph processing incomplete (cyclic reference?)");
 }
 
 }