• Skip to content
• Skip to link menu

KDE 3.5 API Reference

• KDE API Reference
• API Reference

• Sitemap
• Contact Us

 

kviewshell

GContainer.h

Go to the documentation of this file.

//C-  -*- C++ -*-
//C- -------------------------------------------------------------------
//C- DjVuLibre-3.5
//C- Copyright (c) 2002  Leon Bottou and Yann Le Cun.
//C- Copyright (c) 2001  AT&T
//C-
//C- This software is subject to, and may be distributed under, the
//C- GNU General Public License, Version 2. The license should have
//C- accompanied the software or you may obtain a copy of the license
//C- from the Free Software Foundation at http://www.fsf.org .
//C-
//C- This program is distributed in the hope that it will be useful,
//C- but WITHOUT ANY WARRANTY; without even the implied warranty of
//C- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//C- GNU General Public License for more details.
//C- 
//C- DjVuLibre-3.5 is derived from the DjVu(r) Reference Library
//C- distributed by Lizardtech Software.  On July 19th 2002, Lizardtech 
//C- Software authorized us to replace the original DjVu(r) Reference 
//C- Library notice by the following text (see doc/lizard2002.djvu):
//C-
//C-  ------------------------------------------------------------------
//C- | DjVu (r) Reference Library (v. 3.5)
//C- | Copyright (c) 1999-2001 LizardTech, Inc. All Rights Reserved.
//C- | The DjVu Reference Library is protected by U.S. Pat. No.
//C- | 6,058,214 and patents pending.
//C- |
//C- | This software is subject to, and may be distributed under, the
//C- | GNU General Public License, Version 2. The license should have
//C- | accompanied the software or you may obtain a copy of the license
//C- | from the Free Software Foundation at http://www.fsf.org .
//C- |
//C- | The computer code originally released by LizardTech under this
//C- | license and unmodified by other parties is deemed "the LIZARDTECH
//C- | ORIGINAL CODE."  Subject to any third party intellectual property
//C- | claims, LizardTech grants recipient a worldwide, royalty-free, 
//C- | non-exclusive license to make, use, sell, or otherwise dispose of 
//C- | the LIZARDTECH ORIGINAL CODE or of programs derived from the 
//C- | LIZARDTECH ORIGINAL CODE in compliance with the terms of the GNU 
//C- | General Public License.   This grant only confers the right to 
//C- | infringe patent claims underlying the LIZARDTECH ORIGINAL CODE to 
//C- | the extent such infringement is reasonably necessary to enable 
//C- | recipient to make, have made, practice, sell, or otherwise dispose 
//C- | of the LIZARDTECH ORIGINAL CODE (or portions thereof) and not to 
//C- | any greater extent that may be necessary to utilize further 
//C- | modifications or combinations.
//C- |
//C- | The LIZARDTECH ORIGINAL CODE is provided "AS IS" WITHOUT WARRANTY
//C- | OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
//C- | TO ANY WARRANTY OF NON-INFRINGEMENT, OR ANY IMPLIED WARRANTY OF
//C- | MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
//C- +------------------------------------------------------------------
// 
// $Id: GContainer.h,v 1.15 2004/05/13 15:16:34 leonb Exp $
// $Name: release_3_5_15 $

#ifndef _GCONTAINER_H_
#define _GCONTAINER_H_
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
#if NEED_GNUG_PRAGMAS
# pragma interface
#endif


#include "GException.h"
#include "GSmartPointer.h"
#include <string.h>

#ifdef HAVE_NAMESPACES
namespace DJVU {
# ifdef NOT_DEFINED // Just to fool emacs c++ mode
}
#endif
#endif


// Supports old iterators (first/last/next/prev) on lists and maps?
#ifndef GCONTAINER_OLD_ITERATORS
#define GCONTAINER_OLD_ITERATORS 1
#endif

// Check array bounds at runtime ?
#ifndef GCONTAINER_BOUNDS_CHECK
#define GCONTAINER_BOUNDS_CHECK 1
#endif

// Clears allocated memory prior to running constructors ?
#ifndef GCONTAINER_ZERO_FILL
#define GCONTAINER_ZERO_FILL 1
#endif

// Avoid member templates (needed by old compilers)
#ifndef GCONTAINER_NO_MEMBER_TEMPLATES
#if defined(__GNUC__) && (__GNUC__==2) && (__GNUC_MINOR__<91)
#define GCONTAINER_NO_MEMBER_TEMPLATES 1
#elif defined(_MSC_VER) && !defined(__ICL)
#define GCONTAINER_NO_MEMBER_TEMPLATES 1
#elif defined(__MWERKS__)
#define GCONTAINER_NO_MEMBER_TEMPLATES 1
#else
#define GCONTAINER_NO_MEMBER_TEMPLATES 0
#endif
#endif

// Define typename when needed
#ifndef GCONTAINER_NO_TYPENAME
#define GCONTAINER_NO_TYPENAME 0
#endif
#if GCONTAINER_NO_TYPENAME
#define typename 
#endif





// ------------------------------------------------------------
// HELPER CLASSES
// ------------------------------------------------------------



/* Namespace for containers support classes.  This class is used as a
   namespace for global identifiers related to the implementation of
   containers.  It is inherited by all container objects.  This is disabled by
   defining compilation symbol #GCONTAINER_NO_MEMBER_TEMPATES# to 1. */


#ifdef _MSC_VER
// Language lawyer say MS is wrong on that one. 
// Cf section 5.4.7 in november 1997 draft.
#pragma warning( disable : 4243 )
#endif


// GPEnabled inhertenced removed again so the code works on more machines.
class GCont
#if GCONTAINER_NO_MEMBER_TEMPLATES
{
};
#else
{
public:
#endif
  // --- Pointers to type management functions
  struct Traits
  {
    int       size;
    void     *(*lea)     (void *base, int n);
    void      (*init)    (void *dst, int n); 
    void      (*copy)    (void *dst, const void* src, int n, int zap);
    void      (*fini)    (void *dst, int n);
  };
#if !GCONTAINER_NO_MEMBER_TEMPLATES
protected:
#endif
  // --- Management of simple types
  template <int SZ> class TrivTraits
  {
  public:
    // The unique object
    static const Traits & traits();
    // Offset in an array of T
    static void * lea(void* base, int n)
      { return (void*)( ((char*)base) + SZ*n ); }
    // Trivial default constructor
    static void   init(void* dst, int n) {}
    // Trivial copy constructor
    static void   copy(void* dst, const void* src, int n, int ) 
      { memcpy(dst, src, SZ*n); }
    // Trivial destructor
    static void   fini(void* dst, int n) {}
  };
  // --- Management of regular types
  template <class T> class NormTraits
  {
  public:
    // The unique object
    static const Traits & traits();
    // Offset in an array of T
    static void * lea(void* base, int n)
      { return (void*)( ((T*)base) + n ); }
    // Template based default constructor
    static void init(void* dst, int n) 
      { T* d = (T*)dst;   while (--n>=0) { new ((void*)d) T; d++; } }
    // Template based copy constructor
    static void copy(void* dst, const void* src, int n, int zap)
      { T* d = (T*)dst; const T *s = (const T*)src; 
        while (--n>=0) { new ((void*)d) T(*s); if (zap) { s->T::~T(); }; d++; s++; } }
    // Template based destructor
    static void fini(void* dst, int n) 
      { T* d = (T*)dst; while (--n>=0) { d->T::~T(); d++; } }
  };
  // --- Base class for list nodes
  struct Node
  {
    Node *next;
    Node *prev;
  };
  // -- Class for list nodes
  template <class T> struct ListNode : public Node
  { 
    T val;
  };
  // -- Class for map nodes showing the hash
  struct HNode : public Node
  {
    HNode *hprev;
    unsigned int hashcode;
  };
  // -- Class for map nodes showing the hash and the key
  template <class K> struct SetNode : public HNode
  { 
    K key;
  };
  // -- Class for map nodes with everything
  template <class K, class T> struct MapNode : public SetNode<K>
  {
    T val;
  };
#if !GCONTAINER_NO_MEMBER_TEMPLATES
};
#endif


#if !GCONTAINER_NO_MEMBER_TEMPLATES
#define GCONT GCont::
#else
#define GCONT
#endif

template <int SZ> const GCONT Traits & 
GCONT TrivTraits<SZ>::traits()
{
  static const Traits theTraits = {
    SZ,
    TrivTraits<SZ>::lea,
    TrivTraits<SZ>::init,
    TrivTraits<SZ>::copy,
    TrivTraits<SZ>::fini
  };
  return theTraits;
}

template <class T> const GCONT Traits & 
GCONT NormTraits<T>::traits()
{
  static const Traits theTraits = {
    sizeof(T),
    NormTraits<T>::lea,
    NormTraits<T>::init,
    NormTraits<T>::copy,
    NormTraits<T>::fini
  };
  return theTraits;
}


// ------------------------------------------------------------
// DYNAMIC ARRAYS
// ------------------------------------------------------------



class GArrayBase : public GCont
{
public:
  // -- CONSTRUCTORS
  GArrayBase(const GArrayBase &ref);
  GArrayBase(const Traits &traits);
  GArrayBase(const Traits &traits, int lobound, int hibound);
  // -- DESTRUCTOR
  ~GArrayBase();
  // -- ASSIGNMENT
  GArrayBase& operator= (const GArrayBase &ga);
  // -- ALTERATION
  void empty();
  void touch(int n);
  void resize(int lobound, int hibound);
  void shift(int disp);
  void del(int n, int howmany=1);
  void ins(int n, const void *src, int howmany=1);
  void steal(GArrayBase &ga);
protected:
  const Traits &traits;
  void  *data;
  GPBufferBase gdata;
  int   minlo;
  int   maxhi;
  int   lobound;
  int   hibound;
};


template<class TYPE>
class GArrayTemplate : protected GArrayBase
{
public:
  // -- CONSTRUCTORS
  GArrayTemplate(const Traits &traits) : GArrayBase(traits) {}
  GArrayTemplate(const Traits &traits, int lobound, int hibound)
    : GArrayBase(traits, lobound, hibound) {}
  // -- ACCESS
  int size() const
    { return hibound-lobound+1; }
  int lbound() const
    { return lobound; }
  int hbound() const
    { return hibound; }
  inline TYPE& operator[](int const n);
  inline const TYPE& operator[](int n) const;
  // -- CONVERSION
  operator TYPE* ()
    { return ((TYPE*)data)-minlo; }
  operator const TYPE* () const
    { return ((const TYPE*)data)-minlo; }
  operator const TYPE* ()  // suppress warning with gcc-2.95
    { return ((const TYPE*)data)-minlo; }
  // -- ALTERATION
  void empty()
    { GArrayBase::empty(); }
  void touch(int n)
    { if (n<lobound || n>hibound) GArrayBase::touch(n); }
  void resize(int hibound)
    { GArrayBase::resize(0, hibound); }
  void resize(int lobound, int hibound)
    { GArrayBase::resize(lobound, hibound); }
  void shift(int disp)
    { GArrayBase::shift(disp); }
  void del(int n, int howmany=1)
    { GArrayBase::del(n, howmany); }
  void ins(int n, int howmany=1)
    { GArrayBase::ins(n, 0, howmany); }
  void ins(int n, const TYPE &val, int howmany=1)
    { GArrayBase::ins(n, (const void*)&val, howmany); }
  void steal(GArrayTemplate &ga)
    { GArrayBase::steal(ga); }
  // -- SORTING
  void sort()
    { sort(lbound(), hbound()); }
  void sort(int lo, int hi);
};



/* That one must be implemented as a regular template function. */
template <class TYPE> void
GArrayTemplate<TYPE>::sort(int lo, int hi)
{
  if (hi <= lo)
    return;
  if (hi > hibound || lo<lobound)
    G_THROW( ERR_MSG("GContainer.illegal_subscript") );
  TYPE *data = (TYPE*)(*this);
  // Test for insertion sort
  if (hi <= lo + 50)
    {
      for (int i=lo+1; i<=hi; i++)
        {
          int j = i;
          TYPE tmp = data[i];
          while ((--j>=lo) && !(data[j]<=tmp))
            data[j+1] = data[j];
          data[j+1] = tmp;
        }
      return;
    }
  // -- determine suitable quick-sort pivot
  TYPE tmp = data[lo];
  TYPE pivot = data[(lo+hi)/2];
  if (pivot <= tmp)
    { tmp = pivot; pivot=data[lo]; }
  if (data[hi] <= tmp)
    { pivot = tmp; }
  else if (data[hi] <= pivot)
    { pivot = data[hi]; }
  // -- partition set
  int h = hi;
  int l = lo;
  while (l < h)
    {
      while (! (pivot <= data[l])) l++;
      while (! (data[h] <= pivot)) h--;
      if (l < h)
        {
          tmp = data[l];
          data[l] = data[h];
          data[h] = tmp;
          l = l+1;
          h = h-1;
      }
    }
  // -- recursively restart
  sort(lo, h);
  sort(l, hi);
}

template<class TYPE> inline TYPE&
GArrayTemplate<TYPE>::operator[](int const n)
{
#if GCONTAINER_BOUNDS_CHECK
  if (n<lobound || n>hibound)
  {
    G_THROW( ERR_MSG("GContainer.illegal_subscript") ); 
  }
#endif
  return ((TYPE*)data)[n-minlo];
}


template<class TYPE> inline const TYPE &
GArrayTemplate<TYPE>::operator[](int const n) const
{
#if GCONTAINER_BOUNDS_CHECK
  if (n<lobound || n>hibound)
  {
    G_THROW( ERR_MSG("GContainer.illegal_subscript") ); 
  }
#endif
  return ((const TYPE*)data)[n-minlo];
}



template<class TYPE>
class GArray : public GArrayTemplate<TYPE>
{
public:
  GArray() 
    : GArrayTemplate<TYPE>(GCONT NormTraits<TYPE>::traits() ) {}
  GArray(int hi) 
    : GArrayTemplate<TYPE>(GCONT NormTraits<TYPE>::traits(), 0, hi ) {}
  GArray(int lo, int hi) 
    : GArrayTemplate<TYPE>(GCONT NormTraits<TYPE>::traits(), lo, hi ) {}
  // Copy operator
  GArray& operator=(const GArray &r)
    { GArrayBase::operator=(r); return *this; }
};


template<class TYPE>
class GPArray : public GArrayTemplate<GP<TYPE> >
{
public:
  GPArray() 
    : GArrayTemplate<GP<TYPE> >(GCONT NormTraits<GPBase>::traits() ) {}
  GPArray(int hi) 
    : GArrayTemplate<GP<TYPE> >(GCONT NormTraits<GPBase>::traits(), 0, hi ) {}
  GPArray(int lo, int hi) 
    : GArrayTemplate<GP<TYPE> >(GCONT NormTraits<GPBase>::traits(), lo, hi ) {}
  // Copy operator
  GPArray& operator=(const GPArray &r)
    { GArrayBase::operator=(r); return *this; }
};

template<class TYPE>
class GTArray : public GArrayTemplate<TYPE>
{
public:
  GTArray() 
    : GArrayTemplate<TYPE>(GCONT TrivTraits<sizeof(TYPE)>::traits() ) {}
  GTArray(int hi) 
    : GArrayTemplate<TYPE>(GCONT TrivTraits<sizeof(TYPE)>::traits(), 0, hi ) {}
  GTArray(int lo, int hi) 
    : GArrayTemplate<TYPE>(GCONT TrivTraits<sizeof(TYPE)>::traits(), lo, hi ) {}
  // Copy operator
  GTArray& operator=(const GTArray &r)
    { GArrayBase::operator=(r); return *this; }
};





// ------------------------------------------------------------
// DOUBLY LINKED LISTS
// ------------------------------------------------------------



class GPosition : protected GCont
{
public:
  GPosition() : ptr(0), cont(0) {}
  GPosition(const GPosition &ref) : ptr(ref.ptr), cont(ref.cont) {}
  operator int() const 
    { return !!ptr; }
  int operator !() const 
    { return !ptr; }
  GPosition& operator ++() 
    { if (ptr) ptr = ptr->next; return *this; }
  GPosition& operator --() 
    { if (ptr) ptr = ptr->prev; return *this; }
  // Internal. Do not use.
  GPosition(Node *p, void *c) : ptr(p), cont(c) {}
#if GCONTAINER_BOUNDS_CHECK
  Node *check(void *c) 
    { if (!ptr || c!=cont) throw_invalid(c); return ptr; }
  const Node *check(void *c) const
    { if (!ptr || c!=cont) throw_invalid(c); return ptr; }
#else
  Node *check(void *c) 
    { return ptr; }
  const Node *check(void *c) const
    { return ptr; }
#endif
protected:
  Node *ptr;
  void *cont;
  friend class GListBase;
  friend class GSetBase;
  void throw_invalid(void *c) const no_return;
};


class GListBase : public GCont
{
protected:
  GListBase(const Traits& traits);
  GListBase(const GListBase &ref);
  void append(Node *n);
  void prepend(Node *n);
  void insert_after(GPosition pos, Node *n);
  void insert_before(GPosition pos, Node *n);
  void insert_before(GPosition pos, GListBase &fromlist, GPosition &frompos);
  void del(GPosition &pos);
protected:
  const Traits &traits;
  int nelem;
  Node head;
public:
  ~GListBase();
  GListBase & operator= (const GListBase & gl);
  GPosition firstpos() const { return GPosition(head.next, (void*)this); }
  GPosition lastpos() const { return GPosition(head.prev, (void*)this); }
  int isempty() const { return nelem==0; };
  GPosition nth(unsigned int n) const;
  void empty();
};


template<class TI>
class GListImpl : public GListBase
{
protected:
  GListImpl();
  typedef GCONT ListNode<TI> LNode;
  static Node * newnode(const TI &elt);
  int operator==(const GListImpl<TI> &l2) const;
  int search(const TI &elt, GPosition &pos) const;
};

template<class TI> 
GListImpl<TI>::GListImpl() 
  : GListBase( GCONT NormTraits<LNode>::traits() ) 
{ 
}

template<class TI> GCONT Node *
GListImpl<TI>::newnode(const TI &elt)
{
  LNode  *n = (LNode *) operator new (sizeof(LNode ));
#if GCONTAINER_ZERO_FILL
  memset(n, 0, sizeof(LNode ));
#endif
  new ((void*)&(n->val)) TI(elt);
  return (Node*) n;
}

template<class TI> int
GListImpl<TI>::operator==(const GListImpl<TI> &l2) const
{
  Node *p, *q;
  for (p=head.next, q=l2.head.next; p && q; p=p->next, q=q->next )
    if (((LNode*)p)->val != ((LNode*)q)->val)
      return 0;
  return p==0 && q==0;
}

template<class TI> int
GListImpl<TI>::search(const TI &elt, GPosition &pos) const
{
  Node *n = (pos ? pos.check((void*)this) : head.next);
  for (; n; n=n->next) 
    if ( ((LNode *)n)->val == elt ) 
      break;
  if (n) pos = GPosition(n, (void*)this);
  return (n != 0);
}


template <class TYPE, class TI>
class GListTemplate : protected GListImpl<TI>
{
public:
  // -- ACCESS
  int size() const
    { return this->nelem; }
  GPosition firstpos() const
    { return GListImpl<TI>::firstpos(); }
  GPosition lastpos() const
    { return GListImpl<TI>::lastpos(); }
  operator GPosition() const
    { return firstpos(); }    
  TYPE& operator[](GPosition pos)
    { return (TYPE&) (((typename GListImpl<TI>::LNode *)pos.check((void*)this))->val); }
  const TYPE& operator[](GPosition pos) const
    { return (const TYPE&) (((const typename GListImpl<TI>::LNode *)pos.check((void*)this))->val); }
  // -- TEST
  int isempty() const 
    { return this->nelem==0; }
  int operator==(const GListTemplate<TYPE,TI> &l2) const
    { return GListImpl<TI>::operator==(l2); }
  // -- SEARCHING
  GPosition nth(unsigned int n) const
    { return GListImpl<TI>::nth(n); }
  /*  Compatibility */
  int nth(unsigned int n, GPosition &pos) const
    { GPosition npos=nth(n); if (npos) pos=npos; return !!pos; }
  GPosition contains(const TYPE &elt) const
    { GPosition pos; GListImpl<TI>::search((const TI&)elt, pos); return pos; }
  int search(const TYPE &elt, GPosition &pos) const
    { return GListImpl<TI>::search((const TI&)elt, pos); }
  // -- ALTERATION
  void empty()
    { GListImpl<TI>::empty(); }
  void append(const TYPE &elt)
    { GListImpl<TI>::append(newnode((const TI&)elt)); }
  void prepend(const TYPE &elt)
    { GListImpl<TI>::prepend(newnode((const TI&)elt)); }
  void insert_after(GPosition pos, const TYPE &elt)
    { GListImpl<TI>::insert_after(pos, newnode((const TI&)elt)); }
  void insert_before(GPosition pos, const TYPE &elt)
    { GListImpl<TI>::insert_before(pos, newnode((const TI&)elt)); }
  void insert_before(GPosition pos, GListTemplate<TYPE,TI> &fromlist, GPosition &frompos)
    { GListImpl<TI>::insert_before(pos, fromlist, frompos); }
  void del(GPosition &pos)
    { GListImpl<TI>::del(pos); }
  /* Old iterators. Do not use. */
#if GCONTAINER_OLD_ITERATORS
  void first(GPosition &pos) const { pos = firstpos(); }
  void last(GPosition &pos) const { pos = lastpos(); }
  const TYPE *next(GPosition &pos) const 
    { if (!pos) return 0; const TYPE *x=&((*this)[pos]); ++pos; return x; }
  const TYPE *prev(GPosition &pos) const 
    { if (!pos) return 0; const TYPE *x=&((*this)[pos]); --pos; return x; }
  TYPE *next(GPosition &pos)
    { if (!pos) return 0; TYPE *x=&((*this)[pos]); ++pos; return x; }
  TYPE *prev(GPosition &pos)
    { if (!pos) return 0; TYPE *x=&((*this)[pos]); --pos; return x; }
#endif
};


template <class TYPE>
class GList : public GListTemplate<TYPE,TYPE>
{
public:
  GList() : GListTemplate<TYPE,TYPE>() {}
  GList& operator=(const GList &r) 
    { GListBase::operator=(r); return *this; }
};


template <class TYPE>
class GPList : public GListTemplate<GP<TYPE>,GPBase>
{
public:
  GPList() : GListTemplate<GP<TYPE>,GPBase>() {}
  GPList& operator=(const GPList &r) 
    { GListBase::operator=(r); return *this; }
};





// ------------------------------------------------------------
// ASSOCIATIVE MAPS
// ------------------------------------------------------------


class GSetBase : public GCont
{
protected:
  GSetBase(const Traits &traits);
  GSetBase(const GSetBase &ref);
  static GCONT HNode *newnode(const void *key);
  HNode *hashnode(unsigned int hashcode) const;
  HNode *installnode(HNode *n);
  void   deletenode(HNode *n);
protected:
  const Traits &traits;
  int nelems;
  int nbuckets;
  HNode **table;
  GPBuffer<HNode *> gtable;
  HNode *first;
private:
  void insertnode(HNode *n);
  void rehash(int newbuckets);
public:
  ~GSetBase();
  GSetBase& operator=(const GSetBase &ref);
  GPosition firstpos() const;
  void del(GPosition &pos); 
  void empty();
};

template <class K>
class GSetImpl : public GSetBase
{
protected:
  GSetImpl();
  GSetImpl(const Traits &traits);
  typedef GCONT SetNode<K> SNode;
  HNode *get(const K &key) const;
  HNode *get_or_throw(const K &key) const;
  HNode *get_or_create(const K &key);
public:
  GPosition contains(const K &key) const 
    { return GPosition( get(key), (void*)this); }
  void del(const K &key) 
    { deletenode(get(key)); }
};

template<class K>
GSetImpl<K>::GSetImpl()
  : GSetBase( GCONT NormTraits<GCONT SetNode<K> >::traits() )
{ 
}

template<class K>
GSetImpl<K>::GSetImpl(const Traits &traits)
  : GSetBase(traits) 
{ 
}

template<class K> GCONT HNode *
GSetImpl<K>::get(const K &key) const
{ 
  unsigned int hashcode = hash(key);
  for (SNode *s=(SNode*)hashnode(hashcode); s; s=(SNode*)(s->hprev))
    if (s->hashcode == hashcode && s->key == key) return s;
  return 0;
}

#if GCONTAINER_BOUNDS_CHECK
template<class K> GCONT HNode *
GSetImpl<K>::get_or_throw(const K &key) const
{ 
  HNode *m = get(key);
  if (!m)
  {
    G_THROW( ERR_MSG("GContainer.cannot_add") );
  }
  return m;
}
#else
template<class K> inline GCONT HNode *
GSetImpl<K>::get_or_throw(const K &key) const
{ 
  return get(key);
}
#endif

template<class K> GCONT HNode *
GSetImpl<K>::get_or_create(const K &key)
{
  HNode *m = get(key);
  if (m) return m;
  SNode *n = (SNode*) operator new (sizeof(SNode));
#if GCONTAINER_ZERO_FILL
  memset(n, 0, sizeof(SNode));
#endif
  new ((void*)&(n->key)) K ( key );
  n->hashcode = hash((const K&)(n->key));
  installnode(n);
  return n;
}

template <class K, class TI>
class GMapImpl : public GSetImpl<K>
{
protected:
  GMapImpl();
  GMapImpl(const GCONT Traits &traits);
  typedef GCONT MapNode<K,TI> MNode;
  GCONT HNode* get_or_create(const K &key);
};

template<class K, class TI>
GMapImpl<K,TI>::GMapImpl()
  : GSetImpl<K> ( GCONT NormTraits<GCONT MapNode<K,TI> >::traits() ) 
{ 
}

template<class K, class TI>
GMapImpl<K,TI>::GMapImpl(const GCONT Traits &traits)
  : GSetImpl<K>(traits) 
{ 
}

template<class K, class TI> GCONT HNode *
GMapImpl<K,TI>::get_or_create(const K &key)
{
  GCONT HNode *m = get(key);
  if (m) return m;
  MNode *n = (MNode*) operator new (sizeof(MNode));
#if GCONTAINER_ZERO_FILL
  memset(n, 0, sizeof(MNode));
#endif
  new ((void*)&(n->key)) K  (key);
  new ((void*)&(n->val)) TI ();
  n->hashcode = hash((const K&)(n->key));
  installnode(n);
  return n;
}



template <class KTYPE, class VTYPE, class TI>
class GMapTemplate : protected GMapImpl<KTYPE,TI>
{
public:
  int size() const
    { return this->nelems; }
  GPosition firstpos() const
    { return GMapImpl<KTYPE,TI>::firstpos(); }
  operator GPosition() const
    { return firstpos(); }    
  int isempty() const
    { return this->nelems==0; }
  GPosition contains(const KTYPE &key) const
    { return GMapImpl<KTYPE,TI>::contains(key); }
  /*  Compatibility */
  GPosition contains(const KTYPE &key, GPosition &pos) const
    { return pos = GMapImpl<KTYPE,TI>::contains(key); }
  // -- ALTERATION
  void empty()
    { GMapImpl<KTYPE,TI>::empty(); }
  const KTYPE &key(const GPosition &pos) const
    { return (const KTYPE&)(((typename GMapImpl<KTYPE,TI>::MNode*)(pos.check((void*)this)))->key); }
  VTYPE& operator[](const GPosition &pos)
    { return (VTYPE&)(((typename GMapImpl<KTYPE,TI>::MNode*)(pos.check((void*)this)))->val); }
  const VTYPE& operator[](const GPosition &pos) const
    { return (const VTYPE&)(((typename GMapImpl<KTYPE,TI>::MNode*)(pos.check((void*)this)))->val); }
  const VTYPE& operator[](const KTYPE &key) const
    { return (const VTYPE&)(((const typename GMapImpl<KTYPE,TI>::MNode*)(get_or_throw(key)))->val); }
  VTYPE& operator[](const KTYPE &key)
    { return (VTYPE&)(((typename GMapImpl<KTYPE,TI>::MNode*)(get_or_create(key)))->val); }
  void del(GPosition &pos)
    { GSetBase::del(pos); }
  void del(const KTYPE &key)
    { GMapImpl<KTYPE,TI>::del(key); }
  /* Old iterators. Do not use. */
#if GCONTAINER_OLD_ITERATORS
  void first(GPosition &pos) const { pos = firstpos(); }
  const VTYPE *next(GPosition &pos) const 
    { if (!pos) return 0; const VTYPE *x=&((*this)[pos]); ++pos; return x; }
  VTYPE *next(GPosition &pos)
    { if (!pos) return 0; VTYPE *x=&((*this)[pos]); ++pos; return x; }
#endif
};



template <class KTYPE, class VTYPE>
class GMap : public GMapTemplate<KTYPE,VTYPE,VTYPE>
{
public:
  // -- ACCESS
  GMap() : GMapTemplate<KTYPE,VTYPE,VTYPE>() {}
  GMap& operator=(const GMap &r) 
    { GSetBase::operator=(r); return *this; }
};

template <class KTYPE, class VTYPE>
class GPMap : public GMapTemplate<KTYPE,GP<VTYPE>,GPBase>
{
public:
  GPMap() : GMapTemplate<KTYPE,GP<VTYPE>,GPBase>() {}
  GPMap& operator=(const GPMap &r) 
    { GSetBase::operator=(r); return *this; }
};


// ------------------------------------------------------------
// HASH FUNCTIONS
// ------------------------------------------------------------



static inline unsigned int 
hash(const unsigned int & x) 
{ 
  return x; 
}

static inline unsigned int 
hash(const int & x) 
{ 
  return (unsigned int)x;
}

static inline unsigned int
hash(const long & x) 
{ 
  return (unsigned int)x;
}

static inline unsigned int
hash(const unsigned long & x) 
{ 
  return (unsigned int)x;
}

static inline unsigned int 
hash(void * const & x) 
{ 
  return (unsigned long) x; 
}

static inline unsigned int 
hash(const void * const & x) 
{ 
  return (unsigned long) x; 
}

static inline unsigned int
hash(const float & x) 
{ 
  // optimizer will get rid of unnecessary code  
  unsigned int *addr = (unsigned int*)&x;
  if (sizeof(float)<2*sizeof(unsigned int))
    return addr[0];
  else
    return addr[0]^addr[1];
}

static inline unsigned int
hash(const double & x) 
{ 
  // optimizer will get rid of unnecessary code
  unsigned int *addr = (unsigned int*)&x;
  if (sizeof(double)<2*sizeof(unsigned int))
    return addr[0];
  else if (sizeof(double)<4*sizeof(unsigned int))
    return addr[0]^addr[1];
  else
    return addr[0]^addr[1]^addr[2]^addr[3];    
}





// ------------ THE END


#ifdef HAVE_NAMESPACES
}
# ifndef NOT_USING_DJVU_NAMESPACE
using namespace DJVU;
# endif
#endif
#endif

kviewshell

Skip menu "kviewshell"

• Main Page
• Namespace List
• Class Hierarchy
• Alphabetical List
• Class List
• File List
• Namespace Members
• Class Members

API Reference

Skip menu "API Reference"

• kviewshell

Generated for API Reference by doxygen 1.5.9
This website is maintained by Adriaan de Groot and Allen Winter.
KDE^® and the K Desktop Environment^® logo are registered trademarks of KDE e.V. | Legal