diff options
author | 2012-01-17 19:06:55 +0000 | |
---|---|---|
committer | 2012-01-17 19:06:55 +0000 | |
commit | 49f15acb7d06857c0c8cdb8e837057f05c4f0a8b (patch) | |
tree | 805a028d8e52dda49196816f8454b3f2c04dc262 | |
parent | c8fd0760b8b60e266d38eec880e07845f1842552 (diff) |
tagmap is just a C++ template now. Added iterators to it as
well. Updated a few outlying uses.
-rw-r--r-- | .gitattributes | 1 | ||||
-rw-r--r-- | src/build/makedep.c | 13 | ||||
-rw-r--r-- | src/emu/emualloc.h | 3 | ||||
-rw-r--r-- | src/emu/sound/discrete.c | 2 | ||||
-rw-r--r-- | src/emu/sound/discrete.h | 2 | ||||
-rw-r--r-- | src/lib/lib.mak | 1 | ||||
-rw-r--r-- | src/lib/util/tagmap.c | 218 | ||||
-rw-r--r-- | src/lib/util/tagmap.h | 319 |
8 files changed, 179 insertions, 380 deletions
diff --git a/.gitattributes b/.gitattributes index 618e7028d38..990faf0dcc3 100644 --- a/.gitattributes +++ b/.gitattributes @@ -1689,7 +1689,6 @@ src/lib/util/pool.c svneol=native#text/plain src/lib/util/pool.h svneol=native#text/plain src/lib/util/sha1.c svneol=native#text/plain src/lib/util/sha1.h svneol=native#text/plain -src/lib/util/tagmap.c svneol=native#text/plain src/lib/util/tagmap.h svneol=native#text/plain src/lib/util/unicode.c svneol=native#text/plain src/lib/util/unicode.h svneol=native#text/plain diff --git a/src/build/makedep.c b/src/build/makedep.c index 2da090be743..7a4e0aa9367 100644 --- a/src/build/makedep.c +++ b/src/build/makedep.c @@ -95,6 +95,8 @@ struct file_entry dependency * deplist; }; +typedef tagmap_t<UINT8> dependency_map; + /*************************************************************************** @@ -210,7 +212,7 @@ static int compare_list_entries(const void *p1, const void *p2) unless we already exist in the map -------------------------------------------------*/ -static void recurse_dependencies(file_entry &file, tagmap_t<astring *> &map) +static void recurse_dependencies(file_entry &file, dependency_map &map) { // skip if we're in an exclude path int filelen = file.name.len(); @@ -220,7 +222,7 @@ static void recurse_dependencies(file_entry &file, tagmap_t<astring *> &map) return; // attempt to add; if we get an error, we're already present - if (map.add(file.name, &file.name) != TMERR_NONE) + if (map.add(file.name, 0) != TMERR_NONE) return; // recurse the list from there @@ -304,7 +306,7 @@ static int recurse_dir(int srcrootlen, astring &srcdir) // make sure we care, first if (core_filename_ends_with(curlist->name, ".c")) { - tagmap_t<astring *> depend_map; + dependency_map depend_map; // find dependencies file_entry &file = compute_dependencies(srcrootlen, srcfile); @@ -317,9 +319,8 @@ static int recurse_dir(int srcrootlen, astring &srcdir) printf("\n%s : \\\n", target.cstr()); // iterate over the hashed dependencies and output them as well - for (int taghash = 0; taghash < TAGMAP_HASH_SIZE; taghash++) - for (tagmap_entry *map_entry = depend_map.table[taghash]; map_entry != NULL; map_entry = map_entry->next) - printf("\t%s \\\n", ((astring *)map_entry->object)->cstr()); + for (dependency_map::entry_t *entry = depend_map.first(); entry != NULL; entry = depend_map.next(entry)) + printf("\t%s \\\n", entry->tag().cstr()); } } diff --git a/src/emu/emualloc.h b/src/emu/emualloc.h index 67a9afd486e..f13deeb906c 100644 --- a/src/emu/emualloc.h +++ b/src/emu/emualloc.h @@ -331,9 +331,6 @@ extern const zeromem_t zeromem; #define calloc(x,y) __error_use_auto_alloc_clear_or_global_alloc_clear_instead__ #define realloc(x,y) __error_realloc_is_dangerous__ #define free(x) free_file_line(x, __FILE__, __LINE__) - -// disable direct deletion -#define delete __error_use_pool_free_mechanisms__ #endif #endif /* __EMUALLOC_H__ */ diff --git a/src/emu/sound/discrete.c b/src/emu/sound/discrete.c index 09571d0b866..d4017eae74b 100644 --- a/src/emu/sound/discrete.c +++ b/src/emu/sound/discrete.c @@ -541,7 +541,7 @@ void discrete_device::discrete_build_list(const discrete_block *intf, sound_bloc } } for_each (int *, i, &deletethem) - block_list.delete(*i); + block_list.remove(*i); } else { diff --git a/src/emu/sound/discrete.h b/src/emu/sound/discrete.h index 65a0fe56002..7df8b90ce68 100644 --- a/src/emu/sound/discrete.h +++ b/src/emu/sound/discrete.h @@ -3810,7 +3810,7 @@ public: m_count++; return &m_arr[m_count-1]; } - inline void delete(int index) + inline void remove(int index) { for (int i=index+1; i < m_count; i++) m_arr[i-1] = m_arr[i]; diff --git a/src/lib/lib.mak b/src/lib/lib.mak index 6b98c10a191..d23462bb9b4 100644 --- a/src/lib/lib.mak +++ b/src/lib/lib.mak @@ -48,7 +48,6 @@ UTILOBJS = \ $(LIBOBJ)/util/png.o \ $(LIBOBJ)/util/pool.o \ $(LIBOBJ)/util/sha1.o \ - $(LIBOBJ)/util/tagmap.o \ $(LIBOBJ)/util/unicode.o \ $(LIBOBJ)/util/unzip.o \ $(LIBOBJ)/util/vbiparse.o \ diff --git a/src/lib/util/tagmap.c b/src/lib/util/tagmap.c deleted file mode 100644 index 86dda38bbc4..00000000000 --- a/src/lib/util/tagmap.c +++ /dev/null @@ -1,218 +0,0 @@ -/*************************************************************************** - - tagmap.c - - Simple tag->object mapping functions. - -**************************************************************************** - - Copyright Aaron Giles - All rights reserved. - - Redistribution and use in source and binary forms, with or without - modification, are permitted provided that the following conditions are - met: - - * Redistributions of source code must retain the above copyright - notice, this list of conditions and the following disclaimer. - * Redistributions in binary form must reproduce the above copyright - notice, this list of conditions and the following disclaimer in - the documentation and/or other materials provided with the - distribution. - * Neither the name 'MAME' nor the names of its contributors may be - used to endorse or promote products derived from this software - without specific prior written permission. - - THIS SOFTWARE IS PROVIDED BY AARON GILES ''AS IS'' AND ANY EXPRESS OR - IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED - WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE - DISCLAIMED. IN NO EVENT SHALL AARON GILES BE LIABLE FOR ANY DIRECT, - INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES - (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR - SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) - HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, - STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING - IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE - POSSIBILITY OF SUCH DAMAGE. - -****************************************************************************/ - -#include "tagmap.h" - -#include <stdlib.h> - - -/*************************************************************************** - FUNCTION PROTOTYPES -***************************************************************************/ - -static tagmap_error tagmap_add_common(tagmap *map, const char *tag, void *object, UINT8 replace_if_duplicate, UINT8 unique_hash); - - - -/*************************************************************************** - MAP ALLOCATION AND MANAGEMENT -***************************************************************************/ - -/*------------------------------------------------- - tagmap_alloc - allocate a new tagmap --------------------------------------------------*/ - -tagmap *tagmap_alloc(void) -{ - tagmap *map = (tagmap *)malloc(sizeof(*map)); - if (map != NULL) - memset(map, 0, sizeof(*map)); - return map; -} - - -/*------------------------------------------------- - tagmap_free - free a tagmap, and all - entries within it --------------------------------------------------*/ - -void tagmap_free(tagmap *map) -{ - tagmap_reset(map); - free(map); -} - - -/*------------------------------------------------- - tagmap_reset - reset a tagmap by freeing - all entries --------------------------------------------------*/ - -void tagmap_reset(tagmap *map) -{ - UINT32 hashindex; - - for (hashindex = 0; hashindex < ARRAY_LENGTH(map->table); hashindex++) - { - tagmap_entry *entry, *next; - - for (entry = map->table[hashindex]; entry != NULL; entry = next) - { - next = entry->next; - free(entry); - } - map->table[hashindex] = NULL; - } -} - - - -/*************************************************************************** - MAP ALLOCATION AND MANAGEMENT -***************************************************************************/ - -/*------------------------------------------------- - tagmap_add - add a new object to the - tagmap --------------------------------------------------*/ - -tagmap_error tagmap_add(tagmap *map, const char *tag, void *object, UINT8 replace_if_duplicate) -{ - return tagmap_add_common(map, tag, object, replace_if_duplicate, FALSE); -} - - -/*------------------------------------------------- - tagmap_add_unique_hash - 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) -{ - return tagmap_add_common(map, tag, object, replace_if_duplicate, TRUE); -} - - -/*------------------------------------------------- - tagmap_remove - remove an entr from a - tagmap --------------------------------------------------*/ - -void tagmap_remove(tagmap *map, const char *tag) -{ - UINT32 fullhash = tagmap_hash(tag); - tagmap_entry **entryptr; - - for (entryptr = &map->table[fullhash % ARRAY_LENGTH(map->table)]; *entryptr != NULL; entryptr = &(*entryptr)->next) - if ((*entryptr)->fullhash == fullhash && strcmp((*entryptr)->tag, tag) == 0) - { - tagmap_entry *entry = *entryptr; - *entryptr = entry->next; - free(entry); - break; - } -} - - -/*------------------------------------------------- - tagmap_remove_object - remove an entry from a - tagmap by object pointer --------------------------------------------------*/ - -void tagmap_remove_object(tagmap *map, void *object) -{ - UINT32 hashindex; - - for (hashindex = 0; hashindex < ARRAY_LENGTH(map->table); hashindex++) - { - tagmap_entry **entryptr; - - for (entryptr = &map->table[hashindex]; *entryptr != NULL; entryptr = &(*entryptr)->next) - if ((*entryptr)->object == object) - { - tagmap_entry *entry = *entryptr; - *entryptr = entry->next; - free(entry); - return; - } - } -} - - - -/*************************************************************************** - LOCAL FUNCTIONS -***************************************************************************/ - -/*------------------------------------------------- - tagmap_add_common - core implementation of - a tagmap addition --------------------------------------------------*/ - -static tagmap_error tagmap_add_common(tagmap *map, const char *tag, void *object, UINT8 replace_if_duplicate, UINT8 unique_hash) -{ - UINT32 fullhash = tagmap_hash(tag); - UINT32 hashindex = fullhash % ARRAY_LENGTH(map->table); - tagmap_entry *entry; - - /* first make sure we don't have a duplicate */ - for (entry = map->table[hashindex]; entry != NULL; entry = entry->next) - if (entry->fullhash == fullhash) - if (unique_hash || strcmp(tag, entry->tag) == 0) - { - if (replace_if_duplicate) - entry->object = object; - return TMERR_DUPLICATE; - } - - /* now allocate a new entry */ - entry = (tagmap_entry *)malloc(sizeof(*entry) + strlen(tag)); - if (entry == NULL) - return TMERR_OUT_OF_MEMORY; - - /* fill in the entry */ - entry->object = object; - entry->fullhash = fullhash; - strcpy(entry->tag, tag); - - /* add it to the head of the list */ - entry->next = map->table[hashindex]; - map->table[hashindex] = entry; - return TMERR_NONE; -} 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; } |