diff options
Diffstat (limited to 'src/common/db.c')
-rw-r--r-- | src/common/db.c | 188 |
1 files changed, 99 insertions, 89 deletions
diff --git a/src/common/db.c b/src/common/db.c index 8d6b08815..f414ca04d 100644 --- a/src/common/db.c +++ b/src/common/db.c @@ -3,7 +3,7 @@ * For more information, see LICENCE in the main folder * * This file is separated in five sections: - * (1) Private typedefs, enums, structures, defines and gblobal variables + * (1) Private typedefs, enums, structures, defines and global variables * (2) Private functions * (3) Protected functions used internally * (4) Protected functions used in the interface of the database @@ -67,14 +67,18 @@ * @encoding US-ASCII * @see #db.h \*****************************************************************************/ + +#define HERCULES_CORE + +#include "db.h" + #include <stdio.h> #include <stdlib.h> -#include "db.h" -#include "../common/mmo.h" +#include "../common/ers.h" #include "../common/malloc.h" +#include "../common/mmo.h" #include "../common/showmsg.h" -#include "../common/ers.h" #include "../common/strlib.h" /*****************************************************************************\ @@ -85,15 +89,15 @@ * DBNColor - Enumeration of colors of the nodes. * * DBNode - Structure of a node in RED-BLACK trees. * * struct db_free - Structure that holds a deleted node to be freed. * - * DBMap_impl - Struture of the database. * + * DBMap_impl - Structure of the database. * * stats - Statistics about the database system. * \*****************************************************************************/ /** - * If defined statistics about database nodes, database creating/destruction - * and function usage are keept and displayed when finalizing the database + * If defined statistics about database nodes, database creating/destruction + * and function usage are kept and displayed when finalizing the database * system. - * WARNING: This adds overhead to every database operation (not shure how much). + * WARNING: This adds overhead to every database operation (not sure how much). * @private * @see #DBStats * @see #stats @@ -141,7 +145,7 @@ typedef struct dbn { // Other node_color color; unsigned deleted : 1; -} *DBNode; +} DBNode; /** * Structure that holds a deleted node. @@ -151,8 +155,8 @@ typedef struct dbn { * @see DBMap_impl#free_list */ struct db_free { - DBNode node; - DBNode *root; + DBNode *node; + DBNode **root; }; /** @@ -189,12 +193,12 @@ typedef struct DBMap_impl { unsigned int free_max; unsigned int free_lock; // Other - ERS nodes; + ERS *nodes; DBComparator cmp; DBHasher hash; DBReleaser release; - DBNode ht[HASH_SIZE]; - DBNode cache; + DBNode *ht[HASH_SIZE]; + DBNode *cache; DBType type; DBOptions options; uint32 item_count; @@ -218,7 +222,7 @@ typedef struct DBIterator_impl { struct DBIterator vtable; DBMap_impl* db; int ht_index; - DBNode node; + DBNode *node; } DBIterator_impl; #if defined(DB_ENABLE_STATS) @@ -326,7 +330,7 @@ static struct db_stats { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; -#define DB_COUNTSTAT(token) do { if (stats. ## token != UINT32_MAX) ++stats. ## token ; } while(0) +#define DB_COUNTSTAT(token) do { if ((stats.token) != UINT32_MAX) ++(stats.token); } while(0) #else /* !defined(DB_ENABLE_STATS) */ #define DB_COUNTSTAT(token) #endif /* !defined(DB_ENABLE_STATS) */ @@ -357,12 +361,12 @@ struct eri *db_alloc_ers; * @param node Node to be rotated * @param root Pointer to the root of the tree * @private - * @see #db_rebalance(DBNode,DBNode *) - * @see #db_rebalance_erase(DBNode,DBNode *) + * @see #db_rebalance(DBNode *,DBNode **) + * @see #db_rebalance_erase(DBNode *,DBNode **) */ -static void db_rotate_left(DBNode node, DBNode *root) +static void db_rotate_left(DBNode *node, DBNode **root) { - DBNode y = node->right; + DBNode *y = node->right; DB_COUNTSTAT(db_rotate_left); // put the left of y at the right of node @@ -388,12 +392,12 @@ static void db_rotate_left(DBNode node, DBNode *root) * @param node Node to be rotated * @param root Pointer to the root of the tree * @private - * @see #db_rebalance(DBNode,DBNode *) - * @see #db_rebalance_erase(DBNode,DBNode *) + * @see #db_rebalance(DBNode *,DBNode **) + * @see #db_rebalance_erase(DBNode *,DBNode **) */ -static void db_rotate_right(DBNode node, DBNode *root) +static void db_rotate_right(DBNode *node, DBNode **root) { - DBNode y = node->left; + DBNode *y = node->left; DB_COUNTSTAT(db_rotate_right); // put the right of y at the left of node @@ -420,13 +424,13 @@ static void db_rotate_right(DBNode node, DBNode *root) * @param node Node to be rebalanced * @param root Pointer to the root of the tree * @private - * @see #db_rotate_left(DBNode,DBNode *) - * @see #db_rotate_right(DBNode,DBNode *) + * @see #db_rotate_left(DBNode *,DBNode **) + * @see #db_rotate_right(DBNode *,DBNode **) * @see #db_obj_put(DBMap*,DBKey,DBData) */ -static void db_rebalance(DBNode node, DBNode *root) +static void db_rebalance(DBNode *node, DBNode **root) { - DBNode y; + DBNode *y; DB_COUNTSTAT(db_rebalance); // Restore the RED-BLACK properties @@ -482,16 +486,16 @@ static void db_rebalance(DBNode node, DBNode *root) * @param node Node to be erased from the tree * @param root Root of the tree * @private - * @see #db_rotate_left(DBNode,DBNode *) - * @see #db_rotate_right(DBNode,DBNode *) + * @see #db_rotate_left(DBNode *,DBNode **) + * @see #db_rotate_right(DBNode *,DBNode **) * @see #db_free_unlock(DBMap_impl*) */ -static void db_rebalance_erase(DBNode node, DBNode *root) +static void db_rebalance_erase(DBNode *node, DBNode **root) { - DBNode y = node; - DBNode x = NULL; - DBNode x_parent = NULL; - DBNode w; + DBNode *y = node; + DBNode *x = NULL; + DBNode *x_parent = NULL; + DBNode *w; DB_COUNTSTAT(db_rebalance_erase); // Select where to change the tree @@ -507,7 +511,7 @@ static void db_rebalance_erase(DBNode node, DBNode *root) } // Remove the node from the tree - if (y != node) { // both childs existed + if (y != node) { // both child existed // put the left of 'node' in the left of 'y' node->left->parent = y; y->left = node->left; @@ -518,7 +522,7 @@ static void db_rebalance_erase(DBNode node, DBNode *root) x_parent = y->parent; if (x) x->parent = y->parent; y->parent->left = x; - // put the right of 'node' in 'y' + // put the right of 'node' in 'y' y->right = node->right; node->right->parent = y; // 'y' is a direct child of 'node' @@ -646,8 +650,8 @@ static int db_is_key_null(DBType type, DBKey key) * @param key Key to be duplicated * @param Duplicated key * @private - * @see #db_free_add(DBMap_impl*,DBNode,DBNode *) - * @see #db_free_remove(DBMap_impl*,DBNode) + * @see #db_free_add(DBMap_impl*,DBNode *,DBNode **) + * @see #db_free_remove(DBMap_impl*,DBNode *) * @see #db_obj_put(DBMap*,DBKey,void *) * @see #db_dup_key_free(DBMap_impl*,DBKey) */ @@ -706,9 +710,9 @@ static void db_dup_key_free(DBMap_impl* db, DBKey key) * @see DBMap_impl#free_count * @see DBMap_impl#free_max * @see #db_obj_remove(DBMap*,DBKey) - * @see #db_free_remove(DBMap_impl*,DBNode) + * @see #db_free_remove(DBMap_impl*,DBNode *) */ -static void db_free_add(DBMap_impl* db, DBNode node, DBNode *root) +static void db_free_add(DBMap_impl* db, DBNode *node, DBNode **root) { DBKey old_key; @@ -755,9 +759,9 @@ static void db_free_add(DBMap_impl* db, DBNode node, DBNode *root) * @see DBMap_impl#free_list * @see DBMap_impl#free_count * @see #db_obj_put(DBMap*,DBKey,DBData) - * @see #db_free_add(DBMap_impl*,DBNode*,DBNode) + * @see #db_free_add(DBMap_impl*,DBNode**,DBNode*) */ -static void db_free_remove(DBMap_impl* db, DBNode node) +static void db_free_remove(DBMap_impl* db, DBNode *node) { unsigned int i; @@ -806,7 +810,7 @@ static void db_free_lock(DBMap_impl* db) * @param db Target database * @private * @see DBMap_impl#free_lock - * @see #db_free_dbn(DBNode) + * @see #db_free_dbn(DBNode*) * @see #db_lock(DBMap_impl*) */ static void db_free_unlock(DBMap_impl* db) @@ -1151,7 +1155,10 @@ static void db_release_data(DBKey key, DBData data, DBRelease which) { (void)key;//not used DB_COUNTSTAT(db_release_data); - if (which&DB_RELEASE_DATA && data.type == DB_DATA_PTR) aFree(data.u.ptr); + if (which&DB_RELEASE_DATA && data.type == DB_DATA_PTR) { + aFree(data.u.ptr); + data.u.ptr = NULL; + } } /** @@ -1170,7 +1177,10 @@ static void db_release_both(DBKey key, DBData data, DBRelease which) { DB_COUNTSTAT(db_release_both); if (which&DB_RELEASE_KEY) aFree((char*)key.str); // needs to be a pointer - if (which&DB_RELEASE_DATA && data.type == DB_DATA_PTR) aFree(data.u.ptr); + if (which&DB_RELEASE_DATA && data.type == DB_DATA_PTR) { + aFree(data.u.ptr); + data.u.ptr = NULL; + } } /*****************************************************************************\ @@ -1263,8 +1273,8 @@ DBData* dbit_obj_last(DBIterator* self, DBKey* out_key) DBData* dbit_obj_next(DBIterator* self, DBKey* out_key) { DBIterator_impl* it = (DBIterator_impl*)self; - DBNode node; - DBNode parent; + DBNode *node; + DBNode *parent; struct dbn fake; DB_COUNTSTAT(dbit_next); @@ -1339,8 +1349,8 @@ DBData* dbit_obj_next(DBIterator* self, DBKey* out_key) DBData* dbit_obj_prev(DBIterator* self, DBKey* out_key) { DBIterator_impl* it = (DBIterator_impl*)self; - DBNode node; - DBNode parent; + DBNode *node; + DBNode *parent; struct dbn fake; DB_COUNTSTAT(dbit_prev); @@ -1405,7 +1415,7 @@ DBData* dbit_obj_prev(DBIterator* self, DBKey* out_key) /** * Returns true if the fetched entry exists. - * The databases entries might have NULL data, so use this to to test if + * The databases entries might have NULL data, so use this to to test if * the iterator is done. * @param self Iterator * @return true if the entry exists @@ -1422,9 +1432,9 @@ bool dbit_obj_exists(DBIterator* self) /** * Removes the current entry from the database. - * NOTE: {@link DBIterator#exists} will return false until another entry + * NOTE: {@link DBIterator#exists} will return false until another entry * is fetched - * Puts data of the removed entry in out_data, if out_data is not NULL. + * Puts data of the removed entry in out_data, if out_data is not NULL (unless data has been released) * @param self Iterator * @param out_data Data of the removed entry. * @return 1 if entry was removed, 0 otherwise @@ -1435,7 +1445,7 @@ bool dbit_obj_exists(DBIterator* self) int dbit_obj_remove(DBIterator* self, DBData *out_data) { DBIterator_impl* it = (DBIterator_impl*)self; - DBNode node; + DBNode *node; int retval = 0; DB_COUNTSTAT(dbit_remove); @@ -1445,10 +1455,10 @@ int dbit_obj_remove(DBIterator* self, DBData *out_data) DBMap_impl* db = it->db; if( db->cache == node ) db->cache = NULL; + db->release(node->key, node->data, DB_RELEASE_DATA); if( out_data ) memcpy(out_data, &node->data, sizeof(DBData)); retval = 1; - db->release(node->key, node->data, DB_RELEASE_DATA); db_free_add(db, node, &db->ht[it->ht_index]); } return retval; @@ -1473,7 +1483,7 @@ void dbit_obj_destroy(DBIterator* self) /** * Returns a new iterator for this database. * The iterator keeps the database locked until it is destroyed. - * The database will keep functioning normally but will only free internal + * The database will keep functioning normally but will only free internal * memory when unlocked, so destroy the iterator as soon as possible. * @param self Database * @return New iterator @@ -1514,7 +1524,7 @@ static DBIterator* db_obj_iterator(DBMap* self) static bool db_obj_exists(DBMap* self, DBKey key) { DBMap_impl* db = (DBMap_impl*)self; - DBNode node; + DBNode *node; int c; bool found = false; @@ -1565,7 +1575,7 @@ static bool db_obj_exists(DBMap* self, DBKey key) static DBData* db_obj_get(DBMap* self, DBKey key) { DBMap_impl* db = (DBMap_impl*)self; - DBNode node; + DBNode *node; int c; DBData *data = NULL; @@ -1611,7 +1621,7 @@ static DBData* db_obj_get(DBMap* self, DBKey key) * It puts a maximum of <code>max</code> entries into <code>buf</code>. * If <code>buf</code> is NULL, it only counts the matches. * Returns the number of entries that matched. - * NOTE: if the value returned is greater than <code>max</code>, only the + * NOTE: if the value returned is greater than <code>max</code>, only the * first <code>max</code> entries found are put into the buffer. * @param self Interface of the database * @param buf Buffer to put the data of the matched entries @@ -1626,8 +1636,8 @@ static unsigned int db_obj_vgetall(DBMap* self, DBData **buf, unsigned int max, { DBMap_impl* db = (DBMap_impl*)self; unsigned int i; - DBNode node; - DBNode parent; + DBNode *node; + DBNode *parent; unsigned int ret = 0; DB_COUNTSTAT(db_vgetall); @@ -1682,7 +1692,7 @@ static unsigned int db_obj_vgetall(DBMap* self, DBData **buf, unsigned int max, * It puts a maximum of <code>max</code> entries into <code>buf</code>. * If <code>buf</code> is NULL, it only counts the matches. * Returns the number of entries that matched. - * NOTE: if the value returned is greater than <code>max</code>, only the + * NOTE: if the value returned is greater than <code>max</code>, only the * first <code>max</code> entries found are put into the buffer. * @param self Interface of the database * @param buf Buffer to put the data of the matched entries @@ -1710,7 +1720,7 @@ static unsigned int db_obj_getall(DBMap* self, DBData **buf, unsigned int max, D /** * Get the data of the entry identified by the key. - * If the entry does not exist, an entry is added with the data returned by + * If the entry does not exist, an entry is added with the data returned by * <code>create</code>. * @param self Interface of the database * @param key Key that identifies the entry @@ -1723,8 +1733,8 @@ static unsigned int db_obj_getall(DBMap* self, DBData **buf, unsigned int max, D static DBData* db_obj_vensure(DBMap* self, DBKey key, DBCreateData create, va_list args) { DBMap_impl* db = (DBMap_impl*)self; - DBNode node; - DBNode parent = NULL; + DBNode *node; + DBNode *parent = NULL; unsigned int hash; int c = 0; DBData *data = NULL; @@ -1809,7 +1819,7 @@ static DBData* db_obj_vensure(DBMap* self, DBKey key, DBCreateData create, va_li /** * Just calls {@link DBMap#vensure}. * Get the data of the entry identified by the key. - * If the entry does not exist, an entry is added with the data returned by + * If the entry does not exist, an entry is added with the data returned by * <code>create</code>. * @param self Interface of the database * @param key Key that identifies the entry @@ -1836,7 +1846,7 @@ static DBData* db_obj_ensure(DBMap* self, DBKey key, DBCreateData create, ...) /** * Put the data identified by the key in the database. - * Puts the previous data in out_data, if out_data is not NULL. + * Puts the previous data in out_data, if out_data is not NULL. (unless data has been released) * NOTE: Uses the new key, the old one is released. * @param self Interface of the database * @param key Key that identifies the data @@ -1852,8 +1862,8 @@ static DBData* db_obj_ensure(DBMap* self, DBKey key, DBCreateData create, ...) static int db_obj_put(DBMap* self, DBKey key, DBData data, DBData *out_data) { DBMap_impl* db = (DBMap_impl*)self; - DBNode node; - DBNode parent = NULL; + DBNode *node; + DBNode *parent = NULL; int c = 0, retval = 0; unsigned int hash; @@ -1889,9 +1899,9 @@ static int db_obj_put(DBMap* self, DBKey key, DBData data, DBData *out_data) if (node->deleted) { db_free_remove(db, node); } else { + db->release(node->key, node->data, DB_RELEASE_BOTH); if (out_data) memcpy(out_data, &node->data, sizeof(*out_data)); - db->release(node->key, node->data, DB_RELEASE_BOTH); retval = 1; } break; @@ -1944,20 +1954,20 @@ static int db_obj_put(DBMap* self, DBKey key, DBData data, DBData *out_data) /** * Remove an entry from the database. - * Puts the previous data in out_data, if out_data is not NULL. - * NOTE: The key (of the database) is released in {@link #db_free_add(DBMap_impl*,DBNode,DBNode *)}. + * Puts the previous data in out_data, if out_data is not NULL. (unless data has been released) + * NOTE: The key (of the database) is released in {@link #db_free_add(DBMap_impl*,DBNode*,DBNode **)}. * @param self Interface of the database * @param key Key that identifies the entry * @param out_data Previous data if the entry exists * @return 1 if if the entry already exists, 0 otherwise * @protected - * @see #db_free_add(DBMap_impl*,DBNode,DBNode *) + * @see #db_free_add(DBMap_impl*,DBNode*,DBNode **) * @see DBMap#remove */ static int db_obj_remove(DBMap* self, DBKey key, DBData *out_data) { DBMap_impl* db = (DBMap_impl*)self; - DBNode node; + DBNode *node; unsigned int hash; int c = 0, retval = 0; @@ -1982,10 +1992,10 @@ static int db_obj_remove(DBMap* self, DBKey key, DBData *out_data) if (!(node->deleted)) { if (db->cache == node) db->cache = NULL; + db->release(node->key, node->data, DB_RELEASE_DATA); if (out_data) memcpy(out_data, &node->data, sizeof(*out_data)); retval = 1; - db->release(node->key, node->data, DB_RELEASE_DATA); db_free_add(db, node, &db->ht[hash]); } break; @@ -2014,8 +2024,8 @@ static int db_obj_vforeach(DBMap* self, DBApply func, va_list args) DBMap_impl* db = (DBMap_impl*)self; unsigned int i; int sum = 0; - DBNode node; - DBNode parent; + DBNode *node; + DBNode *parent; DB_COUNTSTAT(db_vforeach); if (db == NULL) return 0; // nullpo candidate @@ -2062,7 +2072,7 @@ static int db_obj_vforeach(DBMap* self, DBApply func, va_list args) * Apply <code>func</code> to every entry in the database. * Returns the sum of values returned by func. * @param self Interface of the database - * @param func Function to be applyed + * @param func Function to be applied * @param ... Extra arguments for func * @return Sum of the values returned by func * @protected @@ -2100,8 +2110,8 @@ static int db_obj_vclear(DBMap* self, DBApply func, va_list args) DBMap_impl* db = (DBMap_impl*)self; int sum = 0; unsigned int i; - DBNode node; - DBNode parent; + DBNode *node; + DBNode *parent; DB_COUNTSTAT(db_vclear); if (db == NULL) return 0; // nullpo candidate @@ -2159,7 +2169,7 @@ static int db_obj_vclear(DBMap* self, DBApply func, va_list args) * Before deleting an entry, func is applied to it. * Releases the key and the data. * Returns the sum of values returned by func, if it exists. - * NOTE: This locks the database globally. Any attempt to insert or remove + * NOTE: This locks the database globally. Any attempt to insert or remove * a database entry will give an error and be aborted (except for clearing). * @param self Interface of the database * @param func Function to be applied to every entry before deleting @@ -2187,7 +2197,7 @@ static int db_obj_clear(DBMap* self, DBApply func, ...) * Finalize the database, feeing all the memory it uses. * Before deleting an entry, func is applied to it. * Returns the sum of values returned by func, if it exists. - * NOTE: This locks the database globally. Any attempt to insert or remove + * NOTE: This locks the database globally. Any attempt to insert or remove * a database entry will give an error and be aborted (except for clearing). * @param self Interface of the database * @param func Function to be applied to every entry before deleting @@ -2242,7 +2252,7 @@ static int db_obj_vdestroy(DBMap* self, DBApply func, va_list args) * Before deleting an entry, func is applied to it. * Releases the key and the data. * Returns the sum of values returned by func, if it exists. - * NOTE: This locks the database globally. Any attempt to insert or remove + * NOTE: This locks the database globally. Any attempt to insert or remove * a database entry will give an error and be aborted. * @param self Database * @param func Function to be applied to every entry before deleting @@ -2341,7 +2351,7 @@ static DBOptions db_obj_options(DBMap* self) * db_default_cmp - Get the default comparator for a type of database. * db_default_hash - Get the default hasher for a type of database. * db_default_release - Get the default releaser for a type of database with the specified options. - * db_custom_release - Get a releaser that behaves a certains way. + * db_custom_release - Get a releaser that behaves a certain way. * db_alloc - Allocate a new database. * db_i2key - Manual cast from 'int' to 'DBKey'. * db_ui2key - Manual cast from 'unsigned int' to 'DBKey'. @@ -2444,7 +2454,7 @@ DBHasher db_default_hash(DBType type) } /** - * Returns the default releaser for the specified type of database with the + * Returns the default releaser for the specified type of database with the * specified options. * NOTE: the options are fixed with {@link #db_fix_options(DBType,DBOptions)} * before choosing the releaser. @@ -2505,7 +2515,7 @@ DBReleaser db_custom_release(DBRelease which) * @param line Line of the file where the database is being allocated * @param type Type of database * @param options Options of the database - * @param maxlen Maximum length of the string to be used as key in string + * @param maxlen Maximum length of the string to be used as key in string * databases. If 0, the maximum number of maxlen is used (64K). * @return The interface of the database * @public @@ -2776,15 +2786,15 @@ void db_final(void) "DB_INT : allocated %10u, destroyed %10u\n" "DB_UINT : allocated %10u, destroyed %10u\n" "DB_STRING : allocated %10u, destroyed %10u\n" - "DB_ISTRING : allocated %10u, destroyed %10u\n", + "DB_ISTRING : allocated %10u, destroyed %10u\n" "DB_INT64 : allocated %10u, destroyed %10u\n" - "DB_UINT64 : allocated %10u, destroyed %10u\n" + "DB_UINT64 : allocated %10u, destroyed %10u\n", stats.db_int_alloc, stats.db_int_destroy, stats.db_uint_alloc, stats.db_uint_destroy, stats.db_string_alloc, stats.db_string_destroy, stats.db_istring_alloc, stats.db_istring_destroy, stats.db_int64_alloc, stats.db_int64_destroy, - stats.db_uint64_alloc, stats.db_uint64_destroy,); + stats.db_uint64_alloc, stats.db_uint64_destroy); ShowInfo(CL_WHITE"Database function counters"CL_RESET":\n" "db_rotate_left %10u, db_rotate_right %10u,\n" "db_rebalance %10u, db_rebalance_erase %10u,\n" |