Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  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<LispStringSmartPtr, ArrOpsCustomObj<LispStringSmartPtr> > iHashTable[KSymTableSize];
  46. };
  47.  
  48.  
  49.  
  50.  
  51.  
  52. /** VoidGrow is a helper class for LispAssociatedHash
  53.  */
  54. class VoidGrow : public CArrayGrower<void*, ArrOpsCustomPtr<void> >
  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<class T>
  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<T>
  93.   VoidGrow iHashTable[KSymTableSize];
  94. };
  95.  
  96.  
  97.  
  98. #include "lisphash.inl"
  99.  
  100.  
  101. #endif
  102.