From 288490094a7fe9167747dc78d416940759a31197 Mon Sep 17 00:00:00 2001 From: FlavioJS Date: Tue, 5 Dec 2006 13:23:07 +0000 Subject: - Massive EOL normalization & 'svn:eol-style native' flag setting for all txt/conf/h/c files. git-svn-id: https://rathena.svn.sourceforge.net/svnroot/rathena/trunk@9410 54d463be-8e91-2dee-dedb-b68131a5f0ec --- src/common/db.c | 4896 +++++++++++++++++++++++++++---------------------------- 1 file changed, 2448 insertions(+), 2448 deletions(-) (limited to 'src/common/db.c') diff --git a/src/common/db.c b/src/common/db.c index ebb5b9a30..28b5721e9 100644 --- a/src/common/db.c +++ b/src/common/db.c @@ -1,2448 +1,2448 @@ -/*****************************************************************************\ - * Copyright (c) Athena Dev Teams - Licensed under GNU GPL * - * 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 * - * (2) Private functions * - * (3) Protected functions used internally * - * (4) Protected functions used in the interface of the database * - * (5) Public functions * - * * - * The databases are structured as a hashtable of RED-BLACK trees. * - * * - * Properties of the RED-BLACK trees being used: * - * 1. The value of any node is greater than the value of its left child and * - * less than the value of its right child. * - * 2. Every node is colored either RED or BLACK. * - * 3. Every red node that is not a leaf has only black children. * - * 4. Every path from the root to a leaf contains the same number of black * - * nodes. * - * 5. The root node is black. * - * An n node in a RED-BLACK tree has the property that its * - * height is O(lg(n)). * - * Another important property is that after adding a node to a RED-BLACK * - * tree, the tree can be readjusted in O(lg(n)) time. * - * Similarly, after deleting a node from a RED-BLACK tree, the tree can be * - * readjusted in O(lg(n)) time. * - * {@link http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic18/} * - * * - * How to add new database types: * - * 1. Add the identifier of the new database type to the enum DBType * - * 2. If not already there, add the data type of the key to the union DBKey * - * 3. If the key can be considered NULL, update the function db_is_key_null * - * 4. If the key can be duplicated, update the functions db_dup_key and * - * db_dup_key_free * - * 5. Create a comparator and update the function db_default_cmp * - * 6. Create a hasher and update the function db_default_hash * - * 7. If the new database type requires or does not support some options, * - * update the function db_fix_options * - * * - * TODO: * - * - create test cases to test the database system thoroughly * - * - make data an enumeration * - * - finish this header describing the database system * - * - create custom database allocator * - * - make the system thread friendly * - * - change the structure of the database to T-Trees * - * - create a db that organizes itself by splaying * - * * - * HISTORY: * - * 2.1 (Athena build #???#) - Portability fix * - * - Fixed the portability of casting to union and added the functions * - * {@link DBInterface#ensure(DBInterface,DBKey,DBCreateData,...)} and * - * {@link DBInterface#clear(DBInterface,DBApply,...)}. * - * 2.0 (Athena build 4859) - Transition version * - * - Almost everything recoded with a strategy similar to objects, * - * database structure is maintained. * - * 1.0 (up to Athena build 4706) * - * - Previous database system. * - * * - * @version 2.1 (Athena build #???#) - Portability fix * - * @author (Athena build 4859) Flavio @ Amazon Project * - * @author (up to Athena build 4706) Athena Dev Teams * - * @encoding US-ASCII * - * @see common#db.h * -\*****************************************************************************/ -#include -#include -#include - -#include "db.h" -#include "../common/mmo.h" -#include "../common/utils.h" -#include "../common/malloc.h" -#include "../common/showmsg.h" -#include "../common/ers.h" - -/*****************************************************************************\ - * (1) Private typedefs, enums, structures, defines and global variables of * - * the database system. * - * DB_ENABLE_STATS - Define to enable database statistics. * - * HASH_SIZE - Define with the size of the hashtable. * - * 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. * - * Database - Struture 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 - * system. - * WARNING: This adds overhead to every database operation (not shure how much). - * @private - * @see #DBStats - * @see #stats - * @see #db_final(void) - */ -//#define DB_ENABLE_STATS - -/** - * Size of the hashtable in the database. - * @private - * @see Database#ht - */ -#define HASH_SIZE (256+27) - -/** - * A node in a RED-BLACK tree of the database. - * @param parent Parent node - * @param left Left child node - * @param right Right child node - * @param key Key of this database entry - * @param data Data of this database entry - * @param deleted If the node is deleted - * @param color Color of the node - * @private - * @see Database#ht - */ -typedef struct dbn { - // Tree structure - struct dbn *parent; - struct dbn *left; - struct dbn *right; - // Node data - DBKey key; - void *data; - // Other - enum {RED, BLACK} color; - unsigned deleted : 1; -} *DBNode; - -/** - * Structure that holds a deleted node. - * @param node Deleted node - * @param root Address to the root of the tree - * @private - * @see Database#free_list - */ -struct db_free { - DBNode node; - DBNode *root; -}; - -/** - * Complete database structure. - * @param dbi Interface of the database - * @param alloc_file File where the database was allocated - * @param alloc_line Line in the file where the database was allocated - * @param free_list Array of deleted nodes to be freed - * @param free_count Number of deleted nodes in free_list - * @param free_max Current maximum capacity of free_list - * @param free_lock Lock for freeing the nodes - * @param nodes Manager of reusable tree nodes - * @param cmp Comparator of the database - * @param hash Hasher of the database - * @param release Releaser of the database - * @param ht Hashtable of RED-BLACK trees - * @param type Type of the database - * @param options Options of the database - * @param item_count Number of items in the database - * @param maxlen Maximum length of strings in DB_STRING and DB_ISTRING databases - * @param global_lock Global lock of the database - * @private - * @see common\db.h#DBInterface - * @see #HASH_SIZE - * @see #DBNode - * @see #struct db_free - * @see common\db.h#DBComparator(void *,void *) - * @see common\db.h#DBHasher(void *) - * @see common\db.h#DBReleaser(void *,void *,DBRelease) - * @see common\db.h#DBOptions - * @see common\db.h#DBType - * @see #db_alloc(const char *,int,DBOptions,DBType,...) - */ -typedef struct db { - // Database interface - struct dbt dbi; - // File and line of allocation - const char *alloc_file; - int alloc_line; - // Lock system - struct db_free *free_list; - unsigned int free_count; - unsigned int free_max; - unsigned int free_lock; - // Other - ERInterface nodes; - DBComparator cmp; - DBHasher hash; - DBReleaser release; - DBNode ht[HASH_SIZE]; - DBType type; - DBOptions options; - unsigned int item_count; - unsigned short maxlen; - unsigned global_lock : 1; -} *Database; - -#ifdef DB_ENABLE_STATS -/** - * Structure with what is counted when the database estatistics are enabled. - * @private - * @see #DB_ENABLE_STATS - * @see #stats - */ -static struct { - // Node alloc/free - unsigned int db_node_alloc; - unsigned int db_node_free; - // Database creating/destruction counters - unsigned int db_int_alloc; - unsigned int db_uint_alloc; - unsigned int db_string_alloc; - unsigned int db_istring_alloc; - unsigned int db_int_destroy; - unsigned int db_uint_destroy; - unsigned int db_string_destroy; - unsigned int db_istring_destroy; - // Function usage counters - unsigned int db_rotate_left; - unsigned int db_rotate_right; - unsigned int db_rebalance; - unsigned int db_rebalance_erase; - unsigned int db_is_key_null; - unsigned int db_dup_key; - unsigned int db_dup_key_free; - unsigned int db_free_add; - unsigned int db_free_remove; - unsigned int db_free_lock; - unsigned int db_free_unlock; - unsigned int db_int_cmp; - unsigned int db_uint_cmp; - unsigned int db_string_cmp; - unsigned int db_istring_cmp; - unsigned int db_int_hash; - unsigned int db_uint_hash; - unsigned int db_string_hash; - unsigned int db_istring_hash; - unsigned int db_release_nothing; - unsigned int db_release_key; - unsigned int db_release_data; - unsigned int db_release_both; - unsigned int db_get; - unsigned int db_getall; - unsigned int db_vgetall; - unsigned int db_ensure; - unsigned int db_vensure; - unsigned int db_put; - unsigned int db_remove; - unsigned int db_foreach; - unsigned int db_vforeach; - unsigned int db_clear; - unsigned int db_vclear; - unsigned int db_destroy; - unsigned int db_vdestroy; - unsigned int db_size; - unsigned int db_type; - unsigned int db_options; - unsigned int db_fix_options; - unsigned int db_default_cmp; - unsigned int db_default_hash; - unsigned int db_default_release; - unsigned int db_custom_release; - unsigned int db_alloc; - unsigned int db_i2key; - unsigned int db_ui2key; - unsigned int db_str2key; - unsigned int db_init; - unsigned int db_final; -} stats = { - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0 -}; -#endif /* DB_ENABLE_STATS */ - -/*****************************************************************************\ - * (2) Section of private functions used by the database system. * - * db_rotate_left - Rotate a tree node to the left. * - * db_rotate_right - Rotate a tree node to the right. * - * db_rebalance - Rebalance the tree. * - * db_rebalance_erase - Rebalance the tree after a BLACK node was erased. * - * db_is_key_null - Returns not 0 if the key is considered NULL. * - * db_dup_key - Duplicate a key for internal use. * - * db_dup_key_free - Free the duplicated key. * - * db_free_add - Add a node to the free_list of a database. * - * db_free_remove - Remove a node from the free_list of a database. * - * db_free_lock - Increment the free_lock of a database. * - * db_free_unlock - Decrement the free_lock of a database. * - * If it was the last lock, frees the nodes in free_list. * - * NOTE: Keeps the database trees balanced. * -\*****************************************************************************/ - -/** - * Rotate a node to the left. - * @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 *) - */ -static void db_rotate_left(DBNode node, DBNode *root) -{ - DBNode y = node->right; - -#ifdef DB_ENABLE_STATS - if (stats.db_rotate_left != (unsigned int)~0) stats.db_rotate_left++; -#endif /* DB_ENABLE_STATS */ - // put the left of y at the right of node - node->right = y->left; - if (y->left) - y->left->parent = node; - y->parent = node->parent; - // link y and node's parent - if (node == *root) { - *root = y; // node was root - } else if (node == node->parent->left) { - node->parent->left = y; // node was at the left - } else { - node->parent->right = y; // node was at the right - } - // put node at the left of y - y->left = node; - node->parent = y; -} - -/** - * Rotate a node to the right - * @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 *) - */ -static void db_rotate_right(DBNode node, DBNode *root) -{ - DBNode y = node->left; - -#ifdef DB_ENABLE_STATS - if (stats.db_rotate_right != (unsigned int)~0) stats.db_rotate_right++; -#endif /* DB_ENABLE_STATS */ - // put the right of y at the left of node - node->left = y->right; - if (y->right != 0) - y->right->parent = node; - y->parent = node->parent; - // link y and node's parent - if (node == *root) { - *root = y; // node was root - } else if (node == node->parent->right) { - node->parent->right = y; // node was at the right - } else { - node->parent->left = y; // node was at the left - } - // put node at the right of y - y->right = node; - node->parent = y; -} - -/** - * Rebalance the RED-BLACK tree. - * Called when the node and it's parent are both RED. - * @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_put(DBInterface,DBKey,void *) - */ -static void db_rebalance(DBNode node, DBNode *root) -{ - DBNode y; - -#ifdef DB_ENABLE_STATS - if (stats.db_rebalance != (unsigned int)~0) stats.db_rebalance++; -#endif /* DB_ENABLE_STATS */ - // Restore the RED-BLACK properties - node->color = RED; - while (node != *root && node->parent->color == RED) { - if (node->parent == node->parent->parent->left) { - // If node's parent is a left, y is node's right 'uncle' - y = node->parent->parent->right; - if (y && y->color == RED) { // case 1 - // change the colors and move up the tree - node->parent->color = BLACK; - y->color = BLACK; - node->parent->parent->color = RED; - node = node->parent->parent; - } else { - if (node == node->parent->right) { // case 2 - // move up and rotate - node = node->parent; - db_rotate_left(node, root); - } - // case 3 - node->parent->color = BLACK; - node->parent->parent->color = RED; - db_rotate_right(node->parent->parent, root); - } - } else { - // If node's parent is a right, y is node's left 'uncle' - y = node->parent->parent->left; - if (y && y->color == RED) { // case 1 - // change the colors and move up the tree - node->parent->color = BLACK; - y->color = BLACK; - node->parent->parent->color = RED; - node = node->parent->parent; - } else { - if (node == node->parent->left) { // case 2 - // move up and rotate - node = node->parent; - db_rotate_right(node, root); - } - // case 3 - node->parent->color = BLACK; - node->parent->parent->color = RED; - db_rotate_left(node->parent->parent, root); - } - } - } - (*root)->color = BLACK; // the root can and should always be black -} - -/** - * Erase a node from the RED-BLACK tree, keeping the tree balanced. - * @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_free_unlock(Database) - */ -static void db_rebalance_erase(DBNode node, DBNode *root) -{ - DBNode y = node; - DBNode x = NULL; - DBNode x_parent = NULL; - DBNode w; - -#ifdef DB_ENABLE_STATS - if (stats.db_rebalance_erase != (unsigned int)~0) stats.db_rebalance_erase++; -#endif /* DB_ENABLE_STATS */ - // Select where to change the tree - if (y->left == NULL) { // no left - x = y->right; - } else if (y->right == NULL) { // no right - x = y->left; - } else { // both exist, go to the leftmost node of the right sub-tree - y = y->right; - while (y->left != NULL) - y = y->left; - x = y->right; - } - - // Remove the node from the tree - if (y != node) { // both childs existed - // put the left of 'node' in the left of 'y' - node->left->parent = y; - y->left = node->left; - - // 'y' is not the direct child of 'node' - if (y != node->right) { - // put 'x' in the old position of 'y' - x_parent = y->parent; - if (x) x->parent = y->parent; - y->parent->left = x; - // put the right of 'node' in 'y' - y->right = node->right; - node->right->parent = y; - // 'y' is a direct child of 'node' - } else { - x_parent = y; - } - - // link 'y' and the parent of 'node' - if (*root == node) { - *root = y; // 'node' was the root - } else if (node->parent->left == node) { - node->parent->left = y; // 'node' was at the left - } else { - node->parent->right = y; // 'node' was at the right - } - y->parent = node->parent; - // switch colors - { - int tmp = y->color; - y->color = node->color; - node->color = tmp; - } - y = node; - } else { // one child did not exist - // put x in node's position - x_parent = y->parent; - if (x) x->parent = y->parent; - // link x and node's parent - if (*root == node) { - *root = x; // node was the root - } else if (node->parent->left == node) { - node->parent->left = x; // node was at the left - } else { - node->parent->right = x; // node was at the right - } - } - - // Restore the RED-BLACK properties - if (y->color != RED) { - while (x != *root && (x == NULL || x->color == BLACK)) { - if (x == x_parent->left) { - w = x_parent->right; - if (w->color == RED) { - w->color = BLACK; - x_parent->color = RED; - db_rotate_left(x_parent, root); - w = x_parent->right; - } - if ((w->left == NULL || w->left->color == BLACK) && - (w->right == NULL || w->right->color == BLACK)) { - w->color = RED; - x = x_parent; - x_parent = x_parent->parent; - } else { - if (w->right == NULL || w->right->color == BLACK) { - if (w->left) w->left->color = BLACK; - w->color = RED; - db_rotate_right(w, root); - w = x_parent->right; - } - w->color = x_parent->color; - x_parent->color = BLACK; - if (w->right) w->right->color = BLACK; - db_rotate_left(x_parent, root); - break; - } - } else { - w = x_parent->left; - if (w->color == RED) { - w->color = BLACK; - x_parent->color = RED; - db_rotate_right(x_parent, root); - w = x_parent->left; - } - if ((w->right == NULL || w->right->color == BLACK) && - (w->left == NULL || w->left->color == BLACK)) { - w->color = RED; - x = x_parent; - x_parent = x_parent->parent; - } else { - if (w->left == NULL || w->left->color == BLACK) { - if (w->right) w->right->color = BLACK; - w->color = RED; - db_rotate_left(w, root); - w = x_parent->left; - } - w->color = x_parent->color; - x_parent->color = BLACK; - if (w->left) w->left->color = BLACK; - db_rotate_right(x_parent, root); - break; - } - } - } - if (x) x->color = BLACK; - } -} - -/** - * Returns not 0 if the key is considerd to be NULL. - * @param type Type of database - * @param key Key being tested - * @return not 0 if considered NULL, 0 otherwise - * @private - * @see common\db.h#DBType - * @see common\db.h#DBKey - * @see #db_get(DBInterface,DBKey) - * @see #db_put(DBInterface,DBKey,void *) - * @see #db_remove(DBInterface,DBKey) - */ -static int db_is_key_null(DBType type, DBKey key) -{ -#ifdef DB_ENABLE_STATS - if (stats.db_is_key_null != (unsigned int)~0) stats.db_is_key_null++; -#endif /* DB_ENABLE_STATS */ - switch (type) { - case DB_STRING: - case DB_ISTRING: - return (key.str == NULL); - - default: // Not a pointer - return 0; - } -} - -/** - * Duplicate the key used in the database. - * @param db Database the key is being used in - * @param key Key to be duplicated - * @param Duplicated key - * @private - * @see #db_free_add(Database,DBNode,DBNode *) - * @see #db_free_remove(Database,DBNode) - * @see #db_put(DBInterface,DBKey,void *) - * @see #db_dup_key_free(Database,DBKey) - */ -static DBKey db_dup_key(Database db, DBKey key) -{ - unsigned char *str; - -#ifdef DB_ENABLE_STATS - if (stats.db_dup_key != (unsigned int)~0) stats.db_dup_key++; -#endif /* DB_ENABLE_STATS */ - switch (db->type) { - case DB_STRING: - case DB_ISTRING: - if (db->maxlen) { - CREATE(str, unsigned char, db->maxlen +1); - memcpy(str, key.str, db->maxlen); - str[db->maxlen] = '\0'; - key.str = str; - } else { - key.str = (unsigned char *)aStrdup((const char *)key.str); - } - return key; - - default: - return key; - } -} - -/** - * Free a key duplicated by db_dup_key. - * @param db Database the key is being used in - * @param key Key to be freed - * @private - * @see #db_dup_key(Database,DBKey) - */ -static void db_dup_key_free(Database db, DBKey key) -{ -#ifdef DB_ENABLE_STATS - if (stats.db_dup_key_free != (unsigned int)~0) stats.db_dup_key_free++; -#endif /* DB_ENABLE_STATS */ - switch (db->type) { - case DB_STRING: - case DB_ISTRING: - aFree(key.str); - return; - - default: - return; - } -} - -/** - * Add a node to the free_list of the database. - * Marks the node as deleted. - * If the key isn't duplicated, the key is duplicated and released. - * @param db Target database - * @param root Root of the tree from the node - * @param node Target node - * @private - * @see #struct db_free - * @see Database#free_list - * @see Database#free_count - * @see Database#free_max - * @see #db_remove(DBInterface,DBKey) - * @see #db_free_remove(Database,DBNode) - */ -static void db_free_add(Database db, DBNode node, DBNode *root) -{ - DBKey old_key; - -#ifdef DB_ENABLE_STATS - if (stats.db_free_add != (unsigned int)~0) stats.db_free_add++; -#endif /* DB_ENABLE_STATS */ - if (db->free_lock == (unsigned int)~0) { - ShowFatalError("db_free_add: free_lock overflow\n" - "Database allocated at %s:%d\n", - db->alloc_file, db->alloc_line); - exit(EXIT_FAILURE); - } - if (!(db->options&DB_OPT_DUP_KEY)) { // Make shure we have a key until the node is freed - old_key = node->key; - node->key = db_dup_key(db, node->key); - db->release(old_key, node->data, DB_RELEASE_KEY); - } - if (db->free_count == db->free_max) { // No more space, expand free_list - db->free_max = (db->free_max<<2) +3; // = db->free_max*4 +3 - if (db->free_max <= db->free_count) { - if (db->free_count == (unsigned int)~0) { - ShowFatalError("db_free_add: free_count overflow\n" - "Database allocated at %s:%d\n", - db->alloc_file, db->alloc_line); - exit(EXIT_FAILURE); - } - db->free_max = (unsigned int)~0; - } - RECREATE(db->free_list, struct db_free, db->free_max); - } - node->deleted = 1; - db->free_list[db->free_count].node = node; - db->free_list[db->free_count].root = root; - db->free_count++; - db->item_count--; -} - -/** - * Remove a node from the free_list of the database. - * Marks the node as not deleted. - * NOTE: Frees the duplicated key of the node. - * @param db Target database - * @param node Node being removed from free_list - * @private - * @see #struct db_free - * @see Database#free_list - * @see Database#free_count - * @see #db_put(DBInterface,DBKey,void *) - * @see #db_free_add(Database,DBNode *,DBNode) - */ -static void db_free_remove(Database db, DBNode node) -{ - unsigned int i; - -#ifdef DB_ENABLE_STATS - if (stats.db_free_remove != (unsigned int)~0) stats.db_free_remove++; -#endif /* DB_ENABLE_STATS */ - for (i = 0; i < db->free_count; i++) { - if (db->free_list[i].node == node) { - if (i < db->free_count -1) // copy the last item to where the removed one was - memcpy(&db->free_list[i], &db->free_list[db->free_count -1], sizeof(struct db_free)); - db_dup_key_free(db, node->key); - break; - } - } - node->deleted = 0; - if (i == db->free_count) { - ShowWarning("db_free_remove: node was not found - database allocated at %s:%d\n", db->alloc_file, db->alloc_line); - } else { - db->free_count--; - } - db->item_count++; -} - -/** - * Increment the free_lock of the database. - * @param db Target database - * @private - * @see Database#free_lock - * @see #db_unlock(Database) - */ -static void db_free_lock(Database db) -{ -#ifdef DB_ENABLE_STATS - if (stats.db_free_lock != (unsigned int)~0) stats.db_free_lock++; -#endif /* DB_ENABLE_STATS */ - if (db->free_lock == (unsigned int)~0) { - ShowFatalError("db_free_lock: free_lock overflow\n" - "Database allocated at %s:%d\n", - db->alloc_file, db->alloc_line); - exit(EXIT_FAILURE); - } - db->free_lock++; -} - -/** - * Decrement the free_lock of the database. - * If it was the last lock, frees the nodes of the database. - * Keeps the tree balanced. - * NOTE: Frees the duplicated keys of the nodes - * @param db Target database - * @private - * @see Database#free_lock - * @see #db_free_dbn(DBNode) - * @see #db_lock(Database) - */ -static void db_free_unlock(Database db) -{ - unsigned int i; - -#ifdef DB_ENABLE_STATS - if (stats.db_free_unlock != (unsigned int)~0) stats.db_free_unlock++; -#endif /* DB_ENABLE_STATS */ - if (db->free_lock == 0) { - ShowWarning("db_free_unlock: free_lock was already 0\n" - "Database allocated at %s:%d\n", - db->alloc_file, db->alloc_line); - } else { - db->free_lock--; - } - if (db->free_lock) - return; // Not last lock - - for (i = 0; i < db->free_count ; i++) { - db_rebalance_erase(db->free_list[i].node, db->free_list[i].root); - db_dup_key_free(db, db->free_list[i].node->key); -#ifdef DB_ENABLE_STATS - if (stats.db_node_free != (unsigned int)~0) stats.db_node_free++; -#endif /* DB_ENABLE_STATS */ - ers_free(db->nodes, db->free_list[i].node); - } - db->free_count = 0; -} - -/*****************************************************************************\ - * (3) Section of protected functions used internally. * - * NOTE: the protected functions used in the database interface are in the * - * next section. * - * db_int_cmp - Default comparator for DB_INT databases. * - * db_uint_cmp - Default comparator for DB_UINT databases. * - * db_string_cmp - Default comparator for DB_STRING databases. * - * db_istring_cmp - Default comparator for DB_ISTRING databases. * - * db_int_hash - Default hasher for DB_INT databases. * - * db_uint_hash - Default hasher for DB_UINT databases. * - * db_string_hash - Default hasher for DB_STRING databases. * - * db_istring_hash - Default hasher for DB_ISTRING databases. * - * db_release_nothing - Releaser that releases nothing. * - * db_release_key - Releaser that only releases the key. * - * db_release_data - Releaser that only releases the data. * - * db_release_both - Releaser that releases key and data. * -\*****************************************************************************/ - -/** - * Default comparator for DB_INT databases. - * Compares key1 to key2. - * Return 0 if equal, negative if lower and positive if higher. - * maxlen is ignored. - * @param key1 Key to be compared - * @param key2 Key being compared to - * @param maxlen Maximum length of the key to hash - * @return 0 if equal, negative if lower and positive if higher - * @see common\db.h#DBKey - * @see common\db.h\DBType#DB_INT - * @see common\db.h#DBComparator - * @see #db_default_cmp(DBType) - */ -static int db_int_cmp(DBKey key1, DBKey key2, unsigned short maxlen) -{ -#ifdef DB_ENABLE_STATS - if (stats.db_int_cmp != (unsigned int)~0) stats.db_int_cmp++; -#endif /* DB_ENABLE_STATS */ - if (key1.i < key2.i) return -1; - if (key1.i > key2.i) return 1; - return 0; -} - -/** - * Default comparator for DB_UINT databases. - * Compares key1 to key2. - * Return 0 if equal, negative if lower and positive if higher. - * maxlen is ignored. - * @param key1 Key to be compared - * @param key2 Key being compared to - * @param maxlen Maximum length of the key to hash - * @return 0 if equal, negative if lower and positive if higher - * @see common\db.h#DBKey - * @see common\db.h\DBType#DB_UINT - * @see common\db.h#DBComparator - * @see #db_default_cmp(DBType) - */ -static int db_uint_cmp(DBKey key1, DBKey key2, unsigned short maxlen) -{ -#ifdef DB_ENABLE_STATS - if (stats.db_uint_cmp != (unsigned int)~0) stats.db_uint_cmp++; -#endif /* DB_ENABLE_STATS */ - if (key1.ui < key2.ui) return -1; - if (key1.ui > key2.ui) return 1; - return 0; -} - -/** - * Default comparator for DB_STRING databases. - * Compares key1 to key2. - * Return 0 if equal, negative if lower and positive if higher. - * @param key1 Key to be compared - * @param key2 Key being compared to - * @param maxlen Maximum length of the key to hash - * @return 0 if equal, negative if lower and positive if higher - * @see common\db.h#DBKey - * @see common\db.h\DBType#DB_STRING - * @see common\db.h#DBComparator - * @see #db_default_cmp(DBType) - */ -static int db_string_cmp(DBKey key1, DBKey key2, unsigned short maxlen) -{ -#ifdef DB_ENABLE_STATS - if (stats.db_string_cmp != (unsigned int)~0) stats.db_string_cmp++; -#endif /* DB_ENABLE_STATS */ - if (maxlen == 0) maxlen = (unsigned short)~0; - return strncmp((const char *)key1.str, (const char *)key2.str, maxlen); -} - -/** - * Default comparator for DB_ISTRING databases. - * Compares key1 to key2 case insensitively. - * Return 0 if equal, negative if lower and positive if higher. - * @param key1 Key to be compared - * @param key2 Key being compared to - * @param maxlen Maximum length of the key to hash - * @return 0 if equal, negative if lower and positive if higher - * @see common\db.h#DBKey - * @see common\db.h\DBType#DB_ISTRING - * @see common\db.h#DBComparator - * @see #db_default_cmp(DBType) - */ -static int db_istring_cmp(DBKey key1, DBKey key2, unsigned short maxlen) -{ -#ifdef DB_ENABLE_STATS - if (stats.db_istring_cmp != (unsigned int)~0) stats.db_istring_cmp++; -#endif /* DB_ENABLE_STATS */ - if (maxlen == 0) maxlen = (unsigned short)~0; - return strncasecmp((const char *)key1.str, (const char *)key2.str, maxlen); -} - -/** - * Default hasher for DB_INT databases. - * Returns the value of the key as an unsigned int. - * maxlen is ignored. - * @param key Key to be hashed - * @param maxlen Maximum length of the key to hash - * @return hash of the key - * @see common\db.h#DBKey - * @see common\db.h\DBType#DB_INT - * @see common\db.h#DBHasher - * @see #db_default_hash(DBType) - */ -static unsigned int db_int_hash(DBKey key, unsigned short maxlen) -{ -#ifdef DB_ENABLE_STATS - if (stats.db_int_hash != (unsigned int)~0) stats.db_int_hash++; -#endif /* DB_ENABLE_STATS */ - return (unsigned int)key.i; -} - -/** - * Default hasher for DB_UINT databases. - * Just returns the value of the key. - * maxlen is ignored. - * @param key Key to be hashed - * @param maxlen Maximum length of the key to hash - * @return hash of the key - * @see common\db.h#DBKey - * @see common\db.h\DBType#DB_UINT - * @see #db_default_hash(DBType) - */ -static unsigned int db_uint_hash(DBKey key, unsigned short maxlen) -{ -#ifdef DB_ENABLE_STATS - if (stats.db_uint_hash != (unsigned int)~0) stats.db_uint_hash++; -#endif /* DB_ENABLE_STATS */ - return key.ui; -} - -/** - * Default hasher for DB_STRING databases. - * If maxlen if 0, the maximum number of maxlen is used instead. - * @param key Key to be hashed - * @param maxlen Maximum length of the key to hash - * @return hash of the key - * @see common\db.h#DBKey - * @see common\db.h\DBType#DB_STRING - * @see #db_default_hash(DBType) - */ -static unsigned int db_string_hash(DBKey key, unsigned short maxlen) -{ - unsigned char *k = key.str; - unsigned int hash = 0; - unsigned short i; - -#ifdef DB_ENABLE_STATS - if (stats.db_string_hash != (unsigned int)~0) stats.db_string_hash++; -#endif /* DB_ENABLE_STATS */ - if (maxlen == 0) - maxlen = (unsigned short)~0; // Maximum - - for (i = 0; *k; i++) { - hash = (hash*33 + *k++)^(hash>>24); - if (i == maxlen) - break; - } - - return hash; -} - -/** - * Default hasher for DB_ISTRING databases. - * If maxlen if 0, the maximum number of maxlen is used instead. - * @param key Key to be hashed - * @param maxlen Maximum length of the key to hash - * @return hash of the key - * @see common\db.h#DBKey - * @see common\db.h\DBType#DB_ISTRING - * @see #db_default_hash(DBType) - */ -static unsigned int db_istring_hash(DBKey key, unsigned short maxlen) -{ - unsigned char *k = key.str; - unsigned int hash = 0; - unsigned short i; - -#ifdef DB_ENABLE_STATS - if (stats.db_istring_hash != (unsigned int)~0) stats.db_istring_hash++; -#endif /* DB_ENABLE_STATS */ - if (maxlen == 0) - maxlen = (unsigned short)~0; // Maximum - - for (i = 0; *k; i++) { - hash = (hash*33 + LOWER(*k))^(hash>>24); - k++; - if (i == maxlen) - break; - } - - return hash; -} - -/** - * Releaser that releases nothing. - * @param key Key of the database entry - * @param data Data of the database entry - * @param which What is being requested to be released - * @protected - * @see common\db.h#DBKey - * @see common\db.h#DBRelease - * @see common\db.h#DBReleaser - * @see #db_default_releaser(DBType,DBOptions) - */ -static void db_release_nothing(DBKey key, void *data, DBRelease which) -{ -#ifdef DB_ENABLE_STATS - if (stats.db_release_nothing != (unsigned int)~0) stats.db_release_nothing++; -#endif /* DB_ENABLE_STATS */ -} - -/** - * Releaser that only releases the key. - * @param key Key of the database entry - * @param data Data of the database entry - * @param which What is being requested to be released - * @protected - * @see common\db.h#DBKey - * @see common\db.h#DBRelease - * @see common\db.h#DBReleaser - * @see #db_default_release(DBType,DBOptions) - */ -static void db_release_key(DBKey key, void *data, DBRelease which) -{ -#ifdef DB_ENABLE_STATS - if (stats.db_release_key != (unsigned int)~0) stats.db_release_key++; -#endif /* DB_ENABLE_STATS */ - if (which&DB_RELEASE_KEY) aFree(key.str); // needs to be a pointer -} - -/** - * Releaser that only releases the data. - * @param key Key of the database entry - * @param data Data of the database entry - * @param which What is being requested to be released - * @protected - * @see common\db.h#DBKey - * @see common\db.h#DBRelease - * @see common\db.h#DBReleaser - * @see #db_default_release(DBType,DBOptions) - */ -static void db_release_data(DBKey key, void *data, DBRelease which) -{ -#ifdef DB_ENABLE_STATS - if (stats.db_release_data != (unsigned int)~0) stats.db_release_data++; -#endif /* DB_ENABLE_STATS */ - if (which&DB_RELEASE_DATA) aFree(data); -} - -/** - * Releaser that releases both key and data. - * @param key Key of the database entry - * @param data Data of the database entry - * @param which What is being requested to be released - * @protected - * @see common\db.h#DBKey - * @see common\db.h#DBRelease - * @see common\db.h#DBReleaser - * @see #db_default_release(DBType,DBOptions) - */ -static void db_release_both(DBKey key, void *data, DBRelease which) -{ -#ifdef DB_ENABLE_STATS - if (stats.db_release_both != (unsigned int)~0) stats.db_release_both++; -#endif /* DB_ENABLE_STATS */ - if (which&DB_RELEASE_KEY) aFree(key.str); // needs to be a pointer - if (which&DB_RELEASE_DATA) aFree(data); -} - -/*****************************************************************************\ - * (4) Section with protected functions used in the interface of the * - * database. * - * db_obj_get - Get the data identified by the key. * - * db_obj_vgetall - Get the data of the matched entries. * - * db_obj_getall - Get the data of the matched entries. * - * db_obj_vensure - Get the data identified by the key, creating if it * - * doesn't exist yet. * - * db_obj_ensure - Get the data identified by the key, creating if it * - * doesn't exist yet. * - * db_obj_put - Put data identified by the key in the database. * - * db_obj_remove - Remove an entry from the database. * - * db_obj_vforeach - Apply a function to every entry in the database. * - * db_obj_foreach - Apply a function to every entry in the database. * - * db_obj_vclear - Remove all entries from the database. * - * db_obj_clear - Remove all entries from the database. * - * db_obj_vdestroy - Destroy the database, freeing all the used memory. * - * db_obj_destroy - Destroy the database, freeing all the used memory. * - * db_obj_size - Return the size of the database. * - * db_obj_type - Return the type of the database. * - * db_obj_options - Return the options of the database. * -\*****************************************************************************/ - -/** - * Get the data of the entry identifid by the key. - * @param self Interface of the database - * @param key Key that identifies the entry - * @return Data of the entry or NULL if not found - * @protected - * @see common\db.h#DBKey - * @see common\db.h#DBInterface - * @see common\db.h\DBInterface#get(DBInterface,DBKey) - */ -static void *db_obj_get(DBInterface self, DBKey key) -{ - Database db = (Database)self; - DBNode node; - int c; - void *data = NULL; - -#ifdef DB_ENABLE_STATS - if (stats.db_get != (unsigned int)~0) stats.db_get++; -#endif /* DB_ENABLE_STATS */ - if (db == NULL) return NULL; // nullpo candidate - if (!(db->options&DB_OPT_ALLOW_NULL_KEY) && db_is_key_null(db->type, key)) { - ShowError("db_get: Attempted to retrieve non-allowed NULL key for db allocated at %s:%d\n",db->alloc_file, db->alloc_line); - return NULL; // nullpo candidate - } - - db_free_lock(db); - node = db->ht[db->hash(key, db->maxlen)%HASH_SIZE]; - while (node) { - c = db->cmp(key, node->key, db->maxlen); - if (c == 0) { - data = node->data; - break; - } - if (c < 0) - node = node->left; - else - node = node->right; - } - db_free_unlock(db); - return data; -} - -/** - * Get the data of the entries matched by match. - * It puts a maximum of max entries into buf. - * If buf is NULL, it only counts the matches. - * Returns the number of entries that matched. - * NOTE: if the value returned is greater than max, only the - * first max entries found are put into the buffer. - * @param self Interface of the database - * @param buf Buffer to put the data of the matched entries - * @param max Maximum number of data entries to be put into buf - * @param match Function that matches the database entries - * @param ... Extra arguments for match - * @return The number of entries that matched - * @protected - * @see common\db.h#DBInterface - * @see common\db.h#DBMatcher(DBKey key, void *data, va_list args) - * @see common\db.h\DBInterface#vgetall(DBInterface,void **,unsigned int,DBMatch,va_list) - */ -static unsigned int db_obj_vgetall(DBInterface self, void **buf, unsigned int max, DBMatcher match, va_list args) -{ - Database db = (Database)self; - unsigned int i; - DBNode node; - DBNode parent; - unsigned int ret = 0; - -#ifdef DB_ENABLE_STATS - if (stats.db_vgetall != (unsigned int)~0) stats.db_vgetall++; -#endif /* DB_ENABLE_STATS */ - if (db == NULL) return 0; // nullpo candidate - if (match == NULL) return 0; // nullpo candidate - - db_free_lock(db); - for (i = 0; i < HASH_SIZE; i++) { - // Match in the order: current node, left tree, right tree - node = db->ht[i]; - while (node) { - parent = node->parent; - if (!(node->deleted) && match(node->key, node->data, args) == 0) { - if (buf && ret < max) - buf[ret] = node->data; - ret++; - } - if (node->left) { - node = node->left; - continue; - } - if (node->right) { - node = node->right; - continue; - } - while (node) { - parent = node->parent; - if (parent && parent->right && parent->left == node) { - node = parent->right; - break; - } - node = parent; - } - } - } - db_free_unlock(db); - return ret; -} - -/** - * Just calls {@link common\db.h\DBInterface#vgetall(DBInterface,void **,unsigned int,DBMatch,va_list)}. - * Get the data of the entries matched by match. - * It puts a maximum of max entries into buf. - * If buf is NULL, it only counts the matches. - * Returns the number of entries that matched. - * NOTE: if the value returned is greater than max, only the - * first max entries found are put into the buffer. - * @param self Interface of the database - * @param buf Buffer to put the data of the matched entries - * @param max Maximum number of data entries to be put into buf - * @param match Function that matches the database entries - * @param ... Extra arguments for match - * @return The number of entries that matched - * @protected - * @see common\db.h#DBMatcher(DBKey key, void *data, va_list args) - * @see common\db.h#DBInterface - * @see common\db.h\DBInterface#vgetall(DBInterface,void **,unsigned int,DBMatch,va_list) - * @see common\db.h\DBInterface#getall(DBInterface,void **,unsigned int,DBMatch,...) - */ -static unsigned int db_obj_getall(DBInterface self, void **buf, unsigned int max, DBMatcher match, ...) -{ - va_list args; - unsigned int ret; - -#ifdef DB_ENABLE_STATS - if (stats.db_getall != (unsigned int)~0) stats.db_getall++; -#endif /* DB_ENABLE_STATS */ - if (self == NULL) return 0; // nullpo candidate - - va_start(args, match); - ret = self->vgetall(self, buf, max, match, args); - va_end(args); - return ret; -} - -/** - * 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 - * create. - * @param self Interface of the database - * @param key Key that identifies the entry - * @param create Function used to create the data if the entry doesn't exist - * @param args Extra arguments for create - * @return Data of the entry - * @protected - * @see common\db.h#DBKey - * @see common\db.h#DBCreateData - * @see common\db.h#DBInterface - * @see common\db.h\DBInterface#vensure(DBInterface,DBKey,DBCreateData,va_list) - */ -static void *db_obj_vensure(DBInterface self, DBKey key, DBCreateData create, va_list args) -{ - Database db = (Database)self; - DBNode node; - DBNode parent = NULL; - unsigned int hash; - int c = 0; - void *data = NULL; - -#ifdef DB_ENABLE_STATS - if (stats.db_vensure != (unsigned int)~0) stats.db_vensure++; -#endif /* DB_ENABLE_STATS */ - if (db == NULL) return NULL; // nullpo candidate - if (create == NULL) { - ShowError("db_ensure: Create function is NULL for db allocated at %s:%d\n",db->alloc_file, db->alloc_line); - return NULL; // nullpo candidate - } - if (!(db->options&DB_OPT_ALLOW_NULL_KEY) && db_is_key_null(db->type, key)) { - ShowError("db_ensure: Attempted to use non-allowed NULL key for db allocated at %s:%d\n",db->alloc_file, db->alloc_line); - return NULL; // nullpo candidate - } - - db_free_lock(db); - hash = db->hash(key, db->maxlen)%HASH_SIZE; - node = db->ht[hash]; - while (node) { - c = db->cmp(key, node->key, db->maxlen); - if (c == 0) { - break; - } - parent = node; - if (c < 0) - node = node->left; - else - node = node->right; - } - // Create node if necessary - if (node == NULL) { - if (db->item_count == (unsigned int)~0) { - ShowError("db_vensure: item_count overflow, aborting item insertion.\n" - "Database allocated at %s:%d", - db->alloc_file, db->alloc_line); - return NULL; - } -#ifdef DB_ENABLE_STATS - if (stats.db_node_alloc != (unsigned int)~0) stats.db_node_alloc++; -#endif /* DB_ENABLE_STATS */ - node = ers_alloc(db->nodes, struct dbn); - node->left = NULL; - node->right = NULL; - node->deleted = 0; - db->item_count++; - if (c == 0) { // hash entry is empty - node->color = BLACK; - node->parent = NULL; - db->ht[hash] = node; - } else { - node->color = RED; - if (c < 0) { // put at the left - parent->left = node; - node->parent = parent; - } else { // put at the right - parent->right = node; - node->parent = parent; - } - if (parent->color == RED) // two consecutive RED nodes, must rebalance - db_rebalance(node, &db->ht[hash]); - } - // put key and data in the node - if (db->options&DB_OPT_DUP_KEY) { - node->key = db_dup_key(db, key); - if (db->options&DB_OPT_RELEASE_KEY) - db->release(key, data, DB_RELEASE_KEY); - } else { - node->key = key; - } - node->data = create(key, args); - } - data = node->data; - db_free_unlock(db); - return data; -} - -/** - * Just calls {@link common\db.h\DBInterface#vensure(DBInterface,DBKey,DBCreateData,va_list)}. - * 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 - * create. - * @param self Interface of the database - * @param key Key that identifies the entry - * @param create Function used to create the data if the entry doesn't exist - * @param ... Extra arguments for create - * @return Data of the entry - * @protected - * @see common\db.h#DBKey - * @see common\db.h#DBCreateData - * @see common\db.h#DBInterface - * @see common\db.h\DBInterface#vensure(DBInterface,DBKey,DBCreateData,va_list) - * @see common\db.h\DBInterface#ensure(DBInterface,DBKey,DBCreateData,...) - */ -static void *db_obj_ensure(DBInterface self, DBKey key, DBCreateData create, ...) -{ - va_list args; - void *ret; - -#ifdef DB_ENABLE_STATS - if (stats.db_ensure != (unsigned int)~0) stats.db_ensure++; -#endif /* DB_ENABLE_STATS */ - if (self == NULL) return 0; // nullpo candidate - - va_start(args, create); - ret = self->vensure(self, key, create, args); - va_end(args); - return ret; -} - -/** - * Put the data identified by the key in the database. - * Returns the previous data if the entry exists or NULL. - * NOTE: Uses the new key, the old one is released. - * @param self Interface of the database - * @param key Key that identifies the data - * @param data Data to be put in the database - * @return The previous data if the entry exists or NULL - * @protected - * @see common\db.h#DBKey - * @see common\db.h#DBInterface - * @see #db_malloc_dbn(void) - * @see common\db.h\DBInterface#put(DBInterface,DBKey,void *) - */ -static void *db_obj_put(DBInterface self, DBKey key, void *data) -{ - Database db = (Database)self; - DBNode node; - DBNode parent = NULL; - int c = 0; - unsigned int hash; - void *old_data = NULL; - -#ifdef DB_ENABLE_STATS - if (stats.db_put != (unsigned int)~0) stats.db_put++; -#endif /* DB_ENABLE_STATS */ - if (db == NULL) return NULL; // nullpo candidate - if (db->global_lock) { - ShowError("db_put: Database is being destroyed, aborting entry insertion.\n" - "Database allocated at %s:%d\n", - db->alloc_file, db->alloc_line); - return NULL; // nullpo candidate - } - if (!(db->options&DB_OPT_ALLOW_NULL_KEY) && db_is_key_null(db->type, key)) { - ShowError("db_put: Attempted to use non-allowed NULL key for db allocated at %s:%d\n",db->alloc_file, db->alloc_line); - return NULL; // nullpo candidate - } - if (!(data || db->options&DB_OPT_ALLOW_NULL_DATA)) { - ShowError("db_put: Attempted to use non-allowed NULL data for db allocated at %s:%d\n",db->alloc_file, db->alloc_line); - return NULL; // nullpo candidate - } - - if (db->item_count == (unsigned int)~0) { - ShowError("db_put: item_count overflow, aborting item insertion.\n" - "Database allocated at %s:%d", - db->alloc_file, db->alloc_line); - return NULL; - } - // search for an equal node - db_free_lock(db); - hash = db->hash(key, db->maxlen)%HASH_SIZE; - for (node = db->ht[hash]; node; ) { - c = db->cmp(key, node->key, db->maxlen); - if (c == 0) { // equal entry, replace - if (node->deleted) { - db_free_remove(db, node); - } else { - db->release(node->key, node->data, DB_RELEASE_BOTH); - } - old_data = node->data; - break; - } - parent = node; - if (c < 0) { - node = node->left; - } else { - node = node->right; - } - } - // allocate a new node if necessary - if (node == NULL) { -#ifdef DB_ENABLE_STATS - if (stats.db_node_alloc != (unsigned int)~0) stats.db_node_alloc++; -#endif /* DB_ENABLE_STATS */ - node = ers_alloc(db->nodes, struct dbn); - node->left = NULL; - node->right = NULL; - node->deleted = 0; - db->item_count++; - if (c == 0) { // hash entry is empty - node->color = BLACK; - node->parent = NULL; - db->ht[hash] = node; - } else { - node->color = RED; - if (c < 0) { // put at the left - parent->left = node; - node->parent = parent; - } else { // put at the right - parent->right = node; - node->parent = parent; - } - if (parent->color == RED) // two consecutive RED nodes, must rebalance - db_rebalance(node, &db->ht[hash]); - } - } - // put key and data in the node - if (db->options&DB_OPT_DUP_KEY) { - node->key = db_dup_key(db, key); - if (db->options&DB_OPT_RELEASE_KEY) - db->release(key, data, DB_RELEASE_KEY); - } else { - node->key = key; - } - node->data = data; - db_free_unlock(db); - return old_data; -} - -/** - * Remove an entry from the database. - * Returns the data of the entry. - * NOTE: The key (of the database) is released in {@link #db_free_add(Database,DBNode,DBNode *)}. - * @param self Interface of the database - * @param key Key that identifies the entry - * @return The data of the entry or NULL if not found - * @protected - * @see common\db.h#DBKey - * @see common\db.h#DBInterface - * @see #db_free_add(Database,DBNode,DBNode *) - * @see common\db.h\DBInterface#remove(DBInterface,DBKey) - */ -static void *db_obj_remove(DBInterface self, DBKey key) -{ - Database db = (Database)self; - void *data = NULL; - DBNode node; - unsigned int hash; - int c = 0; - -#ifdef DB_ENABLE_STATS - if (stats.db_remove != (unsigned int)~0) stats.db_remove++; -#endif /* DB_ENABLE_STATS */ - if (db == NULL) return NULL; // nullpo candidate - if (db->global_lock) { - ShowError("db_remove: Database is being destroyed. Aborting entry deletion.\n" - "Database allocated at %s:%d\n", - db->alloc_file, db->alloc_line); - return NULL; // nullpo candidate - } - if (!(db->options&DB_OPT_ALLOW_NULL_KEY) && db_is_key_null(db->type, key)) { - ShowError("db_remove: Attempted to use non-allowed NULL key for db allocated at %s:%d\n",db->alloc_file, db->alloc_line); - return NULL; // nullpo candidate - } - - db_free_lock(db); - hash = db->hash(key, db->maxlen)%HASH_SIZE; - for(node = db->ht[hash]; node; ){ - c = db->cmp(key, node->key, db->maxlen); - if (c == 0) { - if (!(node->deleted)) { - data = node->data; - db->release(node->key, node->data, DB_RELEASE_DATA); - db_free_add(db, node, &db->ht[hash]); - } - break; - } - if (c < 0) - node = node->left; - else - node = node->right; - } - db_free_unlock(db); - return data; -} - -/** - * Apply func 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 args Extra arguments for func - * @return Sum of the values returned by func - * @protected - * @see common\db.h#DBInterface - * @see common\db.h#DBApply(DBKey,void *,va_list) - * @see common\db.h\DBInterface#vforeach(DBInterface,DBApply,va_list) - */ -static int db_obj_vforeach(DBInterface self, DBApply func, va_list args) -{ - Database db = (Database)self; - unsigned int i; - int sum = 0; - DBNode node; - DBNode parent; - -#ifdef DB_ENABLE_STATS - if (stats.db_vforeach != (unsigned int)~0) stats.db_vforeach++; -#endif /* DB_ENABLE_STATS */ - if (db == NULL) return 0; // nullpo candidate - if (func == NULL) { - ShowError("db_foreach: Passed function is NULL for db allocated at %s:%d\n",db->alloc_file, db->alloc_line); - return 0; // nullpo candidate - } - - db_free_lock(db); - for (i = 0; i < HASH_SIZE; i++) { - // Apply func in the order: current node, left node, right node - node = db->ht[i]; - while (node) { - parent = node->parent; - if (!(node->deleted)) - sum += func(node->key, node->data, args); - if (node->left) { - node = node->left; - continue; - } - if (node->right) { - node = node->right; - continue; - } - while (node) { - parent = node->parent; - if (parent && parent->right && parent->left == node) { - node = parent->right; - break; - } - node = parent; - } - } - } - db_free_unlock(db); - return sum; -} - -/** - * Just calls {@link common\db.h\DBInterface#vforeach(DBInterface,DBApply,va_list)}. - * Apply func 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 ... Extra arguments for func - * @return Sum of the values returned by func - * @protected - * @see common\db.h#DBInterface - * @see common\db.h#DBApply(DBKey,void *,va_list) - * @see common\db.h\DBInterface#vforeach(DBInterface,DBApply,va_list) - * @see common\db.h\DBInterface#foreach(DBInterface,DBApply,...) - */ -static int db_obj_foreach(DBInterface self, DBApply func, ...) -{ - va_list args; - int ret; - -#ifdef DB_ENABLE_STATS - if (stats.db_foreach != (unsigned int)~0) stats.db_foreach++; -#endif /* DB_ENABLE_STATS */ - if (self == NULL) return 0; // nullpo candidate - - va_start(args, func); - ret = self->vforeach(self, func, args); - va_end(args); - return ret; -} - -/** - * Removes all entries from the database. - * Before deleting an entry, func is applyed to it. - * Releases the key and the data. - * Returns the sum of values returned by func, if it exists. - * @param self Interface of the database - * @param func Function to be applyed to every entry before deleting - * @param args Extra arguments for func - * @return Sum of values returned by func - * @protected - * @see common\db.h#DBApply(DBKey,void *,va_list) - * @see common\db.h#DBInterface - * @see common\db.h\DBInterface#vclear(DBInterface,DBApply,va_list) - */ -static int db_obj_vclear(DBInterface self, DBApply func, va_list args) -{ - Database db = (Database)self; - int sum = 0; - unsigned int i; - DBNode node; - DBNode parent; - -#ifdef DB_ENABLE_STATS - if (stats.db_vclear != (unsigned int)~0) stats.db_vclear++; -#endif /* DB_ENABLE_STATS */ - if (db == NULL) return 0; // nullpo candidate - - db_free_lock(db); - for (i = 0; i < HASH_SIZE; i++) { - // Apply the func and delete in the order: left tree, right tree, current node - node = db->ht[i]; - db->ht[i] = NULL; - while (node) { - parent = node->parent; - if (node->left) { - node = node->left; - continue; - } - if (node->right) { - node = node->right; - continue; - } - if (node->deleted) { - db_dup_key_free(db, node->key); - } else { - if (func) - sum += func(node->key, node->data, args); - db->release(node->key, node->data, DB_RELEASE_BOTH); - node->deleted = 1; - } -#ifdef DB_ENABLE_STATS - if (stats.db_node_free != (unsigned int)~0) stats.db_node_free++; -#endif /* DB_ENABLE_STATS */ - ers_free(db->nodes, node); - if (parent) { - if (parent->left == node) - parent->left = NULL; - else - parent->right = NULL; - } - node = parent; - } - db->ht[i] = NULL; - } - db->free_count = 0; - db->item_count = 0; - db_free_unlock(db); - return sum; -} - -/** - * Just calls {@link common\db.h\DBInterface#vclear(DBInterface,DBApply,va_list)}. - * Removes all entries from the database. - * Before deleting an entry, func is applyed 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 - * a database entry will give an error and be aborted (except for clearing). - * @param self Interface of the database - * @param func Function to be applyed to every entry before deleting - * @param ... Extra arguments for func - * @return Sum of values returned by func - * @protected - * @see common\db.h#DBApply(DBKey,void *,va_list) - * @see common\db.h#DBInterface - * @see common\db.h\DBInterface#vclear(DBInterface,DBApply,va_list) - * @see common\db.h\DBInterface#clear(DBInterface,DBApply,...) - */ -static int db_obj_clear(DBInterface self, DBApply func, ...) -{ - va_list args; - int ret; - -#ifdef DB_ENABLE_STATS - if (stats.db_clear != (unsigned int)~0) stats.db_clear++; -#endif /* DB_ENABLE_STATS */ - if (self == NULL) return 0; // nullpo candidate - - va_start(args, func); - ret = self->vclear(self, func, args); - va_end(args); - return ret; -} - -/** - * Finalize the database, feeing all the memory it uses. - * Before deleting an entry, func is applyed 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 - * a database entry will give an error and be aborted (except for clearing). - * @param self Interface of the database - * @param func Function to be applyed to every entry before deleting - * @param args Extra arguments for func - * @return Sum of values returned by func - * @protected - * @see common\db.h#DBApply(DBKey,void *,va_list) - * @see common\db.h#DBInterface - * @see common\db.h\DBInterface#vdestroy(DBInterface,DBApply,va_list) - */ -static int db_obj_vdestroy(DBInterface self, DBApply func, va_list args) -{ - Database db = (Database)self; - int sum; - -#ifdef DB_ENABLE_STATS - if (stats.db_vdestroy != (unsigned int)~0) stats.db_vdestroy++; -#endif /* DB_ENABLE_STATS */ - if (db == NULL) return 0; // nullpo candidate - if (db->global_lock) { - ShowError("db_vdestroy: Database is already locked for destruction. Aborting second database destruction.\n" - "Database allocated at %s:%d\n", - db->alloc_file, db->alloc_line); - return 0; - } - if (db->free_lock) - ShowWarning("db_vdestroy: Database is still in use, %u lock(s) left. Continuing database destruction.\n" - "Database allocated at %s:%d\n", - db->alloc_file, db->alloc_line, db->free_lock); - -#ifdef DB_ENABLE_STATS - switch (db->type) { - case DB_INT: - stats.db_int_destroy++; - break; - case DB_UINT: - stats.db_uint_destroy++; - break; - case DB_STRING: - stats.db_string_destroy++; - break; - case DB_ISTRING: - stats.db_istring_destroy++; - break; - } -#endif /* DB_ENABLE_STATS */ - db_free_lock(db); - db->global_lock = 1; - sum = self->vclear(self, func, args); - aFree(db->free_list); - db->free_list = NULL; - db->free_max = 0; - ers_destroy(db->nodes); - db_free_unlock(db); - aFree(db); - return sum; -} - -/** - * Just calls {@link common\db.h\DBInterface#db_vdestroy(DBInterface,DBApply,va_list)}. - * Finalize the database, feeing all the memory it uses. - * Before deleting an entry, func is applyed 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 - * a database entry will give an error and be aborted. - * @param self Interface of the database - * @param func Function to be applyed to every entry before deleting - * @param ... Extra arguments for func - * @return Sum of values returned by func - * @protected - * @see common\db.h#DBApply(DBKey,void *,va_list) - * @see common\db.h#DBInterface - * @see common\db.h\DBInterface#vdestroy(DBInterface,DBApply,va_list) - * @see common\db.h\DBInterface#destroy(DBInterface,DBApply,...) - */ -static int db_obj_destroy(DBInterface self, DBApply func, ...) -{ - va_list args; - int ret; - -#ifdef DB_ENABLE_STATS - if (stats.db_destroy != (unsigned int)~0) stats.db_destroy++; -#endif /* DB_ENABLE_STATS */ - if (self == NULL) return 0; // nullpo candidate - - va_start(args, func); - ret = self->vdestroy(self, func, args); - va_end(args); - return ret; -} - -/** - * Return the size of the database (number of items in the database). - * @param self Interface of the database - * @return Size of the database - * @protected - * @see common\db.h#DBInterface - * @see Database#item_count - * @see common\db.h\DBInterface#size(DBInterface) - */ -static unsigned int db_obj_size(DBInterface self) -{ - Database db = (Database)self; - unsigned int item_count; - -#ifdef DB_ENABLE_STATS - if (stats.db_size != (unsigned int)~0) stats.db_size++; -#endif /* DB_ENABLE_STATS */ - if (db == NULL) return 0; // nullpo candidate - - db_free_lock(db); - item_count = db->item_count; - db_free_unlock(db); - - return item_count; -} - -/** - * Return the type of database. - * @param self Interface of the database - * @return Type of the database - * @protected - * @see common\db.h#DBType - * @see common\db.h#DBInterface - * @see Database#type - * @see common\db.h\DBInterface#type(DBInterface) - */ -static DBType db_obj_type(DBInterface self) -{ - Database db = (Database)self; - DBType type; - -#ifdef DB_ENABLE_STATS - if (stats.db_type != (unsigned int)~0) stats.db_type++; -#endif /* DB_ENABLE_STATS */ - if (db == NULL) return -1; // nullpo candidate - TODO what should this return? - - db_free_lock(db); - type = db->type; - db_free_unlock(db); - - return type; -} - -/** - * Return the options of the database. - * @param self Interface of the database - * @return Options of the database - * @protected - * @see common\db.h#DBOptions - * @see common\db.h#DBInterface - * @see Database#options - * @see common\db.h\DBInterface#options(DBInterface) - */ -static DBOptions db_obj_options(DBInterface self) -{ - Database db = (Database)self; - DBOptions options; - -#ifdef DB_ENABLE_STATS - if (stats.db_options != (unsigned int)~0) stats.db_options++; -#endif /* DB_ENABLE_STATS */ - if (db == NULL) return DB_OPT_BASE; // nullpo candidate - TODO what should this return? - - db_free_lock(db); - options = db->options; - db_free_unlock(db); - - return options; -} - -/*****************************************************************************\ - * (5) Section with public functions. * - * db_fix_options - Apply database type restrictions to the options. * - * 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_alloc - Allocate a new database. * - * db_i2key - Manual cast from 'int' to 'DBKey'. * - * db_ui2key - Manual cast from 'unsigned int' to 'DBKey'. * - * db_str2key - Manual cast from 'unsigned char *' to 'DBKey'. * - * db_init - Initialize the database system. * - * db_final - Finalize the database system. * -\*****************************************************************************/ - -/** - * Returns the fixed options according to the database type. - * Sets required options and unsets unsupported options. - * For numeric databases DB_OPT_DUP_KEY and DB_OPT_RELEASE_KEY are unset. - * @param type Type of the database - * @param options Original options of the database - * @return Fixed options of the database - * @private - * @see common\db.h#DBType - * @see common\db.h#DBOptions - * @see #db_default_release(DBType,DBOptions) - * @see #db_alloc(const char *,int,DBType,DBOptions,unsigned short) - * @see common\db.h#db_fix_options(DBType,DBOptions) - */ -DBOptions db_fix_options(DBType type, DBOptions options) -{ -#ifdef DB_ENABLE_STATS - if (stats.db_fix_options != (unsigned int)~0) stats.db_fix_options++; -#endif /* DB_ENABLE_STATS */ - switch (type) { - case DB_INT: - case DB_UINT: // Numeric database, do nothing with the keys - return options&~(DB_OPT_DUP_KEY|DB_OPT_RELEASE_KEY); - - default: - ShowError("db_fix_options: Unknown database type %u with options %x\n", type, options); - case DB_STRING: - case DB_ISTRING: // String databases, no fix required - return options; - } -} - -/** - * Returns the default comparator for the specified type of database. - * @param type Type of database - * @return Comparator for the type of database or NULL if unknown database - * @public - * @see common\db.h#DBType - * @see #db_int_cmp(DBKey,DBKey,unsigned short) - * @see #db_uint_cmp(DBKey,DBKey,unsigned short) - * @see #db_string_cmp(DBKey,DBKey,unsigned short) - * @see #db_istring_cmp(DBKey,DBKey,unsigned short) - * @see common\db.h#db_default_cmp(DBType) - */ -DBComparator db_default_cmp(DBType type) -{ -#ifdef DB_ENABLE_STATS - if (stats.db_default_cmp != (unsigned int)~0) stats.db_default_cmp++; -#endif /* DB_ENABLE_STATS */ - switch (type) { - case DB_INT: return db_int_cmp; - case DB_UINT: return db_uint_cmp; - case DB_STRING: return db_string_cmp; - case DB_ISTRING: return db_istring_cmp; - default: - ShowError("db_default_cmp: Unknown database type %u\n", type); - return NULL; - } -} - -/** - * Returns the default hasher for the specified type of database. - * @param type Type of database - * @return Hasher of the type of database or NULL if unknown database - * @public - * @see common\db.h#DBType - * @see #db_int_hash(DBKey,unsigned short) - * @see #db_uint_hash(DBKey,unsigned short) - * @see #db_string_hash(DBKey,unsigned short) - * @see #db_istring_hash(DBKey,unsigned short) - * @see common\db.h#db_default_hash(DBType) - */ -DBHasher db_default_hash(DBType type) -{ -#ifdef DB_ENABLE_STATS - if (stats.db_default_hash != (unsigned int)~0) stats.db_default_hash++; -#endif /* DB_ENABLE_STATS */ - switch (type) { - case DB_INT: return db_int_hash; - case DB_UINT: return db_uint_hash; - case DB_STRING: return db_string_hash; - case DB_ISTRING: return db_istring_hash; - default: - ShowError("db_default_hash: Unknown database type %u\n", type); - return NULL; - } -} - -/** - * 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. - * @param type Type of database - * @param options Options of the database - * @return Default releaser for the type of database with the specified options - * @public - * @see common\db.h#DBType - * @see common\db.h#DBOptions - * @see common\db.h#DBReleaser - * @see #db_release_nothing(DBKey,void *,DBRelease) - * @see #db_release_key(DBKey,void *,DBRelease) - * @see #db_release_data(DBKey,void *,DBRelease) - * @see #db_release_both(DBKey,void *,DBRelease) - * @see #db_custom_release(DBRelease) - * @see common\db.h#db_default_release(DBType,DBOptions) - */ -DBReleaser db_default_release(DBType type, DBOptions options) -{ -#ifdef DB_ENABLE_STATS - if (stats.db_default_release != (unsigned int)~0) stats.db_default_release++; -#endif /* DB_ENABLE_STATS */ - options = db_fix_options(type, options); - if (options&DB_OPT_RELEASE_DATA) { // Release data, what about the key? - if (options&(DB_OPT_DUP_KEY|DB_OPT_RELEASE_KEY)) - return db_release_both; // Release both key and data - return db_release_data; // Only release data - } - if (options&(DB_OPT_DUP_KEY|DB_OPT_RELEASE_KEY)) - return db_release_key; // Only release key - return db_release_nothing; // Release nothing -} - -/** - * Returns the releaser that releases the specified release options. - * @param which Options that specified what the releaser releases - * @return Releaser for the specified release options - * @public - * @see common\db.h#DBRelease - * @see common\db.h#DBReleaser - * @see #db_release_nothing(DBKey,void *,DBRelease) - * @see #db_release_key(DBKey,void *,DBRelease) - * @see #db_release_data(DBKey,void *,DBRelease) - * @see #db_release_both(DBKey,void *,DBRelease) - * @see #db_default_release(DBType,DBOptions) - * @see common\db.h#db_custom_release(DBRelease) - */ -DBReleaser db_custom_release(DBRelease which) -{ -#ifdef DB_ENABLE_STATS - if (stats.db_custom_release != (unsigned int)~0) stats.db_custom_release++; -#endif /* DB_ENABLE_STATS */ - switch (which) { - case DB_RELEASE_NOTHING: return db_release_nothing; - case DB_RELEASE_KEY: return db_release_key; - case DB_RELEASE_DATA: return db_release_data; - case DB_RELEASE_BOTH: return db_release_both; - default: - ShowError("db_custom_release: Unknown release options %u\n", which); - return NULL; - } -} - -/** - * Allocate a new database of the specified type. - * NOTE: the options are fixed by {@link #db_fix_options(DBType,DBOptions)} - * before creating the database. - * @param file File where the database is being allocated - * @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 - * databases - * @return The interface of the database - * @public - * @see common\db.h#DBType - * @see common\db.h#DBInterface - * @see #Database - * @see #db_fix_options(DBType,DBOptions) - * @see common\db.h#db_alloc(const char *,int,DBType,unsigned short) - */ -DBInterface db_alloc(const char *file, int line, DBType type, DBOptions options, unsigned short maxlen) -{ - Database db; - unsigned int i; - -#ifdef DB_ENABLE_STATS - if (stats.db_alloc != (unsigned int)~0) stats.db_alloc++; - switch (type) { - case DB_INT: - stats.db_int_alloc++; - break; - case DB_UINT: - stats.db_uint_alloc++; - break; - case DB_STRING: - stats.db_string_alloc++; - break; - case DB_ISTRING: - stats.db_istring_alloc++; - break; - } -#endif /* DB_ENABLE_STATS */ - CREATE(db, struct db, 1); - - options = db_fix_options(type, options); - /* Interface of the database */ - db->dbi.get = db_obj_get; - db->dbi.getall = db_obj_getall; - db->dbi.vgetall = db_obj_vgetall; - db->dbi.ensure = db_obj_ensure; - db->dbi.vensure = db_obj_vensure; - db->dbi.put = db_obj_put; - db->dbi.remove = db_obj_remove; - db->dbi.foreach = db_obj_foreach; - db->dbi.vforeach = db_obj_vforeach; - db->dbi.clear = db_obj_clear; - db->dbi.vclear = db_obj_vclear; - db->dbi.destroy = db_obj_destroy; - db->dbi.vdestroy = db_obj_vdestroy; - db->dbi.size = db_obj_size; - db->dbi.type = db_obj_type; - db->dbi.options = db_obj_options; - /* File and line of allocation */ - db->alloc_file = file; - db->alloc_line = line; - /* Lock system */ - db->free_list = NULL; - db->free_count = 0; - db->free_max = 0; - db->free_lock = 0; - /* Other */ - db->nodes = ers_new((uint32)sizeof(struct dbn)); - db->cmp = db_default_cmp(type); - db->hash = db_default_hash(type); - db->release = db_default_release(type, options); - for (i = 0; i < HASH_SIZE; i++) - db->ht[i] = NULL; - db->type = type; - db->options = options; - db->item_count = 0; - db->maxlen = maxlen; - db->global_lock = 0; - - return &db->dbi; -} - -#ifdef DB_MANUAL_CAST_TO_UNION -/** - * Manual cast from 'int' to the union DBKey. - * Created for compilers that don't support casting to unions. - * @param key Key to be casted - * @return The key as a DBKey union - * @public - * @see common\db.h#DB_MANUAL_CAST_TO_UNION - * @see #db_ui2key(unsigned int) - * @see #db_str2key(unsigned char *) - * @see common\db.h#db_i2key(int) - */ -DBKey db_i2key(int key) -{ - DBKey ret; - -#ifdef DB_ENABLE_STATS - if (stats.db_i2key != (unsigned int)~0) stats.db_i2key++; -#endif /* DB_ENABLE_STATS */ - ret.i = key; - return ret; -} - -/** - * Manual cast from 'unsigned int' to the union DBKey. - * Created for compilers that don't support casting to unions. - * @param key Key to be casted - * @return The key as a DBKey union - * @public - * @see common\db.h#DB_MANUAL_CAST_TO_UNION - * @see #db_i2key(int) - * @see #db_str2key(unsigned char *) - * @see common\db.h#db_ui2key(unsigned int) - */ -DBKey db_ui2key(unsigned int key) -{ - DBKey ret; - -#ifdef DB_ENABLE_STATS - if (stats.db_ui2key != (unsigned int)~0) stats.db_ui2key++; -#endif /* DB_ENABLE_STATS */ - ret.ui = key; - return ret; -} - -/** - * Manual cast from 'unsigned char *' to the union DBKey. - * Created for compilers that don't support casting to unions. - * @param key Key to be casted - * @return The key as a DBKey union - * @public - * @see common\db.h#DB_MANUAL_CAST_TO_UNION - * @see #db_i2key(int) - * @see #db_ui2key(unsigned int) - * @see common\db.h#db_str2key(unsigned char *) - */ -DBKey db_str2key(unsigned char *key) -{ - DBKey ret; - -#ifdef DB_ENABLE_STATS - if (stats.db_str2key != (unsigned int)~0) stats.db_str2key++; -#endif /* DB_ENABLE_STATS */ - ret.str = key; - return ret; -} -#endif /* DB_MANUAL_CAST_TO_UNION */ - -/** - * Initialize the database system. - * @public - * @see #db_final(void) - * @see common\db.h#db_init(void) - */ -void db_init(void) -{ -#ifdef DB_ENABLE_STATS - if (stats.db_init != (unsigned int)~0) stats.db_init++; -#endif /* DB_ENABLE_STATS */ -} - -/** - * Finalize the database system. - * Frees the memory used by the block reusage system. - * @public - * @see common\db.h#DB_FINAL_NODE_CHECK - * @see #db_init(void) - * @see common\db.h#db_final(void) - */ -void db_final(void) -{ -#ifdef DB_ENABLE_STATS - if (stats.db_final != (unsigned int)~0) - stats.db_final++; - ShowInfo(CL_WHITE"Database nodes"CL_RESET":\n" - "allocated %u, freed %u\n", - stats.db_node_alloc, stats.db_node_free); - ShowInfo(CL_WHITE"Database types"CL_RESET":\n" - "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", - 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); - 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" - "db_is_key_null %10u,\n" - "db_dup_key %10u, db_dup_key_free %10u,\n" - "db_free_add %10u, db_free_remove %10u,\n" - "db_free_lock %10u, db_free_unlock %10u,\n" - "db_int_cmp %10u, db_uint_cmp %10u,\n" - "db_string_cmp %10u, db_istring_cmp %10u,\n" - "db_int_hash %10u, db_uint_hash %10u,\n" - "db_string_hash %10u, db_istring_hash %10u,\n" - "db_release_nothing %10u, db_release_key %10u,\n" - "db_release_data %10u, db_release_both %10u,\n" - "db_get %10u,\n" - "db_getall %10u, db_vgetall %10u,\n" - "db_ensure %10u, db_vensure %10u,\n" - "db_put %10u, db_remove %10u,\n" - "db_foreach %10u, db_vforeach %10u,\n" - "db_clear %10u, db_vclear %10u,\n" - "db_destroy %10u, db_vdestroy %10u,\n" - "db_size %10u, db_type %10u,\n" - "db_options %10u, db_fix_options %10u,\n" - "db_default_cmp %10u, db_default_hash %10u,\n" - "db_default_release %10u, db_custom_release %10u,\n" - "db_alloc %10u, db_i2key %10u,\n" - "db_ui2key %10u, db_str2key %10u,\n" - "db_init %10u, db_final %10u\n", - stats.db_rotate_left, stats.db_rotate_right, - stats.db_rebalance, stats.db_rebalance_erase, - stats.db_is_key_null, - stats.db_dup_key, stats.db_dup_key_free, - stats.db_free_add, stats.db_free_remove, - stats.db_free_lock, stats.db_free_unlock, - stats.db_int_cmp, stats.db_uint_cmp, - stats.db_string_cmp, stats.db_istring_cmp, - stats.db_int_hash, stats.db_uint_hash, - stats.db_string_hash, stats.db_istring_hash, - stats.db_release_nothing, stats.db_release_key, - stats.db_release_data, stats.db_release_both, - stats.db_get, - stats.db_getall, stats.db_vgetall, - stats.db_ensure, stats.db_vensure, - stats.db_put, stats.db_remove, - stats.db_foreach, stats.db_vforeach, - stats.db_clear, stats.db_vclear, - stats.db_destroy, stats.db_vdestroy, - stats.db_size, stats.db_type, - stats.db_options, stats.db_fix_options, - stats.db_default_cmp, stats.db_default_hash, - stats.db_default_release, stats.db_custom_release, - stats.db_alloc, stats.db_i2key, - stats.db_ui2key, stats.db_str2key, - stats.db_init, stats.db_final); -#endif /* DB_ENABLE_STATS */ -} - -// Link DB System - jAthena -void linkdb_insert( struct linkdb_node** head, void *key, void* data) { - struct linkdb_node *node; - if( head == NULL ) return ; - node = aMalloc( sizeof(struct linkdb_node) ); - if( *head == NULL ) { - // first node - *head = node; - node->prev = NULL; - node->next = NULL; - } else { - // link nodes - node->next = *head; - node->prev = (*head)->prev; - (*head)->prev = node; - (*head) = node; - } - node->key = key; - node->data = data; -} - -void* linkdb_search( struct linkdb_node** head, void *key) { - int n = 0; - struct linkdb_node *node; - if( head == NULL ) return NULL; - node = *head; - while( node ) { - if( node->key == key ) { - if( node->prev && n > 5 ) { - // 処理効率改善の為にheadに移動させる - if(node->prev) node->prev->next = node->next; - if(node->next) node->next->prev = node->prev; - node->next = *head; - node->prev = (*head)->prev; - (*head)->prev = node; - (*head) = node; - } - return node->data; - } - node = node->next; - n++; - } - return NULL; -} - -void* linkdb_erase( struct linkdb_node** head, void *key) { - struct linkdb_node *node; - if( head == NULL ) return NULL; - node = *head; - while( node ) { - if( node->key == key ) { - void *data = node->data; - if( node->prev == NULL ) - *head = node->next; - else - node->prev->next = node->next; - if( node->next ) - node->next->prev = node->prev; - aFree( node ); - return data; - } - node = node->next; - } - return NULL; -} - -void linkdb_replace( struct linkdb_node** head, void *key, void *data ) { - int n = 0; - struct linkdb_node *node; - if( head == NULL ) return ; - node = *head; - while( node ) { - if( node->key == key ) { - if( node->prev && n > 5 ) { - // 処理効率改善の為にheadに移動させる - if(node->prev) node->prev->next = node->next; - if(node->next) node->next->prev = node->prev; - node->next = *head; - node->prev = (*head)->prev; - (*head)->prev = node; - (*head) = node; - } - node->data = data; - return ; - } - node = node->next; - n++; - } - // 見つからないので挿入 - linkdb_insert( head, key, data ); -} - -void linkdb_final( struct linkdb_node** head ) { - struct linkdb_node *node, *node2; - if( head == NULL ) return ; - node = *head; - while( node ) { - node2 = node->next; - aFree( node ); - node = node2; - } - *head = NULL; -} - +/*****************************************************************************\ + * Copyright (c) Athena Dev Teams - Licensed under GNU GPL * + * 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 * + * (2) Private functions * + * (3) Protected functions used internally * + * (4) Protected functions used in the interface of the database * + * (5) Public functions * + * * + * The databases are structured as a hashtable of RED-BLACK trees. * + * * + * Properties of the RED-BLACK trees being used: * + * 1. The value of any node is greater than the value of its left child and * + * less than the value of its right child. * + * 2. Every node is colored either RED or BLACK. * + * 3. Every red node that is not a leaf has only black children. * + * 4. Every path from the root to a leaf contains the same number of black * + * nodes. * + * 5. The root node is black. * + * An n node in a RED-BLACK tree has the property that its * + * height is O(lg(n)). * + * Another important property is that after adding a node to a RED-BLACK * + * tree, the tree can be readjusted in O(lg(n)) time. * + * Similarly, after deleting a node from a RED-BLACK tree, the tree can be * + * readjusted in O(lg(n)) time. * + * {@link http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic18/} * + * * + * How to add new database types: * + * 1. Add the identifier of the new database type to the enum DBType * + * 2. If not already there, add the data type of the key to the union DBKey * + * 3. If the key can be considered NULL, update the function db_is_key_null * + * 4. If the key can be duplicated, update the functions db_dup_key and * + * db_dup_key_free * + * 5. Create a comparator and update the function db_default_cmp * + * 6. Create a hasher and update the function db_default_hash * + * 7. If the new database type requires or does not support some options, * + * update the function db_fix_options * + * * + * TODO: * + * - create test cases to test the database system thoroughly * + * - make data an enumeration * + * - finish this header describing the database system * + * - create custom database allocator * + * - make the system thread friendly * + * - change the structure of the database to T-Trees * + * - create a db that organizes itself by splaying * + * * + * HISTORY: * + * 2.1 (Athena build #???#) - Portability fix * + * - Fixed the portability of casting to union and added the functions * + * {@link DBInterface#ensure(DBInterface,DBKey,DBCreateData,...)} and * + * {@link DBInterface#clear(DBInterface,DBApply,...)}. * + * 2.0 (Athena build 4859) - Transition version * + * - Almost everything recoded with a strategy similar to objects, * + * database structure is maintained. * + * 1.0 (up to Athena build 4706) * + * - Previous database system. * + * * + * @version 2.1 (Athena build #???#) - Portability fix * + * @author (Athena build 4859) Flavio @ Amazon Project * + * @author (up to Athena build 4706) Athena Dev Teams * + * @encoding US-ASCII * + * @see common#db.h * +\*****************************************************************************/ +#include +#include +#include + +#include "db.h" +#include "../common/mmo.h" +#include "../common/utils.h" +#include "../common/malloc.h" +#include "../common/showmsg.h" +#include "../common/ers.h" + +/*****************************************************************************\ + * (1) Private typedefs, enums, structures, defines and global variables of * + * the database system. * + * DB_ENABLE_STATS - Define to enable database statistics. * + * HASH_SIZE - Define with the size of the hashtable. * + * 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. * + * Database - Struture 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 + * system. + * WARNING: This adds overhead to every database operation (not shure how much). + * @private + * @see #DBStats + * @see #stats + * @see #db_final(void) + */ +//#define DB_ENABLE_STATS + +/** + * Size of the hashtable in the database. + * @private + * @see Database#ht + */ +#define HASH_SIZE (256+27) + +/** + * A node in a RED-BLACK tree of the database. + * @param parent Parent node + * @param left Left child node + * @param right Right child node + * @param key Key of this database entry + * @param data Data of this database entry + * @param deleted If the node is deleted + * @param color Color of the node + * @private + * @see Database#ht + */ +typedef struct dbn { + // Tree structure + struct dbn *parent; + struct dbn *left; + struct dbn *right; + // Node data + DBKey key; + void *data; + // Other + enum {RED, BLACK} color; + unsigned deleted : 1; +} *DBNode; + +/** + * Structure that holds a deleted node. + * @param node Deleted node + * @param root Address to the root of the tree + * @private + * @see Database#free_list + */ +struct db_free { + DBNode node; + DBNode *root; +}; + +/** + * Complete database structure. + * @param dbi Interface of the database + * @param alloc_file File where the database was allocated + * @param alloc_line Line in the file where the database was allocated + * @param free_list Array of deleted nodes to be freed + * @param free_count Number of deleted nodes in free_list + * @param free_max Current maximum capacity of free_list + * @param free_lock Lock for freeing the nodes + * @param nodes Manager of reusable tree nodes + * @param cmp Comparator of the database + * @param hash Hasher of the database + * @param release Releaser of the database + * @param ht Hashtable of RED-BLACK trees + * @param type Type of the database + * @param options Options of the database + * @param item_count Number of items in the database + * @param maxlen Maximum length of strings in DB_STRING and DB_ISTRING databases + * @param global_lock Global lock of the database + * @private + * @see common\db.h#DBInterface + * @see #HASH_SIZE + * @see #DBNode + * @see #struct db_free + * @see common\db.h#DBComparator(void *,void *) + * @see common\db.h#DBHasher(void *) + * @see common\db.h#DBReleaser(void *,void *,DBRelease) + * @see common\db.h#DBOptions + * @see common\db.h#DBType + * @see #db_alloc(const char *,int,DBOptions,DBType,...) + */ +typedef struct db { + // Database interface + struct dbt dbi; + // File and line of allocation + const char *alloc_file; + int alloc_line; + // Lock system + struct db_free *free_list; + unsigned int free_count; + unsigned int free_max; + unsigned int free_lock; + // Other + ERInterface nodes; + DBComparator cmp; + DBHasher hash; + DBReleaser release; + DBNode ht[HASH_SIZE]; + DBType type; + DBOptions options; + unsigned int item_count; + unsigned short maxlen; + unsigned global_lock : 1; +} *Database; + +#ifdef DB_ENABLE_STATS +/** + * Structure with what is counted when the database estatistics are enabled. + * @private + * @see #DB_ENABLE_STATS + * @see #stats + */ +static struct { + // Node alloc/free + unsigned int db_node_alloc; + unsigned int db_node_free; + // Database creating/destruction counters + unsigned int db_int_alloc; + unsigned int db_uint_alloc; + unsigned int db_string_alloc; + unsigned int db_istring_alloc; + unsigned int db_int_destroy; + unsigned int db_uint_destroy; + unsigned int db_string_destroy; + unsigned int db_istring_destroy; + // Function usage counters + unsigned int db_rotate_left; + unsigned int db_rotate_right; + unsigned int db_rebalance; + unsigned int db_rebalance_erase; + unsigned int db_is_key_null; + unsigned int db_dup_key; + unsigned int db_dup_key_free; + unsigned int db_free_add; + unsigned int db_free_remove; + unsigned int db_free_lock; + unsigned int db_free_unlock; + unsigned int db_int_cmp; + unsigned int db_uint_cmp; + unsigned int db_string_cmp; + unsigned int db_istring_cmp; + unsigned int db_int_hash; + unsigned int db_uint_hash; + unsigned int db_string_hash; + unsigned int db_istring_hash; + unsigned int db_release_nothing; + unsigned int db_release_key; + unsigned int db_release_data; + unsigned int db_release_both; + unsigned int db_get; + unsigned int db_getall; + unsigned int db_vgetall; + unsigned int db_ensure; + unsigned int db_vensure; + unsigned int db_put; + unsigned int db_remove; + unsigned int db_foreach; + unsigned int db_vforeach; + unsigned int db_clear; + unsigned int db_vclear; + unsigned int db_destroy; + unsigned int db_vdestroy; + unsigned int db_size; + unsigned int db_type; + unsigned int db_options; + unsigned int db_fix_options; + unsigned int db_default_cmp; + unsigned int db_default_hash; + unsigned int db_default_release; + unsigned int db_custom_release; + unsigned int db_alloc; + unsigned int db_i2key; + unsigned int db_ui2key; + unsigned int db_str2key; + unsigned int db_init; + unsigned int db_final; +} stats = { + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0 +}; +#endif /* DB_ENABLE_STATS */ + +/*****************************************************************************\ + * (2) Section of private functions used by the database system. * + * db_rotate_left - Rotate a tree node to the left. * + * db_rotate_right - Rotate a tree node to the right. * + * db_rebalance - Rebalance the tree. * + * db_rebalance_erase - Rebalance the tree after a BLACK node was erased. * + * db_is_key_null - Returns not 0 if the key is considered NULL. * + * db_dup_key - Duplicate a key for internal use. * + * db_dup_key_free - Free the duplicated key. * + * db_free_add - Add a node to the free_list of a database. * + * db_free_remove - Remove a node from the free_list of a database. * + * db_free_lock - Increment the free_lock of a database. * + * db_free_unlock - Decrement the free_lock of a database. * + * If it was the last lock, frees the nodes in free_list. * + * NOTE: Keeps the database trees balanced. * +\*****************************************************************************/ + +/** + * Rotate a node to the left. + * @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 *) + */ +static void db_rotate_left(DBNode node, DBNode *root) +{ + DBNode y = node->right; + +#ifdef DB_ENABLE_STATS + if (stats.db_rotate_left != (unsigned int)~0) stats.db_rotate_left++; +#endif /* DB_ENABLE_STATS */ + // put the left of y at the right of node + node->right = y->left; + if (y->left) + y->left->parent = node; + y->parent = node->parent; + // link y and node's parent + if (node == *root) { + *root = y; // node was root + } else if (node == node->parent->left) { + node->parent->left = y; // node was at the left + } else { + node->parent->right = y; // node was at the right + } + // put node at the left of y + y->left = node; + node->parent = y; +} + +/** + * Rotate a node to the right + * @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 *) + */ +static void db_rotate_right(DBNode node, DBNode *root) +{ + DBNode y = node->left; + +#ifdef DB_ENABLE_STATS + if (stats.db_rotate_right != (unsigned int)~0) stats.db_rotate_right++; +#endif /* DB_ENABLE_STATS */ + // put the right of y at the left of node + node->left = y->right; + if (y->right != 0) + y->right->parent = node; + y->parent = node->parent; + // link y and node's parent + if (node == *root) { + *root = y; // node was root + } else if (node == node->parent->right) { + node->parent->right = y; // node was at the right + } else { + node->parent->left = y; // node was at the left + } + // put node at the right of y + y->right = node; + node->parent = y; +} + +/** + * Rebalance the RED-BLACK tree. + * Called when the node and it's parent are both RED. + * @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_put(DBInterface,DBKey,void *) + */ +static void db_rebalance(DBNode node, DBNode *root) +{ + DBNode y; + +#ifdef DB_ENABLE_STATS + if (stats.db_rebalance != (unsigned int)~0) stats.db_rebalance++; +#endif /* DB_ENABLE_STATS */ + // Restore the RED-BLACK properties + node->color = RED; + while (node != *root && node->parent->color == RED) { + if (node->parent == node->parent->parent->left) { + // If node's parent is a left, y is node's right 'uncle' + y = node->parent->parent->right; + if (y && y->color == RED) { // case 1 + // change the colors and move up the tree + node->parent->color = BLACK; + y->color = BLACK; + node->parent->parent->color = RED; + node = node->parent->parent; + } else { + if (node == node->parent->right) { // case 2 + // move up and rotate + node = node->parent; + db_rotate_left(node, root); + } + // case 3 + node->parent->color = BLACK; + node->parent->parent->color = RED; + db_rotate_right(node->parent->parent, root); + } + } else { + // If node's parent is a right, y is node's left 'uncle' + y = node->parent->parent->left; + if (y && y->color == RED) { // case 1 + // change the colors and move up the tree + node->parent->color = BLACK; + y->color = BLACK; + node->parent->parent->color = RED; + node = node->parent->parent; + } else { + if (node == node->parent->left) { // case 2 + // move up and rotate + node = node->parent; + db_rotate_right(node, root); + } + // case 3 + node->parent->color = BLACK; + node->parent->parent->color = RED; + db_rotate_left(node->parent->parent, root); + } + } + } + (*root)->color = BLACK; // the root can and should always be black +} + +/** + * Erase a node from the RED-BLACK tree, keeping the tree balanced. + * @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_free_unlock(Database) + */ +static void db_rebalance_erase(DBNode node, DBNode *root) +{ + DBNode y = node; + DBNode x = NULL; + DBNode x_parent = NULL; + DBNode w; + +#ifdef DB_ENABLE_STATS + if (stats.db_rebalance_erase != (unsigned int)~0) stats.db_rebalance_erase++; +#endif /* DB_ENABLE_STATS */ + // Select where to change the tree + if (y->left == NULL) { // no left + x = y->right; + } else if (y->right == NULL) { // no right + x = y->left; + } else { // both exist, go to the leftmost node of the right sub-tree + y = y->right; + while (y->left != NULL) + y = y->left; + x = y->right; + } + + // Remove the node from the tree + if (y != node) { // both childs existed + // put the left of 'node' in the left of 'y' + node->left->parent = y; + y->left = node->left; + + // 'y' is not the direct child of 'node' + if (y != node->right) { + // put 'x' in the old position of 'y' + x_parent = y->parent; + if (x) x->parent = y->parent; + y->parent->left = x; + // put the right of 'node' in 'y' + y->right = node->right; + node->right->parent = y; + // 'y' is a direct child of 'node' + } else { + x_parent = y; + } + + // link 'y' and the parent of 'node' + if (*root == node) { + *root = y; // 'node' was the root + } else if (node->parent->left == node) { + node->parent->left = y; // 'node' was at the left + } else { + node->parent->right = y; // 'node' was at the right + } + y->parent = node->parent; + // switch colors + { + int tmp = y->color; + y->color = node->color; + node->color = tmp; + } + y = node; + } else { // one child did not exist + // put x in node's position + x_parent = y->parent; + if (x) x->parent = y->parent; + // link x and node's parent + if (*root == node) { + *root = x; // node was the root + } else if (node->parent->left == node) { + node->parent->left = x; // node was at the left + } else { + node->parent->right = x; // node was at the right + } + } + + // Restore the RED-BLACK properties + if (y->color != RED) { + while (x != *root && (x == NULL || x->color == BLACK)) { + if (x == x_parent->left) { + w = x_parent->right; + if (w->color == RED) { + w->color = BLACK; + x_parent->color = RED; + db_rotate_left(x_parent, root); + w = x_parent->right; + } + if ((w->left == NULL || w->left->color == BLACK) && + (w->right == NULL || w->right->color == BLACK)) { + w->color = RED; + x = x_parent; + x_parent = x_parent->parent; + } else { + if (w->right == NULL || w->right->color == BLACK) { + if (w->left) w->left->color = BLACK; + w->color = RED; + db_rotate_right(w, root); + w = x_parent->right; + } + w->color = x_parent->color; + x_parent->color = BLACK; + if (w->right) w->right->color = BLACK; + db_rotate_left(x_parent, root); + break; + } + } else { + w = x_parent->left; + if (w->color == RED) { + w->color = BLACK; + x_parent->color = RED; + db_rotate_right(x_parent, root); + w = x_parent->left; + } + if ((w->right == NULL || w->right->color == BLACK) && + (w->left == NULL || w->left->color == BLACK)) { + w->color = RED; + x = x_parent; + x_parent = x_parent->parent; + } else { + if (w->left == NULL || w->left->color == BLACK) { + if (w->right) w->right->color = BLACK; + w->color = RED; + db_rotate_left(w, root); + w = x_parent->left; + } + w->color = x_parent->color; + x_parent->color = BLACK; + if (w->left) w->left->color = BLACK; + db_rotate_right(x_parent, root); + break; + } + } + } + if (x) x->color = BLACK; + } +} + +/** + * Returns not 0 if the key is considerd to be NULL. + * @param type Type of database + * @param key Key being tested + * @return not 0 if considered NULL, 0 otherwise + * @private + * @see common\db.h#DBType + * @see common\db.h#DBKey + * @see #db_get(DBInterface,DBKey) + * @see #db_put(DBInterface,DBKey,void *) + * @see #db_remove(DBInterface,DBKey) + */ +static int db_is_key_null(DBType type, DBKey key) +{ +#ifdef DB_ENABLE_STATS + if (stats.db_is_key_null != (unsigned int)~0) stats.db_is_key_null++; +#endif /* DB_ENABLE_STATS */ + switch (type) { + case DB_STRING: + case DB_ISTRING: + return (key.str == NULL); + + default: // Not a pointer + return 0; + } +} + +/** + * Duplicate the key used in the database. + * @param db Database the key is being used in + * @param key Key to be duplicated + * @param Duplicated key + * @private + * @see #db_free_add(Database,DBNode,DBNode *) + * @see #db_free_remove(Database,DBNode) + * @see #db_put(DBInterface,DBKey,void *) + * @see #db_dup_key_free(Database,DBKey) + */ +static DBKey db_dup_key(Database db, DBKey key) +{ + unsigned char *str; + +#ifdef DB_ENABLE_STATS + if (stats.db_dup_key != (unsigned int)~0) stats.db_dup_key++; +#endif /* DB_ENABLE_STATS */ + switch (db->type) { + case DB_STRING: + case DB_ISTRING: + if (db->maxlen) { + CREATE(str, unsigned char, db->maxlen +1); + memcpy(str, key.str, db->maxlen); + str[db->maxlen] = '\0'; + key.str = str; + } else { + key.str = (unsigned char *)aStrdup((const char *)key.str); + } + return key; + + default: + return key; + } +} + +/** + * Free a key duplicated by db_dup_key. + * @param db Database the key is being used in + * @param key Key to be freed + * @private + * @see #db_dup_key(Database,DBKey) + */ +static void db_dup_key_free(Database db, DBKey key) +{ +#ifdef DB_ENABLE_STATS + if (stats.db_dup_key_free != (unsigned int)~0) stats.db_dup_key_free++; +#endif /* DB_ENABLE_STATS */ + switch (db->type) { + case DB_STRING: + case DB_ISTRING: + aFree(key.str); + return; + + default: + return; + } +} + +/** + * Add a node to the free_list of the database. + * Marks the node as deleted. + * If the key isn't duplicated, the key is duplicated and released. + * @param db Target database + * @param root Root of the tree from the node + * @param node Target node + * @private + * @see #struct db_free + * @see Database#free_list + * @see Database#free_count + * @see Database#free_max + * @see #db_remove(DBInterface,DBKey) + * @see #db_free_remove(Database,DBNode) + */ +static void db_free_add(Database db, DBNode node, DBNode *root) +{ + DBKey old_key; + +#ifdef DB_ENABLE_STATS + if (stats.db_free_add != (unsigned int)~0) stats.db_free_add++; +#endif /* DB_ENABLE_STATS */ + if (db->free_lock == (unsigned int)~0) { + ShowFatalError("db_free_add: free_lock overflow\n" + "Database allocated at %s:%d\n", + db->alloc_file, db->alloc_line); + exit(EXIT_FAILURE); + } + if (!(db->options&DB_OPT_DUP_KEY)) { // Make shure we have a key until the node is freed + old_key = node->key; + node->key = db_dup_key(db, node->key); + db->release(old_key, node->data, DB_RELEASE_KEY); + } + if (db->free_count == db->free_max) { // No more space, expand free_list + db->free_max = (db->free_max<<2) +3; // = db->free_max*4 +3 + if (db->free_max <= db->free_count) { + if (db->free_count == (unsigned int)~0) { + ShowFatalError("db_free_add: free_count overflow\n" + "Database allocated at %s:%d\n", + db->alloc_file, db->alloc_line); + exit(EXIT_FAILURE); + } + db->free_max = (unsigned int)~0; + } + RECREATE(db->free_list, struct db_free, db->free_max); + } + node->deleted = 1; + db->free_list[db->free_count].node = node; + db->free_list[db->free_count].root = root; + db->free_count++; + db->item_count--; +} + +/** + * Remove a node from the free_list of the database. + * Marks the node as not deleted. + * NOTE: Frees the duplicated key of the node. + * @param db Target database + * @param node Node being removed from free_list + * @private + * @see #struct db_free + * @see Database#free_list + * @see Database#free_count + * @see #db_put(DBInterface,DBKey,void *) + * @see #db_free_add(Database,DBNode *,DBNode) + */ +static void db_free_remove(Database db, DBNode node) +{ + unsigned int i; + +#ifdef DB_ENABLE_STATS + if (stats.db_free_remove != (unsigned int)~0) stats.db_free_remove++; +#endif /* DB_ENABLE_STATS */ + for (i = 0; i < db->free_count; i++) { + if (db->free_list[i].node == node) { + if (i < db->free_count -1) // copy the last item to where the removed one was + memcpy(&db->free_list[i], &db->free_list[db->free_count -1], sizeof(struct db_free)); + db_dup_key_free(db, node->key); + break; + } + } + node->deleted = 0; + if (i == db->free_count) { + ShowWarning("db_free_remove: node was not found - database allocated at %s:%d\n", db->alloc_file, db->alloc_line); + } else { + db->free_count--; + } + db->item_count++; +} + +/** + * Increment the free_lock of the database. + * @param db Target database + * @private + * @see Database#free_lock + * @see #db_unlock(Database) + */ +static void db_free_lock(Database db) +{ +#ifdef DB_ENABLE_STATS + if (stats.db_free_lock != (unsigned int)~0) stats.db_free_lock++; +#endif /* DB_ENABLE_STATS */ + if (db->free_lock == (unsigned int)~0) { + ShowFatalError("db_free_lock: free_lock overflow\n" + "Database allocated at %s:%d\n", + db->alloc_file, db->alloc_line); + exit(EXIT_FAILURE); + } + db->free_lock++; +} + +/** + * Decrement the free_lock of the database. + * If it was the last lock, frees the nodes of the database. + * Keeps the tree balanced. + * NOTE: Frees the duplicated keys of the nodes + * @param db Target database + * @private + * @see Database#free_lock + * @see #db_free_dbn(DBNode) + * @see #db_lock(Database) + */ +static void db_free_unlock(Database db) +{ + unsigned int i; + +#ifdef DB_ENABLE_STATS + if (stats.db_free_unlock != (unsigned int)~0) stats.db_free_unlock++; +#endif /* DB_ENABLE_STATS */ + if (db->free_lock == 0) { + ShowWarning("db_free_unlock: free_lock was already 0\n" + "Database allocated at %s:%d\n", + db->alloc_file, db->alloc_line); + } else { + db->free_lock--; + } + if (db->free_lock) + return; // Not last lock + + for (i = 0; i < db->free_count ; i++) { + db_rebalance_erase(db->free_list[i].node, db->free_list[i].root); + db_dup_key_free(db, db->free_list[i].node->key); +#ifdef DB_ENABLE_STATS + if (stats.db_node_free != (unsigned int)~0) stats.db_node_free++; +#endif /* DB_ENABLE_STATS */ + ers_free(db->nodes, db->free_list[i].node); + } + db->free_count = 0; +} + +/*****************************************************************************\ + * (3) Section of protected functions used internally. * + * NOTE: the protected functions used in the database interface are in the * + * next section. * + * db_int_cmp - Default comparator for DB_INT databases. * + * db_uint_cmp - Default comparator for DB_UINT databases. * + * db_string_cmp - Default comparator for DB_STRING databases. * + * db_istring_cmp - Default comparator for DB_ISTRING databases. * + * db_int_hash - Default hasher for DB_INT databases. * + * db_uint_hash - Default hasher for DB_UINT databases. * + * db_string_hash - Default hasher for DB_STRING databases. * + * db_istring_hash - Default hasher for DB_ISTRING databases. * + * db_release_nothing - Releaser that releases nothing. * + * db_release_key - Releaser that only releases the key. * + * db_release_data - Releaser that only releases the data. * + * db_release_both - Releaser that releases key and data. * +\*****************************************************************************/ + +/** + * Default comparator for DB_INT databases. + * Compares key1 to key2. + * Return 0 if equal, negative if lower and positive if higher. + * maxlen is ignored. + * @param key1 Key to be compared + * @param key2 Key being compared to + * @param maxlen Maximum length of the key to hash + * @return 0 if equal, negative if lower and positive if higher + * @see common\db.h#DBKey + * @see common\db.h\DBType#DB_INT + * @see common\db.h#DBComparator + * @see #db_default_cmp(DBType) + */ +static int db_int_cmp(DBKey key1, DBKey key2, unsigned short maxlen) +{ +#ifdef DB_ENABLE_STATS + if (stats.db_int_cmp != (unsigned int)~0) stats.db_int_cmp++; +#endif /* DB_ENABLE_STATS */ + if (key1.i < key2.i) return -1; + if (key1.i > key2.i) return 1; + return 0; +} + +/** + * Default comparator for DB_UINT databases. + * Compares key1 to key2. + * Return 0 if equal, negative if lower and positive if higher. + * maxlen is ignored. + * @param key1 Key to be compared + * @param key2 Key being compared to + * @param maxlen Maximum length of the key to hash + * @return 0 if equal, negative if lower and positive if higher + * @see common\db.h#DBKey + * @see common\db.h\DBType#DB_UINT + * @see common\db.h#DBComparator + * @see #db_default_cmp(DBType) + */ +static int db_uint_cmp(DBKey key1, DBKey key2, unsigned short maxlen) +{ +#ifdef DB_ENABLE_STATS + if (stats.db_uint_cmp != (unsigned int)~0) stats.db_uint_cmp++; +#endif /* DB_ENABLE_STATS */ + if (key1.ui < key2.ui) return -1; + if (key1.ui > key2.ui) return 1; + return 0; +} + +/** + * Default comparator for DB_STRING databases. + * Compares key1 to key2. + * Return 0 if equal, negative if lower and positive if higher. + * @param key1 Key to be compared + * @param key2 Key being compared to + * @param maxlen Maximum length of the key to hash + * @return 0 if equal, negative if lower and positive if higher + * @see common\db.h#DBKey + * @see common\db.h\DBType#DB_STRING + * @see common\db.h#DBComparator + * @see #db_default_cmp(DBType) + */ +static int db_string_cmp(DBKey key1, DBKey key2, unsigned short maxlen) +{ +#ifdef DB_ENABLE_STATS + if (stats.db_string_cmp != (unsigned int)~0) stats.db_string_cmp++; +#endif /* DB_ENABLE_STATS */ + if (maxlen == 0) maxlen = (unsigned short)~0; + return strncmp((const char *)key1.str, (const char *)key2.str, maxlen); +} + +/** + * Default comparator for DB_ISTRING databases. + * Compares key1 to key2 case insensitively. + * Return 0 if equal, negative if lower and positive if higher. + * @param key1 Key to be compared + * @param key2 Key being compared to + * @param maxlen Maximum length of the key to hash + * @return 0 if equal, negative if lower and positive if higher + * @see common\db.h#DBKey + * @see common\db.h\DBType#DB_ISTRING + * @see common\db.h#DBComparator + * @see #db_default_cmp(DBType) + */ +static int db_istring_cmp(DBKey key1, DBKey key2, unsigned short maxlen) +{ +#ifdef DB_ENABLE_STATS + if (stats.db_istring_cmp != (unsigned int)~0) stats.db_istring_cmp++; +#endif /* DB_ENABLE_STATS */ + if (maxlen == 0) maxlen = (unsigned short)~0; + return strncasecmp((const char *)key1.str, (const char *)key2.str, maxlen); +} + +/** + * Default hasher for DB_INT databases. + * Returns the value of the key as an unsigned int. + * maxlen is ignored. + * @param key Key to be hashed + * @param maxlen Maximum length of the key to hash + * @return hash of the key + * @see common\db.h#DBKey + * @see common\db.h\DBType#DB_INT + * @see common\db.h#DBHasher + * @see #db_default_hash(DBType) + */ +static unsigned int db_int_hash(DBKey key, unsigned short maxlen) +{ +#ifdef DB_ENABLE_STATS + if (stats.db_int_hash != (unsigned int)~0) stats.db_int_hash++; +#endif /* DB_ENABLE_STATS */ + return (unsigned int)key.i; +} + +/** + * Default hasher for DB_UINT databases. + * Just returns the value of the key. + * maxlen is ignored. + * @param key Key to be hashed + * @param maxlen Maximum length of the key to hash + * @return hash of the key + * @see common\db.h#DBKey + * @see common\db.h\DBType#DB_UINT + * @see #db_default_hash(DBType) + */ +static unsigned int db_uint_hash(DBKey key, unsigned short maxlen) +{ +#ifdef DB_ENABLE_STATS + if (stats.db_uint_hash != (unsigned int)~0) stats.db_uint_hash++; +#endif /* DB_ENABLE_STATS */ + return key.ui; +} + +/** + * Default hasher for DB_STRING databases. + * If maxlen if 0, the maximum number of maxlen is used instead. + * @param key Key to be hashed + * @param maxlen Maximum length of the key to hash + * @return hash of the key + * @see common\db.h#DBKey + * @see common\db.h\DBType#DB_STRING + * @see #db_default_hash(DBType) + */ +static unsigned int db_string_hash(DBKey key, unsigned short maxlen) +{ + unsigned char *k = key.str; + unsigned int hash = 0; + unsigned short i; + +#ifdef DB_ENABLE_STATS + if (stats.db_string_hash != (unsigned int)~0) stats.db_string_hash++; +#endif /* DB_ENABLE_STATS */ + if (maxlen == 0) + maxlen = (unsigned short)~0; // Maximum + + for (i = 0; *k; i++) { + hash = (hash*33 + *k++)^(hash>>24); + if (i == maxlen) + break; + } + + return hash; +} + +/** + * Default hasher for DB_ISTRING databases. + * If maxlen if 0, the maximum number of maxlen is used instead. + * @param key Key to be hashed + * @param maxlen Maximum length of the key to hash + * @return hash of the key + * @see common\db.h#DBKey + * @see common\db.h\DBType#DB_ISTRING + * @see #db_default_hash(DBType) + */ +static unsigned int db_istring_hash(DBKey key, unsigned short maxlen) +{ + unsigned char *k = key.str; + unsigned int hash = 0; + unsigned short i; + +#ifdef DB_ENABLE_STATS + if (stats.db_istring_hash != (unsigned int)~0) stats.db_istring_hash++; +#endif /* DB_ENABLE_STATS */ + if (maxlen == 0) + maxlen = (unsigned short)~0; // Maximum + + for (i = 0; *k; i++) { + hash = (hash*33 + LOWER(*k))^(hash>>24); + k++; + if (i == maxlen) + break; + } + + return hash; +} + +/** + * Releaser that releases nothing. + * @param key Key of the database entry + * @param data Data of the database entry + * @param which What is being requested to be released + * @protected + * @see common\db.h#DBKey + * @see common\db.h#DBRelease + * @see common\db.h#DBReleaser + * @see #db_default_releaser(DBType,DBOptions) + */ +static void db_release_nothing(DBKey key, void *data, DBRelease which) +{ +#ifdef DB_ENABLE_STATS + if (stats.db_release_nothing != (unsigned int)~0) stats.db_release_nothing++; +#endif /* DB_ENABLE_STATS */ +} + +/** + * Releaser that only releases the key. + * @param key Key of the database entry + * @param data Data of the database entry + * @param which What is being requested to be released + * @protected + * @see common\db.h#DBKey + * @see common\db.h#DBRelease + * @see common\db.h#DBReleaser + * @see #db_default_release(DBType,DBOptions) + */ +static void db_release_key(DBKey key, void *data, DBRelease which) +{ +#ifdef DB_ENABLE_STATS + if (stats.db_release_key != (unsigned int)~0) stats.db_release_key++; +#endif /* DB_ENABLE_STATS */ + if (which&DB_RELEASE_KEY) aFree(key.str); // needs to be a pointer +} + +/** + * Releaser that only releases the data. + * @param key Key of the database entry + * @param data Data of the database entry + * @param which What is being requested to be released + * @protected + * @see common\db.h#DBKey + * @see common\db.h#DBRelease + * @see common\db.h#DBReleaser + * @see #db_default_release(DBType,DBOptions) + */ +static void db_release_data(DBKey key, void *data, DBRelease which) +{ +#ifdef DB_ENABLE_STATS + if (stats.db_release_data != (unsigned int)~0) stats.db_release_data++; +#endif /* DB_ENABLE_STATS */ + if (which&DB_RELEASE_DATA) aFree(data); +} + +/** + * Releaser that releases both key and data. + * @param key Key of the database entry + * @param data Data of the database entry + * @param which What is being requested to be released + * @protected + * @see common\db.h#DBKey + * @see common\db.h#DBRelease + * @see common\db.h#DBReleaser + * @see #db_default_release(DBType,DBOptions) + */ +static void db_release_both(DBKey key, void *data, DBRelease which) +{ +#ifdef DB_ENABLE_STATS + if (stats.db_release_both != (unsigned int)~0) stats.db_release_both++; +#endif /* DB_ENABLE_STATS */ + if (which&DB_RELEASE_KEY) aFree(key.str); // needs to be a pointer + if (which&DB_RELEASE_DATA) aFree(data); +} + +/*****************************************************************************\ + * (4) Section with protected functions used in the interface of the * + * database. * + * db_obj_get - Get the data identified by the key. * + * db_obj_vgetall - Get the data of the matched entries. * + * db_obj_getall - Get the data of the matched entries. * + * db_obj_vensure - Get the data identified by the key, creating if it * + * doesn't exist yet. * + * db_obj_ensure - Get the data identified by the key, creating if it * + * doesn't exist yet. * + * db_obj_put - Put data identified by the key in the database. * + * db_obj_remove - Remove an entry from the database. * + * db_obj_vforeach - Apply a function to every entry in the database. * + * db_obj_foreach - Apply a function to every entry in the database. * + * db_obj_vclear - Remove all entries from the database. * + * db_obj_clear - Remove all entries from the database. * + * db_obj_vdestroy - Destroy the database, freeing all the used memory. * + * db_obj_destroy - Destroy the database, freeing all the used memory. * + * db_obj_size - Return the size of the database. * + * db_obj_type - Return the type of the database. * + * db_obj_options - Return the options of the database. * +\*****************************************************************************/ + +/** + * Get the data of the entry identifid by the key. + * @param self Interface of the database + * @param key Key that identifies the entry + * @return Data of the entry or NULL if not found + * @protected + * @see common\db.h#DBKey + * @see common\db.h#DBInterface + * @see common\db.h\DBInterface#get(DBInterface,DBKey) + */ +static void *db_obj_get(DBInterface self, DBKey key) +{ + Database db = (Database)self; + DBNode node; + int c; + void *data = NULL; + +#ifdef DB_ENABLE_STATS + if (stats.db_get != (unsigned int)~0) stats.db_get++; +#endif /* DB_ENABLE_STATS */ + if (db == NULL) return NULL; // nullpo candidate + if (!(db->options&DB_OPT_ALLOW_NULL_KEY) && db_is_key_null(db->type, key)) { + ShowError("db_get: Attempted to retrieve non-allowed NULL key for db allocated at %s:%d\n",db->alloc_file, db->alloc_line); + return NULL; // nullpo candidate + } + + db_free_lock(db); + node = db->ht[db->hash(key, db->maxlen)%HASH_SIZE]; + while (node) { + c = db->cmp(key, node->key, db->maxlen); + if (c == 0) { + data = node->data; + break; + } + if (c < 0) + node = node->left; + else + node = node->right; + } + db_free_unlock(db); + return data; +} + +/** + * Get the data of the entries matched by match. + * It puts a maximum of max entries into buf. + * If buf is NULL, it only counts the matches. + * Returns the number of entries that matched. + * NOTE: if the value returned is greater than max, only the + * first max entries found are put into the buffer. + * @param self Interface of the database + * @param buf Buffer to put the data of the matched entries + * @param max Maximum number of data entries to be put into buf + * @param match Function that matches the database entries + * @param ... Extra arguments for match + * @return The number of entries that matched + * @protected + * @see common\db.h#DBInterface + * @see common\db.h#DBMatcher(DBKey key, void *data, va_list args) + * @see common\db.h\DBInterface#vgetall(DBInterface,void **,unsigned int,DBMatch,va_list) + */ +static unsigned int db_obj_vgetall(DBInterface self, void **buf, unsigned int max, DBMatcher match, va_list args) +{ + Database db = (Database)self; + unsigned int i; + DBNode node; + DBNode parent; + unsigned int ret = 0; + +#ifdef DB_ENABLE_STATS + if (stats.db_vgetall != (unsigned int)~0) stats.db_vgetall++; +#endif /* DB_ENABLE_STATS */ + if (db == NULL) return 0; // nullpo candidate + if (match == NULL) return 0; // nullpo candidate + + db_free_lock(db); + for (i = 0; i < HASH_SIZE; i++) { + // Match in the order: current node, left tree, right tree + node = db->ht[i]; + while (node) { + parent = node->parent; + if (!(node->deleted) && match(node->key, node->data, args) == 0) { + if (buf && ret < max) + buf[ret] = node->data; + ret++; + } + if (node->left) { + node = node->left; + continue; + } + if (node->right) { + node = node->right; + continue; + } + while (node) { + parent = node->parent; + if (parent && parent->right && parent->left == node) { + node = parent->right; + break; + } + node = parent; + } + } + } + db_free_unlock(db); + return ret; +} + +/** + * Just calls {@link common\db.h\DBInterface#vgetall(DBInterface,void **,unsigned int,DBMatch,va_list)}. + * Get the data of the entries matched by match. + * It puts a maximum of max entries into buf. + * If buf is NULL, it only counts the matches. + * Returns the number of entries that matched. + * NOTE: if the value returned is greater than max, only the + * first max entries found are put into the buffer. + * @param self Interface of the database + * @param buf Buffer to put the data of the matched entries + * @param max Maximum number of data entries to be put into buf + * @param match Function that matches the database entries + * @param ... Extra arguments for match + * @return The number of entries that matched + * @protected + * @see common\db.h#DBMatcher(DBKey key, void *data, va_list args) + * @see common\db.h#DBInterface + * @see common\db.h\DBInterface#vgetall(DBInterface,void **,unsigned int,DBMatch,va_list) + * @see common\db.h\DBInterface#getall(DBInterface,void **,unsigned int,DBMatch,...) + */ +static unsigned int db_obj_getall(DBInterface self, void **buf, unsigned int max, DBMatcher match, ...) +{ + va_list args; + unsigned int ret; + +#ifdef DB_ENABLE_STATS + if (stats.db_getall != (unsigned int)~0) stats.db_getall++; +#endif /* DB_ENABLE_STATS */ + if (self == NULL) return 0; // nullpo candidate + + va_start(args, match); + ret = self->vgetall(self, buf, max, match, args); + va_end(args); + return ret; +} + +/** + * 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 + * create. + * @param self Interface of the database + * @param key Key that identifies the entry + * @param create Function used to create the data if the entry doesn't exist + * @param args Extra arguments for create + * @return Data of the entry + * @protected + * @see common\db.h#DBKey + * @see common\db.h#DBCreateData + * @see common\db.h#DBInterface + * @see common\db.h\DBInterface#vensure(DBInterface,DBKey,DBCreateData,va_list) + */ +static void *db_obj_vensure(DBInterface self, DBKey key, DBCreateData create, va_list args) +{ + Database db = (Database)self; + DBNode node; + DBNode parent = NULL; + unsigned int hash; + int c = 0; + void *data = NULL; + +#ifdef DB_ENABLE_STATS + if (stats.db_vensure != (unsigned int)~0) stats.db_vensure++; +#endif /* DB_ENABLE_STATS */ + if (db == NULL) return NULL; // nullpo candidate + if (create == NULL) { + ShowError("db_ensure: Create function is NULL for db allocated at %s:%d\n",db->alloc_file, db->alloc_line); + return NULL; // nullpo candidate + } + if (!(db->options&DB_OPT_ALLOW_NULL_KEY) && db_is_key_null(db->type, key)) { + ShowError("db_ensure: Attempted to use non-allowed NULL key for db allocated at %s:%d\n",db->alloc_file, db->alloc_line); + return NULL; // nullpo candidate + } + + db_free_lock(db); + hash = db->hash(key, db->maxlen)%HASH_SIZE; + node = db->ht[hash]; + while (node) { + c = db->cmp(key, node->key, db->maxlen); + if (c == 0) { + break; + } + parent = node; + if (c < 0) + node = node->left; + else + node = node->right; + } + // Create node if necessary + if (node == NULL) { + if (db->item_count == (unsigned int)~0) { + ShowError("db_vensure: item_count overflow, aborting item insertion.\n" + "Database allocated at %s:%d", + db->alloc_file, db->alloc_line); + return NULL; + } +#ifdef DB_ENABLE_STATS + if (stats.db_node_alloc != (unsigned int)~0) stats.db_node_alloc++; +#endif /* DB_ENABLE_STATS */ + node = ers_alloc(db->nodes, struct dbn); + node->left = NULL; + node->right = NULL; + node->deleted = 0; + db->item_count++; + if (c == 0) { // hash entry is empty + node->color = BLACK; + node->parent = NULL; + db->ht[hash] = node; + } else { + node->color = RED; + if (c < 0) { // put at the left + parent->left = node; + node->parent = parent; + } else { // put at the right + parent->right = node; + node->parent = parent; + } + if (parent->color == RED) // two consecutive RED nodes, must rebalance + db_rebalance(node, &db->ht[hash]); + } + // put key and data in the node + if (db->options&DB_OPT_DUP_KEY) { + node->key = db_dup_key(db, key); + if (db->options&DB_OPT_RELEASE_KEY) + db->release(key, data, DB_RELEASE_KEY); + } else { + node->key = key; + } + node->data = create(key, args); + } + data = node->data; + db_free_unlock(db); + return data; +} + +/** + * Just calls {@link common\db.h\DBInterface#vensure(DBInterface,DBKey,DBCreateData,va_list)}. + * 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 + * create. + * @param self Interface of the database + * @param key Key that identifies the entry + * @param create Function used to create the data if the entry doesn't exist + * @param ... Extra arguments for create + * @return Data of the entry + * @protected + * @see common\db.h#DBKey + * @see common\db.h#DBCreateData + * @see common\db.h#DBInterface + * @see common\db.h\DBInterface#vensure(DBInterface,DBKey,DBCreateData,va_list) + * @see common\db.h\DBInterface#ensure(DBInterface,DBKey,DBCreateData,...) + */ +static void *db_obj_ensure(DBInterface self, DBKey key, DBCreateData create, ...) +{ + va_list args; + void *ret; + +#ifdef DB_ENABLE_STATS + if (stats.db_ensure != (unsigned int)~0) stats.db_ensure++; +#endif /* DB_ENABLE_STATS */ + if (self == NULL) return 0; // nullpo candidate + + va_start(args, create); + ret = self->vensure(self, key, create, args); + va_end(args); + return ret; +} + +/** + * Put the data identified by the key in the database. + * Returns the previous data if the entry exists or NULL. + * NOTE: Uses the new key, the old one is released. + * @param self Interface of the database + * @param key Key that identifies the data + * @param data Data to be put in the database + * @return The previous data if the entry exists or NULL + * @protected + * @see common\db.h#DBKey + * @see common\db.h#DBInterface + * @see #db_malloc_dbn(void) + * @see common\db.h\DBInterface#put(DBInterface,DBKey,void *) + */ +static void *db_obj_put(DBInterface self, DBKey key, void *data) +{ + Database db = (Database)self; + DBNode node; + DBNode parent = NULL; + int c = 0; + unsigned int hash; + void *old_data = NULL; + +#ifdef DB_ENABLE_STATS + if (stats.db_put != (unsigned int)~0) stats.db_put++; +#endif /* DB_ENABLE_STATS */ + if (db == NULL) return NULL; // nullpo candidate + if (db->global_lock) { + ShowError("db_put: Database is being destroyed, aborting entry insertion.\n" + "Database allocated at %s:%d\n", + db->alloc_file, db->alloc_line); + return NULL; // nullpo candidate + } + if (!(db->options&DB_OPT_ALLOW_NULL_KEY) && db_is_key_null(db->type, key)) { + ShowError("db_put: Attempted to use non-allowed NULL key for db allocated at %s:%d\n",db->alloc_file, db->alloc_line); + return NULL; // nullpo candidate + } + if (!(data || db->options&DB_OPT_ALLOW_NULL_DATA)) { + ShowError("db_put: Attempted to use non-allowed NULL data for db allocated at %s:%d\n",db->alloc_file, db->alloc_line); + return NULL; // nullpo candidate + } + + if (db->item_count == (unsigned int)~0) { + ShowError("db_put: item_count overflow, aborting item insertion.\n" + "Database allocated at %s:%d", + db->alloc_file, db->alloc_line); + return NULL; + } + // search for an equal node + db_free_lock(db); + hash = db->hash(key, db->maxlen)%HASH_SIZE; + for (node = db->ht[hash]; node; ) { + c = db->cmp(key, node->key, db->maxlen); + if (c == 0) { // equal entry, replace + if (node->deleted) { + db_free_remove(db, node); + } else { + db->release(node->key, node->data, DB_RELEASE_BOTH); + } + old_data = node->data; + break; + } + parent = node; + if (c < 0) { + node = node->left; + } else { + node = node->right; + } + } + // allocate a new node if necessary + if (node == NULL) { +#ifdef DB_ENABLE_STATS + if (stats.db_node_alloc != (unsigned int)~0) stats.db_node_alloc++; +#endif /* DB_ENABLE_STATS */ + node = ers_alloc(db->nodes, struct dbn); + node->left = NULL; + node->right = NULL; + node->deleted = 0; + db->item_count++; + if (c == 0) { // hash entry is empty + node->color = BLACK; + node->parent = NULL; + db->ht[hash] = node; + } else { + node->color = RED; + if (c < 0) { // put at the left + parent->left = node; + node->parent = parent; + } else { // put at the right + parent->right = node; + node->parent = parent; + } + if (parent->color == RED) // two consecutive RED nodes, must rebalance + db_rebalance(node, &db->ht[hash]); + } + } + // put key and data in the node + if (db->options&DB_OPT_DUP_KEY) { + node->key = db_dup_key(db, key); + if (db->options&DB_OPT_RELEASE_KEY) + db->release(key, data, DB_RELEASE_KEY); + } else { + node->key = key; + } + node->data = data; + db_free_unlock(db); + return old_data; +} + +/** + * Remove an entry from the database. + * Returns the data of the entry. + * NOTE: The key (of the database) is released in {@link #db_free_add(Database,DBNode,DBNode *)}. + * @param self Interface of the database + * @param key Key that identifies the entry + * @return The data of the entry or NULL if not found + * @protected + * @see common\db.h#DBKey + * @see common\db.h#DBInterface + * @see #db_free_add(Database,DBNode,DBNode *) + * @see common\db.h\DBInterface#remove(DBInterface,DBKey) + */ +static void *db_obj_remove(DBInterface self, DBKey key) +{ + Database db = (Database)self; + void *data = NULL; + DBNode node; + unsigned int hash; + int c = 0; + +#ifdef DB_ENABLE_STATS + if (stats.db_remove != (unsigned int)~0) stats.db_remove++; +#endif /* DB_ENABLE_STATS */ + if (db == NULL) return NULL; // nullpo candidate + if (db->global_lock) { + ShowError("db_remove: Database is being destroyed. Aborting entry deletion.\n" + "Database allocated at %s:%d\n", + db->alloc_file, db->alloc_line); + return NULL; // nullpo candidate + } + if (!(db->options&DB_OPT_ALLOW_NULL_KEY) && db_is_key_null(db->type, key)) { + ShowError("db_remove: Attempted to use non-allowed NULL key for db allocated at %s:%d\n",db->alloc_file, db->alloc_line); + return NULL; // nullpo candidate + } + + db_free_lock(db); + hash = db->hash(key, db->maxlen)%HASH_SIZE; + for(node = db->ht[hash]; node; ){ + c = db->cmp(key, node->key, db->maxlen); + if (c == 0) { + if (!(node->deleted)) { + data = node->data; + db->release(node->key, node->data, DB_RELEASE_DATA); + db_free_add(db, node, &db->ht[hash]); + } + break; + } + if (c < 0) + node = node->left; + else + node = node->right; + } + db_free_unlock(db); + return data; +} + +/** + * Apply func 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 args Extra arguments for func + * @return Sum of the values returned by func + * @protected + * @see common\db.h#DBInterface + * @see common\db.h#DBApply(DBKey,void *,va_list) + * @see common\db.h\DBInterface#vforeach(DBInterface,DBApply,va_list) + */ +static int db_obj_vforeach(DBInterface self, DBApply func, va_list args) +{ + Database db = (Database)self; + unsigned int i; + int sum = 0; + DBNode node; + DBNode parent; + +#ifdef DB_ENABLE_STATS + if (stats.db_vforeach != (unsigned int)~0) stats.db_vforeach++; +#endif /* DB_ENABLE_STATS */ + if (db == NULL) return 0; // nullpo candidate + if (func == NULL) { + ShowError("db_foreach: Passed function is NULL for db allocated at %s:%d\n",db->alloc_file, db->alloc_line); + return 0; // nullpo candidate + } + + db_free_lock(db); + for (i = 0; i < HASH_SIZE; i++) { + // Apply func in the order: current node, left node, right node + node = db->ht[i]; + while (node) { + parent = node->parent; + if (!(node->deleted)) + sum += func(node->key, node->data, args); + if (node->left) { + node = node->left; + continue; + } + if (node->right) { + node = node->right; + continue; + } + while (node) { + parent = node->parent; + if (parent && parent->right && parent->left == node) { + node = parent->right; + break; + } + node = parent; + } + } + } + db_free_unlock(db); + return sum; +} + +/** + * Just calls {@link common\db.h\DBInterface#vforeach(DBInterface,DBApply,va_list)}. + * Apply func 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 ... Extra arguments for func + * @return Sum of the values returned by func + * @protected + * @see common\db.h#DBInterface + * @see common\db.h#DBApply(DBKey,void *,va_list) + * @see common\db.h\DBInterface#vforeach(DBInterface,DBApply,va_list) + * @see common\db.h\DBInterface#foreach(DBInterface,DBApply,...) + */ +static int db_obj_foreach(DBInterface self, DBApply func, ...) +{ + va_list args; + int ret; + +#ifdef DB_ENABLE_STATS + if (stats.db_foreach != (unsigned int)~0) stats.db_foreach++; +#endif /* DB_ENABLE_STATS */ + if (self == NULL) return 0; // nullpo candidate + + va_start(args, func); + ret = self->vforeach(self, func, args); + va_end(args); + return ret; +} + +/** + * Removes all entries from the database. + * Before deleting an entry, func is applyed to it. + * Releases the key and the data. + * Returns the sum of values returned by func, if it exists. + * @param self Interface of the database + * @param func Function to be applyed to every entry before deleting + * @param args Extra arguments for func + * @return Sum of values returned by func + * @protected + * @see common\db.h#DBApply(DBKey,void *,va_list) + * @see common\db.h#DBInterface + * @see common\db.h\DBInterface#vclear(DBInterface,DBApply,va_list) + */ +static int db_obj_vclear(DBInterface self, DBApply func, va_list args) +{ + Database db = (Database)self; + int sum = 0; + unsigned int i; + DBNode node; + DBNode parent; + +#ifdef DB_ENABLE_STATS + if (stats.db_vclear != (unsigned int)~0) stats.db_vclear++; +#endif /* DB_ENABLE_STATS */ + if (db == NULL) return 0; // nullpo candidate + + db_free_lock(db); + for (i = 0; i < HASH_SIZE; i++) { + // Apply the func and delete in the order: left tree, right tree, current node + node = db->ht[i]; + db->ht[i] = NULL; + while (node) { + parent = node->parent; + if (node->left) { + node = node->left; + continue; + } + if (node->right) { + node = node->right; + continue; + } + if (node->deleted) { + db_dup_key_free(db, node->key); + } else { + if (func) + sum += func(node->key, node->data, args); + db->release(node->key, node->data, DB_RELEASE_BOTH); + node->deleted = 1; + } +#ifdef DB_ENABLE_STATS + if (stats.db_node_free != (unsigned int)~0) stats.db_node_free++; +#endif /* DB_ENABLE_STATS */ + ers_free(db->nodes, node); + if (parent) { + if (parent->left == node) + parent->left = NULL; + else + parent->right = NULL; + } + node = parent; + } + db->ht[i] = NULL; + } + db->free_count = 0; + db->item_count = 0; + db_free_unlock(db); + return sum; +} + +/** + * Just calls {@link common\db.h\DBInterface#vclear(DBInterface,DBApply,va_list)}. + * Removes all entries from the database. + * Before deleting an entry, func is applyed 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 + * a database entry will give an error and be aborted (except for clearing). + * @param self Interface of the database + * @param func Function to be applyed to every entry before deleting + * @param ... Extra arguments for func + * @return Sum of values returned by func + * @protected + * @see common\db.h#DBApply(DBKey,void *,va_list) + * @see common\db.h#DBInterface + * @see common\db.h\DBInterface#vclear(DBInterface,DBApply,va_list) + * @see common\db.h\DBInterface#clear(DBInterface,DBApply,...) + */ +static int db_obj_clear(DBInterface self, DBApply func, ...) +{ + va_list args; + int ret; + +#ifdef DB_ENABLE_STATS + if (stats.db_clear != (unsigned int)~0) stats.db_clear++; +#endif /* DB_ENABLE_STATS */ + if (self == NULL) return 0; // nullpo candidate + + va_start(args, func); + ret = self->vclear(self, func, args); + va_end(args); + return ret; +} + +/** + * Finalize the database, feeing all the memory it uses. + * Before deleting an entry, func is applyed 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 + * a database entry will give an error and be aborted (except for clearing). + * @param self Interface of the database + * @param func Function to be applyed to every entry before deleting + * @param args Extra arguments for func + * @return Sum of values returned by func + * @protected + * @see common\db.h#DBApply(DBKey,void *,va_list) + * @see common\db.h#DBInterface + * @see common\db.h\DBInterface#vdestroy(DBInterface,DBApply,va_list) + */ +static int db_obj_vdestroy(DBInterface self, DBApply func, va_list args) +{ + Database db = (Database)self; + int sum; + +#ifdef DB_ENABLE_STATS + if (stats.db_vdestroy != (unsigned int)~0) stats.db_vdestroy++; +#endif /* DB_ENABLE_STATS */ + if (db == NULL) return 0; // nullpo candidate + if (db->global_lock) { + ShowError("db_vdestroy: Database is already locked for destruction. Aborting second database destruction.\n" + "Database allocated at %s:%d\n", + db->alloc_file, db->alloc_line); + return 0; + } + if (db->free_lock) + ShowWarning("db_vdestroy: Database is still in use, %u lock(s) left. Continuing database destruction.\n" + "Database allocated at %s:%d\n", + db->alloc_file, db->alloc_line, db->free_lock); + +#ifdef DB_ENABLE_STATS + switch (db->type) { + case DB_INT: + stats.db_int_destroy++; + break; + case DB_UINT: + stats.db_uint_destroy++; + break; + case DB_STRING: + stats.db_string_destroy++; + break; + case DB_ISTRING: + stats.db_istring_destroy++; + break; + } +#endif /* DB_ENABLE_STATS */ + db_free_lock(db); + db->global_lock = 1; + sum = self->vclear(self, func, args); + aFree(db->free_list); + db->free_list = NULL; + db->free_max = 0; + ers_destroy(db->nodes); + db_free_unlock(db); + aFree(db); + return sum; +} + +/** + * Just calls {@link common\db.h\DBInterface#db_vdestroy(DBInterface,DBApply,va_list)}. + * Finalize the database, feeing all the memory it uses. + * Before deleting an entry, func is applyed 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 + * a database entry will give an error and be aborted. + * @param self Interface of the database + * @param func Function to be applyed to every entry before deleting + * @param ... Extra arguments for func + * @return Sum of values returned by func + * @protected + * @see common\db.h#DBApply(DBKey,void *,va_list) + * @see common\db.h#DBInterface + * @see common\db.h\DBInterface#vdestroy(DBInterface,DBApply,va_list) + * @see common\db.h\DBInterface#destroy(DBInterface,DBApply,...) + */ +static int db_obj_destroy(DBInterface self, DBApply func, ...) +{ + va_list args; + int ret; + +#ifdef DB_ENABLE_STATS + if (stats.db_destroy != (unsigned int)~0) stats.db_destroy++; +#endif /* DB_ENABLE_STATS */ + if (self == NULL) return 0; // nullpo candidate + + va_start(args, func); + ret = self->vdestroy(self, func, args); + va_end(args); + return ret; +} + +/** + * Return the size of the database (number of items in the database). + * @param self Interface of the database + * @return Size of the database + * @protected + * @see common\db.h#DBInterface + * @see Database#item_count + * @see common\db.h\DBInterface#size(DBInterface) + */ +static unsigned int db_obj_size(DBInterface self) +{ + Database db = (Database)self; + unsigned int item_count; + +#ifdef DB_ENABLE_STATS + if (stats.db_size != (unsigned int)~0) stats.db_size++; +#endif /* DB_ENABLE_STATS */ + if (db == NULL) return 0; // nullpo candidate + + db_free_lock(db); + item_count = db->item_count; + db_free_unlock(db); + + return item_count; +} + +/** + * Return the type of database. + * @param self Interface of the database + * @return Type of the database + * @protected + * @see common\db.h#DBType + * @see common\db.h#DBInterface + * @see Database#type + * @see common\db.h\DBInterface#type(DBInterface) + */ +static DBType db_obj_type(DBInterface self) +{ + Database db = (Database)self; + DBType type; + +#ifdef DB_ENABLE_STATS + if (stats.db_type != (unsigned int)~0) stats.db_type++; +#endif /* DB_ENABLE_STATS */ + if (db == NULL) return -1; // nullpo candidate - TODO what should this return? + + db_free_lock(db); + type = db->type; + db_free_unlock(db); + + return type; +} + +/** + * Return the options of the database. + * @param self Interface of the database + * @return Options of the database + * @protected + * @see common\db.h#DBOptions + * @see common\db.h#DBInterface + * @see Database#options + * @see common\db.h\DBInterface#options(DBInterface) + */ +static DBOptions db_obj_options(DBInterface self) +{ + Database db = (Database)self; + DBOptions options; + +#ifdef DB_ENABLE_STATS + if (stats.db_options != (unsigned int)~0) stats.db_options++; +#endif /* DB_ENABLE_STATS */ + if (db == NULL) return DB_OPT_BASE; // nullpo candidate - TODO what should this return? + + db_free_lock(db); + options = db->options; + db_free_unlock(db); + + return options; +} + +/*****************************************************************************\ + * (5) Section with public functions. * + * db_fix_options - Apply database type restrictions to the options. * + * 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_alloc - Allocate a new database. * + * db_i2key - Manual cast from 'int' to 'DBKey'. * + * db_ui2key - Manual cast from 'unsigned int' to 'DBKey'. * + * db_str2key - Manual cast from 'unsigned char *' to 'DBKey'. * + * db_init - Initialize the database system. * + * db_final - Finalize the database system. * +\*****************************************************************************/ + +/** + * Returns the fixed options according to the database type. + * Sets required options and unsets unsupported options. + * For numeric databases DB_OPT_DUP_KEY and DB_OPT_RELEASE_KEY are unset. + * @param type Type of the database + * @param options Original options of the database + * @return Fixed options of the database + * @private + * @see common\db.h#DBType + * @see common\db.h#DBOptions + * @see #db_default_release(DBType,DBOptions) + * @see #db_alloc(const char *,int,DBType,DBOptions,unsigned short) + * @see common\db.h#db_fix_options(DBType,DBOptions) + */ +DBOptions db_fix_options(DBType type, DBOptions options) +{ +#ifdef DB_ENABLE_STATS + if (stats.db_fix_options != (unsigned int)~0) stats.db_fix_options++; +#endif /* DB_ENABLE_STATS */ + switch (type) { + case DB_INT: + case DB_UINT: // Numeric database, do nothing with the keys + return options&~(DB_OPT_DUP_KEY|DB_OPT_RELEASE_KEY); + + default: + ShowError("db_fix_options: Unknown database type %u with options %x\n", type, options); + case DB_STRING: + case DB_ISTRING: // String databases, no fix required + return options; + } +} + +/** + * Returns the default comparator for the specified type of database. + * @param type Type of database + * @return Comparator for the type of database or NULL if unknown database + * @public + * @see common\db.h#DBType + * @see #db_int_cmp(DBKey,DBKey,unsigned short) + * @see #db_uint_cmp(DBKey,DBKey,unsigned short) + * @see #db_string_cmp(DBKey,DBKey,unsigned short) + * @see #db_istring_cmp(DBKey,DBKey,unsigned short) + * @see common\db.h#db_default_cmp(DBType) + */ +DBComparator db_default_cmp(DBType type) +{ +#ifdef DB_ENABLE_STATS + if (stats.db_default_cmp != (unsigned int)~0) stats.db_default_cmp++; +#endif /* DB_ENABLE_STATS */ + switch (type) { + case DB_INT: return db_int_cmp; + case DB_UINT: return db_uint_cmp; + case DB_STRING: return db_string_cmp; + case DB_ISTRING: return db_istring_cmp; + default: + ShowError("db_default_cmp: Unknown database type %u\n", type); + return NULL; + } +} + +/** + * Returns the default hasher for the specified type of database. + * @param type Type of database + * @return Hasher of the type of database or NULL if unknown database + * @public + * @see common\db.h#DBType + * @see #db_int_hash(DBKey,unsigned short) + * @see #db_uint_hash(DBKey,unsigned short) + * @see #db_string_hash(DBKey,unsigned short) + * @see #db_istring_hash(DBKey,unsigned short) + * @see common\db.h#db_default_hash(DBType) + */ +DBHasher db_default_hash(DBType type) +{ +#ifdef DB_ENABLE_STATS + if (stats.db_default_hash != (unsigned int)~0) stats.db_default_hash++; +#endif /* DB_ENABLE_STATS */ + switch (type) { + case DB_INT: return db_int_hash; + case DB_UINT: return db_uint_hash; + case DB_STRING: return db_string_hash; + case DB_ISTRING: return db_istring_hash; + default: + ShowError("db_default_hash: Unknown database type %u\n", type); + return NULL; + } +} + +/** + * 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. + * @param type Type of database + * @param options Options of the database + * @return Default releaser for the type of database with the specified options + * @public + * @see common\db.h#DBType + * @see common\db.h#DBOptions + * @see common\db.h#DBReleaser + * @see #db_release_nothing(DBKey,void *,DBRelease) + * @see #db_release_key(DBKey,void *,DBRelease) + * @see #db_release_data(DBKey,void *,DBRelease) + * @see #db_release_both(DBKey,void *,DBRelease) + * @see #db_custom_release(DBRelease) + * @see common\db.h#db_default_release(DBType,DBOptions) + */ +DBReleaser db_default_release(DBType type, DBOptions options) +{ +#ifdef DB_ENABLE_STATS + if (stats.db_default_release != (unsigned int)~0) stats.db_default_release++; +#endif /* DB_ENABLE_STATS */ + options = db_fix_options(type, options); + if (options&DB_OPT_RELEASE_DATA) { // Release data, what about the key? + if (options&(DB_OPT_DUP_KEY|DB_OPT_RELEASE_KEY)) + return db_release_both; // Release both key and data + return db_release_data; // Only release data + } + if (options&(DB_OPT_DUP_KEY|DB_OPT_RELEASE_KEY)) + return db_release_key; // Only release key + return db_release_nothing; // Release nothing +} + +/** + * Returns the releaser that releases the specified release options. + * @param which Options that specified what the releaser releases + * @return Releaser for the specified release options + * @public + * @see common\db.h#DBRelease + * @see common\db.h#DBReleaser + * @see #db_release_nothing(DBKey,void *,DBRelease) + * @see #db_release_key(DBKey,void *,DBRelease) + * @see #db_release_data(DBKey,void *,DBRelease) + * @see #db_release_both(DBKey,void *,DBRelease) + * @see #db_default_release(DBType,DBOptions) + * @see common\db.h#db_custom_release(DBRelease) + */ +DBReleaser db_custom_release(DBRelease which) +{ +#ifdef DB_ENABLE_STATS + if (stats.db_custom_release != (unsigned int)~0) stats.db_custom_release++; +#endif /* DB_ENABLE_STATS */ + switch (which) { + case DB_RELEASE_NOTHING: return db_release_nothing; + case DB_RELEASE_KEY: return db_release_key; + case DB_RELEASE_DATA: return db_release_data; + case DB_RELEASE_BOTH: return db_release_both; + default: + ShowError("db_custom_release: Unknown release options %u\n", which); + return NULL; + } +} + +/** + * Allocate a new database of the specified type. + * NOTE: the options are fixed by {@link #db_fix_options(DBType,DBOptions)} + * before creating the database. + * @param file File where the database is being allocated + * @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 + * databases + * @return The interface of the database + * @public + * @see common\db.h#DBType + * @see common\db.h#DBInterface + * @see #Database + * @see #db_fix_options(DBType,DBOptions) + * @see common\db.h#db_alloc(const char *,int,DBType,unsigned short) + */ +DBInterface db_alloc(const char *file, int line, DBType type, DBOptions options, unsigned short maxlen) +{ + Database db; + unsigned int i; + +#ifdef DB_ENABLE_STATS + if (stats.db_alloc != (unsigned int)~0) stats.db_alloc++; + switch (type) { + case DB_INT: + stats.db_int_alloc++; + break; + case DB_UINT: + stats.db_uint_alloc++; + break; + case DB_STRING: + stats.db_string_alloc++; + break; + case DB_ISTRING: + stats.db_istring_alloc++; + break; + } +#endif /* DB_ENABLE_STATS */ + CREATE(db, struct db, 1); + + options = db_fix_options(type, options); + /* Interface of the database */ + db->dbi.get = db_obj_get; + db->dbi.getall = db_obj_getall; + db->dbi.vgetall = db_obj_vgetall; + db->dbi.ensure = db_obj_ensure; + db->dbi.vensure = db_obj_vensure; + db->dbi.put = db_obj_put; + db->dbi.remove = db_obj_remove; + db->dbi.foreach = db_obj_foreach; + db->dbi.vforeach = db_obj_vforeach; + db->dbi.clear = db_obj_clear; + db->dbi.vclear = db_obj_vclear; + db->dbi.destroy = db_obj_destroy; + db->dbi.vdestroy = db_obj_vdestroy; + db->dbi.size = db_obj_size; + db->dbi.type = db_obj_type; + db->dbi.options = db_obj_options; + /* File and line of allocation */ + db->alloc_file = file; + db->alloc_line = line; + /* Lock system */ + db->free_list = NULL; + db->free_count = 0; + db->free_max = 0; + db->free_lock = 0; + /* Other */ + db->nodes = ers_new((uint32)sizeof(struct dbn)); + db->cmp = db_default_cmp(type); + db->hash = db_default_hash(type); + db->release = db_default_release(type, options); + for (i = 0; i < HASH_SIZE; i++) + db->ht[i] = NULL; + db->type = type; + db->options = options; + db->item_count = 0; + db->maxlen = maxlen; + db->global_lock = 0; + + return &db->dbi; +} + +#ifdef DB_MANUAL_CAST_TO_UNION +/** + * Manual cast from 'int' to the union DBKey. + * Created for compilers that don't support casting to unions. + * @param key Key to be casted + * @return The key as a DBKey union + * @public + * @see common\db.h#DB_MANUAL_CAST_TO_UNION + * @see #db_ui2key(unsigned int) + * @see #db_str2key(unsigned char *) + * @see common\db.h#db_i2key(int) + */ +DBKey db_i2key(int key) +{ + DBKey ret; + +#ifdef DB_ENABLE_STATS + if (stats.db_i2key != (unsigned int)~0) stats.db_i2key++; +#endif /* DB_ENABLE_STATS */ + ret.i = key; + return ret; +} + +/** + * Manual cast from 'unsigned int' to the union DBKey. + * Created for compilers that don't support casting to unions. + * @param key Key to be casted + * @return The key as a DBKey union + * @public + * @see common\db.h#DB_MANUAL_CAST_TO_UNION + * @see #db_i2key(int) + * @see #db_str2key(unsigned char *) + * @see common\db.h#db_ui2key(unsigned int) + */ +DBKey db_ui2key(unsigned int key) +{ + DBKey ret; + +#ifdef DB_ENABLE_STATS + if (stats.db_ui2key != (unsigned int)~0) stats.db_ui2key++; +#endif /* DB_ENABLE_STATS */ + ret.ui = key; + return ret; +} + +/** + * Manual cast from 'unsigned char *' to the union DBKey. + * Created for compilers that don't support casting to unions. + * @param key Key to be casted + * @return The key as a DBKey union + * @public + * @see common\db.h#DB_MANUAL_CAST_TO_UNION + * @see #db_i2key(int) + * @see #db_ui2key(unsigned int) + * @see common\db.h#db_str2key(unsigned char *) + */ +DBKey db_str2key(unsigned char *key) +{ + DBKey ret; + +#ifdef DB_ENABLE_STATS + if (stats.db_str2key != (unsigned int)~0) stats.db_str2key++; +#endif /* DB_ENABLE_STATS */ + ret.str = key; + return ret; +} +#endif /* DB_MANUAL_CAST_TO_UNION */ + +/** + * Initialize the database system. + * @public + * @see #db_final(void) + * @see common\db.h#db_init(void) + */ +void db_init(void) +{ +#ifdef DB_ENABLE_STATS + if (stats.db_init != (unsigned int)~0) stats.db_init++; +#endif /* DB_ENABLE_STATS */ +} + +/** + * Finalize the database system. + * Frees the memory used by the block reusage system. + * @public + * @see common\db.h#DB_FINAL_NODE_CHECK + * @see #db_init(void) + * @see common\db.h#db_final(void) + */ +void db_final(void) +{ +#ifdef DB_ENABLE_STATS + if (stats.db_final != (unsigned int)~0) + stats.db_final++; + ShowInfo(CL_WHITE"Database nodes"CL_RESET":\n" + "allocated %u, freed %u\n", + stats.db_node_alloc, stats.db_node_free); + ShowInfo(CL_WHITE"Database types"CL_RESET":\n" + "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", + 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); + 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" + "db_is_key_null %10u,\n" + "db_dup_key %10u, db_dup_key_free %10u,\n" + "db_free_add %10u, db_free_remove %10u,\n" + "db_free_lock %10u, db_free_unlock %10u,\n" + "db_int_cmp %10u, db_uint_cmp %10u,\n" + "db_string_cmp %10u, db_istring_cmp %10u,\n" + "db_int_hash %10u, db_uint_hash %10u,\n" + "db_string_hash %10u, db_istring_hash %10u,\n" + "db_release_nothing %10u, db_release_key %10u,\n" + "db_release_data %10u, db_release_both %10u,\n" + "db_get %10u,\n" + "db_getall %10u, db_vgetall %10u,\n" + "db_ensure %10u, db_vensure %10u,\n" + "db_put %10u, db_remove %10u,\n" + "db_foreach %10u, db_vforeach %10u,\n" + "db_clear %10u, db_vclear %10u,\n" + "db_destroy %10u, db_vdestroy %10u,\n" + "db_size %10u, db_type %10u,\n" + "db_options %10u, db_fix_options %10u,\n" + "db_default_cmp %10u, db_default_hash %10u,\n" + "db_default_release %10u, db_custom_release %10u,\n" + "db_alloc %10u, db_i2key %10u,\n" + "db_ui2key %10u, db_str2key %10u,\n" + "db_init %10u, db_final %10u\n", + stats.db_rotate_left, stats.db_rotate_right, + stats.db_rebalance, stats.db_rebalance_erase, + stats.db_is_key_null, + stats.db_dup_key, stats.db_dup_key_free, + stats.db_free_add, stats.db_free_remove, + stats.db_free_lock, stats.db_free_unlock, + stats.db_int_cmp, stats.db_uint_cmp, + stats.db_string_cmp, stats.db_istring_cmp, + stats.db_int_hash, stats.db_uint_hash, + stats.db_string_hash, stats.db_istring_hash, + stats.db_release_nothing, stats.db_release_key, + stats.db_release_data, stats.db_release_both, + stats.db_get, + stats.db_getall, stats.db_vgetall, + stats.db_ensure, stats.db_vensure, + stats.db_put, stats.db_remove, + stats.db_foreach, stats.db_vforeach, + stats.db_clear, stats.db_vclear, + stats.db_destroy, stats.db_vdestroy, + stats.db_size, stats.db_type, + stats.db_options, stats.db_fix_options, + stats.db_default_cmp, stats.db_default_hash, + stats.db_default_release, stats.db_custom_release, + stats.db_alloc, stats.db_i2key, + stats.db_ui2key, stats.db_str2key, + stats.db_init, stats.db_final); +#endif /* DB_ENABLE_STATS */ +} + +// Link DB System - jAthena +void linkdb_insert( struct linkdb_node** head, void *key, void* data) { + struct linkdb_node *node; + if( head == NULL ) return ; + node = aMalloc( sizeof(struct linkdb_node) ); + if( *head == NULL ) { + // first node + *head = node; + node->prev = NULL; + node->next = NULL; + } else { + // link nodes + node->next = *head; + node->prev = (*head)->prev; + (*head)->prev = node; + (*head) = node; + } + node->key = key; + node->data = data; +} + +void* linkdb_search( struct linkdb_node** head, void *key) { + int n = 0; + struct linkdb_node *node; + if( head == NULL ) return NULL; + node = *head; + while( node ) { + if( node->key == key ) { + if( node->prev && n > 5 ) { + // 処理効率改善の為にheadに移動させる + if(node->prev) node->prev->next = node->next; + if(node->next) node->next->prev = node->prev; + node->next = *head; + node->prev = (*head)->prev; + (*head)->prev = node; + (*head) = node; + } + return node->data; + } + node = node->next; + n++; + } + return NULL; +} + +void* linkdb_erase( struct linkdb_node** head, void *key) { + struct linkdb_node *node; + if( head == NULL ) return NULL; + node = *head; + while( node ) { + if( node->key == key ) { + void *data = node->data; + if( node->prev == NULL ) + *head = node->next; + else + node->prev->next = node->next; + if( node->next ) + node->next->prev = node->prev; + aFree( node ); + return data; + } + node = node->next; + } + return NULL; +} + +void linkdb_replace( struct linkdb_node** head, void *key, void *data ) { + int n = 0; + struct linkdb_node *node; + if( head == NULL ) return ; + node = *head; + while( node ) { + if( node->key == key ) { + if( node->prev && n > 5 ) { + // 処理効率改善の為にheadに移動させる + if(node->prev) node->prev->next = node->next; + if(node->next) node->next->prev = node->prev; + node->next = *head; + node->prev = (*head)->prev; + (*head)->prev = node; + (*head) = node; + } + node->data = data; + return ; + } + node = node->next; + n++; + } + // 見つからないので挿入 + linkdb_insert( head, key, data ); +} + +void linkdb_final( struct linkdb_node** head ) { + struct linkdb_node *node, *node2; + if( head == NULL ) return ; + node = *head; + while( node ) { + node2 = node->next; + aFree( node ); + node = node2; + } + *head = NULL; +} + -- cgit v1.2.3-60-g2f50