KenLM 5a7efd8fe1db88ee0a9f7e9479b24ac3ca348221 with Hieu's patch to exception.hh

46 files changed, 1135 insertions, 191 deletions

diff --git a/util/Jamfile b/util/Jamfile
index d4996e483..18b20a33a 100644
--- a/util/Jamfile
+++ b/util/Jamfile
@@ -11,28 +11,26 @@ if [ test_library "lzma" ] && [ test_header "lzma.h" ] {
   compressed_deps += lzma ;
 }
 
-local have-clock = [ SHELL "bash -c \"g++ -dM -x c++ -E /dev/null -include time.h 2>/dev/null |grep CLOCK_MONOTONIC\"" : exit-status ] ;
-if $(have-clock[2]) = 0 {
-  #required for clock_gettime.  Threads already have rt.  
-  lib rt : : <runtime-link>static:<link>static <runtime-link>shared:<link>shared ;
-} else {
-  alias rt ;
-}
+#rt is needed for clock_gettime on linux.  But it's already included with threading=multi
+lib rt ;
 
 obj read_compressed.o : read_compressed.cc : $(compressed_flags) ;
 alias read_compressed : read_compressed.o $(compressed_deps) ;
 obj read_compressed_test.o : read_compressed_test.cc /top//boost_unit_test_framework : $(compressed_flags) ;
 obj file_piece_test.o : file_piece_test.cc /top//boost_unit_test_framework : $(compressed_flags) ;
 
-fakelib kenutil : bit_packing.cc ersatz_progress.cc exception.cc file.cc file_piece.cc mmap.cc murmur_hash.cc pool.cc read_compressed scoped.cc string_piece.cc usage.cc double-conversion//double-conversion : <include>.. <os>LINUX,<threading>single:<source>rt : : <include>.. ;
+fakelib parallel_read : parallel_read.cc : <threading>multi:<source>/top//boost_thread <threading>multi:<define>WITH_THREADS : : <include>.. ;
+
+fakelib kenutil : bit_packing.cc ersatz_progress.cc exception.cc file.cc file_piece.cc mmap.cc murmur_hash.cc parallel_read pool.cc read_compressed scoped.cc string_piece.cc usage.cc double-conversion//double-conversion : <include>.. <os>LINUX,<threading>single:<source>rt : : <include>.. ;
+
+exe cat_compressed : cat_compressed_main.cc kenutil ;
+
+alias programs : cat_compressed ;
 
 import testing ;
 
 run file_piece_test.o kenutil /top//boost_unit_test_framework : : file_piece.cc ;
-unit-test pcqueue_test : pcqueue_test.cc kenutil /top//boost_unit_test_framework /top//boost_system : <threading>single:<build>no ;
-
-for local t in [ glob *_test.cc : file_piece_test.cc read_compressed_test.cc pcqueue_test.cc ] {
+for local t in [ glob *_test.cc : file_piece_test.cc read_compressed_test.cc ] {
     local name = [ MATCH "(.*)\.cc" : $(t) ] ;
     unit-test $(name) : $(t) kenutil /top//boost_unit_test_framework /top//boost_system ;
 }
-
diff --git a/util/bit_packing.hh b/util/bit_packing.hh
index dcbd814c3..1e34d9ab1 100644
--- a/util/bit_packing.hh
+++ b/util/bit_packing.hh
@@ -1,5 +1,5 @@
-#ifndef UTIL_BIT_PACKING__
-#define UTIL_BIT_PACKING__
+#ifndef UTIL_BIT_PACKING_H
+#define UTIL_BIT_PACKING_H
 
 /* Bit-level packing routines 
  *
@@ -183,4 +183,4 @@ struct BitAddress {
 
 } // namespace util
 
-#endif // UTIL_BIT_PACKING__
+#endif // UTIL_BIT_PACKING_H
diff --git a/util/cat_compressed_main.cc b/util/cat_compressed_main.cc
new file mode 100644
index 000000000..2b4d72927
--- /dev/null
+++ b/util/cat_compressed_main.cc
@@ -0,0 +1,47 @@
+// Like cat but interprets compressed files.
+#include "util/file.hh"
+#include "util/read_compressed.hh"
+
+#include <string.h>
+#include <iostream>
+
+namespace {
+const std::size_t kBufSize = 16384;
+void Copy(util::ReadCompressed &from, int to) {
+  util::scoped_malloc buffer(util::MallocOrThrow(kBufSize));
+  while (std::size_t amount = from.Read(buffer.get(), kBufSize)) {
+    util::WriteOrThrow(to, buffer.get(), amount);
+  }
+}
+} // namespace
+
+int main(int argc, char *argv[]) {
+  // Lane Schwartz likes -h and --help
+  for (int i = 1; i < argc; ++i) {
+    char *arg = argv[i];
+    if (!strcmp(arg, "--")) break;
+    if (!strcmp(arg, "-h") || !strcmp(arg, "--help")) {
+      std::cerr << 
+        "A cat implementation that interprets compressed files.\n"
+        "Usage: " << argv[0] << " [file1] [file2] ...\n"
+        "If no file is provided, then stdin is read.\n";
+      return 1;
+    }
+  }
+
+  try {
+    if (argc == 1) {
+      util::ReadCompressed in(0);
+      Copy(in, 1);
+    } else {
+      for (int i = 1; i < argc; ++i) {
+        util::ReadCompressed in(util::OpenReadOrThrow(argv[i]));
+        Copy(in, 1);
+      }
+    }
+  } catch (const std::exception &e) {
+    std::cerr << e.what() << std::endl;
+    return 2;
+  }
+  return 0;
+}
diff --git a/util/ersatz_progress.hh b/util/ersatz_progress.hh
index b94399a80..535dbde23 100644
--- a/util/ersatz_progress.hh
+++ b/util/ersatz_progress.hh
@@ -1,5 +1,5 @@
-#ifndef UTIL_ERSATZ_PROGRESS__
-#define UTIL_ERSATZ_PROGRESS__
+#ifndef UTIL_ERSATZ_PROGRESS_H
+#define UTIL_ERSATZ_PROGRESS_H
 
 #include <iostream>
 #include <string>
@@ -55,4 +55,4 @@ class ErsatzProgress {
 
 } // namespace util
 
-#endif // UTIL_ERSATZ_PROGRESS__
+#endif // UTIL_ERSATZ_PROGRESS_H
diff --git a/util/fake_ofstream.hh b/util/fake_ofstream.hh
index bcdebe455..eefb1edce 100644
--- a/util/fake_ofstream.hh
+++ b/util/fake_ofstream.hh
@@ -2,6 +2,9 @@
  * Does not support many data types.  Currently, it's targeted at writing ARPA
  * files quickly.
  */
+#ifndef UTIL_FAKE_OFSTREAM_H
+#define UTIL_FAKE_OFSTREAM_H
+
 #include "util/double-conversion/double-conversion.h"
 #include "util/double-conversion/utils.h"
 #include "util/file.hh"
@@ -17,7 +20,8 @@ class FakeOFStream {
     static const std::size_t kOutBuf = 1048576;
 
     // Does not take ownership of out.
-    explicit FakeOFStream(int out)
+    // Allows default constructor, but must call SetFD.
+    explicit FakeOFStream(int out = -1)
       : buf_(util::MallocOrThrow(kOutBuf)),
         builder_(static_cast<char*>(buf_.get()), kOutBuf),
         // Mostly the default but with inf instead.  And no flags.
@@ -28,6 +32,11 @@ class FakeOFStream {
       if (buf_.get()) Flush();
     }
 
+    void SetFD(int to) {
+      if (builder_.position()) Flush();
+      fd_ = to;
+    }
+
     FakeOFStream &operator<<(float value) {
       // Odd, but this is the largest number found in the comments.
       EnsureRemaining(double_conversion::DoubleToStringConverter::kMaxPrecisionDigits + 8);
@@ -92,3 +101,5 @@ class FakeOFStream {
 };
 
 } // namespace
+
+#endif
diff --git a/util/file.cc b/util/file.cc
index 51eaf972f..25ff8183a 100644
--- a/util/file.cc
+++ b/util/file.cc
@@ -5,28 +5,29 @@
 
 #include "util/exception.hh"
 
+#include <algorithm>
 #include <cstdlib>
 #include <cstdio>
-#include <sstream>
 #include <iostream>
+#include <limits>
+#include <sstream>
+
 
 #include <assert.h>
 #include <errno.h>
+#include <limits.h>
 #include <sys/types.h>
 #include <sys/stat.h>
 #include <fcntl.h>
 #include <stdint.h>
 
-#if defined __MINGW32__
+#if defined(__MINGW32__)
 #include <windows.h>
 #include <unistd.h>
 #warning "The file functions on MinGW have not been tested for file sizes above 2^31 - 1.  Please read https://stackoverflow.com/questions/12539488/determine-64-bit-file-size-in-c-on-mingw-32-bit and fix"
 #elif defined(_WIN32) || defined(_WIN64)
 #include <windows.h>
 #include <io.h>
-#include <algorithm>
-#include <limits.h>
-#include <limits>
 #else
 #include <unistd.h>
 #endif
@@ -111,7 +112,7 @@ uint64_t SizeOrThrow(int fd) {
 
 void ResizeOrThrow(int fd, uint64_t to) {
 #if defined __MINGW32__
-    // Does this handle 64-bit?  
+    // Does this handle 64-bit?
     int ret = ftruncate
 #elif defined(_WIN32) || defined(_WIN64)
     errno_t ret = _chsize_s
@@ -128,8 +129,10 @@ namespace {
 std::size_t GuardLarge(std::size_t size) {
   // The following operating systems have broken read/write/pread/pwrite that
   // only supports up to 2^31.
+  // OS X man pages claim to support 64-bit, but Kareem M. Darwish had problems
+  // building with larger files, so APPLE is also here.
 #if defined(_WIN32) || defined(_WIN64) || defined(__APPLE__) || defined(OS_ANDROID) || defined(__MINGW32__)
-  return std::min(static_cast<std::size_t>(static_cast<unsigned>(-1)), size);
+  return size < INT_MAX ? size : INT_MAX;
 #else
   return size;
 #endif
@@ -172,13 +175,44 @@ std::size_t ReadOrEOF(int fd, void *to_void, std::size_t amount) {
   return amount;
 }
 
-void PReadOrThrow(int fd, void *to_void, std::size_t size, uint64_t off) {
-  uint8_t *to = static_cast<uint8_t*>(to_void);
+void WriteOrThrow(int fd, const void *data_void, std::size_t size) {
+  const uint8_t *data = static_cast<const uint8_t*>(data_void);
+  while (size) {
 #if defined(_WIN32) || defined(_WIN64)
-  UTIL_THROW(Exception, "This pread implementation for windows is broken.  Please send me a patch that does not change the file pointer.  Atomically.  Or send me an implementation of pwrite that is allowed to change the file pointer but can be called concurrently with pread.");
-  const std::size_t kMaxDWORD = static_cast<std::size_t>(4294967295UL);
+    int ret;
+#else
+    ssize_t ret;
 #endif
-  for (;size ;) {
+    errno = 0;
+    do {
+      ret =
+#if defined(_WIN32) || defined(_WIN64)
+        _write
+#else
+        write
+#endif
+        (fd, data, GuardLarge(size));
+    } while (ret == -1 && errno == EINTR);
+    UTIL_THROW_IF_ARG(ret < 1, FDException, (fd), "while writing " << size << " bytes");
+    data += ret;
+    size -= ret;
+  }
+}
+
+void WriteOrThrow(FILE *to, const void *data, std::size_t size) {
+  if (!size) return;
+  UTIL_THROW_IF(1 != std::fwrite(data, size, 1, to), ErrnoException, "Short write; requested size " << size);
+}
+
+#if defined(_WIN32) || defined(_WIN64)
+namespace {
+const std::size_t kMaxDWORD = static_cast<std::size_t>(4294967295UL);
+} // namespace
+#endif
+
+void ErsatzPRead(int fd, void *to_void, std::size_t size, uint64_t off) {
+  uint8_t *to = static_cast<uint8_t*>(to_void);
+  while (size) {
 #if defined(_WIN32) || defined(_WIN64)
     /* BROKEN: changes file pointer.  Even if you save it and change it back, it won't be safe to use concurrently with write() or read() which lmplz does. */
     // size_t might be 64-bit.  DWORD is always 32.
@@ -192,16 +226,15 @@ void PReadOrThrow(int fd, void *to_void, std::size_t size, uint64_t off) {
 #else
     ssize_t ret;
     errno = 0;
-    do {
-      ret =
+    ret =
 #ifdef OS_ANDROID
-        pread64
+      pread64
 #else
-        pread
+      pread
 #endif
-        (fd, to, GuardLarge(size), off);
-    } while (ret == -1 && errno == EINTR);
+      (fd, to, GuardLarge(size), off);
     if (ret <= 0) {
+      if (ret == -1 && errno == EINTR) continue;
       UTIL_THROW_IF(ret == 0, EndOfFileException, " for reading " << size << " bytes at " << off << " from " << NameFromFD(fd));
       UTIL_THROW_ARG(FDException, (fd), "while reading " << size << " bytes at offset " << off);
     }
@@ -212,34 +245,41 @@ void PReadOrThrow(int fd, void *to_void, std::size_t size, uint64_t off) {
   }
 }
 
-void WriteOrThrow(int fd, const void *data_void, std::size_t size) {
-  const uint8_t *data = static_cast<const uint8_t*>(data_void);
-  while (size) {
+void ErsatzPWrite(int fd, const void *from_void, std::size_t size, uint64_t off) {
+  const uint8_t *from = static_cast<const uint8_t*>(from_void);
+  while(size) {
 #if defined(_WIN32) || defined(_WIN64)
-    int ret;
+    /* Changes file pointer.  Even if you save it and change it back, it won't be safe to use concurrently with write() or read() */
+    // size_t might be 64-bit.  DWORD is always 32.
+    DWORD writing = static_cast<DWORD>(std::min<std::size_t>(kMaxDWORD, size));
+    DWORD ret;
+    OVERLAPPED overlapped;
+    memset(&overlapped, 0, sizeof(OVERLAPPED));
+    overlapped.Offset = static_cast<DWORD>(off);
+    overlapped.OffsetHigh = static_cast<DWORD>(off >> 32);
+    UTIL_THROW_IF(!WriteFile((HANDLE)_get_osfhandle(fd), from, writing, &ret, &overlapped), Exception, "WriteFile failed for offset " << off);
 #else
     ssize_t ret;
-#endif
     errno = 0;
-    do {
-      ret =
-#if defined(_WIN32) || defined(_WIN64)
-        _write
+    ret =
+#ifdef OS_ANDROID
+      pwrite64
 #else
-        write
+      pwrite
+#endif
+      (fd, from, GuardLarge(size), off);
+    if (ret <= 0) {
+      if (ret == -1 && errno == EINTR) continue;
+      UTIL_THROW_IF(ret == 0, EndOfFileException, " for writing " << size << " bytes at " << off << " from " << NameFromFD(fd));
+      UTIL_THROW_ARG(FDException, (fd), "while writing " << size << " bytes at offset " << off);
+    }
 #endif
-        (fd, data, GuardLarge(size));
-    } while (ret == -1 && errno == EINTR);
-    UTIL_THROW_IF_ARG(ret < 1, FDException, (fd), "while writing " << size << " bytes");
-    data += ret;
     size -= ret;
+    off += ret;
+    from += ret;
   }
 }
 
-void WriteOrThrow(FILE *to, const void *data, std::size_t size) {
-  if (!size) return;
-  UTIL_THROW_IF(1 != std::fwrite(data, size, 1, to), ErrnoException, "Short write; requested size " << size);
-}
 
 void FSyncOrThrow(int fd) {
 // Apparently windows doesn't have fsync?
@@ -443,8 +483,8 @@ void NormalizeTempPrefix(std::string &base) {
     ) base += '/';
 }
 
-int MakeTemp(const std::string &base) {
-  std::string name(base);
+int MakeTemp(const StringPiece &base) {
+  std::string name(base.data(), base.size());
   name += "XXXXXX";
   name.push_back(0);
   int ret;
@@ -452,7 +492,7 @@ int MakeTemp(const std::string &base) {
   return ret;
 }
 
-std::FILE *FMakeTemp(const std::string &base) {
+std::FILE *FMakeTemp(const StringPiece &base) {
   util::scoped_fd file(MakeTemp(base));
   return FDOpenOrThrow(file);
 }
@@ -478,14 +518,18 @@ bool TryName(int fd, std::string &out) {
   if (-1 == lstat(name.c_str(), &sb))
     return false;
   out.resize(sb.st_size + 1);
-  ssize_t ret = readlink(name.c_str(), &out[0], sb.st_size + 1);
-  if (-1 == ret)
-    return false;
-  if (ret > sb.st_size) {
-    // Increased in size?!
-    return false;
+  // lstat gave us a size, but I've seen it grow, possibly due to symlinks on top of symlinks.
+  while (true) {
+    ssize_t ret = readlink(name.c_str(), &out[0], out.size());
+    if (-1 == ret)
+      return false;
+    if ((size_t)ret < out.size()) {
+      out.resize(ret);
+      break;
+    }
+    // Exponential growth.
+    out.resize(out.size() * 2);
   }
-  out.resize(ret);
   // Don't use the non-file names.
   if (!out.empty() && out[0] != '/')
     return false;
diff --git a/util/file.hh b/util/file.hh
index be88431dd..f2bb319d5 100644
--- a/util/file.hh
+++ b/util/file.hh
@@ -1,7 +1,8 @@
-#ifndef UTIL_FILE__
-#define UTIL_FILE__
+#ifndef UTIL_FILE_H
+#define UTIL_FILE_H
 
 #include "util/exception.hh"
+#include "util/string_piece.hh"
 
 #include <cstddef>
 #include <cstdio>
@@ -106,12 +107,20 @@ void ResizeOrThrow(int fd, uint64_t to);
 std::size_t PartialRead(int fd, void *to, std::size_t size);
 void ReadOrThrow(int fd, void *to, std::size_t size);
 std::size_t ReadOrEOF(int fd, void *to_void, std::size_t size);
-// Positioned: unix only for now.  
-void PReadOrThrow(int fd, void *to, std::size_t size, uint64_t off);
 
 void WriteOrThrow(int fd, const void *data_void, std::size_t size);
 void WriteOrThrow(FILE *to, const void *data, std::size_t size);
 
+/* These call pread/pwrite in a loop.  However, on Windows they call ReadFile/
+ * WriteFile which changes the file pointer.  So it's safe to call ErsatzPRead
+ * and ErsatzPWrite concurrently (or any combination thereof).  But it changes
+ * the file pointer on windows, so it's not safe to call concurrently with
+ * anything that uses the implicit file pointer e.g. the Read/Write functions
+ * above.
+ */
+void ErsatzPRead(int fd, void *to, std::size_t size, uint64_t off);
+void ErsatzPWrite(int fd, const void *data_void, std::size_t size, uint64_t off);
+
 void FSyncOrThrow(int fd);
 
 // Seeking
@@ -125,8 +134,8 @@ std::FILE *FDOpenReadOrThrow(scoped_fd &file);
 // Temporary files
 // Append a / if base is a directory.
 void NormalizeTempPrefix(std::string &base);
-int MakeTemp(const std::string &prefix);
-std::FILE *FMakeTemp(const std::string &prefix);
+int MakeTemp(const StringPiece &prefix);
+std::FILE *FMakeTemp(const StringPiece &prefix);
 
 // dup an fd.
 int DupOrThrow(int fd);
@@ -139,4 +148,4 @@ std::string NameFromFD(int fd);
 
 } // namespace util
 
-#endif // UTIL_FILE__
+#endif // UTIL_FILE_H
diff --git a/util/file_piece.cc b/util/file_piece.cc
index 9c7e00c4c..4aaa250e3 100644
--- a/util/file_piece.cc
+++ b/util/file_piece.cc
@@ -84,6 +84,13 @@ StringPiece FilePiece::ReadLine(char delim) {
   }
 }
 
+bool FilePiece::ReadLineOrEOF(StringPiece &to, char delim) {
+  try {
+    to = ReadLine(delim);
+  } catch (const util::EndOfFileException &e) { return false; }
+  return true;
+}
+
 float FilePiece::ReadFloat() {
   return ReadNumber<float>();
 }
diff --git a/util/file_piece.hh b/util/file_piece.hh
index ed3dc5adf..5495ddccc 100644
--- a/util/file_piece.hh
+++ b/util/file_piece.hh
@@ -1,5 +1,5 @@
-#ifndef UTIL_FILE_PIECE__
-#define UTIL_FILE_PIECE__
+#ifndef UTIL_FILE_PIECE_H
+#define UTIL_FILE_PIECE_H
 
 #include "util/ersatz_progress.hh"
 #include "util/exception.hh"
@@ -56,10 +56,33 @@ class FilePiece {
       return Consume(FindDelimiterOrEOF(delim));
     }
 
+    // Read word until the line or file ends.
+    bool ReadWordSameLine(StringPiece &to, const bool *delim = kSpaces) {
+      assert(delim[static_cast<unsigned char>('\n')]);
+      // Skip non-enter spaces.
+      for (; ; ++position_) {
+        if (position_ == position_end_) {
+          try {
+            Shift();
+          } catch (const util::EndOfFileException &e) { return false; }
+          // And break out at end of file.
+          if (position_ == position_end_) return false;
+        }
+        if (!delim[static_cast<unsigned char>(*position_)]) break;
+        if (*position_ == '\n') return false;
+      }
+      // We can't be at the end of file because there's at least one character open.
+      to = Consume(FindDelimiterOrEOF(delim));
+      return true;
+    }
+
     // Unlike ReadDelimited, this includes leading spaces and consumes the delimiter.
     // It is similar to getline in that way.
     StringPiece ReadLine(char delim = '\n');
 
+    // Doesn't throw EndOfFileException, just returns false.
+    bool ReadLineOrEOF(StringPiece &to, char delim = '\n');
+
     float ReadFloat();
     double ReadDouble();
     long int ReadLong();
@@ -132,4 +155,4 @@ class FilePiece {
 
 } // namespace util
 
-#endif // UTIL_FILE_PIECE__
+#endif // UTIL_FILE_PIECE_H
diff --git a/util/fixed_array.hh b/util/fixed_array.hh
new file mode 100644
index 000000000..416b92f4e
--- /dev/null
+++ b/util/fixed_array.hh
@@ -0,0 +1,153 @@
+#ifndef UTIL_FIXED_ARRAY_H
+#define UTIL_FIXED_ARRAY_H
+
+#include "util/scoped.hh"
+
+#include <cstddef>
+
+#include <assert.h>
+#include <stdlib.h>
+
+namespace util {
+
+/**
+ * Defines a fixed-size collection.
+ *
+ * Ever want an array of things by they don't have a default constructor or are
+ * non-copyable?  FixedArray allows constructing one at a time.
+ */
+template <class T> class FixedArray {
+  public:
+    /** Initialize with a given size bound but do not construct the objects. */
+    explicit FixedArray(std::size_t limit) {
+      Init(limit);
+    }
+
+    /** 
+     * Constructs an instance, but does not initialize it.
+     *
+     * Any objects constructed in this manner must be subsequently @ref FixedArray::Init() "initialized" prior to use.
+     *
+     * @see FixedArray::Init()
+     */
+    FixedArray() 
+      : newed_end_(NULL) 
+#ifndef NDEBUG
+      , allocated_end_(NULL) 
+#endif
+    {}
+
+    /** 
+     * Initialize with a given size bound but do not construct the objects. 
+     *
+     * This method is responsible for allocating memory.
+     * Objects stored in this array will be constructed in a location within this allocated memory.
+     */
+    void Init(std::size_t count) {
+      assert(!block_.get());
+      block_.reset(malloc(sizeof(T) * count));
+      if (!block_.get()) throw std::bad_alloc();
+      newed_end_ = begin();
+#ifndef NDEBUG
+      allocated_end_ = begin() + count;
+#endif
+    }
+
+    /**
+     * Constructs a copy of the provided array.
+     *
+     * @param from Array whose elements should be copied into this newly-constructed data structure.
+     */
+    FixedArray(const FixedArray &from) {
+      std::size_t size = from.newed_end_ - static_cast<const T*>(from.block_.get());
+      Init(size);
+      for (std::size_t i = 0; i < size; ++i) {
+        push_back(from[i]);
+      }
+    }
+
+    /**
+     * Frees the memory held by this object.
+     */
+    ~FixedArray() { clear(); }
+
+    /** Gets a pointer to the first object currently stored in this data structure. */
+    T *begin() { return static_cast<T*>(block_.get()); }
+  
+    /** Gets a const pointer to the last object currently stored in this data structure. */
+    const T *begin() const { return static_cast<const T*>(block_.get()); }
+    
+    /** Gets a pointer to the last object currently stored in this data structure. */
+    T *end() { return newed_end_; }
+  
+    /** Gets a const pointer to the last object currently stored in this data structure. */
+    const T *end() const { return newed_end_; }
+
+    /** Gets a reference to the last object currently stored in this data structure. */
+    T &back() { return *(end() - 1); }
+  
+    /** Gets a const reference to the last object currently stored in this data structure. */
+    const T &back() const { return *(end() - 1); }
+
+    /** Gets the number of objects currently stored in this data structure. */
+    std::size_t size() const { return end() - begin(); }
+  
+    /** Returns true if there are no objects currently stored in this data structure. */
+    bool empty() const { return begin() == end(); }
+
+    /** 
+     * Gets a reference to the object with index i currently stored in this data structure. 
+     *
+     * @param i Index of the object to reference
+     */
+    T &operator[](std::size_t i) { return begin()[i]; }
+  
+    /** 
+     * Gets a const reference to the object with index i currently stored in this data structure. 
+     *
+     * @param i Index of the object to reference
+     */
+    const T &operator[](std::size_t i) const { return begin()[i]; }
+
+    /**
+     * Constructs a new object using the provided parameter,
+     * and stores it in this data structure.
+     *
+     * The memory backing the constructed object is managed by this data structure.
+     */
+    template <class C> void push_back(const C &c) {
+      new (end()) T(c); // use "placement new" syntax to initalize T in an already-allocated memory location
+      Constructed();
+    }
+
+    /**
+     * Removes all elements from this array.
+     */
+    void clear() {
+      for (T *i = begin(); i != end(); ++i)
+        i->~T();
+      newed_end_ = begin();
+    }
+
+  protected:
+    // Always call Constructed after successful completion of new.
+    void Constructed() {
+      ++newed_end_;
+#ifndef NDEBUG
+      assert(newed_end_ <= allocated_end_);
+#endif
+    }
+
+  private:
+    util::scoped_malloc block_;
+
+    T *newed_end_;
+
+#ifndef NDEBUG
+    T *allocated_end_;
+#endif
+};
+
+} // namespace util
+
+#endif // UTIL_FIXED_ARRAY_H
diff --git a/util/getopt.hh b/util/getopt.hh
index 6ad977324..50eab56f4 100644
--- a/util/getopt.hh
+++ b/util/getopt.hh
@@ -11,8 +11,8 @@ Code given out at the 1985 UNIFORUM conference in Dallas.
 #endif
 #ifndef __GNUC__
 
-#ifndef _WINGETOPT_H_
-#define _WINGETOPT_H_
+#ifndef UTIL_GETOPT_H
+#define UTIL_GETOPT_H
 
 #ifdef __cplusplus
 extern "C" {
@@ -28,6 +28,6 @@ extern int getopt(int argc, char **argv, char *opts);
 }
 #endif
 
-#endif  /* _GETOPT_H_ */
+#endif  /* UTIL_GETOPT_H */
 #endif  /* __GNUC__ */
 
diff --git a/util/have.hh b/util/have.hh
index 6e18529d2..dc3f63303 100644
--- a/util/have.hh
+++ b/util/have.hh
@@ -1,6 +1,6 @@
 /* Optional packages.  You might want to integrate this with your build system e.g. config.h from ./configure. */
-#ifndef UTIL_HAVE__
-#define UTIL_HAVE__
+#ifndef UTIL_HAVE_H
+#define UTIL_HAVE_H
 
 #ifdef HAVE_CONFIG_H
 #include "config.h"
@@ -10,4 +10,4 @@
 //#define HAVE_ICU
 #endif
 
-#endif // UTIL_HAVE__
+#endif // UTIL_HAVE_H
diff --git a/util/joint_sort.hh b/util/joint_sort.hh
index b1ec48e26..de4b554ff 100644
--- a/util/joint_sort.hh
+++ b/util/joint_sort.hh
@@ -1,5 +1,5 @@
-#ifndef UTIL_JOINT_SORT__
-#define UTIL_JOINT_SORT__
+#ifndef UTIL_JOINT_SORT_H
+#define UTIL_JOINT_SORT_H
 
 /* A terrifying amount of C++ to coax std::sort into soring one range while
  * also permuting another range the same way.
@@ -143,4 +143,4 @@ template <class KeyIter, class ValueIter> void JointSort(const KeyIter &key_begi
 
 } // namespace util
 
-#endif // UTIL_JOINT_SORT__
+#endif // UTIL_JOINT_SORT_H
diff --git a/util/mmap.cc b/util/mmap.cc
index cee6a9709..a3c8a0225 100644
--- a/util/mmap.cc
+++ b/util/mmap.cc
@@ -6,6 +6,7 @@
 
 #include "util/exception.hh"
 #include "util/file.hh"
+#include "util/parallel_read.hh"
 #include "util/scoped.hh"
 
 #include <iostream>
@@ -40,7 +41,7 @@ void SyncOrThrow(void *start, size_t length) {
 #if defined(_WIN32) || defined(_WIN64)
   UTIL_THROW_IF(!::FlushViewOfFile(start, length), ErrnoException, "Failed to sync mmap");
 #else
-  UTIL_THROW_IF(msync(start, length, MS_SYNC), ErrnoException, "Failed to sync mmap");
+  UTIL_THROW_IF(length && msync(start, length, MS_SYNC), ErrnoException, "Failed to sync mmap");
 #endif
 }
 
@@ -154,6 +155,10 @@ void MapRead(LoadMethod method, int fd, uint64_t offset, std::size_t size, scope
       SeekOrThrow(fd, offset);
       ReadOrThrow(fd, out.get(), size);
       break;
+    case PARALLEL_READ:
+      out.reset(MallocOrThrow(size), size, scoped_memory::MALLOC_ALLOCATED);
+      ParallelRead(fd, out.get(), size, offset);
+      break;
   }
 }
 
@@ -189,4 +194,66 @@ void *MapZeroedWrite(const char *name, std::size_t size, scoped_fd &file) {
   }
 }
 
+Rolling::Rolling(const Rolling &copy_from, uint64_t increase) {
+  *this = copy_from;
+  IncreaseBase(increase);
+}
+
+Rolling &Rolling::operator=(const Rolling &copy_from) {
+  fd_ = copy_from.fd_;
+  file_begin_ = copy_from.file_begin_;
+  file_end_ = copy_from.file_end_;
+  for_write_ = copy_from.for_write_;
+  block_ = copy_from.block_;
+  read_bound_ = copy_from.read_bound_;
+
+  current_begin_ = 0;
+  if (copy_from.IsPassthrough()) {
+    current_end_ = copy_from.current_end_;
+    ptr_ = copy_from.ptr_;
+  } else {
+    // Force call on next mmap.
+    current_end_ = 0;
+    ptr_ = NULL;
+  }
+  return *this;
+}
+
+Rolling::Rolling(int fd, bool for_write, std::size_t block, std::size_t read_bound, uint64_t offset, uint64_t amount) {
+  current_begin_ = 0;
+  current_end_ = 0;
+  fd_ = fd;
+  file_begin_ = offset;
+  file_end_ = offset + amount;
+  for_write_ = for_write;
+  block_ = block;
+  read_bound_ = read_bound;
+}
+
+void *Rolling::ExtractNonRolling(scoped_memory &out, uint64_t index, std::size_t size) {
+  out.reset();
+  if (IsPassthrough()) return static_cast<uint8_t*>(get()) + index;
+  uint64_t offset = index + file_begin_;
+  // Round down to multiple of page size.
+  uint64_t cruft = offset % static_cast<uint64_t>(SizePage());
+  std::size_t map_size = static_cast<std::size_t>(size + cruft);
+  out.reset(MapOrThrow(map_size, for_write_, kFileFlags, true, fd_, offset - cruft), map_size, scoped_memory::MMAP_ALLOCATED);
+  return static_cast<uint8_t*>(out.get()) + static_cast<std::size_t>(cruft);
+}
+
+void Rolling::Roll(uint64_t index) {
+  assert(!IsPassthrough());
+  std::size_t amount;
+  if (file_end_ - (index + file_begin_) > static_cast<uint64_t>(block_)) {
+    amount = block_;
+    current_end_ = index + amount - read_bound_;
+  } else {
+    amount = file_end_ - (index + file_begin_);
+    current_end_ = index + amount;
+  }
+  ptr_ = static_cast<uint8_t*>(ExtractNonRolling(mem_, index, amount)) - index;
+
+  current_begin_ = index;
+}
+
 } // namespace util
diff --git a/util/mmap.hh b/util/mmap.hh
index b218c4d19..9b1e120f3 100644
--- a/util/mmap.hh
+++ b/util/mmap.hh
@@ -1,8 +1,9 @@
-#ifndef UTIL_MMAP__
-#define UTIL_MMAP__
+#ifndef UTIL_MMAP_H
+#define UTIL_MMAP_H
 // Utilities for mmaped files.  
 
 #include <cstddef>
+#include <limits>
 
 #include <stdint.h>
 #include <sys/types.h>
@@ -52,6 +53,9 @@ class scoped_memory {
   public:
     typedef enum {MMAP_ALLOCATED, ARRAY_ALLOCATED, MALLOC_ALLOCATED, NONE_ALLOCATED} Alloc;
 
+    scoped_memory(void *data, std::size_t size, Alloc source) 
+      : data_(data), size_(size), source_(source) {}
+
     scoped_memory() : data_(NULL), size_(0), source_(NONE_ALLOCATED) {}
 
     ~scoped_memory() { reset(); }
@@ -72,7 +76,6 @@ class scoped_memory {
     void call_realloc(std::size_t to);
 
   private:
-
     void *data_;
     std::size_t size_;
 
@@ -90,7 +93,9 @@ typedef enum {
   // Populate on Linux.  malloc and read on non-Linux.  
   POPULATE_OR_READ,
   // malloc and read.  
-  READ
+  READ,
+  // malloc and read in parallel (recommended for Lustre)
+  PARALLEL_READ,
 } LoadMethod;
 
 extern const int kFileFlags;
@@ -109,6 +114,79 @@ void *MapZeroedWrite(const char *name, std::size_t size, scoped_fd &file);
 // msync wrapper 
 void SyncOrThrow(void *start, size_t length);
 
+// Forward rolling memory map with no overlap.
+class Rolling {
+  public:
+    Rolling() {}
+    
+    explicit Rolling(void *data) { Init(data); }
+
+    Rolling(const Rolling &copy_from, uint64_t increase = 0);
+    Rolling &operator=(const Rolling &copy_from);
+
+    // For an actual rolling mmap.
+    explicit Rolling(int fd, bool for_write, std::size_t block, std::size_t read_bound, uint64_t offset, uint64_t amount);
+
+    // For a static mapping
+    void Init(void *data) {
+      ptr_ = data;
+      current_end_ = std::numeric_limits<uint64_t>::max();
+      current_begin_ = 0;
+      // Mark as a pass-through.
+      fd_ = -1;
+    }
+
+    void IncreaseBase(uint64_t by) {
+      file_begin_ += by;
+      ptr_ = static_cast<uint8_t*>(ptr_) + by;
+      if (!IsPassthrough()) current_end_ = 0;
+    }
+
+    void DecreaseBase(uint64_t by) {
+      file_begin_ -= by;
+      ptr_ = static_cast<uint8_t*>(ptr_) - by;
+      if (!IsPassthrough()) current_end_ = 0;
+    }
+
+    void *ExtractNonRolling(scoped_memory &out, uint64_t index, std::size_t size);
+
+    // Returns base pointer
+    void *get() const { return ptr_; }
+
+    // Returns base pointer.
+    void *CheckedBase(uint64_t index) {
+      if (index >= current_end_ || index < current_begin_) {
+        Roll(index);
+      }
+      return ptr_;
+    }
+    
+    // Returns indexed pointer.
+    void *CheckedIndex(uint64_t index) {
+      return static_cast<uint8_t*>(CheckedBase(index)) + index;
+    }
+
+  private:
+    void Roll(uint64_t index);
+
+    // True if this is just a thin wrapper on a pointer.
+    bool IsPassthrough() const { return fd_ == -1; }
+
+    void *ptr_;
+    uint64_t current_begin_;
+    uint64_t current_end_;
+    
+    scoped_memory mem_;
+
+    int fd_;
+    uint64_t file_begin_;
+    uint64_t file_end_;
+
+    bool for_write_;
+    std::size_t block_;
+    std::size_t read_bound_;
+};
+
 } // namespace util
 
-#endif // UTIL_MMAP__
+#endif // UTIL_MMAP_H
diff --git a/util/multi_intersection.hh b/util/multi_intersection.hh
index 04678352d..2955acc72 100644
--- a/util/multi_intersection.hh
+++ b/util/multi_intersection.hh
@@ -1,5 +1,5 @@
-#ifndef UTIL_MULTI_INTERSECTION__
-#define UTIL_MULTI_INTERSECTION__
+#ifndef UTIL_MULTI_INTERSECTION_H
+#define UTIL_MULTI_INTERSECTION_H
 
 #include <boost/optional.hpp>
 #include <boost/range/iterator_range.hpp>
@@ -77,4 +77,4 @@ template <class Iterator, class Output> void AllIntersection(std::vector<boost::
 
 } // namespace util
 
-#endif // UTIL_MULTI_INTERSECTION__
+#endif // UTIL_MULTI_INTERSECTION_H
diff --git a/util/murmur_hash.hh b/util/murmur_hash.hh
index 4891833e9..f17157cd9 100644
--- a/util/murmur_hash.hh
+++ b/util/murmur_hash.hh
@@ -1,5 +1,5 @@
-#ifndef UTIL_MURMUR_HASH__
-#define UTIL_MURMUR_HASH__
+#ifndef UTIL_MURMUR_HASH_H
+#define UTIL_MURMUR_HASH_H
 #include <cstddef>
 #include <stdint.h>
 
@@ -15,4 +15,4 @@ uint64_t MurmurHashNative(const void * key, std::size_t len, uint64_t seed = 0);
 
 } // namespace util
 
-#endif // UTIL_MURMUR_HASH__
+#endif // UTIL_MURMUR_HASH_H
diff --git a/util/parallel_read.cc b/util/parallel_read.cc
new file mode 100644
index 000000000..6435eb843
--- /dev/null
+++ b/util/parallel_read.cc
@@ -0,0 +1,69 @@
+#include "util/parallel_read.hh"
+
+#include "util/file.hh"
+
+#ifdef WITH_THREADS
+#include "util/thread_pool.hh"
+
+namespace util {
+namespace {
+
+class Reader {
+  public:
+    explicit Reader(int fd) : fd_(fd) {}
+
+    struct Request {
+      void *to;
+      std::size_t size;
+      uint64_t offset;
+
+      bool operator==(const Request &other) const {
+        return (to == other.to) && (size == other.size) && (offset == other.offset);
+      }
+    };
+
+    void operator()(const Request &request) {
+      util::ErsatzPRead(fd_, request.to, request.size, request.offset);
+    }
+
+  private:
+    int fd_;
+};
+
+} // namespace
+
+void ParallelRead(int fd, void *to, std::size_t amount, uint64_t offset) {
+  Reader::Request poison;
+  poison.to = NULL;
+  poison.size = 0;
+  poison.offset = 0;
+  unsigned threads = boost::thread::hardware_concurrency();
+  if (!threads) threads = 2;
+  ThreadPool<Reader> pool(2 /* don't need much of a queue */, threads, fd, poison);
+  const std::size_t kBatch = 1ULL << 25; // 32 MB
+  Reader::Request request;
+  request.to = to;
+  request.size = kBatch;
+  request.offset = offset;
+  for (; amount > kBatch; amount -= kBatch) {
+    pool.Produce(request);
+    request.to = reinterpret_cast<uint8_t*>(request.to) + kBatch;
+    request.offset += kBatch;
+  }
+  request.size = amount;
+  if (request.size) {
+    pool.Produce(request);
+  }
+}
+
+} // namespace util
+
+#else // WITH_THREADS
+
+namespace util {
+void ParallelRead(int fd, void *to, std::size_t amount, uint64_t offset) {
+ util::ErsatzPRead(fd, to, amount, offset);
+}
+} // namespace util
+
+#endif
diff --git a/util/parallel_read.hh b/util/parallel_read.hh
new file mode 100644
index 000000000..1e96e7903
--- /dev/null
+++ b/util/parallel_read.hh
@@ -0,0 +1,16 @@
+#ifndef UTIL_PARALLEL_READ__
+#define UTIL_PARALLEL_READ__
+
+/* Read pieces of a file in parallel.  This has a very specific use case:
+ * reading files from Lustre is CPU bound so multiple threads actually
+ * increases throughput.  Speed matters when an LM takes a terabyte.
+ */
+
+#include <cstddef>
+#include <stdint.h>
+
+namespace util {
+void ParallelRead(int fd, void *to, std::size_t amount, uint64_t offset);
+} // namespace util
+
+#endif // UTIL_PARALLEL_READ__
diff --git a/util/pcqueue.hh b/util/pcqueue.hh
index 07e4146f5..d2ffee777 100644
--- a/util/pcqueue.hh
+++ b/util/pcqueue.hh
@@ -1,5 +1,5 @@
-#ifndef UTIL_PCQUEUE__
-#define UTIL_PCQUEUE__
+#ifndef UTIL_PCQUEUE_H
+#define UTIL_PCQUEUE_H
 
 #include "util/exception.hh"
 
@@ -72,7 +72,8 @@ inline void WaitSemaphore (Semaphore &on) {
 
 #endif // __APPLE__
 
-/* Producer consumer queue safe for multiple producers and multiple consumers.
+/**
+ * Producer consumer queue safe for multiple producers and multiple consumers.
  * T must be default constructable and have operator=.  
  * The value is copied twice for Consume(T &out) or three times for Consume(),
  * so larger objects should be passed via pointer.
@@ -152,4 +153,4 @@ template <class T> class PCQueue : boost::noncopyable {
 
 } // namespace util
 
-#endif // UTIL_PCQUEUE__
+#endif // UTIL_PCQUEUE_H
diff --git a/util/pool.hh b/util/pool.hh
index 72f8a0c8b..89e793d7e 100644
--- a/util/pool.hh
+++ b/util/pool.hh
@@ -1,8 +1,8 @@
 // Very simple pool.  It can only allocate memory.  And all of the memory it
 // allocates must be freed at the same time.  
 
-#ifndef UTIL_POOL__
-#define UTIL_POOL__
+#ifndef UTIL_POOL_H
+#define UTIL_POOL_H
 
 #include <vector>
 
@@ -42,4 +42,4 @@ class Pool {
 
 } // namespace util
 
-#endif // UTIL_POOL__
+#endif // UTIL_POOL_H
diff --git a/util/probing_hash_table.hh b/util/probing_hash_table.hh
index 38524806c..ea228dd9a 100644
--- a/util/probing_hash_table.hh
+++ b/util/probing_hash_table.hh
@@ -1,5 +1,5 @@
-#ifndef UTIL_PROBING_HASH_TABLE__
-#define UTIL_PROBING_HASH_TABLE__
+#ifndef UTIL_PROBING_HASH_TABLE_H
+#define UTIL_PROBING_HASH_TABLE_H
 
 #include "util/exception.hh"
 #include "util/scoped.hh"
@@ -258,6 +258,10 @@ template <class EntryT, class HashT, class EqualT = std::equal_to<typename Entry
   private:
     typedef ProbingHashTable<EntryT, HashT, EqualT> Backend;
   public:
+    static std::size_t MemUsage(std::size_t size, float multiplier = 1.5) {
+      return Backend::Size(size, multiplier);
+    }
+
     typedef EntryT Entry;
     typedef typename Entry::Key Key;
     typedef const Entry *ConstIterator;
@@ -268,6 +272,7 @@ template <class EntryT, class HashT, class EqualT = std::equal_to<typename Entry
     AutoProbing(std::size_t initial_size = 10, const Key &invalid = Key(), const Hash &hash_func = Hash(), const Equal &equal_func = Equal()) :
       allocated_(Backend::Size(initial_size, 1.5)), mem_(util::MallocOrThrow(allocated_)), backend_(mem_.get(), allocated_, invalid, hash_func, equal_func) {
       threshold_ = initial_size * 1.2;
+      Clear();
     }
 
     // Assumes that the key is unique.  Multiple insertions won't cause a failure, just inconsistent lookup.
@@ -323,4 +328,4 @@ template <class EntryT, class HashT, class EqualT = std::equal_to<typename Entry
 
 } // namespace util
 
-#endif // UTIL_PROBING_HASH_TABLE__
+#endif // UTIL_PROBING_HASH_TABLE_H
diff --git a/util/proxy_iterator.hh b/util/proxy_iterator.hh
index a2810a472..8aa697bf1 100644
--- a/util/proxy_iterator.hh
+++ b/util/proxy_iterator.hh
@@ -1,5 +1,5 @@
-#ifndef UTIL_PROXY_ITERATOR__
-#define UTIL_PROXY_ITERATOR__
+#ifndef UTIL_PROXY_ITERATOR_H
+#define UTIL_PROXY_ITERATOR_H
 
 #include <cstddef>
 #include <iterator>
@@ -98,4 +98,4 @@ template <class Proxy> ProxyIterator<Proxy> operator+(std::ptrdiff_t amount, con
 
 } // namespace util
 
-#endif // UTIL_PROXY_ITERATOR__
+#endif // UTIL_PROXY_ITERATOR_H
diff --git a/util/read_compressed.hh b/util/read_compressed.hh
index 8b54c9e82..763e6bbd3 100644
--- a/util/read_compressed.hh
+++ b/util/read_compressed.hh
@@ -1,5 +1,5 @@
-#ifndef UTIL_READ_COMPRESSED__
-#define UTIL_READ_COMPRESSED__
+#ifndef UTIL_READ_COMPRESSED_H
+#define UTIL_READ_COMPRESSED_H
 
 #include "util/exception.hh"
 #include "util/scoped.hh"
@@ -78,4 +78,4 @@ class ReadCompressed {
 
 } // namespace util
 
-#endif // UTIL_READ_COMPRESSED__
+#endif // UTIL_READ_COMPRESSED_H
diff --git a/util/scoped.hh b/util/scoped.hh
index b642d0649..ae70b6b53 100644
--- a/util/scoped.hh
+++ b/util/scoped.hh
@@ -1,5 +1,5 @@
-#ifndef UTIL_SCOPED__
-#define UTIL_SCOPED__
+#ifndef UTIL_SCOPED_H
+#define UTIL_SCOPED_H
 /* Other scoped objects in the style of scoped_ptr. */
 
 #include "util/exception.hh"
@@ -101,4 +101,4 @@ template <class T> class scoped_ptr {
 
 } // namespace util
 
-#endif // UTIL_SCOPED__
+#endif // UTIL_SCOPED_H
diff --git a/util/sized_iterator.hh b/util/sized_iterator.hh
index a72657b50..75f6886f7 100644
--- a/util/sized_iterator.hh
+++ b/util/sized_iterator.hh
@@ -1,5 +1,5 @@
-#ifndef UTIL_SIZED_ITERATOR__
-#define UTIL_SIZED_ITERATOR__
+#ifndef UTIL_SIZED_ITERATOR_H
+#define UTIL_SIZED_ITERATOR_H
 
 #include "util/proxy_iterator.hh"
 
@@ -117,4 +117,4 @@ template <class Delegate, class Proxy = SizedProxy> class SizedCompare : public
 };
 
 } // namespace util
-#endif // UTIL_SIZED_ITERATOR__
+#endif // UTIL_SIZED_ITERATOR_H
diff --git a/util/sorted_uniform.hh b/util/sorted_uniform.hh
index 7700d9e64..a7dba5e39 100644
--- a/util/sorted_uniform.hh
+++ b/util/sorted_uniform.hh
@@ -1,5 +1,5 @@
-#ifndef UTIL_SORTED_UNIFORM__
-#define UTIL_SORTED_UNIFORM__
+#ifndef UTIL_SORTED_UNIFORM_H
+#define UTIL_SORTED_UNIFORM_H
 
 #include <algorithm>
 #include <cstddef>
@@ -124,4 +124,4 @@ template <class Iterator, class Accessor> Iterator BinaryBelow(
 
 } // namespace util
 
-#endif // UTIL_SORTED_UNIFORM__
+#endif // UTIL_SORTED_UNIFORM_H
diff --git a/util/stream/block.hh b/util/stream/block.hh
index 11aa991e4..aa7e28bb1 100644
--- a/util/stream/block.hh
+++ b/util/stream/block.hh
@@ -1,5 +1,5 @@
-#ifndef UTIL_STREAM_BLOCK__
-#define UTIL_STREAM_BLOCK__
+#ifndef UTIL_STREAM_BLOCK_H
+#define UTIL_STREAM_BLOCK_H
 
 #include <cstddef>
 #include <stdint.h>
@@ -7,28 +7,77 @@
 namespace util {
 namespace stream {
 
+/**
+ * Encapsulates a block of memory.
+ */
 class Block {
   public:
+  
+    /** 
+     * Constructs an empty block. 
+     */
     Block() : mem_(NULL), valid_size_(0) {}
 
+    /** 
+     * Constructs a block that encapsulates a segment of memory.
+     *
+     * @param[in] mem  The segment of memory to encapsulate
+     * @param[in] size The size of the memory segment in bytes
+     */
     Block(void *mem, std::size_t size) : mem_(mem), valid_size_(size) {}
 
+    /**
+     * Set the number of bytes in this block that should be interpreted as valid.
+     *
+     * @param[in] to Number of bytes
+     */
     void SetValidSize(std::size_t to) { valid_size_ = to; }
-    // Read might fill in less than Allocated at EOF.   
+
+    /** 
+     * Gets the number of bytes in this block that should be interpreted as valid.
+     * This is important because read might fill in less than Allocated at EOF. 
+     */
     std::size_t ValidSize() const { return valid_size_; }
 
+    /** Gets a void pointer to the memory underlying this block. */
     void *Get() { return mem_; }
+
+    /** Gets a const void pointer to the memory underlying this block. */
     const void *Get() const { return mem_; }
 
+  
+    /**
+     * Gets a const void pointer to the end of the valid section of memory
+     * encapsulated by this block.
+     */
     const void *ValidEnd() const { 
       return reinterpret_cast<const uint8_t*>(mem_) + valid_size_;
     }
 
+    /**
+     * Returns true if this block encapsulates a valid (non-NULL) block of memory.
+     * 
+     * This method is a user-defined implicit conversion function to boolean;
+     * among other things, this method enables bare instances of this class 
+     * to be used as the condition of an if statement.
+     */
     operator bool() const { return mem_ != NULL; }
+  
+    /**
+     * Returns true if this block is empty.
+     * 
+     * In other words, if Get()==NULL, this method will return true.
+     */
     bool operator!() const { return mem_ == NULL; }
  
   private:
     friend class Link;
+  
+    /**
+     * Points this block's memory at NULL.
+     *
+     * This class defines poison as a block whose memory pointer is NULL.
+     */
     void SetToPoison() {
       mem_ = NULL;
     }
@@ -40,4 +89,4 @@ class Block {
 } // namespace stream
 } // namespace util
 
-#endif // UTIL_STREAM_BLOCK__
+#endif // UTIL_STREAM_BLOCK_H
diff --git a/util/stream/chain.cc b/util/stream/chain.cc
index 46708c601..4596af7ae 100644
--- a/util/stream/chain.cc
+++ b/util/stream/chain.cc
@@ -59,6 +59,11 @@ Chain &Chain::operator>>(const WriteAndRecycle &writer) {
   return *this;
 }
 
+Chain &Chain::operator>>(const PWriteAndRecycle &writer) {
+  threads_.push_back(new Thread(Complete(), writer));
+  return *this;
+}
+
 void Chain::Wait(bool release_memory) {
   if (queues_.empty()) {
     assert(threads_.empty());
@@ -126,7 +131,12 @@ Link::~Link() {
 //    abort();
   } else {
     if (!poisoned_) {
-      // Pass the poison!
+      // Poison is a block whose memory pointer is NULL.
+      //
+      // Because we're in the else block,
+      //   we know that the memory pointer of current_ is NULL.
+      //
+      // Pass the current (poison) block!
       out_->Produce(current_);
     }
   }
diff --git a/util/stream/chain.hh b/util/stream/chain.hh
index 0cc83a852..508650860 100644
--- a/util/stream/chain.hh
+++ b/util/stream/chain.hh
@@ -1,5 +1,5 @@
-#ifndef UTIL_STREAM_CHAIN__
-#define UTIL_STREAM_CHAIN__
+#ifndef UTIL_STREAM_CHAIN_H
+#define UTIL_STREAM_CHAIN_H
 
 #include "util/stream/block.hh"
 #include "util/stream/config.hh"
@@ -24,7 +24,12 @@ class ChainConfigException : public Exception {
 };
 
 class Chain;
-// Specifies position in chain for Link constructor.
+  
+/**
+ * Encapsulates a @ref PCQueue "producer queue" and a @ref PCQueue "consumer queue" within a @ref Chain "chain".
+ * 
+ * Specifies position in chain for Link constructor.
+ */
 class ChainPosition {
   public:
     const Chain &GetChain() const { return *chain_; }
@@ -41,14 +46,32 @@ class ChainPosition {
     WorkerProgress progress_;
 };
 
-// Position is usually ChainPosition but if there are multiple streams involved, this can be ChainPositions.  
+ 
+/**
+ * Encapsulates a worker thread processing data at a given position in the chain.
+ *
+ * Each instance of this class owns one boost thread in which the worker is Run().
+ */
 class Thread {
   public:
+    
+    /**
+     * Constructs a new Thread in which the provided Worker is Run().
+     *
+     * Position is usually ChainPosition but if there are multiple streams involved, this can be ChainPositions.
+     *
+     * After a call to this constructor, the provided worker will be running within a boost thread owned by the newly constructed Thread object.
+     */
     template <class Position, class Worker> Thread(const Position &position, const Worker &worker)
       : thread_(boost::ref(*this), position, worker) {}
 
     ~Thread();
 
+    /**
+     * Launches the provided worker in this object's boost thread.
+     *
+     * This method is called automatically by this class's @ref Thread() "constructor".
+     */
     template <class Position, class Worker> void operator()(const Position &position, Worker &worker) {
       try {
         worker.Run(position);
@@ -63,14 +86,27 @@ class Thread {
     boost::thread thread_;
 };
 
+/**
+ * This resets blocks to full valid size.  Used to close the loop in Chain by recycling blocks.
+ */
 class Recycler {
   public:
+    /**
+     * Resets the blocks in the chain such that the blocks' respective valid sizes match the chain's block size.
+     *
+     * @see Block::SetValidSize()
+     * @see Chain::BlockSize()
+     */
     void Run(const ChainPosition &position);
 };
 
 extern const Recycler kRecycle;
 class WriteAndRecycle;
-
+class PWriteAndRecycle;
+  
+/**
+ * Represents a sequence of workers, through which @ref Block "blocks" can pass.
+ */
 class Chain {
   private:
     template <class T, void (T::*ptr)(const ChainPosition &) = &T::Run> struct CheckForRun {
@@ -78,8 +114,20 @@ class Chain {
     };
 
   public:
+  
+    /** 
+     * Constructs a configured Chain.
+     * 
+     * @param config Specifies how to configure the Chain.
+     */
     explicit Chain(const ChainConfig &config);
 
+    /**
+     * Destructs a Chain.
+     *
+     * This method waits for the chain's threads to complete,
+     * and frees the memory held by this chain.
+     */
     ~Chain();
 
     void ActivateProgress() {
@@ -91,24 +139,49 @@ class Chain {
       progress_.SetTarget(target);
     }
 
+    /**
+     * Gets the number of bytes in each record of a Block.
+     *
+     * @see ChainConfig::entry_size
+     */
     std::size_t EntrySize() const {
       return config_.entry_size;
     }
+  
+    /**
+     * Gets the inital @ref Block::ValidSize "valid size" for @ref Block "blocks" in this chain.
+     *
+     * @see Block::ValidSize
+     */
     std::size_t BlockSize() const {
       return block_size_;
     }
 
-    // Two ways to add to the chain: Add() or operator>>.  
+    /** Two ways to add to the chain: Add() or operator>>. */
     ChainPosition Add();
 
-    // This is for adding threaded workers with a Run method.  
+    /** 
+     * Adds a new worker to this chain,
+     * and runs that worker in a new Thread owned by this chain.
+     * 
+     * The worker must have a Run method that accepts a position argument.
+     *
+     * @see Thread::operator()()
+     */
     template <class Worker> typename CheckForRun<Worker>::type &operator>>(const Worker &worker) {
       assert(!complete_called_);
       threads_.push_back(new Thread(Add(), worker));
       return *this;
     }
 
-    // Avoid copying the worker.  
+  /** 
+   * Adds a new worker to this chain (but avoids copying that worker),
+   * and runs that worker in a new Thread owned by this chain.
+   * 
+   * The worker must have a Run method that accepts a position argument.
+   *
+   * @see Thread::operator()()
+   */
     template <class Worker> typename CheckForRun<Worker>::type &operator>>(const boost::reference_wrapper<Worker> &worker) {
       assert(!complete_called_);
       threads_.push_back(new Thread(Add(), worker));
@@ -122,12 +195,21 @@ class Chain {
       threads_.push_back(new Thread(Complete(), kRecycle));
     }
 
+    /** 
+     * Adds a Recycler worker to this chain,
+     * and runs that worker in a new Thread owned by this chain.
+     */
     Chain &operator>>(const Recycler &) {
       CompleteLoop();
       return *this;
     }
 
+    /** 
+     * Adds a WriteAndRecycle worker to this chain,
+     * and runs that worker in a new Thread owned by this chain.
+     */
     Chain &operator>>(const WriteAndRecycle &writer);
+    Chain &operator>>(const PWriteAndRecycle &writer);
 
     // Chains are reusable.  Call Wait to wait for everything to finish and free memory.  
     void Wait(bool release_memory = true);
@@ -156,28 +238,87 @@ class Chain {
 };
 
 // Create the link in the worker thread using the position token.
+/** 
+ * Represents a C++ style iterator over @ref Block "blocks".
+ */
 class Link {
   public:
+  
     // Either default construct and Init or just construct all at once.
+  
+    /**
+     * Constructs an @ref Init "initialized" link.
+     *
+     * @see Init
+     */
+    explicit Link(const ChainPosition &position);
+  
+    /** 
+     * Constructs a link that must subsequently be @ref Init "initialized". 
+     *
+     * @see Init
+     */
     Link();
+  
+    /** 
+     * Initializes the link with the input @ref PCQueue "consumer queue" and output @ref PCQueue "producer queue" at a given @ref ChainPosition "position" in the @ref Chain "chain".
+     *
+     * @see Link()
+     */
     void Init(const ChainPosition &position);
 
-    explicit Link(const ChainPosition &position);
-
+    /**
+     * Destructs the link object.
+     *
+     * If necessary, this method will pass a poison block 
+     * to this link's output @ref PCQueue "producer queue".
+     *
+     * @see Block::SetToPoison()
+     */
     ~Link();
 
+    /**
+     * Gets a reference to the @ref Block "block" at this link.
+     */
     Block &operator*() { return current_; }
+
+    /**
+     * Gets a const reference to the @ref Block "block" at this link.
+     */
     const Block &operator*() const { return current_; }
 
+    /**
+     * Gets a pointer to the @ref Block "block" at this link.
+     */
     Block *operator->() { return &current_; }
+  
+    /**
+     * Gets a const pointer to the @ref Block "block" at this link.
+     */
     const Block *operator->() const { return &current_; }
 
+    /**
+     * Gets the link at the next @ref ChainPosition "position" in the @ref Chain "chain".
+     */
     Link &operator++();
 
+    /**
+     * Returns true if the @ref Block "block" at this link encapsulates a valid (non-NULL) block of memory.
+     * 
+     * This method is a user-defined implicit conversion function to boolean;
+     * among other things, this method enables bare instances of this class 
+     * to be used as the condition of an if statement.
+     */
     operator bool() const { return current_; }
 
+    /** 
+     * @ref Block::SetToPoison() "Poisons" the @ref Block "block" at this link,
+     * and passes this now-poisoned block to this link's output @ref PCQueue "producer queue".
+     *
+     * @see Block::SetToPoison()
+     */
     void Poison();
-
+  
   private:
     Block current_;
     PCQueue<Block> *in_, *out_;
@@ -195,4 +336,4 @@ inline Chain &operator>>(Chain &chain, Link &link) {
 } // namespace stream
 } // namespace util
 
-#endif // UTIL_STREAM_CHAIN__
+#endif // UTIL_STREAM_CHAIN_H
diff --git a/util/stream/config.hh b/util/stream/config.hh
index 1eeb3a8a1..6bad36bc5 100644
--- a/util/stream/config.hh
+++ b/util/stream/config.hh
@@ -1,32 +1,63 @@
-#ifndef UTIL_STREAM_CONFIG__
-#define UTIL_STREAM_CONFIG__
+#ifndef UTIL_STREAM_CONFIG_H
+#define UTIL_STREAM_CONFIG_H
 
 #include <cstddef>
 #include <string>
 
 namespace util { namespace stream {
 
+/**
+ * Represents how a chain should be configured.
+ */
 struct ChainConfig {
+  
+  /** Constructs an configuration with underspecified (or default) parameters. */
   ChainConfig() {}
 
+  /** 
+   * Constructs a chain configuration object.
+   *
+   * @param [in] in_entry_size   Number of bytes in each record.
+   * @param [in] in_block_count  Number of blocks in the chain.
+   * @param [in] in_total_memory Total number of bytes available to the chain.
+   *             This value will be divided amongst the blocks in the chain.
+   */
   ChainConfig(std::size_t in_entry_size, std::size_t in_block_count, std::size_t in_total_memory)
     : entry_size(in_entry_size), block_count(in_block_count), total_memory(in_total_memory) {}
 
+  /**
+   * Number of bytes in each record.
+   */
   std::size_t entry_size;
+  
+  /**
+   * Number of blocks in the chain.
+   */
   std::size_t block_count;
-  // Chain's constructor will make this a multiple of entry_size. 
+  
+  /** 
+   * Total number of bytes available to the chain.
+   * This value will be divided amongst the blocks in the chain.
+   * Chain's constructor will make this a multiple of entry_size. 
+   */
   std::size_t total_memory;
 };
 
+  
+/**
+ * Represents how a sorter should be configured.
+ */
 struct SortConfig {
+  
+  /** Filename prefix where temporary files should be placed. */
   std::string temp_prefix;
 
-  // Size of each input/output buffer.
+  /** Size of each input/output buffer. */
   std::size_t buffer_size;
 
-  // Total memory to use when running alone.
+  /** Total memory to use when running alone. */
   std::size_t total_memory;
 };
 
 }} // namespaces
-#endif // UTIL_STREAM_CONFIG__
+#endif // UTIL_STREAM_CONFIG_H
diff --git a/util/stream/io.cc b/util/stream/io.cc
index 0459f7069..c64004c0b 100644
--- a/util/stream/io.cc
+++ b/util/stream/io.cc
@@ -36,12 +36,12 @@ void PRead::Run(const ChainPosition &position) {
   Link link(position);
   uint64_t offset = 0;
   for (; offset + block_size64 < size; offset += block_size64, ++link) {
-    PReadOrThrow(file_, link->Get(), block_size, offset);
+    ErsatzPRead(file_, link->Get(), block_size, offset);
     link->SetValidSize(block_size);
   }
   // size - offset is <= block_size, so it casts to 32-bit fine.
   if (size - offset) {
-    PReadOrThrow(file_, link->Get(), size - offset, offset);
+    ErsatzPRead(file_, link->Get(), size - offset, offset);
     link->SetValidSize(size - offset);
     ++link;
   }
@@ -62,5 +62,15 @@ void WriteAndRecycle::Run(const ChainPosition &position) {
   }
 }
 
+void PWriteAndRecycle::Run(const ChainPosition &position) {
+  const std::size_t block_size = position.GetChain().BlockSize();
+  uint64_t offset = 0;
+  for (Link link(position); link; ++link) {
+    ErsatzPWrite(file_, link->Get(), link->ValidSize(), offset);
+    offset += link->ValidSize();
+    link->SetValidSize(block_size);
+  }
+}
+
 } // namespace stream
 } // namespace util
diff --git a/util/stream/io.hh b/util/stream/io.hh
index 934b6b3fe..8dae2cbff 100644
--- a/util/stream/io.hh
+++ b/util/stream/io.hh
@@ -1,5 +1,5 @@
-#ifndef UTIL_STREAM_IO__
-#define UTIL_STREAM_IO__
+#ifndef UTIL_STREAM_IO_H
+#define UTIL_STREAM_IO_H
 
 #include "util/exception.hh"
 #include "util/file.hh"
@@ -41,6 +41,8 @@ class Write {
     int file_;
 };
 
+// It's a common case that stuff is written and then recycled.  So rather than
+// spawn another thread to Recycle, this combines the two roles.
 class WriteAndRecycle {
   public:
     explicit WriteAndRecycle(int fd) : file_(fd) {}
@@ -49,14 +51,23 @@ class WriteAndRecycle {
     int file_;
 };
 
+class PWriteAndRecycle {
+  public:
+    explicit PWriteAndRecycle(int fd) : file_(fd) {}
+    void Run(const ChainPosition &position);
+  private:
+    int file_;
+};
+
+
 // Reuse the same file over and over again to buffer output.  
 class FileBuffer {
   public:
     explicit FileBuffer(int fd) : file_(fd) {}
 
-    WriteAndRecycle Sink() const {
+    PWriteAndRecycle Sink() const {
       util::SeekOrThrow(file_.get(), 0);
-      return WriteAndRecycle(file_.get());
+      return PWriteAndRecycle(file_.get());
     }
 
     PRead Source() const {
@@ -73,4 +84,4 @@ class FileBuffer {
 
 } // namespace stream
 } // namespace util
-#endif // UTIL_STREAM_IO__
+#endif // UTIL_STREAM_IO_H
diff --git a/util/stream/line_input.hh b/util/stream/line_input.hh
index 86db1dd06..a870a6648 100644
--- a/util/stream/line_input.hh
+++ b/util/stream/line_input.hh
@@ -1,5 +1,5 @@
-#ifndef UTIL_STREAM_LINE_INPUT__
-#define UTIL_STREAM_LINE_INPUT__
+#ifndef UTIL_STREAM_LINE_INPUT_H
+#define UTIL_STREAM_LINE_INPUT_H
 namespace util {namespace stream {
 
 class ChainPosition;
@@ -19,4 +19,4 @@ class LineInput {
 };
 
 }} // namespaces
-#endif // UTIL_STREAM_LINE_INPUT__
+#endif // UTIL_STREAM_LINE_INPUT_H
diff --git a/util/stream/multi_progress.hh b/util/stream/multi_progress.hh
index c4dd45a9b..82e698a59 100644
--- a/util/stream/multi_progress.hh
+++ b/util/stream/multi_progress.hh
@@ -1,6 +1,6 @@
 /* Progress bar suitable for chains of workers */
-#ifndef UTIL_MULTI_PROGRESS__
-#define UTIL_MULTI_PROGRESS__
+#ifndef UTIL_STREAM_MULTI_PROGRESS_H
+#define UTIL_STREAM_MULTI_PROGRESS_H
 
 #include <boost/thread/mutex.hpp>
 
@@ -87,4 +87,4 @@ class WorkerProgress {
 
 }} // namespaces
 
-#endif // UTIL_MULTI_PROGRESS__
+#endif // UTIL_STREAM_MULTI_PROGRESS_H
diff --git a/util/stream/multi_stream.hh b/util/stream/multi_stream.hh
new file mode 100644
index 000000000..0ee7fab6f
--- /dev/null
+++ b/util/stream/multi_stream.hh
@@ -0,0 +1,127 @@
+#ifndef UTIL_STREAM_MULTI_STREAM_H
+#define UTIL_STREAM_MULTI_STREAM_H
+
+#include "util/fixed_array.hh"
+#include "util/scoped.hh"
+#include "util/stream/chain.hh"
+#include "util/stream/stream.hh"
+
+#include <cstddef>
+#include <new>
+
+#include <assert.h>
+#include <stdlib.h>
+
+namespace util { namespace stream {
+
+class Chains;
+
+class ChainPositions : public util::FixedArray<util::stream::ChainPosition> {
+  public:
+    ChainPositions() {}
+
+    void Init(Chains &chains);
+
+    explicit ChainPositions(Chains &chains) {
+      Init(chains);
+    }
+};
+
+class Chains : public util::FixedArray<util::stream::Chain> {
+  private:
+    template <class T, void (T::*ptr)(const ChainPositions &) = &T::Run> struct CheckForRun {
+      typedef Chains type;
+    };
+
+  public:
+    // Must call Init.
+    Chains() {}
+
+    explicit Chains(std::size_t limit) : util::FixedArray<util::stream::Chain>(limit) {}
+
+    template <class Worker> typename CheckForRun<Worker>::type &operator>>(const Worker &worker) {
+      threads_.push_back(new util::stream::Thread(ChainPositions(*this), worker));
+      return *this;
+    }
+
+    template <class Worker> typename CheckForRun<Worker>::type &operator>>(const boost::reference_wrapper<Worker> &worker) {
+      threads_.push_back(new util::stream::Thread(ChainPositions(*this), worker));
+      return *this;
+    }
+
+    Chains &operator>>(const util::stream::Recycler &recycler) {
+      for (util::stream::Chain *i = begin(); i != end(); ++i) 
+        *i >> recycler;
+      return *this;
+    }
+
+    void Wait(bool release_memory = true) {
+      threads_.clear();
+      for (util::stream::Chain *i = begin(); i != end(); ++i) {
+        i->Wait(release_memory);
+      }
+    }
+
+  private:
+    boost::ptr_vector<util::stream::Thread> threads_;
+
+    Chains(const Chains &);
+    void operator=(const Chains &);
+};
+
+inline void ChainPositions::Init(Chains &chains) {
+  util::FixedArray<util::stream::ChainPosition>::Init(chains.size());
+  for (util::stream::Chain *i = chains.begin(); i != chains.end(); ++i) {
+    // use "placement new" syntax to initalize ChainPosition in an already-allocated memory location
+    new (end()) util::stream::ChainPosition(i->Add()); Constructed();
+  }
+}
+
+inline Chains &operator>>(Chains &chains, ChainPositions &positions) {
+  positions.Init(chains);
+  return chains;
+}
+
+template <class T> class GenericStreams : public util::FixedArray<T> {
+  private:
+    typedef util::FixedArray<T> P;
+  public:
+    GenericStreams() {}
+
+    // This puts a dummy T at the beginning (useful to algorithms that need to reference something at the beginning).
+    void InitWithDummy(const ChainPositions &positions) {
+      P::Init(positions.size() + 1);
+      new (P::end()) T(); // use "placement new" syntax to initalize T in an already-allocated memory location
+      P::Constructed();
+      for (const util::stream::ChainPosition *i = positions.begin(); i != positions.end(); ++i) {
+        P::push_back(*i);
+      }
+    }
+
+    // Limit restricts to positions[0,limit)
+    void Init(const ChainPositions &positions, std::size_t limit) {
+      P::Init(limit);
+      for (const util::stream::ChainPosition *i = positions.begin(); i != positions.begin() + limit; ++i) {
+        P::push_back(*i);
+      }
+    }
+    void Init(const ChainPositions &positions) {
+      Init(positions, positions.size());
+    }
+
+    GenericStreams(const ChainPositions &positions) {
+      Init(positions);
+    }
+};
+
+template <class T> inline Chains &operator>>(Chains &chains, GenericStreams<T> &streams) {
+  ChainPositions positions;
+  chains >> positions;
+  streams.Init(positions);
+  return chains;
+}
+
+typedef GenericStreams<Stream> Streams;
+
+}} // namespaces
+#endif // UTIL_STREAM_MULTI_STREAM_H
diff --git a/util/stream/sort.hh b/util/stream/sort.hh
index 16aa6a036..9082cfdde 100644
--- a/util/stream/sort.hh
+++ b/util/stream/sort.hh
@@ -15,8 +15,8 @@
  * sort.  Use a hash table for that.  
  */
 
-#ifndef UTIL_STREAM_SORT__
-#define UTIL_STREAM_SORT__
+#ifndef UTIL_STREAM_SORT_H
+#define UTIL_STREAM_SORT_H
 
 #include "util/stream/chain.hh"
 #include "util/stream/config.hh"
@@ -182,7 +182,7 @@ template <class Compare> class MergeQueue {
             amount = remaining_;
             buffer_end_ = current_ + remaining_;
           }
-          PReadOrThrow(fd, current_, amount, offset_);
+          ErsatzPRead(fd, current_, amount, offset_);
           offset_ += amount;
           assert(current_ <= buffer_end_);
           remaining_ -= amount;
@@ -307,10 +307,10 @@ template <class Compare, class Combine> class MergingReader {
       const uint64_t block_size = position.GetChain().BlockSize();
       Link l(position);
       for (; offset + block_size < end; ++l, offset += block_size) {
-        PReadOrThrow(in_, l->Get(), block_size, offset);
+        ErsatzPRead(in_, l->Get(), block_size, offset);
         l->SetValidSize(block_size);
       }
-      PReadOrThrow(in_, l->Get(), end - offset, offset);
+      ErsatzPRead(in_, l->Get(), end - offset, offset);
       l->SetValidSize(end - offset);
       (++l).Poison();
       return;
@@ -388,8 +388,10 @@ class BadSortConfig : public Exception {
     ~BadSortConfig() throw() {}
 };
 
+/** Sort */
 template <class Compare, class Combine = NeverCombine> class Sort {
   public:
+    /** Constructs an object capable of sorting */
     Sort(Chain &in, const SortConfig &config, const Compare &compare = Compare(), const Combine &combine = Combine())
       : config_(config),
         data_(MakeTemp(config.temp_prefix)),
@@ -545,4 +547,4 @@ template <class Compare, class Combine> uint64_t BlockingSort(Chain &chain, cons
 } // namespace stream
 } // namespace util
 
-#endif // UTIL_STREAM_SORT__
+#endif // UTIL_STREAM_SORT_H
diff --git a/util/stream/stream.hh b/util/stream/stream.hh
index 6ff45b820..7ea1c9f70 100644
--- a/util/stream/stream.hh
+++ b/util/stream/stream.hh
@@ -1,5 +1,5 @@
-#ifndef UTIL_STREAM_STREAM__
-#define UTIL_STREAM_STREAM__
+#ifndef UTIL_STREAM_STREAM_H
+#define UTIL_STREAM_STREAM_H
 
 #include "util/stream/chain.hh"
 
@@ -56,6 +56,9 @@ class Stream : boost::noncopyable {
       end_ = current_ + block_it_->ValidSize();
     }
 
+    // The following are pointers to raw memory
+    // current_ is the current record
+    // end_ is the end of the block (so we know when to move to the next block)
     uint8_t *current_, *end_;
 
     std::size_t entry_size_;
@@ -71,4 +74,4 @@ inline Chain &operator>>(Chain &chain, Stream &stream) {
 
 } // namespace stream
 } // namespace util
-#endif // UTIL_STREAM_STREAM__
+#endif // UTIL_STREAM_STREAM_H
diff --git a/util/stream/timer.hh b/util/stream/timer.hh
index 7e1a5885d..06488a17e 100644
--- a/util/stream/timer.hh
+++ b/util/stream/timer.hh
@@ -1,5 +1,5 @@
-#ifndef UTIL_STREAM_TIMER__
-#define UTIL_STREAM_TIMER__
+#ifndef UTIL_STREAM_TIMER_H
+#define UTIL_STREAM_TIMER_H
 
 // Sorry Jon, this was adding library dependencies in Moses and people complained.
 
@@ -13,4 +13,4 @@
 #define UTIL_TIMER(str) 
 //#endif
 
-#endif // UTIL_STREAM_TIMER__
+#endif // UTIL_STREAM_TIMER_H
diff --git a/util/string_piece.hh b/util/string_piece.hh
index 84431db17..114e25473 100644
--- a/util/string_piece.hh
+++ b/util/string_piece.hh
@@ -45,8 +45,8 @@
 // conversions from "const char*" to "string" and back again.
 //
 
-#ifndef BASE_STRING_PIECE_H__
-#define BASE_STRING_PIECE_H__
+#ifndef UTIL_STRING_PIECE_H
+#define UTIL_STRING_PIECE_H
 
 #include "util/have.hh"
 
@@ -267,4 +267,4 @@ U_NAMESPACE_END
 using U_NAMESPACE_QUALIFIER StringPiece;
 #endif
 
-#endif  // BASE_STRING_PIECE_H__
+#endif  // UTIL_STRING_PIECE_H
diff --git a/util/string_piece_hash.hh b/util/string_piece_hash.hh
index f206b1d87..5c8c525e5 100644
--- a/util/string_piece_hash.hh
+++ b/util/string_piece_hash.hh
@@ -1,5 +1,5 @@
-#ifndef UTIL_STRING_PIECE_HASH__
-#define UTIL_STRING_PIECE_HASH__
+#ifndef UTIL_STRING_PIECE_HASH_H
+#define UTIL_STRING_PIECE_HASH_H
 
 #include "util/string_piece.hh"
 
@@ -40,4 +40,4 @@ template <class T> typename T::iterator FindStringPiece(T &t, const StringPiece
 #endif
 }
 
-#endif // UTIL_STRING_PIECE_HASH__
+#endif // UTIL_STRING_PIECE_HASH_H
diff --git a/util/thread_pool.hh b/util/thread_pool.hh
index 84e257ea6..d1a883a00 100644
--- a/util/thread_pool.hh
+++ b/util/thread_pool.hh
@@ -1,5 +1,5 @@
-#ifndef UTIL_THREAD_POOL__
-#define UTIL_THREAD_POOL__
+#ifndef UTIL_THREAD_POOL_H
+#define UTIL_THREAD_POOL_H
 
 #include "util/pcqueue.hh"
 
@@ -18,8 +18,8 @@ template <class HandlerT> class Worker : boost::noncopyable {
     typedef HandlerT Handler;
     typedef typename Handler::Request Request;
 
-    template <class Construct> Worker(PCQueue<Request> &in, Construct &construct, Request &poison)
-      : in_(in), handler_(construct), thread_(boost::ref(*this)), poison_(poison) {}
+    template <class Construct> Worker(PCQueue<Request> &in, Construct &construct, const Request &poison)
+      : in_(in), handler_(construct), poison_(poison), thread_(boost::ref(*this)) {}
 
     // Only call from thread.
     void operator()() {
@@ -30,7 +30,7 @@ template <class HandlerT> class Worker : boost::noncopyable {
         try {
           (*handler_)(request);
         }
-        catch(std::exception &e) {
+        catch(const std::exception &e) {
           std::cerr << "Handler threw " << e.what() << std::endl;
           abort();
         }
@@ -49,10 +49,10 @@ template <class HandlerT> class Worker : boost::noncopyable {
     PCQueue<Request> &in_;
 
     boost::optional<Handler> handler_;
+    
+    const Request poison_;
 
     boost::thread thread_;
-
-    Request poison_;
 };
 
 template <class HandlerT> class ThreadPool : boost::noncopyable {
@@ -92,4 +92,4 @@ template <class HandlerT> class ThreadPool : boost::noncopyable {
 
 } // namespace util
 
-#endif // UTIL_THREAD_POOL__
+#endif // UTIL_THREAD_POOL_H
diff --git a/util/tokenize_piece.hh b/util/tokenize_piece.hh
index 24eae8fbe..908c8dafe 100644
--- a/util/tokenize_piece.hh
+++ b/util/tokenize_piece.hh
@@ -1,5 +1,5 @@
-#ifndef UTIL_TOKENIZE_PIECE__
-#define UTIL_TOKENIZE_PIECE__
+#ifndef UTIL_TOKENIZE_PIECE_H
+#define UTIL_TOKENIZE_PIECE_H
 
 #include "util/exception.hh"
 #include "util/string_piece.hh"
@@ -7,7 +7,8 @@
 #include <boost/iterator/iterator_facade.hpp>
 
 #include <algorithm>
-#include <iostream>
+
+#include <string.h>
 
 namespace util {
 
@@ -71,6 +72,13 @@ class BoolCharacter {
       return StringPiece(in.data() + in.size(), 0);
     }
 
+    template <unsigned Length> static void Build(const char (&characters)[Length], bool (&out)[256]) {
+      memset(out, 0, sizeof(out));
+      for (const char *i = characters; i != characters + Length; ++i) {
+        out[static_cast<unsigned char>(*i)] = true;
+      }
+    }
+
   private:
     const bool *delimiter_;
 };
@@ -140,4 +148,4 @@ template <class Find, bool SkipEmpty = false> class TokenIter : public boost::it
 
 } // namespace util
 
-#endif // UTIL_TOKENIZE_PIECE__
+#endif // UTIL_TOKENIZE_PIECE_H
diff --git a/util/unistd.hh b/util/unistd.hh
new file mode 100644
index 000000000..0379c4914
--- /dev/null
+++ b/util/unistd.hh
@@ -0,0 +1,22 @@
+#ifndef UTIL_UNISTD_H
+#define UTIL_UNISTD_H
+
+#if defined(_WIN32) || defined(_WIN64)
+
+// Windows doesn't define <unistd.h>
+//
+// So we define what we need here instead:
+//
+#define STDIN_FILENO=0
+#define STDOUT_FILENO=1
+
+
+#else // Huzzah for POSIX!
+
+#include <unistd.h>
+
+#endif
+
+
+
+#endif // UTIL_UNISTD_H
diff --git a/util/usage.cc b/util/usage.cc
index e68d7c7c1..2a4aa47d4 100644
--- a/util/usage.cc
+++ b/util/usage.cc
@@ -30,6 +30,8 @@ typedef struct
   DWORDLONG ullAvailVirtual;
   DWORDLONG ullAvailExtendedVirtual;
 } lMEMORYSTATUSEX;
+// Is this really supposed to be defined like this?
+typedef int WINBOOL;
 typedef WINBOOL (WINAPI *PFN_MS_EX) (lMEMORYSTATUSEX*);
 #else
 #include <sys/resource.h>
@@ -196,7 +198,7 @@ uint64_t GuessPhysicalMemory() {
 #if defined(_WIN32) || defined(_WIN64)
   { /* this works on windows */
     PFN_MS_EX pfnex;
-    HMODULE h = GetModuleHandle ("kernel32.dll");
+    HMODULE h = GetModuleHandle (TEXT("kernel32.dll"));
 
     if (!h)
       return 0;
diff --git a/util/usage.hh b/util/usage.hh
index da53b9e32..e578b0a65 100644
--- a/util/usage.hh
+++ b/util/usage.hh
@@ -1,5 +1,5 @@
-#ifndef UTIL_USAGE__
-#define UTIL_USAGE__
+#ifndef UTIL_USAGE_H
+#define UTIL_USAGE_H
 #include <cstddef>
 #include <iosfwd>
 #include <string>
@@ -18,4 +18,4 @@ uint64_t GuessPhysicalMemory();
 // Parse a size like unix sort.  Sadly, this means the default multiplier is K.
 uint64_t ParseSize(const std::string &arg);
 } // namespace util
-#endif // UTIL_USAGE__
+#endif // UTIL_USAGE_H