1 files changed, 228 insertions, 0 deletions
diff --git a/src/symtab.h b/src/symtab.h
new file mode 100644
index 0000000..455d967
--- /dev/null
+++ b/src/symtab.h
@@ -0,0 +1,228 @@
+// Copyright 2015 Google Inc. All rights reserved
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef SYMTAB_H_
+#define SYMTAB_H_
+
+#include <bitset>
+#include <string>
+#include <vector>
+
+#include "string_piece.h"
+
+using namespace std;
+
+extern vector<string*>* g_symbols;
+
+class Symtab;
+class Var;
+
+class Symbol {
+ public:
+  explicit Symbol() : v_(-1) {}
+
+  const string& str() const { return *((*g_symbols)[v_]); }
+
+  const char* c_str() const { return str().c_str(); }
+
+  bool empty() const { return !v_; }
+
+  int val() const { return v_; }
+
+  char get(size_t i) const {
+    const string& s = str();
+    if (i >= s.size())
+      return 0;
+    return s[i];
+  }
+
+  bool IsValid() const { return v_ >= 0; }
+
+  Var* PeekGlobalVar() const;
+  Var* GetGlobalVar() const;
+  void SetGlobalVar(Var* v,
+                    bool is_override = false,
+                    bool* readonly = nullptr) const;
+
+ private:
+  explicit Symbol(int v);
+
+  int v_;
+
+  friend class Symtab;
+  friend class SymbolSet;
+};
+
+/* A set of symbols represented as bitmap indexed by Symbol's ordinal value. */
+class SymbolSet {
+ public:
+  SymbolSet() : low_(0), high_(0) {}
+
+  /* Returns true if Symbol belongs to this set. */
+  bool exists(Symbol sym) const {
+    size_t bit_nr = static_cast<size_t>(sym.val());
+    return sym.IsValid() && bit_nr >= low_ && bit_nr < high_ &&
+           bits_[(bit_nr - low_) / 64][(bit_nr - low_) % 64];
+  }
+
+  /* Adds Symbol to this set.  */
+  void insert(Symbol sym) {
+    if (!sym.IsValid()) {
+      return;
+    }
+    size_t bit_nr = static_cast<size_t>(sym.val());
+    if (bit_nr < low_ || bit_nr >= high_) {
+      resize(bit_nr);
+    }
+    bits_[(bit_nr - low_) / 64][(bit_nr - low_) % 64] = true;
+  }
+
+  /* Returns the number of Symbol's in this set.  */
+  size_t size() const {
+    size_t n = 0;
+    for (auto const& bitset : bits_) {
+      n += bitset.count();
+    }
+    return n;
+  }
+
+  /* Allow using foreach.
+   * E.g.,
+   *   SymbolSet symbol_set;
+   *   for (auto const& symbol: symbol_set) { ... }
+   */
+  class iterator {
+    const SymbolSet* bitset_;
+    size_t pos_;
+
+    iterator(const SymbolSet* bitset, size_t pos)
+        : bitset_(bitset), pos_(pos) {}
+
+    /* Proceed to the next Symbol.  */
+    void next() {
+      size_t bit_nr = (pos_ > bitset_->low_) ? pos_ - bitset_->low_ : 0;
+      while (bit_nr < (bitset_->high_ - bitset_->low_)) {
+        if ((bit_nr % 64) == 0 && !bitset_->bits_[bit_nr / 64].any()) {
+          bit_nr += 64;
+          continue;
+        }
+        if (bitset_->bits_[bit_nr / 64][bit_nr % 64]) {
+          break;
+        }
+        ++bit_nr;
+      }
+      pos_ = bitset_->low_ + bit_nr;
+    }
+
+   public:
+    iterator& operator++() {
+      if (pos_ < bitset_->high_) {
+        ++pos_;
+        next();
+      }
+      return *this;
+    }
+
+    bool operator==(iterator other) const {
+      return bitset_ == other.bitset_ && pos_ == other.pos_;
+    }
+
+    bool operator!=(iterator other) const { return !(*this == other); }
+
+    Symbol operator*() { return Symbol(pos_); }
+
+    friend class SymbolSet;
+  };
+
+  iterator begin() const {
+    iterator it(this, low_);
+    it.next();
+    return it;
+  }
+
+  iterator end() const { return iterator(this, high_); }
+
+ private:
+  friend class iterator;
+
+  /* Ensure that given bit number is in [low_, high_)  */
+  void resize(size_t bit_nr) {
+    size_t new_low = bit_nr & ~63;
+    size_t new_high = (bit_nr + 64) & ~63;
+    if (bits_.empty()) {
+      high_ = low_ = new_low;
+    }
+    if (new_low > low_) {
+      new_low = low_;
+    }
+    if (new_high <= high_) {
+      new_high = high_;
+    }
+    if (new_low == low_) {
+      bits_.resize((new_high - new_low) / 64);
+    } else {
+      std::vector<std::bitset<64> > newbits((new_high - new_low) / 64);
+      std::copy(bits_.begin(), bits_.end(),
+                newbits.begin() + (low_ - new_low) / 64);
+      bits_.swap(newbits);
+    }
+    low_ = new_low;
+    high_ = new_high;
+  }
+
+  /* Keep only the (aligned) range where at least one bit has been set.
+   * E.g., if we only ever set bits 65 and 141, |low_| will be 64, |high_|
+   * will be 192, and |bits_| will have 2 elements.
+   */
+  size_t low_;
+  size_t high_;
+  std::vector<std::bitset<64> > bits_;
+};
+
+class ScopedGlobalVar {
+ public:
+  ScopedGlobalVar(Symbol name, Var* var);
+  ~ScopedGlobalVar();
+
+ private:
+  Symbol name_;
+  Var* orig_;
+};
+
+inline bool operator==(const Symbol& x, const Symbol& y) {
+  return x.val() == y.val();
+}
+
+inline bool operator<(const Symbol& x, const Symbol& y) {
+  return x.val() < y.val();
+}
+
+namespace std {
+template <>
+struct hash<Symbol> {
+  size_t operator()(const Symbol& s) const { return s.val(); }
+};
+}  // namespace std
+
+extern Symbol kEmptySym;
+extern Symbol kShellSym;
+extern Symbol kKatiReadonlySym;
+
+void InitSymtab();
+void QuitSymtab();
+Symbol Intern(StringPiece s);
+
+string JoinSymbols(const vector<Symbol>& syms, const char* sep);
+
+#endif  // SYMTAB_H_