summaryrefslogtreecommitdiff
path: root/src/common/db.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/common/db.c')
-rw-r--r--src/common/db.c4896
1 files changed, 2448 insertions, 2448 deletions
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. *
- * *
- * <B>Properties of the RED-BLACK trees being used:</B> *
- * 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 <code>n</code> node in a RED-BLACK tree has the property that its *
- * height is <code>O(lg(n))</code>. *
- * Another important property is that after adding a node to a RED-BLACK *
- * tree, the tree can be readjusted in <code>O(lg(n))</code> time. *
- * Similarly, after deleting a node from a RED-BLACK tree, the tree can be *
- * readjusted in <code>O(lg(n))</code> time. *
- * {@link http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic18/} *
- * *
- * <B>How to add new database types:</B> *
- * 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 <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-#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.
- * <code>maxlen</code> 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.
- * <code>maxlen</code> 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.
- * <code>maxlen</code> 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.
- * <code>maxlen</code> 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 <code>match</code>.
- * It puts a maximum of <code>max</code> entries into <code>buf</code>.
- * If <code>buf</code> is NULL, it only counts the matches.
- * Returns the number of entries that matched.
- * NOTE: if the value returned is greater than <code>max</code>, only the
- * first <code>max</code> entries found are put into the buffer.
- * @param self Interface of the database
- * @param buf Buffer to put the data of the matched entries
- * @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 <code>match</code>.
- * It puts a maximum of <code>max</code> entries into <code>buf</code>.
- * If <code>buf</code> is NULL, it only counts the matches.
- * Returns the number of entries that matched.
- * NOTE: if the value returned is greater than <code>max</code>, only the
- * first <code>max</code> entries found are put into the buffer.
- * @param self Interface of the database
- * @param buf Buffer to put the data of the matched entries
- * @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
- * <code>create</code>.
- * @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
- * <code>create</code>.
- * @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 <code>func</code> to every entry in the database.
- * Returns the sum of values returned by func.
- * @param self Interface of the database
- * @param func Function to be applyed
- * @param 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 <code>func</code> to every entry in the database.
- * Returns the sum of values returned by func.
- * @param self Interface of the database
- * @param func Function to be applyed
- * @param ... 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. *
+ * *
+ * <B>Properties of the RED-BLACK trees being used:</B> *
+ * 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 <code>n</code> node in a RED-BLACK tree has the property that its *
+ * height is <code>O(lg(n))</code>. *
+ * Another important property is that after adding a node to a RED-BLACK *
+ * tree, the tree can be readjusted in <code>O(lg(n))</code> time. *
+ * Similarly, after deleting a node from a RED-BLACK tree, the tree can be *
+ * readjusted in <code>O(lg(n))</code> time. *
+ * {@link http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic18/} *
+ * *
+ * <B>How to add new database types:</B> *
+ * 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 <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#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.
+ * <code>maxlen</code> 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.
+ * <code>maxlen</code> 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.
+ * <code>maxlen</code> 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.
+ * <code>maxlen</code> 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 <code>match</code>.
+ * It puts a maximum of <code>max</code> entries into <code>buf</code>.
+ * If <code>buf</code> is NULL, it only counts the matches.
+ * Returns the number of entries that matched.
+ * NOTE: if the value returned is greater than <code>max</code>, only the
+ * first <code>max</code> entries found are put into the buffer.
+ * @param self Interface of the database
+ * @param buf Buffer to put the data of the matched entries
+ * @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 <code>match</code>.
+ * It puts a maximum of <code>max</code> entries into <code>buf</code>.
+ * If <code>buf</code> is NULL, it only counts the matches.
+ * Returns the number of entries that matched.
+ * NOTE: if the value returned is greater than <code>max</code>, only the
+ * first <code>max</code> entries found are put into the buffer.
+ * @param self Interface of the database
+ * @param buf Buffer to put the data of the matched entries
+ * @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
+ * <code>create</code>.
+ * @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
+ * <code>create</code>.
+ * @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 <code>func</code> to every entry in the database.
+ * Returns the sum of values returned by func.
+ * @param self Interface of the database
+ * @param func Function to be applyed
+ * @param 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 <code>func</code> to every entry in the database.
+ * Returns the sum of values returned by func.
+ * @param self Interface of the database
+ * @param func Function to be applyed
+ * @param ... 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;
+}
+