Panda3D
|
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