1  #ifndef __POOL_FOR_STRINGS_TERMINATED_BY_ZERO_H_
  2  #define __POOL_FOR_STRINGS_TERMINATED_BY_ZERO_H_
  3  
  4  // This library helps keep many short strings.
  5  // StringPool makes a copy of an added string and returns its address.
  6  // Then, that copy will be deleted when the class is deleted.
  7  //
  8  // StringPool uses large blocks to store strings so that the overhead of
  9  // new [] and delete [] becomes little. The size of each block is specified
 10  // by the argument of its construcor, and if the argument is not passed,
 11  // 4,096 is used as the default size.
 12  //
 13  // If an added string is longer than the block size is passed, StringPool
 14  // allocates a large block to that string.
 15  
 16  // For assert().
 17  #include <cassert>
 18  // For std::size_t.
 19  #include <cstddef>
 20  
 21  // For vector.
 22  #include <vector>
 23  
 24  
 25  namespace StringPool {
 26  
 27  using std::size_t;
 28  
 29  // Get the length of a string.
 30  template <typename Letter>
 31  inline size_t GetStringLength(const Letter *s) {
 32    const Letter *p = s;
 33    while (*p != '\0')
 34      ++p;
 35    return static_cast<size_t>(p - s);
 36  }
 37  
 38  // Copy a string.
 39  template <typename LetterTo, typename LetterFrom>
 40  inline LetterTo *CopyString(LetterTo *dst, const LetterFrom *src,
 41                              size_t size) {
 42    for (size_t i = 0; i < size; ++i)
 43      dst[i] = src[i];
 44    return dst;
 45  }
 46  
 47  // This class is to store many short strings.
 48  template <typename Letter>
 49  class Pool {
 50   private:
 51    typedef std::vector<Letter *> BlockVector;
 52    typedef typename BlockVector::iterator BlockIterator;
 53  
 54   public:
 55    Pool(size_t block_size = 4096)
 56        : blocks_(), next_(0), end_(0),
 57          num_strs_(0), total_size_(0), block_size_(block_size) {}
 58    ~Pool() {
 59      for (BlockIterator it = blocks_.begin(); it != blocks_.end(); ++it)
 60        delete [] *it;
 61    }
 62  
 63    // Allocate memory.
 64    Letter *alloc(size_t size) {
 65      if (size > static_cast<size_t>(end_ - next_))
 66        expand_(size);
 67      Letter *start = next_;
 68      next_ += size;
 69      ++num_strs_;
 70      return start;
 71    }
 72  
 73    // Add a copy of a string to the pool.
 74    template <typename LetterFrom>
 75    Letter *add(const LetterFrom *s, size_t size) {
 76      assert(s);
 77      return CopyString(alloc(size), s, size);
 78    }
 79    template <typename LetterFrom>
 80    Letter *add(const LetterFrom *s) {
 81      assert(s);
 82      return add(s, GetStringLength(s) + 1);
 83    }
 84  
 85    // Return the number of strings and the total size.
 86    size_t num_strs() const { return num_strs_; }
 87    size_t total_size() const { return total_size_; }
 88  
 89   private:
 90    BlockVector blocks_;
 91    Letter *next_;
 92    Letter *end_;
 93    size_t num_strs_;
 94    size_t total_size_;
 95    size_t block_size_;
 96  
 97    // Allocate memory to a new block.
 98    void expand_(size_t size) {
 99      size = (size > block_size_) ? size : block_size_;
100      blocks_.push_back(new Letter[size]);
101      next_ = blocks_.back();
102      end_ = next_ + size;
103      total_size_ += sizeof(Letter) * size;
104    }
105  
106    // Prohibit copy and assignment.
107    Pool(const Pool &rhs);
108    Pool &operator=(const Pool<Letter> &rhs);
109  };
110  
111  }  // namespace StringPool.
112  
113  
114  #endif  // __POOL_FOR_STRINGS_TERMINATED_BY_ZERO_H_