summaryrefslogtreecommitdiffstatshomepage
path: root/src/lib/util/tagmap.h
diff options
context:
space:
mode:
author Aaron Giles <aaron@aarongiles.com>2012-01-17 19:06:55 +0000
committer Aaron Giles <aaron@aarongiles.com>2012-01-17 19:06:55 +0000
commit49f15acb7d06857c0c8cdb8e837057f05c4f0a8b (patch)
tree805a028d8e52dda49196816f8454b3f2c04dc262 /src/lib/util/tagmap.h
parentc8fd0760b8b60e266d38eec880e07845f1842552 (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.h319
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;
}