HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
token.h
Go to the documentation of this file.
1 //
2 // Copyright 2016 Pixar
3 //
4 // Licensed under the Apache License, Version 2.0 (the "Apache License")
5 // with the following modification; you may not use this file except in
6 // compliance with the Apache License and the following modification to it:
7 // Section 6. Trademarks. is deleted and replaced with:
8 //
9 // 6. Trademarks. This License does not grant permission to use the trade
10 // names, trademarks, service marks, or product names of the Licensor
11 // and its affiliates, except as required to comply with Section 4(c) of
12 // the License and to reproduce the content of the NOTICE file.
13 //
14 // You may obtain a copy of the Apache License at
15 //
16 // http://www.apache.org/licenses/LICENSE-2.0
17 //
18 // Unless required by applicable law or agreed to in writing, software
19 // distributed under the Apache License with the above modification is
20 // distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
21 // KIND, either express or implied. See the Apache License for the specific
22 // language governing permissions and limitations under the Apache License.
23 //
24 #ifndef TF_TOKEN_H
25 #define TF_TOKEN_H
26 
27 /// \file tf/token.h
28 ///
29 /// \c TfToken class for efficient string referencing and hashing, plus
30 /// conversions to and from stl string containers.
31 
32 #include "pxr/pxr.h"
33 
34 #include "pxr/base/tf/api.h"
36 #include "pxr/base/tf/hash.h"
38 #include "pxr/base/tf/traits.h"
39 
40 #include "pxr/base/tf/hashset.h"
41 #include <atomic>
42 #include <iosfwd>
43 #include <string>
44 #include <vector>
45 #include <map>
46 #include <set>
47 
49 
51 
52 /// \class TfToken
53 /// \ingroup group_tf_String
54 ///
55 /// Token for efficient comparison, assignment, and hashing of known strings.
56 ///
57 /// A TfToken is a handle for a registered string, and can be compared,
58 /// assigned, and hashed in constant time. It is useful when a bounded number
59 /// of strings are used as fixed symbols (but never modified).
60 ///
61 /// For example, the set of avar names in a shot is large but bounded, and
62 /// once an avar name is discovered, it is never manipulated. If these names
63 /// were passed around as strings, every comparison and hash would be linear
64 /// in the number of characters. (String assignment itself is sometimes a
65 /// constant time operation, but it is sometimes linear in the length of the
66 /// string as well as requiring a memory allocation.)
67 ///
68 /// To use TfToken, simply create an instance from a string or const char*.
69 /// If the string hasn't been seen before, a copy of it is added to a global
70 /// table. The resulting TfToken is simply a wrapper around an string*,
71 /// pointing that canonical copy of the string. Thus, operations on the token
72 /// are very fast. (The string's hash is simply the address of the canonical
73 /// copy, so hashing the string is constant time.)
74 ///
75 /// The free functions \c TfToTokenVector() and \c TfToStringVector() provide
76 /// conversions to and from vectors of \c string.
77 ///
78 /// Note: Access to the global table is protected by a mutex. This is a good
79 /// idea as long as clients do not construct tokens from strings too
80 /// frequently. Construct tokens only as often as you must (for example, as
81 /// you read data files), and <i>never</i> in inner loops. Of course, once
82 /// you have a token, feel free to compare, assign, and hash it as often as
83 /// you like. (That's what it's for.) In order to help prevent tokens from
84 /// being re-created over and over, auto type conversion from \c string and \c
85 /// char* to \c TfToken is disabled (you must use the explicit \c TfToken
86 /// constructors). However, auto conversion from \c TfToken to \c string and
87 /// \c char* is provided.
88 ///
89 class TfToken
90 {
91 public:
93 
94  /// Create the empty token, containing the empty string.
95  constexpr TfToken() noexcept {}
96 
97  /// Copy constructor.
98  TfToken(TfToken const& rhs) noexcept : _rep(rhs._rep) { _AddRef(); }
99 
100  /// Move constructor.
101  TfToken(TfToken && rhs) noexcept : _rep(rhs._rep) {
102  rhs._rep = TfPointerAndBits<const _Rep>();
103  }
104 
105  /// Copy assignment.
106  TfToken& operator= (TfToken const& rhs) noexcept {
107  if (&rhs != this) {
108  rhs._AddRef();
109  _RemoveRef();
110  _rep = rhs._rep;
111  }
112  return *this;
113  }
114 
115  /// Move assignment.
116  TfToken& operator= (TfToken && rhs) noexcept {
117  if (&rhs != this) {
118  _RemoveRef();
119  _rep = rhs._rep;
120  rhs._rep = TfPointerAndBits<const _Rep>();
121  }
122  return *this;
123  }
124 
125  /// Destructor.
126  ~TfToken() { _RemoveRef(); }
127 
128  /// Acquire a token for the given string.
129  //
130  // This constructor involves a string hash and a lookup in the global
131  // table, and so should not be done more often than necessary. When
132  // possible, create a token once and reuse it many times.
133  TF_API explicit TfToken(std::string const& s);
134  /// \overload
135  // Create a token for \p s, and make it immortal. If \p s exists in the
136  // token table already and is not immortal, make it immortal. Immortal
137  // tokens are faster to copy than mortal tokens, but they will never expire
138  // and release their memory.
140 
141  /// Acquire a token for the given string.
142  //
143  // This constructor involves a string hash and a lookup in the global
144  // table, and so should not be done more often than necessary. When
145  // possible, create a token once and reuse it many times.
146  TF_API explicit TfToken(char const* s);
147  /// \overload
148  // Create a token for \p s, and make it immortal. If \p s exists in the
149  // token table already and is not immortal, make it immortal. Immortal
150  // tokens are faster to copy than mortal tokens, but they will never expire
151  // and release their memory.
152  TF_API TfToken(char const* s, _ImmortalTag);
153 
154  /// Find the token for the given string, if one exists.
155  //
156  // If a token has previous been created for the given string, this
157  // will return it. Otherwise, the empty token will be returned.
158  TF_API static TfToken Find(std::string const& s);
159 
160  /// Return a size_t hash for this token.
161  //
162  // The hash is based on the token's storage identity; this is immutable
163  // as long as the token is in use anywhere in the process.
164  //
165  size_t Hash() const { return TfHash()(_rep.Get()); }
166 
167  /// Functor to use for hash maps from tokens to other things.
168  struct HashFunctor {
169  size_t operator()(TfToken const& token) const { return token.Hash(); }
170  };
171 
172  /// \typedef TfHashSet<TfToken, TfToken::HashFunctor> HashSet;
173  ///
174  /// Predefined type for TfHashSet of tokens, since it's so awkward to
175  /// manually specify.
176  ///
178 
179  /// \typedef std::set<TfToken, TfTokenFastArbitraryLessThan> Set;
180  ///
181  /// Predefined type for set of tokens, for when faster lookup is
182  /// desired, without paying the memory or initialization cost of a
183  /// TfHashSet.
184  ///
185  typedef std::set<TfToken, TfTokenFastArbitraryLessThan> Set;
186 
187  /// Return the size of the string that this token represents.
188  size_t size() const {
189  _Rep const *rep = _rep.Get();
190  return rep ? rep->_str.size() : 0;
191  }
192 
193  /// Return the text that this token represents.
194  ///
195  /// \note The returned pointer value is not valid after this TfToken
196  /// object has been destroyed.
197  ///
198  char const* GetText() const {
199  _Rep const *rep = _rep.Get();
200  return rep ? rep->_str.c_str() : "";
201  }
202 
203  /// Synonym for GetText().
204  char const *data() const {
205  return GetText();
206  }
207 
208  /// Return the string that this token represents.
209  std::string const& GetString() const {
210  _Rep const *rep = _rep.Get();
211  return rep ? rep->_str : _GetEmptyString();
212  }
213 
214  /// Swap this token with another.
215  inline void Swap(TfToken &other) {
216  std::swap(_rep, other._rep);
217  }
218 
219  /// Equality operator
220  bool operator==(TfToken const& o) const {
221  // Equal if pointers & bits are equal, or if just pointers are. Done
222  // this way to avoid the bitwise operations for common cases.
223  return _rep.GetLiteral() == o._rep.GetLiteral() ||
224  _rep.Get() == o._rep.Get();
225  }
226 
227  /// Equality operator
228  bool operator!=(TfToken const& o) const {
229  return !(*this == o);
230  }
231 
232  /// Equality operator for \c char strings. Not as fast as direct
233  /// token to token equality testing
234  TF_API bool operator==(std::string const& o) const;
235 
236  /// Equality operator for \c char strings. Not as fast as direct
237  /// token to token equality testing
238  TF_API bool operator==(const char *) const;
239 
240  /// \overload
241  friend bool operator==(std::string const& o, TfToken const& t) {
242  return t == o;
243  }
244 
245  /// \overload
246  friend bool operator==(const char *o, TfToken const& t) {
247  return t == o;
248  }
249 
250  /// Inequality operator for \c string's. Not as fast as direct
251  /// token to token equality testing
252  bool operator!=(std::string const& o) const {
253  return !(*this == o);
254  }
255 
256  /// \overload
257  friend bool operator!=(std::string const& o, TfToken const& t) {
258  return !(t == o);
259  }
260 
261  /// Inequality operator for \c char strings. Not as fast as direct
262  /// token to token equality testing
263  bool operator!=(char const* o) const {
264  return !(*this == o);
265  }
266 
267  /// \overload
268  friend bool operator!=(char const* o, TfToken const& t) {
269  return !(t == o);
270  }
271 
272  /// Less-than operator that compares tokenized strings lexicographically.
273  /// Allows \c TfToken to be used in \c std::set
274  inline bool operator<(TfToken const& r) const {
275  auto ll = _rep.GetLiteral(), rl = r._rep.GetLiteral();
276  if (!ll) {
277  return rl;
278  }
279  if (!rl || ll == rl) {
280  return false;
281  }
282  auto lrep = _rep.Get(), rrep = r._rep.Get();
283  uint64_t lcc = lrep->_compareCode, rcc = rrep->_compareCode;
284  if (lcc < rcc) {
285  return true;
286  }
287  return lcc == rcc && lrep->_str < rrep->_str;
288  }
289 
290  /// Greater-than operator that compares tokenized strings lexicographically.
291  inline bool operator>(TfToken const& o) const {
292  return o < *this;
293  }
294 
295  /// Greater-than-or-equal operator that compares tokenized strings
296  /// lexicographically.
297  inline bool operator>=(TfToken const& o) const {
298  return !(*this < o);
299  }
300 
301  /// Less-than-or-equal operator that compares tokenized strings
302  /// lexicographically.
303  inline bool operator<=(TfToken const& o) const {
304  return !(*this > o);
305  }
306 
307  /// Allow \c TfToken to be auto-converted to \c string
308  operator std::string const& () const { return GetString(); }
309 
310  /// Returns \c true iff this token contains the empty string \c ""
311  bool IsEmpty() const { return _rep.GetLiteral() == 0; }
312 
313  /// Returns \c true iff this is an immortal token.
314  bool IsImmortal() const { return !_rep->_isCounted; }
315 
316  /// Stream insertion.
317  friend TF_API std::ostream &operator <<(std::ostream &stream, TfToken const&);
318 
319 private:
320  // Add global swap overload.
321  friend void swap(TfToken &lhs, TfToken &rhs) {
322  lhs.Swap(rhs);
323  }
324 
325  void _AddRef() const {
326  if (_rep.BitsAs<bool>()) {
327  // We believe this rep is refCounted.
328  if (!_rep->IncrementIfCounted()) {
329  // Our belief is wrong, update our cache of countedness.
330  _rep.SetBits(false);
331  }
332  }
333  }
334 
335  void _RemoveRef() const {
336  if (_rep.BitsAs<bool>()) {
337  // We believe this rep is refCounted.
338  if (_rep->_isCounted) {
339  if (_rep->_refCount.load(std::memory_order_relaxed) == 1) {
340  _PossiblyDestroyRep();
341  }
342  else {
343  /*
344  * This is deliberately racy. It's possible the statement
345  * below drops our count to zero, and we leak the rep
346  * (i.e. we leave it in the table). That's a low
347  * probability event, in exchange for only grabbing the lock
348  * (in _PossiblyDestroyRep()) when the odds are we really do
349  * need to modify the table.
350  *
351  * Note that even if we leak the rep, if we look it up
352  * again, we'll simply repull it from the table and keep
353  * using it. So it's not even necessarily a true leak --
354  * it's just a potential leak.
355  */
356  _rep->_refCount.fetch_sub(1, std::memory_order_relaxed);
357  }
358  } else {
359  // Our belief is wrong, update our cache of countedness.
360  _rep.SetBits(false);
361  }
362  }
363  }
364 
365  void TF_API _PossiblyDestroyRep() const;
366 
367  struct _Rep {
368  _Rep() {}
369  explicit _Rep(char const *s) : _str(s), _cstr(_str.c_str()) {}
370  explicit _Rep(std::string const &s) : _str(s), _cstr(_str.c_str()) {}
371 
372  // Make sure we reacquire _cstr from _str on copy and assignment
373  // to avoid holding on to a dangling pointer. However, if rhs'
374  // _cstr member doesn't come from its _str, just copy it directly
375  // over. This is to support lightweight _Rep objects used for
376  // internal lookups.
377  _Rep(_Rep const &rhs) : _str(rhs._str),
378  _cstr(rhs._str.c_str() != rhs._cstr ?
379  rhs._cstr : _str.c_str()),
380  _compareCode(rhs._compareCode),
381  _refCount(rhs._refCount.load()),
382  _isCounted(rhs._isCounted),
383  _setNum(rhs._setNum) {}
384  _Rep& operator=(_Rep const &rhs) {
385  _str = rhs._str;
386  _cstr = (rhs._str.c_str() != rhs._cstr ? rhs._cstr : _str.c_str());
387  _compareCode = rhs._compareCode;
388  _refCount = rhs._refCount.load();
389  _isCounted = rhs._isCounted;
390  _setNum = rhs._setNum;
391  return *this;
392  }
393 
394  inline bool IncrementIfCounted() const {
395  const bool isCounted = _isCounted;
396  if (isCounted) {
397  _refCount.fetch_add(1, std::memory_order_relaxed);
398  }
399  return isCounted;
400  }
401 
402  std::string _str;
403  char const *_cstr;
404  mutable uint64_t _compareCode;
405  mutable std::atomic_int _refCount;
406  mutable bool _isCounted;
407  mutable unsigned char _setNum;
408  };
409 
411  friend struct Tf_TokenRegistry;
412 
413  TF_API static std::string const& _GetEmptyString();
414 
415  mutable TfPointerAndBits<const _Rep> _rep;
416 };
417 
418 /// Fast but non-lexicographical (in fact, arbitrary) less-than comparison for
419 /// TfTokens. Should only be used in performance-critical cases.
421  inline bool operator()(TfToken const &lhs, TfToken const &rhs) const {
422  return lhs._rep.Get() < rhs._rep.Get();
423  }
424 };
425 
426 /// Convert the vector of strings \p sv into a vector of \c TfToken
427 TF_API std::vector<TfToken>
428 TfToTokenVector(const std::vector<std::string> &sv);
429 
430 /// Convert the vector of \c TfToken \p tv into a vector of strings
431 TF_API std::vector<std::string>
432 TfToStringVector(const std::vector<TfToken> &tv);
433 
434 /// Overload hash_value for TfToken.
435 inline size_t hash_value(const TfToken& x) { return x.Hash(); }
436 
437 /// Convenience types.
438 typedef std::vector<TfToken> TfTokenVector;
439 
441 
442 #endif // TF_TOKEN_H
GLdouble s
Definition: glew.h:1390
void Swap(TfToken &other)
Swap this token with another.
Definition: token.h:215
friend TF_API std::ostream & operator<<(std::ostream &stream, TfToken const &)
Stream insertion.
_ImmortalTag
Definition: token.h:92
GLuint GLuint stream
Definition: glew.h:7265
#define TF_API
Definition: api.h:40
void swap(UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual > &a, UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual > &b)
Definition: UT_ArraySet.h:1629
void SetBits(Integral val) noexcept
Set the stored bits. No static range checking is performed.
bool IsImmortal() const
Returns true iff this is an immortal token.
Definition: token.h:314
std::string const & GetString() const
Return the string that this token represents.
Definition: token.h:209
Functor to use for hash maps from tokens to other things.
Definition: token.h:168
TF_API std::vector< TfToken > TfToTokenVector(const std::vector< std::string > &sv)
Convert the vector of strings sv into a vector of TfToken.
TfToken & operator=(TfToken const &rhs) noexcept
Copy assignment.
Definition: token.h:106
friend bool operator!=(std::string const &o, TfToken const &t)
Definition: token.h:257
bool operator()(TfToken const &lhs, TfToken const &rhs) const
Definition: token.h:421
size_t size() const
Return the size of the string that this token represents.
Definition: token.h:188
constexpr T * Get() const noexcept
Retrieve the pointer.
TfHashSet< TfToken, TfToken::HashFunctor > HashSet
Definition: token.h:177
Definition: hash.h:86
bool operator<=(TfToken const &o) const
Definition: token.h:303
atomic< int > atomic_int
Definition: atomic.h:51
bool operator!=(char const *o) const
Definition: token.h:263
Definition: token.h:89
constexpr uintptr_t GetLiteral() const noexcept
size_t operator()(TfToken const &token) const
Definition: token.h:169
size_t hash_value(const TfToken &x)
Overload hash_value for TfToken.
Definition: token.h:435
GLint GLint GLint GLint GLint x
Definition: glew.h:1252
TfToken(TfToken &&rhs) noexcept
Move constructor.
Definition: token.h:101
char const * data() const
Synonym for GetText().
Definition: token.h:204
friend void swap(TfToken &lhs, TfToken &rhs)
Definition: token.h:321
TfToken(TfToken const &rhs) noexcept
Copy constructor.
Definition: token.h:98
constexpr Integral BitsAs() const noexcept
Retrieve the stored bits as the integral type Integral.
bool operator>(TfToken const &o) const
Greater-than operator that compares tokenized strings lexicographically.
Definition: token.h:291
std::vector< TfToken > TfTokenVector
Convenience types.
Definition: token.h:438
friend bool operator==(std::string const &o, TfToken const &t)
Definition: token.h:241
friend bool operator!=(char const *o, TfToken const &t)
Definition: token.h:268
char const * GetText() const
Definition: token.h:198
bool operator!=(std::string const &o) const
Definition: token.h:252
GLsizei const GLchar *const * string
Definition: glew.h:1844
bool operator!=(TfToken const &o) const
Equality operator.
Definition: token.h:228
PXR_NAMESPACE_CLOSE_SCOPE PXR_NAMESPACE_OPEN_SCOPE
Definition: path.h:1245
static TF_API TfToken Find(std::string const &s)
Find the token for the given string, if one exists.
TF_API std::vector< std::string > TfToStringVector(const std::vector< TfToken > &tv)
Convert the vector of TfToken tv into a vector of strings.
~TfToken()
Destructor.
Definition: token.h:126
GLdouble GLdouble GLdouble r
Definition: glew.h:1406
#define PXR_NAMESPACE_CLOSE_SCOPE
Definition: pxr.h:83
friend struct Tf_TokenRegistry
Definition: token.h:411
bool operator==(TfToken const &o) const
Equality operator.
Definition: token.h:220
bool operator<(TfToken const &r) const
Definition: token.h:274
constexpr TfToken() noexcept
Create the empty token, containing the empty string.
Definition: token.h:95
friend bool operator==(const char *o, TfToken const &t)
Definition: token.h:246
size_t Hash() const
Return a size_t hash for this token.
Definition: token.h:165
bool operator>=(TfToken const &o) const
Definition: token.h:297
GLdouble GLdouble t
Definition: glew.h:1398
std::set< TfToken, TfTokenFastArbitraryLessThan > Set
Definition: token.h:185
bool IsEmpty() const
Returns true iff this token contains the empty string "".
Definition: token.h:311