Public API Reference

csutil/weakkeyedhash.h

/*
    Copyright (C) 2011 by Frank Richter

    This library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
    License as published by the Free Software Foundation; either
    version 2 of the License, or (at your option) any later version.

    This library is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    Library General Public License for more details.

    You should have received a copy of the GNU Library General Public
    License along with this library; if not, write to the Free
    Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/

#ifndef __CSUTIL_WEAKKEYEDHASH_H__
#define __CSUTIL_WEAKKEYEDHASH_H__

#include "hash.h"

namespace CS
{
  namespace Container
  {
    template <class T, class K,
      class ArrayMemoryAlloc = CS::Container::ArrayAllocDefault,
      class ArrayElementHandler = csArraySafeCopyElementHandler<
        CS::Container::HashElement<T, K> > > 
    class WeakKeyedHash :
      protected csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler>
    {
      typedef csHash<T, K, ArrayMemoryAlloc, ArrayElementHandler> Superclass;
    public:
      void Purge ()
      {
        for (size_t e = 0; e < this->Elements.GetSize(); e++)
        {
          typename Superclass::ElementArray& values = this->Elements[e];
          for (size_t i = 0; i < values.GetSize (); ++i)
          {
            const typename Superclass::Element& v = values[i];
            // Delete any elements with 'invalid' keys while searching
            if (!v.GetKey())
            {
              values.DeleteIndexFast (i);
              this->Size--;
              i--;
            }
          }
        }
      }

      const T& Get (const K& key, const T& fallback)
      {
        if (this->Elements.GetSize() == 0) return fallback;
        typename Superclass::ElementArray& values = 
          this->Elements[csHashComputer<K>::ComputeHash (key) % this->Modulo];
        for (size_t i = 0; i < values.GetSize (); ++i)
        {
          const typename Superclass::Element& v = values[i];
          // Delete any elements with 'invalid' keys while searching
          if (!v.GetKey())
          {
            values.DeleteIndexFast (i);
            this->Size--;
            i--;
            continue;
          }
          if (csComparator<K, K>::Compare (v.GetKey(), key) == 0)
            return v.GetValue();
        }

        return fallback;
      }
      using Superclass::Get;
      using Superclass::GetOrCreate;
      
      T* GetElementPointer (const K& key)
      {
        if (this->Elements.GetSize() == 0) return 0;
        typename Superclass::ElementArray& values =
          this->Elements[csHashComputer<K>::ComputeHash (key) % this->Modulo];
        for (size_t i = 0; i < values.GetSize (); ++i)
        {
          typename Superclass::Element& v = values[i];
          // Delete any elements with 'invalid' keys while searching
          if (!v.GetKey())
          {
            values.DeleteIndexFast (i);
            this->Size--;
            i--;
            continue;
          }
          if (csComparator<K, K>::Compare (v.GetKey(), key) == 0)
            return &v.GetValue();
        }

        return 0;
      }
      using Superclass::GetElementPointer;

      T& Put (const K& key, const T &value)
      {
        if (this->Elements.GetSize() == 0) this->Elements.SetSize (this->Modulo);
        typename Superclass::ElementArray& values = 
          this->Elements[csHashComputer<K>::ComputeHash (key) % this->Modulo];
        // Delete any elements 'invalid' with keys while looking for a slot
        size_t idx = 0;
        while (idx < values.GetSize())
        {
          if (!values[idx].GetKey())
          {
            break;
          }
          idx++;
        }
        if (idx >= values.GetSize())
        {
          values.Push (typename Superclass::Element (key, value));
          this->Size++;
        }
        if (values.GetSize () > this->Elements.GetSize () / this->GrowRate
          && this->Elements.GetSize () < this->MaxSize)
        {
          this->Grow ();
          /* can't use 'values[idx]' since that is no longer the place where
            the item is stored. */
          return *(this->GetElementPointer (key));
        }
        return values[idx].GetValue();
      }
      T& PutUnique (const K& key, const T &value)
      {
        if (this->Elements.GetSize() == 0) this->Elements.SetSize (this->Modulo);
        typename Superclass::ElementArray& values =
          this->Elements[csHashComputer<K>::ComputeHash (key) % this->Modulo];
        const size_t len = values.GetSize ();
        for (size_t i = 0; i < len; )
        {
          typename Superclass::Element& v = values[i];
          // Delete any elements 'invalid' with keys while looking for the slot
          if (!v.GetKey())
          {
            values.DeleteIndexFast (i);
            continue;
          }
          if (csComparator<K, K>::Compare (v.GetKey(), key) == 0)
          {
            v.GetValue() = value;
            return v.GetValue();
          }
          ++i;
        }

        size_t idx = values.Push (typename Superclass::Element (key, value));
        this->Size++;
        if (values.GetSize () > this->Elements.GetSize () / this->GrowRate
          && this->Elements.GetSize () < this->MaxSize)
        {
          this->Grow ();
          /* can't use 'values[idx]' since that is no longer the place where
            the item is stored. */
          return *(GetElementPointer (key));
        }
        return values[idx].GetValue();
      }

      using Superclass::DeleteAll;
      
      class GlobalIterator
      {
      private:
        typedef typename Superclass::GlobalIterator WrappedIterator;
        WrappedIterator iter;
        
        bool haveNext;
        K key;
        T* value;
      protected:
        void NextElement ()
        {
          while (iter.HasNext ())
          {
            K key;
            value = &(iter.NextNoAdvance (key));
            if (key)
            {
              this->key = key;
              this->value = value;
              haveNext = true;
              return;
            }
            iter.Advance ();
            // @@@ Would be nice to clear out invalid keys as well here
            // like: ...->DeleteElement (*this);
          }
          haveNext = false;
          key = K ();
        }
        
        GlobalIterator (const WrappedIterator& iter)
         : iter (iter)
        {
          NextElement ();
        }

        friend class WeakKeyedHash<T, K, ArrayMemoryAlloc, ArrayElementHandler>;
      public:
        GlobalIterator (const GlobalIterator& o)
         : iter (o.iter), haveNext (o.haveNext), key (o.key), value (o.value) {}

        GlobalIterator& operator=(const GlobalIterator& o)
        {
          iter = o.iter;
          haveNext = o.haveNext;
          key = o.key;
          value = o.value;
          return *this;
        }

        bool HasNext () const
        {
          return haveNext;
        }

        void Advance ()
        {
      iter.Advance ();
          NextElement ();
        }

        T& NextNoAdvance ()
        {
          return *value;
        }

        T& Next ()
        {
          T &ret = NextNoAdvance ();
          Advance ();
          return ret;
        }

        T& NextNoAdvance (K &key)
        {
          key = this->key;
          return NextNoAdvance ();
        }

        T& Next (K &key)
        {
          key = this->key;
          return Next ();
        }

        const csTuple2<T, K> NextTuple ()
        {
          csTuple2<T, K> t (NextNoAdvance (),
            this->key);
          Advance ();
          return t;
        }

        void Reset ()
        {
          iter->Reset ();
          NextElement ();
        }
      };
      friend class GlobalIterator;
      
      GlobalIterator GetIterator ()
      {
        return GlobalIterator (Superclass::GetIterator ());
      }

      void DeleteElement (GlobalIterator& iterator)
      {
        Superclass::DeleteElement (iterator.iter);
      }

      class ConstGlobalIterator
      {
      private:
        typedef typename Superclass::ConstGlobalIterator WrappedIterator;
        WrappedIterator iter;

        bool haveNext;
        K key;
        const T* value;
      protected:
        void NextElement ()
        {
          while (iter.HasNext ())
          {
            K key;
            value = &(iter.NextNoAdvance (key));
            if (key)
            {
              this->key = key;
              this->value = value;
              haveNext = true;
              return;
            }
            iter.Advance ();
            // @@@ Would be nice to clear out invalid keys as well here
            // like: ...->DeleteElement (*this);
          }
          haveNext = false;
          key = K ();
        }

        ConstGlobalIterator (const WrappedIterator& iter)
        : iter (iter)
        {
          NextElement ();
        }

        friend class WeakKeyedHash<T, K, ArrayMemoryAlloc, ArrayElementHandler>;
      public:
        ConstGlobalIterator (const ConstGlobalIterator& o)
        : iter (o.iter), haveNext (o.haveNext), key (o.key), value (o.value) {}

        ConstGlobalIterator& operator=(const ConstGlobalIterator& o)
        {
          iter = o.iter;
          haveNext = o.haveNext;
          key = o.key;
          value = o.value;
          return *this;
        }

        bool HasNext () const
        {
          return haveNext;
        }

        void Advance ()
        {
          iter.Advance();
          NextElement ();
        }

        const T& NextNoAdvance ()
        {
          return *value;
        }

        const T& Next ()
        {
          const T &ret = NextNoAdvance ();
          Advance ();
          return ret;
        }

        const T& NextNoAdvance (K &key)
        {
          key = this->key;
          return NextNoAdvance ();
        }

        const T& Next (K &key)
        {
          key = this->key;
          return Next ();
        }

        const csTuple2<T, K> NextTuple ()
        {
          csTuple2<T, K> t (NextNoAdvance (),
            this->key);
          Advance ();
          return t;
        }

        void Reset ()
        {
          iter->Reset ();
          NextElement ();
        }
      };
      friend class ConstGlobalIterator;

      ConstGlobalIterator GetIterator () const
      {
        return ConstGlobalIterator (Superclass::GetIterator ());
      }

      // @@@ FIXME: More csHash<> methods (and iterators) need to be 'ported'
    };
  } // namespace Container
} // namespace CS

#endif // __CSUTIL_WEAKKEYEDHASH_H__

---