Panda3D

simpleHashMap.h

00001 // Filename: simpleHashMap.h
00002 // Created by:  drose (19Jul07)
00003 //
00004 ////////////////////////////////////////////////////////////////////
00005 //
00006 // PANDA 3D SOFTWARE
00007 // Copyright (c) Carnegie Mellon University.  All rights reserved.
00008 //
00009 // All use of this software is subject to the terms of the revised BSD
00010 // license.  You should have received a copy of this license along
00011 // with this source code in a file named "LICENSE."
00012 //
00013 ////////////////////////////////////////////////////////////////////
00014 
00015 #ifndef SIMPLEHASHMAP_H
00016 #define SIMPLEHASHMAP_H
00017 
00018 #include "pandabase.h"
00019 #include "pvector.h"
00020 #include "config_util.h"
00021 
00022 ////////////////////////////////////////////////////////////////////
00023 //       Class : SimpleHashMap
00024 // Description : This template class implements an unordered map of
00025 //               keys to data, implemented as a hashtable.  It is
00026 //               similar to STL's hash_map, but (a) it has a simpler
00027 //               interface (we don't mess around with iterators), (b)
00028 //               it wants an additional method on the Compare object,
00029 //               Compare::is_equal(a, b), and (c) it doesn't depend on
00030 //               the system STL providing hash_map.
00031 ////////////////////////////////////////////////////////////////////
00032 template<class Key, class Value, class Compare = method_hash<Key, less<Key> > >
00033 class SimpleHashMap {
00034 public:
00035 #ifndef CPPPARSER
00036   INLINE SimpleHashMap(const Compare &comp = Compare());
00037   INLINE ~SimpleHashMap();
00038 
00039   INLINE void swap(SimpleHashMap &other);
00040 
00041   int find(const Key &key) const;
00042   int store(const Key &key, const Value &data);
00043   INLINE bool remove(const Key &key);
00044   void clear();
00045 
00046   INLINE Value &operator [] (const Key &key);
00047 
00048   INLINE int get_size() const;
00049   INLINE bool has_element(int n) const;
00050   INLINE const Key &get_key(int n) const;
00051   INLINE const Value &get_data(int n) const;
00052   INLINE Value &modify_data(int n);
00053   INLINE void set_data(int n, const Value &data);
00054   void remove_element(int n);
00055 
00056   INLINE int get_num_entries() const;
00057   INLINE bool is_empty() const;
00058 
00059   void output(ostream &out) const;
00060   void write(ostream &out) const;
00061   bool validate() const;
00062 
00063 private:
00064   class TableEntry;
00065 
00066   INLINE size_t get_hash(const Key &key) const;
00067 
00068   INLINE bool is_element(int n, const Key &key) const;
00069   INLINE void store_new_element(int n, const Key &key, const Value &data);
00070   INLINE void clear_element(int n);
00071   INLINE unsigned char *get_exists_array() const;
00072 
00073   void new_table();
00074   INLINE bool consider_expand_table();
00075   void expand_table();
00076 
00077   class TableEntry {
00078   public:
00079     INLINE TableEntry(const Key &key, const Value &data) :
00080       _key(key),
00081       _data(data) {}
00082     Key _key;
00083     Value _data;
00084   };
00085 
00086   TableEntry *_table;
00087   DeletedBufferChain *_deleted_chain;
00088   size_t _table_size;
00089   size_t _num_entries;
00090 
00091   Compare _comp;
00092 #endif  // CPPPARSER
00093 };
00094 
00095 template<class Key, class Value, class Compare>
00096 inline ostream &operator << (ostream &out, const SimpleHashMap<Key, Value, Compare> &shm) {
00097   shm.output(out);
00098   return out;
00099 }
00100 
00101 #ifndef CPPPARSER
00102 #include "simpleHashMap.I"
00103 #endif  // CPPPARSER
00104 
00105 #endif
00106 
 All Classes Functions Variables Enumerations