diff options
author | 2012-01-17 19:06:55 +0000 | |
---|---|---|
committer | 2012-01-17 19:06:55 +0000 | |
commit | 49f15acb7d06857c0c8cdb8e837057f05c4f0a8b (patch) | |
tree | 805a028d8e52dda49196816f8454b3f2c04dc262 /src/lib/util/tagmap.h | |
parent | c8fd0760b8b60e266d38eec880e07845f1842552 (diff) |
tagmap is just a C++ template now. Added iterators to it as
well. Updated a few outlying uses.
Diffstat (limited to 'src/lib/util/tagmap.h')
-rw-r--r-- | src/lib/util/tagmap.h | 319 |
1 files changed, 170 insertions, 149 deletions
diff --git a/src/lib/util/tagmap.h b/src/lib/util/tagmap.h index 96430157ec3..75e215de562 100644 --- a/src/lib/util/tagmap.h +++ b/src/lib/util/tagmap.h @@ -43,181 +43,202 @@ #define __TAGMAP_H__ #include "osdcore.h" +#include "astring.h" -/*************************************************************************** - CONSTANTS -***************************************************************************/ - -#define TAGMAP_HASH_SIZE 97 - +//************************************************************************** +// CONSTANTS +//************************************************************************** -enum _tagmap_error +enum tagmap_error { TMERR_NONE, - TMERR_OUT_OF_MEMORY, TMERR_DUPLICATE }; -typedef enum _tagmap_error tagmap_error; - - - -/*************************************************************************** - TYPE DEFINITIONS -***************************************************************************/ - -/* an entry in a tagmap */ -typedef struct _tagmap_entry tagmap_entry; -struct _tagmap_entry -{ - tagmap_entry * next; - void * object; - UINT32 fullhash; - char tag[1]; -}; - - -/* base tagmap structure */ -typedef struct _tagmap tagmap; -struct _tagmap -{ - tagmap_entry * table[TAGMAP_HASH_SIZE]; -}; - - - -/*************************************************************************** - FUNCTION PROTOTYPES -***************************************************************************/ - - -/* ----- map allocation and management ----- */ - -/* allocate a new tagmap */ -tagmap *tagmap_alloc(void); - -/* free a tagmap, and all entries within it */ -void tagmap_free(tagmap *map); - -/* reset a tagmap by freeing all entries */ -void tagmap_reset(tagmap *map); - - - -/* ----- object management ----- */ - -/* add a new entry to a tagmap */ -tagmap_error tagmap_add(tagmap *map, const char *tag, void *object, UINT8 replace_if_duplicate); -/* add a new entry to a tagmap, ensuring it has a unique hash value */ -tagmap_error tagmap_add_unique_hash(tagmap *map, const char *tag, void *object, UINT8 replace_if_duplicate); -/* remove an entry from a tagmap */ -void tagmap_remove(tagmap *map, const char *tag); -/* remove an entry from a tagmap by object pointer */ -void tagmap_remove_object(tagmap *map, void *object); +//************************************************************************** +// TYPE DEFINITIONS +//************************************************************************** - - -/*************************************************************************** - C++ WRAPPERS -***************************************************************************/ - -#ifdef __cplusplus - -/* derived class for C++ */ -template<class _ElementType> class tagmap_t : public tagmap +// generally used for small tables, though the hash size can be increased +// as necessary; good primes are: 53, 97, 193, 389, 769, 1543, 3079, 6151, etc +template<class _ElementType, int _HashSize = 53> +class tagmap_t { private: - tagmap_t(const tagmap &); - tagmap_t &operator=(const tagmap &); + // disable copying/assignment + tagmap_t(const tagmap_t &); + tagmap_t &operator=(const tagmap_t &); public: - tagmap_t() { memset(table, 0, sizeof(table)); } + // an entry in the table + class entry_t + { + friend class tagmap_t<_ElementType, _HashSize>; + + public: + // construction/destruction + entry_t(const char *tag, UINT32 fullhash, _ElementType object) + : m_next(NULL), + m_fullhash(fullhash), + m_tag(tag), + m_object(object) { } + + // accessors + const astring &tag() const { return m_tag; } + _ElementType object() const { return m_object; } + + // setters + void set_object(_ElementType object) { m_object = object; } + + private: + // internal helpers + entry_t *next() const { return m_next; } + UINT32 fullhash() const { return m_fullhash; } + + // internal state + entry_t * m_next; + UINT32 m_fullhash; + astring m_tag; + _ElementType m_object; + }; + + // construction/destruction + tagmap_t() { memset(m_table, 0, sizeof(m_table)); } ~tagmap_t() { reset(); } - void reset() { tagmap_reset(this); } + // core hashing function + UINT32 hash(const char *string) const + { + UINT32 result = *string++; + for (char c = *string++; c != 0; c = *string++) + result = ((result << 5) | (result >> 27)) + c; + return result; + } + + // empty the list + void reset() + { + for (UINT32 hashindex = 0; hashindex < ARRAY_LENGTH(m_table); hashindex++) + while (m_table[hashindex] != NULL) + remove_common(&m_table[hashindex]); + } + + // add/remove + tagmap_error add(const char *tag, _ElementType object, bool replace_if_duplicate = false) { return add_common(tag, object, replace_if_duplicate, false); } + tagmap_error add_unique_hash(const char *tag, _ElementType object, bool replace_if_duplicate = false) { return add_common(tag, object, replace_if_duplicate, true); } + + // remove by tag + void remove(const char *tag) + { + UINT32 fullhash = hash(tag); + for (entry_t **entryptr = &m_table[fullhash % ARRAY_LENGTH(m_table)]; *entryptr != NULL; entryptr = &(*entryptr)->m_next) + if ((*entryptr)->fullhash() == fullhash && (*entryptr)->tag() == tag) + return remove_common(entryptr); + } + + // remove by object + void remove(_ElementType object) + { + for (UINT32 hashindex = 0; hashindex < ARRAY_LENGTH(m_table); hashindex++) + for (entry_t **entryptr = &m_table[hashindex]; *entryptr != NULL; entryptr = &(*entryptr)->m_next) + if ((*entryptr)->object() == object) + return remove_common(entryptr); + } + + // find by tag + _ElementType find(const char *tag) const { return find(tag, hash(tag)); } + + // find by tag with precomputed hash + _ElementType find(const char *tag, UINT32 fullhash) const + { + for (entry_t *entry = m_table[fullhash % ARRAY_LENGTH(m_table)]; entry != NULL; entry = entry->next()) + if (entry->fullhash() == fullhash && entry->tag() == tag) + return entry->object(); + return NULL; + } + + // find by tag without checking anything but the hash + _ElementType find_hash_only(const char *tag) const + { + UINT32 fullhash = hash(tag); + for (entry_t *entry = m_table[fullhash % ARRAY_LENGTH(m_table)]; entry != NULL; entry = entry->next()) + if (entry->fullhash() == fullhash) + return entry->object(); + return NULL; + } + + // return first object in the table + entry_t *first() const { return next(NULL); } + + // return next object in the table + entry_t *next(entry_t *after) const + { + // if there's another item in this hash bucket, just return it + if (after != NULL && after->next() != NULL) + return after->next(); + + // otherwise scan forward for the next bucket with an entry + UINT32 firstindex = (after != NULL) ? (after->fullhash() % ARRAY_LENGTH(m_table) + 1) : 0; + for (UINT32 hashindex = firstindex; hashindex < ARRAY_LENGTH(m_table); hashindex++) + if (m_table[hashindex] != NULL) + return m_table[hashindex]; + + // all out + return NULL; + } - tagmap_error add(const char *tag, _ElementType object, bool replace_if_duplicate = false) { return tagmap_add(this, tag, (void *)object, replace_if_duplicate); } - tagmap_error add_unique_hash(const char *tag, _ElementType object, bool replace_if_duplicate = false) { return tagmap_add_unique_hash(this, tag, (void *)object, replace_if_duplicate); } - void remove(const char *tag) { tagmap_remove(this, tag); } - void remove(_ElementType object) { tagmap_remove_object(this, object); } - - _ElementType find(const char *tag) const { return reinterpret_cast<_ElementType>(tagmap_find(this, tag)); } - _ElementType find(const char *tag, UINT32 hash) const { return reinterpret_cast<_ElementType>(tagmap_find_prehashed(this, tag, hash)); } - _ElementType find_hash_only(const char *tag) const { return reinterpret_cast<_ElementType>(tagmap_find_hash_only(this, tag)); } +private: + // internal helpers + tagmap_error add_common(const char *tag, _ElementType object, bool replace_if_duplicate, bool unique_hash); + + // remove an entry given a pointer to its pointer + void remove_common(entry_t **entryptr) + { + entry_t *entry = *entryptr; + *entryptr = entry->next(); + delete entry; + } + + // internal state + entry_t * m_table[_HashSize]; }; -#endif - - - -/*************************************************************************** - INLINE FUNCTIONS -***************************************************************************/ - -/*------------------------------------------------- - tagmap_hash - compute the hash of a tag --------------------------------------------------*/ - -INLINE UINT32 tagmap_hash(const char *string) -{ - UINT32 hash = *string++; - char c; - - while ((c = *string++) != 0) - hash = ((hash << 5) | (hash >> 27)) + c; - return hash; -} +//************************************************************************** +// IMPLEMENTATION +//************************************************************************** -/*------------------------------------------------- - tagmap_find_prehashed - find an object - associated with a tag, given the tag's - hash --------------------------------------------------*/ +//------------------------------------------------- +// add_common - core implementation of a tagmap +// addition +//------------------------------------------------- -INLINE void *tagmap_find_prehashed(const tagmap *map, const char *tag, UINT32 fullhash) +template<class _ElementType, int _HashSize> +tagmap_error tagmap_t<_ElementType, _HashSize>::add_common(const char *tag, _ElementType object, bool replace_if_duplicate, bool unique_hash) { - tagmap_entry *entry; - - for (entry = map->table[fullhash % ARRAY_LENGTH(map->table)]; entry != NULL; entry = entry->next) - if (entry->fullhash == fullhash && strcmp(entry->tag, tag) == 0) - return entry->object; - return NULL; -} - - -/*------------------------------------------------- - tagmap_find - find an object associated - with a tag --------------------------------------------------*/ - -INLINE void *tagmap_find(const tagmap *map, const char *tag) -{ - return tagmap_find_prehashed(map, tag, tagmap_hash(tag)); -} - - -/*------------------------------------------------- - tagmap_find_hash_only - find an object - associated with a tag using only the hash; - this generally works well but may occasionally - return a false positive --------------------------------------------------*/ - -INLINE void *tagmap_find_hash_only(const tagmap *map, const char *tag) -{ - UINT32 fullhash = tagmap_hash(tag); - tagmap_entry *entry; - - for (entry = map->table[fullhash % ARRAY_LENGTH(map->table)]; entry != NULL; entry = entry->next) - if (entry->fullhash == fullhash) - return entry->object; - return NULL; + UINT32 fullhash = hash(tag); + UINT32 hashindex = fullhash % ARRAY_LENGTH(m_table); + + // first make sure we don't have a duplicate + for (entry_t *entry = m_table[hashindex]; entry != NULL; entry = entry->next()) + if (entry->fullhash() == fullhash) + if (unique_hash || entry->tag() == tag) + { + if (replace_if_duplicate) + entry->set_object(object); + return TMERR_DUPLICATE; + } + + // now allocate a new entry and add to the head of the list + entry_t *entry = new entry_t(tag, fullhash, object); + entry->m_next = m_table[hashindex]; + m_table[hashindex] = entry; + return TMERR_NONE; } |