vcl_hashtable.h

来自「DTMK软件开发包,此为开源软件,是一款很好的医学图像开发资源.」· C头文件 代码 · 共 1,014 行 · 第 1/3 页

// This is vcl/emulation/vcl_hashtable.h
//
// Copyright (c) 1996
// Silicon Graphics Computer Systems, Inc.
//
// Permission to use, copy, modify, distribute and sell this software
// and its documentation for any purpose is hereby granted without fee,
// provided that the above copyright notice appear in all copies and
// that both that copyright notice and this permission notice appear
// in supporting documentation.  Silicon Graphics makes no
// representations about the suitability of this software for any
// purpose.  It is provided "as is" without express or implied warranty.
//
//
// Copyright (c) 1994
// Hewlett-Packard Company
//
// Permission to use, copy, modify, distribute and sell this software
// and its documentation for any purpose is hereby granted without fee,
// provided that the above copyright notice appear in all copies and
// that both that copyright notice and this permission notice appear
// in supporting documentation.  Hewlett-Packard Company makes no
// representations about the suitability of this software for any
// purpose.  It is provided "as is" without express or implied warranty.
//
// Exception Handling:
// Copyright (c) 1997
// Mark of the Unicorn, Inc.
//
// Permission to use, copy, modify, distribute and sell this software
// and its documentation for any purpose is hereby granted without fee,
// provided that the above copyright notice appear in all copies and
// that both that copyright notice and this permission notice appear
// in supporting documentation.  Mark of the Unicorn makes no
// representations about the suitability of this software for any
// purpose.  It is provided "as is" without express or implied warranty.
//
// Adaptation:
// Copyright (c) 1997
// Moscow Center for SPARC Technology
//
// Permission to use, copy, modify, distribute and sell this software
// and its documentation for any purpose is hereby granted without fee,
// provided that the above copyright notice appear in all copies and
// that both that copyright notice and this permission notice appear
// in supporting documentation.  Moscow Center for SPARC Technology makes no
// representations about the suitability of this software for any
// purpose.  It is provided "as is" without express or implied warranty.
//
#ifndef vcl_emulation_hashtable_h
#define vcl_emulation_hashtable_h

// Hashtable class, used to implement the hashed associative containers
// vcl_hash_set, vcl_hash_map, vcl_hash_multiset, and vcl_hash_multimap.


//#include <vcl_cstdlib.h>

#include "vcl_alloc.h"
#include <vcl_algorithm.h>
#include <vcl_iterator.h>
#include <vcl_vector.h>
#include "vcl_pair.h"
#include <vcl_exception.h>
//#include <vcl_memory.h>

#if defined ( __STL_USE_ABBREVS )
# define vcl_hashtable_iterator         hTIt
# define vcl_hashtable_const_iterator   hTcIt
# define vcl_hashtable_node             hTN
# define vcl_hashtable_base             hTB
# define vcl_hashtable                  hT
#endif

#if defined(VCL_EMULATION_STLCONF_H_INCLUDED)
#define VCL_debug_do(x) __stl_debug_do(x)
#define VCL_debug_check(x) __stl_debug_check(x)
#define VCL_verbose_assert(expr, msg) __stl_verbose_assert(expr, msg)
#else
#define VCL_debug_do(x)
#define VCL_debug_check(x)
#define VCL_verbose_assert(expr, msg)
#endif

template <class Key> struct vcl_hash { };

inline vcl_size_t VCL_hash_string(const char* s)
{
  unsigned long h = 0;
  for (; *s; ++s)
    h = 5*h + *s;

  return vcl_size_t(h);
}

struct vcl_hash<char*>
{
  vcl_size_t operator()(const char* s) const { return VCL_hash_string(s); }
};

struct vcl_hash<const char*>
{
  vcl_size_t operator()(const char* s) const { return VCL_hash_string(s); }
};

struct vcl_hash<char> {
  vcl_size_t operator()(char x) const { return x; }
};
struct vcl_hash<unsigned char> {
  vcl_size_t operator()(unsigned char x) const { return x; }
};
struct vcl_hash<signed char> {
  vcl_size_t operator()(unsigned char x) const { return x; }
};
struct vcl_hash<short> {
  vcl_size_t operator()(short x) const { return x; }
};
struct vcl_hash<unsigned short> {
  vcl_size_t operator()(unsigned short x) const { return x; }
};
struct vcl_hash<int> {
  vcl_size_t operator()(int x) const { return x; }
};
struct vcl_hash<unsigned int> {
  vcl_size_t operator()(unsigned int x) const { return x; }
};
struct vcl_hash<long> {
  vcl_size_t operator()(long x) const { return x; }
};
struct vcl_hash<unsigned long> {
  vcl_size_t operator()(unsigned long x) const { return x; }
};

template <class Value>
struct vcl_hashtable_node
{
  typedef vcl_hashtable_node<Value> self;
  self* next;
  Value val;
};

template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey , VCL_DFL_TYPE_PARAM_STLDECL(Alloc,vcl_alloc)>
class vcl_hashtable;

template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
struct vcl_hashtable_iterator;

template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
struct vcl_hashtable_const_iterator;

template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
struct vcl_hashtable_iterator
{
  typedef vcl_hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> hash_table;
  typedef vcl_hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> iterator;
  typedef vcl_hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> const_iterator;
  typedef vcl_hashtable_node<Value> node;
  typedef vcl_size_t size_type;
  typedef Value& reference;
  typedef const Value& const_reference;

  node* cur;
  hash_table* ht;

  vcl_hashtable_iterator(node* n, hash_table* tab) : cur(n), ht(tab) {}
  vcl_hashtable_iterator() {}
  reference operator*() const {
    VCL_verbose_assert(valid() && cur!=0,__STL_MSG_NOT_DEREFERENCEABLE);
    return cur->val;
  }
  inline iterator& operator++();
  inline iterator operator++(int);
  bool operator==(const iterator& it) const {
    VCL_debug_check(__check_same_owner(*this,it));
    return cur == it.cur;
  }
  bool operator!=(const iterator& it) const {
    VCL_debug_check(__check_same_owner(*this,it));
    return cur != it.cur;
  }
};


template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
struct vcl_hashtable_const_iterator
{
  typedef vcl_hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> hash_table;
  typedef vcl_hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> iterator;
  typedef vcl_hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> const_iterator;
  typedef vcl_hashtable_node<Value> node;
  typedef vcl_size_t size_type;
  typedef Value& reference;
  typedef const Value& const_reference;

  const node* cur;
  const hash_table* ht;

  vcl_hashtable_const_iterator(const node* n, const hash_table* tab) : cur(n), ht(tab) {}
  vcl_hashtable_const_iterator() {}
  vcl_hashtable_const_iterator(const iterator& it) : cur(it.cur), ht(it.ht) {}

  const_reference operator*() const {
    VCL_verbose_assert(valid() && cur!=0,__STL_MSG_NOT_DEREFERENCEABLE);
    return cur->val;
  }
  inline const_iterator& operator++();
  inline const_iterator operator++(int);
  bool operator==(const const_iterator& it) const {
    VCL_debug_check(__check_same_owner(*this,it));
    return cur == it.cur;
  }
  bool operator!=(const const_iterator& it) const {
    VCL_debug_check(__check_same_owner(*this,it));
    return cur != it.cur;
  }
};

// Note: assumes long is at least 32 bits.
// fbp: try to avoid intances in every module
enum { VCL_num_primes = 28 };

#if ( __STL_STATIC_TEMPLATE_DATA > 0 ) && ! defined (VCL_WIN32)
#  define VCL_prime_list VCL_prime<false>::list_
   template <bool dummy> struct VCL_prime { public: static const unsigned long list_[]; };
//rick put vcl_list in single .o  dummy here so array constant parses
//   template <bool dummy>
//   const unsigned long VCL_prime<dummy>::list_[] =
      static const unsigned long VCL_prime_list_dummy[VCL_num_primes] =
#  else
#  if ( __STL_WEAK_ATTRIBUTE > 0 )
      extern const unsigned long VCL_prime_list[VCL_num_primes] __attribute__((weak)) =
#  else
      // give up
      static const unsigned long VCL_prime_list[VCL_num_primes] =
#  endif // __STL_WEAK_ATTRIBUTE
#endif // __STL_STATIC_TEMPLATE_DATA
{
  53,         97,         193,       389,       769,
  1543,       3079,       6151,      12289,     24593,
  49157,      98317,      196613,    393241,    786433,
  1572869,    3145739,    6291469,   12582917,  25165843,
  50331653,   100663319,  201326611, 402653189, 805306457,
  1610612741, 3221225473U, 4294967291U
};

inline unsigned long VCL_next_prime(unsigned long n)
{
  const unsigned long* first = VCL_prime_list;
  const unsigned long* last = VCL_prime_list;
  last += VCL_num_primes;
  const unsigned long* pos = vcl_lower_bound(first, last, n);
  return pos == last ? *(last - 1) : *pos;
}

template <class Value, class Alloc>
class vcl_hashtable_base
{
 private:
  typedef Value value_type;
  typedef vcl_size_t size_type;
  typedef vcl_hashtable_node<Value> node;
  typedef vcl_simple_alloc<node, Alloc> node_allocator;
 public: // These are public to get around restriction on protected access
  typedef vcl_vector<VCL_SUNPRO_ALLOCATOR_HACK(node*) > buckets_type;
  buckets_type buckets; // awf killed optional allocator
  size_type num_elements;
 protected:
  inline void clear();

  node* new_node(const value_type& obj)
  {
    node* n = node_allocator::allocate();
    vcl_try {
      new (&(n->val)) value_type(obj);
    }
    vcl_catch_all {
      node_allocator::deallocate(n);
      vcl_throw "";
    }
    n->next = 0;
    return n;
  }

  void delete_node(node* n)
  {
#define vcli_destroy(T, p)    ((T*)p)->~T()
    vcli_destroy(Value, &(n->val));
#undef vcli_destroy
    node_allocator::deallocate(n);
  }

  inline void copy_from(const vcl_hashtable_base<Value,Alloc>& ht);

 public: // These are public to get around restriction on protected access
  vcl_hashtable_base() : num_elements(0) { }
 ~vcl_hashtable_base() { clear(); VCL_debug_do(invalidate()); }
};


// forward declarations
template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc> class vcl_hashtable;
template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
  bool operator== (vcl_hashtable<Value,Key,HashFcn,ExtractKey,EqualKey,Alloc>const&,
                   vcl_hashtable<Value,Key,HashFcn,ExtractKey,EqualKey,Alloc>const&);

template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
class vcl_hashtable : protected vcl_hashtable_base<Value, Alloc>
{
  typedef vcl_hashtable_base<Value, Alloc> super;
  typedef vcl_hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> self;
 public:
  typedef Key key_type;
  typedef Value value_type;
  typedef HashFcn hasher;
  typedef EqualKey key_equal;

  typedef vcl_size_t        size_type;
  typedef vcl_ptrdiff_t     difference_type;
  typedef value_type*       pointer;
  typedef const value_type* const_pointer;
  typedef value_type&       reference;
  typedef const value_type& const_reference;

  hasher hash_funct() const { return hashfun; }
  key_equal key_eq() const { return equals; }

 private:
  hasher hashfun;
  key_equal equals;
  ExtractKey get_key;

  typedef vcl_hashtable_node<Value> node;
  typedef vcl_simple_alloc<node, Alloc> node_allocator;

 public:
  typedef vcl_hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> iterator;
  typedef vcl_hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey,Alloc> const_iterator;
 friend struct