souffle  2.0.2-371-g6315b36
SymbolTable.h
Go to the documentation of this file.
1 /*
2  * Souffle - A Datalog Compiler
3  * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved
4  * Licensed under the Universal Permissive License v 1.0 as shown at:
5  * - https://opensource.org/licenses/UPL
6  * - <souffle root>/licenses/SOUFFLE-UPL.txt
7  */
8 
9 /************************************************************************
10  *
11  * @file SymbolTable.h
12  *
13  * Data container to store symbols of the Datalog program.
14  *
15  ***********************************************************************/
16 
17 #pragma once
18 
19 #include "souffle/RamTypes.h"
23 #include <algorithm>
24 #include <cstdlib>
25 #include <deque>
26 #include <initializer_list>
27 #include <iostream>
28 #include <string>
29 #include <unordered_map>
30 #include <utility>
31 #include <vector>
32 
33 namespace souffle {
34 
35 /**
36  * @class SymbolTable
37  *
38  * Global pool of re-usable strings
39  *
40  * SymbolTable stores Datalog symbols and converts them to numbers and vice versa.
41  */
42 class SymbolTable {
43 private:
44  /** A lock to synchronize parallel accesses */
45  mutable Lock access;
46 
47  /** Map indices to strings. */
48  std::deque<std::string> numToStr;
49 
50  /** Map strings to indices. */
51  std::unordered_map<std::string, size_t> strToNum;
52 
53  /** Convenience method to place a new symbol in the table, if it does not exist, and return the index of
54  * it. */
55  inline size_t newSymbolOfIndex(const std::string& symbol) {
56  size_t index;
57  auto it = strToNum.find(symbol);
58  if (it == strToNum.end()) {
59  index = numToStr.size();
60  strToNum[symbol] = index;
61  numToStr.push_back(symbol);
62  } else {
63  index = it->second;
64  }
65  return index;
66  }
67 
68  /** Convenience method to place a new symbol in the table, if it does not exist. */
69  inline void newSymbol(const std::string& symbol) {
70  if (strToNum.find(symbol) == strToNum.end()) {
71  strToNum[symbol] = numToStr.size();
72  numToStr.push_back(symbol);
73  }
74  }
75 
76 public:
77  /** Empty constructor. */
78  SymbolTable() = default;
79 
80  /** Copy constructor, performs a deep copy. */
81  SymbolTable(const SymbolTable& other) : numToStr(other.numToStr), strToNum(other.strToNum) {}
82 
83  /** Copy constructor for r-value reference. */
84  SymbolTable(SymbolTable&& other) noexcept {
85  numToStr.swap(other.numToStr);
86  strToNum.swap(other.strToNum);
87  }
88 
89  SymbolTable(std::initializer_list<std::string> symbols) {
90  strToNum.reserve(symbols.size());
91  for (const auto& symbol : symbols) {
92  newSymbol(symbol);
93  }
94  }
95 
96  /** Destructor, frees memory allocated for all strings. */
97  virtual ~SymbolTable() = default;
98 
99  /** Assignment operator, performs a deep copy and frees memory allocated for all strings. */
100  SymbolTable& operator=(const SymbolTable& other) {
101  if (this == &other) {
102  return *this;
103  }
104  numToStr = other.numToStr;
105  strToNum = other.strToNum;
106  return *this;
107  }
108 
109  /** Assignment operator for r-value references. */
110  SymbolTable& operator=(SymbolTable&& other) noexcept {
111  numToStr.swap(other.numToStr);
112  strToNum.swap(other.strToNum);
113  return *this;
114  }
115 
116  /** Find the index of a symbol in the table, inserting a new symbol if it does not exist there
117  * already. */
118  RamDomain lookup(const std::string& symbol) {
119  {
120  auto lease = access.acquire();
121  (void)lease; // avoid warning;
122  return static_cast<RamDomain>(newSymbolOfIndex(symbol));
123  }
124  }
125 
126  /** Finds the index of a symbol in the table, giving an error if it's not found */
127  RamDomain lookupExisting(const std::string& symbol) const {
128  {
129  auto lease = access.acquire();
130  (void)lease; // avoid warning;
131  auto result = strToNum.find(symbol);
132  if (result == strToNum.end()) {
133  fatal("Error string not found in call to `SymbolTable::lookupExisting`: `%s`", symbol);
134  }
135  return static_cast<RamDomain>(result->second);
136  }
137  }
138 
139  /** Find the index of a symbol in the table, inserting a new symbol if it does not exist there
140  * already. */
141  RamDomain unsafeLookup(const std::string& symbol) {
142  return static_cast<RamDomain>(newSymbolOfIndex(symbol));
143  }
144 
145  /** Find a symbol in the table by its index, note that this gives an error if the index is out of
146  * bounds.
147  */
148  const std::string& resolve(const RamDomain index) const {
149  {
150  auto lease = access.acquire();
151  (void)lease; // avoid warning;
152  auto pos = static_cast<size_t>(index);
153  if (pos >= size()) {
154  // TODO: use different error reporting here!!
155  fatal("Error index out of bounds in call to `SymbolTable::resolve`. index = `%d`", index);
156  }
157  return numToStr[pos];
158  }
159  }
160 
161  const std::string& unsafeResolve(const RamDomain index) const {
162  return numToStr[static_cast<size_t>(index)];
163  }
164 
165  /* Return the size of the symbol table, being the number of symbols it currently holds. */
166  size_t size() const {
167  return numToStr.size();
168  }
169 
170  /** Bulk insert symbols into the table, note that this operation is more efficient than repeated
171  * inserts
172  * of single symbols. */
173  void insert(const std::vector<std::string>& symbols) {
174  {
175  auto lease = access.acquire();
176  (void)lease; // avoid warning;
177  strToNum.reserve(size() + symbols.size());
178  for (auto& symbol : symbols) {
179  newSymbol(symbol);
180  }
181  }
182  }
183 
184  /** Insert a single symbol into the table, not that this operation should not be used if inserting
185  * symbols
186  * in bulk. */
187  void insert(const std::string& symbol) {
188  {
189  auto lease = access.acquire();
190  (void)lease; // avoid warning;
191  newSymbol(symbol);
192  }
193  }
194 
195  /** Print the symbol table to the given stream. */
196  void print(std::ostream& out) const {
197  {
198  out << "SymbolTable: {\n\t";
199  out << join(strToNum, "\n\t",
200  [](std::ostream& out, const std::pair<std::string, std::size_t>& entry) {
201  out << entry.first << "\t => " << entry.second;
202  })
203  << "\n";
204  out << "}\n";
205  }
206  }
207 
208  /** Check if the symbol table contains a string */
209  bool contains(const std::string& symbol) const {
210  auto lease = access.acquire();
211  (void)lease; // avoid warning;
212  auto result = strToNum.find(symbol);
213  if (result == strToNum.end()) {
214  return false;
215  } else {
216  return true;
217  }
218  }
219 
220  /** Check if the symbol table contains an index */
221  bool contains(const RamDomain index) const {
222  auto lease = access.acquire();
223  (void)lease; // avoid warning;
224  auto pos = static_cast<size_t>(index);
225  if (pos >= size()) {
226  return false;
227  } else {
228  return true;
229  }
230  }
231 
232  Lock::Lease acquireLock() const {
233  return access.acquire();
234  }
235 
236  /** Stream operator, used as a convenience for print. */
237  friend std::ostream& operator<<(std::ostream& out, const SymbolTable& table) {
238  table.print(out);
239  return out;
240  }
241 };
242 
243 } // namespace souffle
souffle::SymbolTable::insert
void insert(const std::vector< std::string > &symbols)
Bulk insert symbols into the table, note that this operation is more efficient than repeated inserts ...
Definition: SymbolTable.h:179
souffle::SymbolTable::unsafeResolve
const std::string & unsafeResolve(const RamDomain index) const
Definition: SymbolTable.h:167
souffle::SymbolTable::resolve
const std::string & resolve(const RamDomain index) const
Find a symbol in the table by its index, note that this gives an error if the index is out of bounds.
Definition: SymbolTable.h:154
souffle::SymbolTable::~SymbolTable
virtual ~SymbolTable()=default
Destructor, frees memory allocated for all strings.
souffle::SymbolTable::newSymbol
void newSymbol(const std::string &symbol)
Convenience method to place a new symbol in the table, if it does not exist.
Definition: SymbolTable.h:75
souffle::RamDomain
int32_t RamDomain
Definition: RamTypes.h:56
souffle::SymbolTable::contains
bool contains(const std::string &symbol) const
Check if the symbol table contains a string.
Definition: SymbolTable.h:215
souffle::SymbolTable::numToStr
std::deque< std::string > numToStr
Map indices to strings.
Definition: SymbolTable.h:54
souffle::SymbolTable::acquireLock
Lock::Lease acquireLock() const
Definition: SymbolTable.h:238
ParallelUtil.h
MiscUtil.h
souffle::SymbolTable::operator=
SymbolTable & operator=(const SymbolTable &other)
Assignment operator, performs a deep copy and frees memory allocated for all strings.
Definition: SymbolTable.h:106
souffle::SymbolTable::strToNum
std::unordered_map< std::string, size_t > strToNum
Map strings to indices.
Definition: SymbolTable.h:57
souffle::SymbolTable::lookup
RamDomain lookup(const std::string &symbol)
Find the index of a symbol in the table, inserting a new symbol if it does not exist there already.
Definition: SymbolTable.h:124
souffle::Lock::acquire
Lease acquire()
Definition: ParallelUtil.h:471
souffle::SymbolTable::lookupExisting
RamDomain lookupExisting(const std::string &symbol) const
Finds the index of a symbol in the table, giving an error if it's not found.
Definition: SymbolTable.h:133
souffle::SymbolTable::print
void print(std::ostream &out) const
Print the symbol table to the given stream.
Definition: SymbolTable.h:202
souffle::join
detail::joined_sequence< Iter, Printer > join(const Iter &a, const Iter &b, const std::string &sep, const Printer &p)
Creates an object to be forwarded to some output stream for printing sequences of elements interspers...
Definition: StreamUtil.h:175
souffle::SymbolTable
Definition: SymbolTable.h:48
souffle::SymbolTable::SymbolTable
SymbolTable()=default
Empty constructor.
souffle::SymbolTable::operator<<
friend std::ostream & operator<<(std::ostream &out, const SymbolTable &table)
Stream operator, used as a convenience for print.
Definition: SymbolTable.h:243
souffle::SymbolTable::access
Lock access
A lock to synchronize parallel accesses.
Definition: SymbolTable.h:51
RamTypes.h
StreamUtil.h
souffle::fatal
void fatal(const char *format, const Args &... args)
Definition: MiscUtil.h:198
souffle
Definition: AggregateOp.h:25
souffle::SymbolTable::unsafeLookup
RamDomain unsafeLookup(const std::string &symbol)
Find the index of a symbol in the table, inserting a new symbol if it does not exist there already.
Definition: SymbolTable.h:147
souffle::SymbolTable::newSymbolOfIndex
size_t newSymbolOfIndex(const std::string &symbol)
Convenience method to place a new symbol in the table, if it does not exist, and return the index of ...
Definition: SymbolTable.h:61
souffle::SymbolTable::size
size_t size() const
Definition: SymbolTable.h:172