| 4680 |
right-hear |
1 |
/** \file lisphash.h |
|
|
2 |
* hashing of strings. Each string will exist only once in the |
|
|
3 |
* hash table, and have an unique id. |
|
|
4 |
*/ |
|
|
5 |
|
|
|
6 |
|
|
|
7 |
#ifndef __lisphash_h__ |
|
|
8 |
#define __lisphash_h__ |
|
|
9 |
|
|
|
10 |
#include "yacasbase.h" |
|
|
11 |
#include "grower.h" |
|
|
12 |
#include "lispstring.h" |
|
|
13 |
|
|
|
14 |
|
|
|
15 |
const LispInt KSymTableSize = 211; |
|
|
16 |
LispInt LispHash( const char *s ); |
|
|
17 |
LispInt LispHashCounted( const char *s, LispInt length ); |
|
|
18 |
LispInt LispHashStringify( const char *s ); |
|
|
19 |
LispInt LispHashUnStringify( const char *s ); |
|
|
20 |
LispInt LispHashPtr(const LispString * aString); // hash the *address*! |
|
|
21 |
|
|
|
22 |
/** |
|
|
23 |
* This is the symbol table, implemented as a hash table for fast |
|
|
24 |
* lookup. It is meant to store any string just once, have fast |
|
|
25 |
* searching for strings and return a reference to the string. |
|
|
26 |
* This also allows fast comparison of two strings (two strings |
|
|
27 |
* are equal iff the pointers to the strings are equal). |
|
|
28 |
*/ |
|
|
29 |
class LispHashTable : public YacasBase |
|
|
30 |
{ |
|
|
31 |
public: |
|
|
32 |
LispHashTable() {} |
|
|
33 |
~LispHashTable(); |
|
|
34 |
// If string not yet in table, insert. Afterwards return the string. |
|
|
35 |
LispString * LookUp(const LispChar * aString, LispBoolean aStringOwnedExternally=LispFalse); |
|
|
36 |
/// LookUp that takes ownership of the string |
|
|
37 |
LispString * LookUp(LispString * aString); |
|
|
38 |
LispString * LookUpCounted(LispChar * aString,LispInt aLength); |
|
|
39 |
LispString * LookUpStringify(LispChar * aString, LispBoolean aStringOwnedExternally=LispFalse); |
|
|
40 |
LispString * LookUpUnStringify(LispChar * aString, LispBoolean aStringOwnedExternally=LispFalse); |
|
|
41 |
void GarbageCollect(); |
|
|
42 |
private: |
|
|
43 |
void AppendString(LispInt bin,LispString * result); |
|
|
44 |
private: |
|
|
45 |
CArrayGrower > iHashTable[KSymTableSize]; |
|
|
46 |
}; |
|
|
47 |
|
|
|
48 |
|
|
|
49 |
|
|
|
50 |
|
|
|
51 |
|
|
|
52 |
/** VoidGrow is a helper class for LispAssociatedHash |
|
|
53 |
*/ |
|
|
54 |
class VoidGrow : public CArrayGrower > |
|
|
55 |
{ |
|
|
56 |
}; |
|
|
57 |
|
|
|
58 |
/** LispAssociatedHash allows you to associate arbitrary |
|
|
59 |
* information with a string in the above hash table. You can |
|
|
60 |
* specify what type of information to link to the string, and |
|
|
61 |
* this class then stores that information for a string. It is |
|
|
62 |
* in a sense a way to extend the string object without modifying |
|
|
63 |
* the string class itself. This class does not own the strings it |
|
|
64 |
* points to, but instead relies on the fact that the strings |
|
|
65 |
* are maintained in a hash table (like LispHashTable above). |
|
|
66 |
*/ |
|
|
67 |
template |
|
|
68 |
class LispAssociatedHash : public YacasBase |
|
|
69 |
{ |
|
|
70 |
public: |
|
|
71 |
/// Find the data associated to \a aString. |
|
|
72 |
/// If \a aString is not stored in the hash table, this function |
|
|
73 |
/// returns #NULL. |
|
|
74 |
inline T* LookUp(LispString * aString); |
|
|
75 |
|
|
|
76 |
/// Add an association to the hash table. |
|
|
77 |
/// If \a aString is already stored in the hash table, its |
|
|
78 |
/// association is changed to \a aData. Otherwise, a new |
|
|
79 |
/// association is added. |
|
|
80 |
inline void SetAssociation(const T& aData, LispString * aString); |
|
|
81 |
|
|
|
82 |
/// Delete an association from the hash table. |
|
|
83 |
inline void Release(LispString * aString); |
|
|
84 |
|
|
|
85 |
protected: |
|
|
86 |
/** The destructor is made protected because we do not want the outside world to directly |
|
|
87 |
* call this destructor. The alternative would be to make the destructor virtual. |
|
|
88 |
*/ |
|
|
89 |
inline ~LispAssociatedHash(); |
|
|
90 |
|
|
|
91 |
private: |
|
|
92 |
// The next array is in fact an array of arrays of type LAssoc |
|
|
93 |
VoidGrow iHashTable[KSymTableSize]; |
|
|
94 |
}; |
|
|
95 |
|
|
|
96 |
|
|
|
97 |
|
|
|
98 |
#include "lisphash.inl" |
|
|
99 |
|
|
|
100 |
|
|
|
101 |
#endif |