diff options
Diffstat (limited to 'src/common/db.c')
| -rw-r--r-- | src/common/db.c | 3246 |
1 files changed, 1634 insertions, 1612 deletions
diff --git a/src/common/db.c b/src/common/db.c index 204c6d2ea..c5db21a02 100644 --- a/src/common/db.c +++ b/src/common/db.c @@ -88,7 +88,7 @@ \*****************************************************************************/ /** - * If defined statistics about database nodes, database creating/destruction + * 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). @@ -112,8 +112,8 @@ * @see struct dbn */ typedef enum node_color { - RED, - BLACK + RED, + BLACK } node_color; /** @@ -129,16 +129,16 @@ typedef enum node_color { * @see DBMap_impl#ht */ typedef struct dbn { - // Tree structure - struct dbn *parent; - struct dbn *left; - struct dbn *right; - // Node data - DBKey key; - DBData data; - // Other - node_color color; - unsigned deleted : 1; + // Tree structure + struct dbn *parent; + struct dbn *left; + struct dbn *right; + // Node data + DBKey key; + DBData data; + // Other + node_color color; + unsigned deleted : 1; } *DBNode; /** @@ -149,8 +149,8 @@ typedef struct dbn { * @see DBMap_impl#free_list */ struct db_free { - DBNode node; - DBNode *root; + DBNode node; + DBNode *root; }; /** @@ -176,28 +176,28 @@ struct db_free { * @see #db_alloc(const char*,int,DBType,DBOptions,unsigned short) */ typedef struct DBMap_impl { - // Database interface - struct DBMap vtable; - // 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 - ERS nodes; - DBComparator cmp; - DBHasher hash; - DBReleaser release; - DBNode ht[HASH_SIZE]; - DBNode cache; - DBType type; - DBOptions options; - uint32 item_count; - unsigned short maxlen; - unsigned global_lock : 1; + // Database interface + struct DBMap vtable; + // 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 + ERS nodes; + DBComparator cmp; + DBHasher hash; + DBReleaser release; + DBNode ht[HASH_SIZE]; + DBNode cache; + DBType type; + DBOptions options; + uint32 item_count; + unsigned short maxlen; + unsigned global_lock : 1; } DBMap_impl; /** @@ -212,11 +212,11 @@ typedef struct DBMap_impl { * @see #DBNode */ typedef struct DBIterator_impl { - // Iterator interface - struct DBIterator vtable; - DBMap_impl* db; - int ht_index; - DBNode node; + // Iterator interface + struct DBIterator vtable; + DBMap_impl *db; + int ht_index; + DBNode node; } DBIterator_impl; #if defined(DB_ENABLE_STATS) @@ -227,92 +227,92 @@ typedef struct DBIterator_impl { * @see #stats */ static struct db_stats { - // Node alloc/free - uint32 db_node_alloc; - uint32 db_node_free; - // Database creating/destruction counters - uint32 db_int_alloc; - uint32 db_uint_alloc; - uint32 db_string_alloc; - uint32 db_istring_alloc; - uint32 db_int_destroy; - uint32 db_uint_destroy; - uint32 db_string_destroy; - uint32 db_istring_destroy; - // Function usage counters - uint32 db_rotate_left; - uint32 db_rotate_right; - uint32 db_rebalance; - uint32 db_rebalance_erase; - uint32 db_is_key_null; - uint32 db_dup_key; - uint32 db_dup_key_free; - uint32 db_free_add; - uint32 db_free_remove; - uint32 db_free_lock; - uint32 db_free_unlock; - uint32 db_int_cmp; - uint32 db_uint_cmp; - uint32 db_string_cmp; - uint32 db_istring_cmp; - uint32 db_int_hash; - uint32 db_uint_hash; - uint32 db_string_hash; - uint32 db_istring_hash; - uint32 db_release_nothing; - uint32 db_release_key; - uint32 db_release_data; - uint32 db_release_both; - uint32 dbit_first; - uint32 dbit_last; - uint32 dbit_next; - uint32 dbit_prev; - uint32 dbit_exists; - uint32 dbit_remove; - uint32 dbit_destroy; - uint32 db_iterator; - uint32 db_exists; - uint32 db_get; - uint32 db_getall; - uint32 db_vgetall; - uint32 db_ensure; - uint32 db_vensure; - uint32 db_put; - uint32 db_remove; - uint32 db_foreach; - uint32 db_vforeach; - uint32 db_clear; - uint32 db_vclear; - uint32 db_destroy; - uint32 db_vdestroy; - uint32 db_size; - uint32 db_type; - uint32 db_options; - uint32 db_fix_options; - uint32 db_default_cmp; - uint32 db_default_hash; - uint32 db_default_release; - uint32 db_custom_release; - uint32 db_alloc; - uint32 db_i2key; - uint32 db_ui2key; - uint32 db_str2key; - uint32 db_i2data; - uint32 db_ui2data; - uint32 db_ptr2data; - uint32 db_data2i; - uint32 db_data2ui; - uint32 db_data2ptr; - uint32 db_init; - uint32 db_final; + // Node alloc/free + uint32 db_node_alloc; + uint32 db_node_free; + // Database creating/destruction counters + uint32 db_int_alloc; + uint32 db_uint_alloc; + uint32 db_string_alloc; + uint32 db_istring_alloc; + uint32 db_int_destroy; + uint32 db_uint_destroy; + uint32 db_string_destroy; + uint32 db_istring_destroy; + // Function usage counters + uint32 db_rotate_left; + uint32 db_rotate_right; + uint32 db_rebalance; + uint32 db_rebalance_erase; + uint32 db_is_key_null; + uint32 db_dup_key; + uint32 db_dup_key_free; + uint32 db_free_add; + uint32 db_free_remove; + uint32 db_free_lock; + uint32 db_free_unlock; + uint32 db_int_cmp; + uint32 db_uint_cmp; + uint32 db_string_cmp; + uint32 db_istring_cmp; + uint32 db_int_hash; + uint32 db_uint_hash; + uint32 db_string_hash; + uint32 db_istring_hash; + uint32 db_release_nothing; + uint32 db_release_key; + uint32 db_release_data; + uint32 db_release_both; + uint32 dbit_first; + uint32 dbit_last; + uint32 dbit_next; + uint32 dbit_prev; + uint32 dbit_exists; + uint32 dbit_remove; + uint32 dbit_destroy; + uint32 db_iterator; + uint32 db_exists; + uint32 db_get; + uint32 db_getall; + uint32 db_vgetall; + uint32 db_ensure; + uint32 db_vensure; + uint32 db_put; + uint32 db_remove; + uint32 db_foreach; + uint32 db_vforeach; + uint32 db_clear; + uint32 db_vclear; + uint32 db_destroy; + uint32 db_vdestroy; + uint32 db_size; + uint32 db_type; + uint32 db_options; + uint32 db_fix_options; + uint32 db_default_cmp; + uint32 db_default_hash; + uint32 db_default_release; + uint32 db_custom_release; + uint32 db_alloc; + uint32 db_i2key; + uint32 db_ui2key; + uint32 db_str2key; + uint32 db_i2data; + uint32 db_ui2data; + uint32 db_ptr2data; + uint32 db_data2i; + uint32 db_data2ui; + uint32 db_data2ptr; + uint32 db_init; + uint32 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, 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, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0 }; #define DB_COUNTSTAT(token) if (stats. ## token != UINT32_MAX) ++stats. ## token #else /* !defined(DB_ENABLE_STATS) */ @@ -346,25 +346,25 @@ static struct db_stats { */ static void db_rotate_left(DBNode node, DBNode *root) { - DBNode y = node->right; + DBNode y = node->right; - DB_COUNTSTAT(db_rotate_left); - // put the left of y at the right of node - 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; + DB_COUNTSTAT(db_rotate_left); + // 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; } /** @@ -377,25 +377,25 @@ static void db_rotate_left(DBNode node, DBNode *root) */ static void db_rotate_right(DBNode node, DBNode *root) { - DBNode y = node->left; + DBNode y = node->left; - DB_COUNTSTAT(db_rotate_right); - // put the right of y at the left of node - 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; + DB_COUNTSTAT(db_rotate_right); + // 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; } /** @@ -410,55 +410,55 @@ static void db_rotate_right(DBNode node, DBNode *root) */ static void db_rebalance(DBNode node, DBNode *root) { - DBNode y; - - DB_COUNTSTAT(db_rebalance); - // 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 + DBNode y; + + DB_COUNTSTAT(db_rebalance); + // 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 } /** @@ -472,133 +472,133 @@ static void db_rebalance(DBNode node, DBNode *root) */ static void db_rebalance_erase(DBNode node, DBNode *root) { - DBNode y = node; - DBNode x = NULL; - DBNode x_parent = NULL; - DBNode w; - - DB_COUNTSTAT(db_rebalance_erase); - // 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 - { - node_color 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; - } + DBNode y = node; + DBNode x = NULL; + DBNode x_parent = NULL; + DBNode w; + + DB_COUNTSTAT(db_rebalance_erase); + // 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 + { + node_color 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; + } } /** @@ -613,15 +613,15 @@ static void db_rebalance_erase(DBNode node, DBNode *root) */ static int db_is_key_null(DBType type, DBKey key) { - DB_COUNTSTAT(db_is_key_null); - switch (type) { - case DB_STRING: - case DB_ISTRING: - return (key.str == NULL); + DB_COUNTSTAT(db_is_key_null); + switch (type) { + case DB_STRING: + case DB_ISTRING: + return (key.str == NULL); - default: // Not a pointer - return 0; - } + default: // Not a pointer + return 0; + } } /** @@ -635,25 +635,25 @@ static int db_is_key_null(DBType type, DBKey key) * @see #db_obj_put(DBMap*,DBKey,void *) * @see #db_dup_key_free(DBMap_impl*,DBKey) */ -static DBKey db_dup_key(DBMap_impl* db, DBKey key) +static DBKey db_dup_key(DBMap_impl *db, DBKey key) { - char *str; - size_t len; + char *str; + size_t len; - DB_COUNTSTAT(db_dup_key); - switch (db->type) { - case DB_STRING: - case DB_ISTRING: - len = strnlen(key.str, db->maxlen); - str = (char*)aMalloc(len + 1); - memcpy(str, key.str, len); - str[len] = '\0'; - key.str = str; - return key; + DB_COUNTSTAT(db_dup_key); + switch (db->type) { + case DB_STRING: + case DB_ISTRING: + len = strnlen(key.str, db->maxlen); + str = (char *)aMalloc(len + 1); + memcpy(str, key.str, len); + str[len] = '\0'; + key.str = str; + return key; - default: - return key; - } + default: + return key; + } } /** @@ -663,18 +663,18 @@ static DBKey db_dup_key(DBMap_impl* db, DBKey key) * @private * @see #db_dup_key(DBMap_impl*,DBKey) */ -static void db_dup_key_free(DBMap_impl* db, DBKey key) +static void db_dup_key_free(DBMap_impl *db, DBKey key) { - DB_COUNTSTAT(db_dup_key_free); - switch (db->type) { - case DB_STRING: - case DB_ISTRING: - aFree((char*)key.str); - return; + DB_COUNTSTAT(db_dup_key_free); + switch (db->type) { + case DB_STRING: + case DB_ISTRING: + aFree((char *)key.str); + return; - default: - return; - } + default: + return; + } } /** @@ -692,40 +692,40 @@ static void db_dup_key_free(DBMap_impl* db, DBKey key) * @see #db_obj_remove(DBMap*,DBKey) * @see #db_free_remove(DBMap_impl*,DBNode) */ -static void db_free_add(DBMap_impl* db, DBNode node, DBNode *root) -{ - DBKey old_key; - - DB_COUNTSTAT(db_free_add); - 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 sure 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--; +static void db_free_add(DBMap_impl *db, DBNode node, DBNode *root) +{ + DBKey old_key; + + DB_COUNTSTAT(db_free_add); + 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 sure 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--; } /** @@ -741,26 +741,26 @@ static void db_free_add(DBMap_impl* db, DBNode node, DBNode *root) * @see #db_obj_put(DBMap*,DBKey,DBData) * @see #db_free_add(DBMap_impl*,DBNode*,DBNode) */ -static void db_free_remove(DBMap_impl* db, DBNode node) +static void db_free_remove(DBMap_impl *db, DBNode node) { - unsigned int i; + unsigned int i; - DB_COUNTSTAT(db_free_remove); - 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++; + DB_COUNTSTAT(db_free_remove); + 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++; } /** @@ -770,16 +770,16 @@ static void db_free_remove(DBMap_impl* db, DBNode node) * @see DBMap_impl#free_lock * @see #db_unlock(DBMap_impl*) */ -static void db_free_lock(DBMap_impl* db) +static void db_free_lock(DBMap_impl *db) { - DB_COUNTSTAT(db_free_lock); - 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++; + DB_COUNTSTAT(db_free_lock); + 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++; } /** @@ -793,28 +793,28 @@ static void db_free_lock(DBMap_impl* db) * @see #db_free_dbn(DBNode) * @see #db_lock(DBMap_impl*) */ -static void db_free_unlock(DBMap_impl* db) +static void db_free_unlock(DBMap_impl *db) { - unsigned int i; + unsigned int i; - DB_COUNTSTAT(db_free_unlock); - 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 + DB_COUNTSTAT(db_free_unlock); + 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); - DB_COUNTSTAT(db_node_free); - ers_free(db->nodes, db->free_list[i].node); - } - db->free_count = 0; + 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); + DB_COUNTSTAT(db_node_free); + ers_free(db->nodes, db->free_list[i].node); + } + db->free_count = 0; } /*****************************************************************************\ @@ -850,11 +850,11 @@ static void db_free_unlock(DBMap_impl* db) */ static int db_int_cmp(DBKey key1, DBKey key2, unsigned short maxlen) { - (void)maxlen;//not used - DB_COUNTSTAT(db_int_cmp); - if (key1.i < key2.i) return -1; - if (key1.i > key2.i) return 1; - return 0; + (void)maxlen;//not used + DB_COUNTSTAT(db_int_cmp); + if (key1.i < key2.i) return -1; + if (key1.i > key2.i) return 1; + return 0; } /** @@ -872,11 +872,11 @@ static int db_int_cmp(DBKey key1, DBKey key2, unsigned short maxlen) */ static int db_uint_cmp(DBKey key1, DBKey key2, unsigned short maxlen) { - (void)maxlen;//not used - DB_COUNTSTAT(db_uint_cmp); - if (key1.ui < key2.ui) return -1; - if (key1.ui > key2.ui) return 1; - return 0; + (void)maxlen;//not used + DB_COUNTSTAT(db_uint_cmp); + if (key1.ui < key2.ui) return -1; + if (key1.ui > key2.ui) return 1; + return 0; } /** @@ -893,8 +893,8 @@ static int db_uint_cmp(DBKey key1, DBKey key2, unsigned short maxlen) */ static int db_string_cmp(DBKey key1, DBKey key2, unsigned short maxlen) { - DB_COUNTSTAT(db_string_cmp); - return strncmp((const char *)key1.str, (const char *)key2.str, maxlen); + DB_COUNTSTAT(db_string_cmp); + return strncmp((const char *)key1.str, (const char *)key2.str, maxlen); } /** @@ -911,8 +911,8 @@ static int db_string_cmp(DBKey key1, DBKey key2, unsigned short maxlen) */ static int db_istring_cmp(DBKey key1, DBKey key2, unsigned short maxlen) { - DB_COUNTSTAT(db_istring_cmp); - return strncasecmp((const char *)key1.str, (const char *)key2.str, maxlen); + DB_COUNTSTAT(db_istring_cmp); + return strncasecmp((const char *)key1.str, (const char *)key2.str, maxlen); } /** @@ -928,9 +928,9 @@ static int db_istring_cmp(DBKey key1, DBKey key2, unsigned short maxlen) */ static unsigned int db_int_hash(DBKey key, unsigned short maxlen) { - (void)maxlen;//not used - DB_COUNTSTAT(db_int_hash); - return (unsigned int)key.i; + (void)maxlen;//not used + DB_COUNTSTAT(db_int_hash); + return (unsigned int)key.i; } /** @@ -946,9 +946,9 @@ static unsigned int db_int_hash(DBKey key, unsigned short maxlen) */ static unsigned int db_uint_hash(DBKey key, unsigned short maxlen) { - (void)maxlen;//not used - DB_COUNTSTAT(db_uint_hash); - return key.ui; + (void)maxlen;//not used + DB_COUNTSTAT(db_uint_hash); + return key.ui; } /** @@ -962,20 +962,20 @@ static unsigned int db_uint_hash(DBKey key, unsigned short maxlen) */ static unsigned int db_string_hash(DBKey key, unsigned short maxlen) { - const char *k = key.str; - unsigned int hash = 0; - unsigned short i; + const char *k = key.str; + unsigned int hash = 0; + unsigned short i; - DB_COUNTSTAT(db_string_hash); + DB_COUNTSTAT(db_string_hash); - for (i = 0; *k; ++i) { - hash = (hash*33 + ((unsigned char)*k))^(hash>>24); - k++; - if (i == maxlen) - break; - } + for (i = 0; *k; ++i) { + hash = (hash*33 + ((unsigned char)*k))^(hash>>24); + k++; + if (i == maxlen) + break; + } - return hash; + return hash; } /** @@ -988,20 +988,20 @@ static unsigned int db_string_hash(DBKey key, unsigned short maxlen) */ static unsigned int db_istring_hash(DBKey key, unsigned short maxlen) { - const char *k = key.str; - unsigned int hash = 0; - unsigned short i; + const char *k = key.str; + unsigned int hash = 0; + unsigned short i; - DB_COUNTSTAT(db_istring_hash); + DB_COUNTSTAT(db_istring_hash); - for (i = 0; *k; i++) { - hash = (hash*33 + ((unsigned char)TOLOWER(*k)))^(hash>>24); - k++; - if (i == maxlen) - break; - } + for (i = 0; *k; i++) { + hash = (hash*33 + ((unsigned char)TOLOWER(*k)))^(hash>>24); + k++; + if (i == maxlen) + break; + } - return hash; + return hash; } /** @@ -1015,8 +1015,10 @@ static unsigned int db_istring_hash(DBKey key, unsigned short maxlen) */ static void db_release_nothing(DBKey key, DBData data, DBRelease which) { - (void)key;(void)data;(void)which;//not used - DB_COUNTSTAT(db_release_nothing); + (void)key; + (void)data; + (void)which;//not used + DB_COUNTSTAT(db_release_nothing); } /** @@ -1030,9 +1032,9 @@ static void db_release_nothing(DBKey key, DBData data, DBRelease which) */ static void db_release_key(DBKey key, DBData data, DBRelease which) { - (void)data;//not used - DB_COUNTSTAT(db_release_key); - if (which&DB_RELEASE_KEY) aFree((char*)key.str); // needs to be a pointer + (void)data;//not used + DB_COUNTSTAT(db_release_key); + if (which&DB_RELEASE_KEY) aFree((char *)key.str); // needs to be a pointer } /** @@ -1048,9 +1050,9 @@ static void db_release_key(DBKey key, DBData data, DBRelease which) */ static void db_release_data(DBKey key, DBData data, DBRelease which) { - (void)key;//not used - DB_COUNTSTAT(db_release_data); - if (which&DB_RELEASE_DATA && data.type == DB_DATA_PTR) aFree(data.u.ptr); + (void)key;//not used + DB_COUNTSTAT(db_release_data); + if (which&DB_RELEASE_DATA && data.type == DB_DATA_PTR) aFree(data.u.ptr); } /** @@ -1067,9 +1069,9 @@ static void db_release_data(DBKey key, DBData data, DBRelease which) */ static void db_release_both(DBKey key, DBData data, DBRelease which) { - DB_COUNTSTAT(db_release_both); - if (which&DB_RELEASE_KEY) aFree((char*)key.str); // needs to be a pointer - if (which&DB_RELEASE_DATA && data.type == DB_DATA_PTR) aFree(data.u.ptr); + DB_COUNTSTAT(db_release_both); + if (which&DB_RELEASE_KEY) aFree((char *)key.str); // needs to be a pointer + if (which&DB_RELEASE_DATA && data.type == DB_DATA_PTR) aFree(data.u.ptr); } /*****************************************************************************\ @@ -1115,16 +1117,16 @@ static void db_release_both(DBKey key, DBData data, DBRelease which) * @protected * @see DBIterator#first */ -DBData* dbit_obj_first(DBIterator* self, DBKey* out_key) +DBData *dbit_obj_first(DBIterator *self, DBKey *out_key) { - DBIterator_impl* it = (DBIterator_impl*)self; - - DB_COUNTSTAT(dbit_first); - // position before the first entry - it->ht_index = -1; - it->node = NULL; - // get next entry - return self->next(self, out_key); + DBIterator_impl *it = (DBIterator_impl *)self; + + DB_COUNTSTAT(dbit_first); + // position before the first entry + it->ht_index = -1; + it->node = NULL; + // get next entry + return self->next(self, out_key); } /** @@ -1137,16 +1139,16 @@ DBData* dbit_obj_first(DBIterator* self, DBKey* out_key) * @protected * @see DBIterator#last */ -DBData* dbit_obj_last(DBIterator* self, DBKey* out_key) +DBData *dbit_obj_last(DBIterator *self, DBKey *out_key) { - DBIterator_impl* it = (DBIterator_impl*)self; - - DB_COUNTSTAT(dbit_last); - // position after the last entry - it->ht_index = HASH_SIZE; - it->node = NULL; - // get previous entry - return self->prev(self, out_key); + DBIterator_impl *it = (DBIterator_impl *)self; + + DB_COUNTSTAT(dbit_last); + // position after the last entry + it->ht_index = HASH_SIZE; + it->node = NULL; + // get previous entry + return self->prev(self, out_key); } /** @@ -1159,70 +1161,67 @@ DBData* dbit_obj_last(DBIterator* self, DBKey* out_key) * @protected * @see DBIterator#next */ -DBData* dbit_obj_next(DBIterator* self, DBKey* out_key) -{ - DBIterator_impl* it = (DBIterator_impl*)self; - DBNode node; - DBNode parent; - struct dbn fake; - - DB_COUNTSTAT(dbit_next); - if( it->ht_index < 0 ) - {// get first node - it->ht_index = 0; - it->node = NULL; - } - node = it->node; - memset(&fake, 0, sizeof(fake)); - for( ; it->ht_index < HASH_SIZE; ++(it->ht_index) ) - { - // Iterate in the order: left tree, current node, right tree - if( node == NULL ) - {// prepare initial node of this hash - node = it->db->ht[it->ht_index]; - if( node == NULL ) - continue;// next hash - fake.right = node; - node = &fake; - } - - while( node ) - {// next node - if( node->right ) - {// continue in the right subtree - node = node->right; - while( node->left ) - node = node->left;// get leftmost node - } - else - {// continue to the next parent (recursive) - parent = node->parent; - while( parent ) - { - if( parent->right != node ) - break; - node = parent; - parent = node->parent; - } - if( parent == NULL ) - {// next hash - node = NULL; - break; - } - node = parent; - } - - if( !node->deleted ) - {// found next entry - it->node = node; - if( out_key ) - memcpy(out_key, &node->key, sizeof(DBKey)); - return &node->data; - } - } - } - it->node = NULL; - return NULL;// not found +DBData *dbit_obj_next(DBIterator *self, DBKey *out_key) +{ + DBIterator_impl *it = (DBIterator_impl *)self; + DBNode node; + DBNode parent; + struct dbn fake; + + DB_COUNTSTAT(dbit_next); + if (it->ht_index < 0) { + // get first node + it->ht_index = 0; + it->node = NULL; + } + node = it->node; + memset(&fake, 0, sizeof(fake)); + for (; it->ht_index < HASH_SIZE; ++(it->ht_index)) { + // Iterate in the order: left tree, current node, right tree + if (node == NULL) { + // prepare initial node of this hash + node = it->db->ht[it->ht_index]; + if (node == NULL) + continue;// next hash + fake.right = node; + node = &fake; + } + + while (node) { + // next node + if (node->right) { + // continue in the right subtree + node = node->right; + while (node->left) + node = node->left;// get leftmost node + } else { + // continue to the next parent (recursive) + parent = node->parent; + while (parent) { + if (parent->right != node) + break; + node = parent; + parent = node->parent; + } + if (parent == NULL) { + // next hash + node = NULL; + break; + } + node = parent; + } + + if (!node->deleted) { + // found next entry + it->node = node; + if (out_key) + memcpy(out_key, &node->key, sizeof(DBKey)); + return &node->data; + } + } + } + it->node = NULL; + return NULL;// not found } /** @@ -1235,93 +1234,90 @@ DBData* dbit_obj_next(DBIterator* self, DBKey* out_key) * @protected * @see DBIterator#prev */ -DBData* dbit_obj_prev(DBIterator* self, DBKey* out_key) -{ - DBIterator_impl* it = (DBIterator_impl*)self; - DBNode node; - DBNode parent; - struct dbn fake; - - DB_COUNTSTAT(dbit_prev); - if( it->ht_index >= HASH_SIZE ) - {// get last node - it->ht_index = HASH_SIZE-1; - it->node = NULL; - } - node = it->node; - memset(&fake, 0, sizeof(fake)); - for( ; it->ht_index >= 0; --(it->ht_index) ) - { - // Iterate in the order: right tree, current node, left tree - if( node == NULL ) - {// prepare initial node of this hash - node = it->db->ht[it->ht_index]; - if( node == NULL ) - continue;// next hash - fake.left = node; - node = &fake; - } - - - while( node ) - {// next node - if( node->left ) - {// continue in the left subtree - node = node->left; - while( node->right ) - node = node->right;// get rightmost node - } - else - {// continue to the next parent (recursive) - parent = node->parent; - while( parent ) - { - if( parent->left != node ) - break; - node = parent; - parent = node->parent; - } - if( parent == NULL ) - {// next hash - node = NULL; - break; - } - node = parent; - } - - if( !node->deleted ) - {// found previous entry - it->node = node; - if( out_key ) - memcpy(out_key, &node->key, sizeof(DBKey)); - return &node->data; - } - } - } - it->node = NULL; - return NULL;// not found +DBData *dbit_obj_prev(DBIterator *self, DBKey *out_key) +{ + DBIterator_impl *it = (DBIterator_impl *)self; + DBNode node; + DBNode parent; + struct dbn fake; + + DB_COUNTSTAT(dbit_prev); + if (it->ht_index >= HASH_SIZE) { + // get last node + it->ht_index = HASH_SIZE-1; + it->node = NULL; + } + node = it->node; + memset(&fake, 0, sizeof(fake)); + for (; it->ht_index >= 0; --(it->ht_index)) { + // Iterate in the order: right tree, current node, left tree + if (node == NULL) { + // prepare initial node of this hash + node = it->db->ht[it->ht_index]; + if (node == NULL) + continue;// next hash + fake.left = node; + node = &fake; + } + + + while (node) { + // next node + if (node->left) { + // continue in the left subtree + node = node->left; + while (node->right) + node = node->right;// get rightmost node + } else { + // continue to the next parent (recursive) + parent = node->parent; + while (parent) { + if (parent->left != node) + break; + node = parent; + parent = node->parent; + } + if (parent == NULL) { + // next hash + node = NULL; + break; + } + node = parent; + } + + if (!node->deleted) { + // found previous entry + it->node = node; + if (out_key) + memcpy(out_key, &node->key, sizeof(DBKey)); + return &node->data; + } + } + } + it->node = NULL; + return NULL;// not found } /** * Returns true if the fetched entry exists. - * The databases entries might have NULL data, so use this to to test if + * The databases entries might have NULL data, so use this to to test if * the iterator is done. * @param self Iterator * @return true if the entry exists * @protected * @see DBIterator#exists */ -bool dbit_obj_exists(DBIterator* self) +bool dbit_obj_exists(DBIterator *self) { - DBIterator_impl* it = (DBIterator_impl*)self; + DBIterator_impl *it = (DBIterator_impl *)self; - DB_COUNTSTAT(dbit_exists); - return (it->node && !it->node->deleted); + DB_COUNTSTAT(dbit_exists); + return (it->node && !it->node->deleted); } /** * Removes the current entry from the database. - * NOTE: {@link DBIterator#exists} will return false until another entry + * NOTE: {@link DBIterator#exists} will return false until another entry * is fetched * Puts data of the removed entry in out_data, if out_data is not NULL. * @param self Iterator @@ -1331,26 +1327,25 @@ bool dbit_obj_exists(DBIterator* self) * @see DBMap#remove * @see DBIterator#remove */ -int dbit_obj_remove(DBIterator* self, DBData *out_data) +int dbit_obj_remove(DBIterator *self, DBData *out_data) { - DBIterator_impl* it = (DBIterator_impl*)self; - DBNode node; - int retval = 0; + DBIterator_impl *it = (DBIterator_impl *)self; + DBNode node; + int retval = 0; - DB_COUNTSTAT(dbit_remove); - node = it->node; - if( node && !node->deleted ) - { - DBMap_impl* db = it->db; - if( db->cache == node ) - db->cache = NULL; - if( out_data ) - memcpy(out_data, &node->data, sizeof(DBData)); - retval = 1; - db->release(node->key, node->data, DB_RELEASE_DATA); - db_free_add(db, node, &db->ht[it->ht_index]); - } - return retval; + DB_COUNTSTAT(dbit_remove); + node = it->node; + if (node && !node->deleted) { + DBMap_impl *db = it->db; + if (db->cache == node) + db->cache = NULL; + if (out_data) + memcpy(out_data, &node->data, sizeof(DBData)); + retval = 1; + db->release(node->key, node->data, DB_RELEASE_DATA); + db_free_add(db, node, &db->ht[it->ht_index]); + } + return retval; } /** @@ -1358,48 +1353,48 @@ int dbit_obj_remove(DBIterator* self, DBData *out_data) * @param self Iterator * @protected */ -void dbit_obj_destroy(DBIterator* self) +void dbit_obj_destroy(DBIterator *self) { - DBIterator_impl* it = (DBIterator_impl*)self; + DBIterator_impl *it = (DBIterator_impl *)self; - DB_COUNTSTAT(dbit_destroy); - // unlock the database - db_free_unlock(it->db); - // free iterator - aFree(self); + DB_COUNTSTAT(dbit_destroy); + // unlock the database + db_free_unlock(it->db); + // free iterator + aFree(self); } /** * Returns a new iterator for this database. * The iterator keeps the database locked until it is destroyed. - * The database will keep functioning normally but will only free internal + * The database will keep functioning normally but will only free internal * memory when unlocked, so destroy the iterator as soon as possible. * @param self Database * @return New iterator * @protected */ -static DBIterator* db_obj_iterator(DBMap* self) +static DBIterator *db_obj_iterator(DBMap *self) { - DBMap_impl* db = (DBMap_impl*)self; - DBIterator_impl* it; + DBMap_impl *db = (DBMap_impl *)self; + DBIterator_impl *it; - DB_COUNTSTAT(db_iterator); - CREATE(it, struct DBIterator_impl, 1); - /* Interface of the iterator **/ - it->vtable.first = dbit_obj_first; - it->vtable.last = dbit_obj_last; - it->vtable.next = dbit_obj_next; - it->vtable.prev = dbit_obj_prev; - it->vtable.exists = dbit_obj_exists; - it->vtable.remove = dbit_obj_remove; - it->vtable.destroy = dbit_obj_destroy; - /* Initial state (before the first entry) */ - it->db = db; - it->ht_index = -1; - it->node = NULL; - /* Lock the database */ - db_free_lock(db); - return &it->vtable; + DB_COUNTSTAT(db_iterator); + CREATE(it, struct DBIterator_impl, 1); + /* Interface of the iterator **/ + it->vtable.first = dbit_obj_first; + it->vtable.last = dbit_obj_last; + it->vtable.next = dbit_obj_next; + it->vtable.prev = dbit_obj_prev; + it->vtable.exists = dbit_obj_exists; + it->vtable.remove = dbit_obj_remove; + it->vtable.destroy = dbit_obj_destroy; + /* Initial state (before the first entry) */ + it->db = db; + it->ht_index = -1; + it->node = NULL; + /* Lock the database */ + db_free_lock(db); + return &it->vtable; } /** @@ -1410,47 +1405,47 @@ static DBIterator* db_obj_iterator(DBMap* self) * @protected * @see DBMap#exists */ -static bool db_obj_exists(DBMap* self, DBKey key) +static bool db_obj_exists(DBMap *self, DBKey key) { - DBMap_impl* db = (DBMap_impl*)self; - DBNode node; - int c; - bool found = false; + DBMap_impl *db = (DBMap_impl *)self; + DBNode node; + int c; + bool found = false; - DB_COUNTSTAT(db_exists); - if (db == NULL) return false; // nullpo candidate - if (!(db->options&DB_OPT_ALLOW_NULL_KEY) && db_is_key_null(db->type, key)) { - return false; // nullpo candidate - } + DB_COUNTSTAT(db_exists); + if (db == NULL) return false; // nullpo candidate + if (!(db->options&DB_OPT_ALLOW_NULL_KEY) && db_is_key_null(db->type, key)) { + return false; // nullpo candidate + } - if (db->cache && db->cmp(key, db->cache->key, db->maxlen) == 0) { + if (db->cache && db->cmp(key, db->cache->key, db->maxlen) == 0) { #if defined(DEBUG) - if (db->cache->deleted) { - ShowDebug("db_exists: Cache contains a deleted node. Please report this!!!\n"); - return false; - } + if (db->cache->deleted) { + ShowDebug("db_exists: Cache contains a deleted node. Please report this!!!\n"); + return false; + } #endif - return true; // cache hit - } - - 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) { - if (!(node->deleted)) { - db->cache = node; - found = true; - } - break; - } - if (c < 0) - node = node->left; - else - node = node->right; - } - db_free_unlock(db); - return found; + return true; // cache hit + } + + 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) { + if (!(node->deleted)) { + db->cache = node; + found = true; + } + break; + } + if (c < 0) + node = node->left; + else + node = node->right; + } + db_free_unlock(db); + return found; } /** @@ -1461,48 +1456,48 @@ static bool db_obj_exists(DBMap* self, DBKey key) * @protected * @see DBMap#get */ -static DBData* db_obj_get(DBMap* self, DBKey key) +static DBData *db_obj_get(DBMap *self, DBKey key) { - DBMap_impl* db = (DBMap_impl*)self; - DBNode node; - int c; - DBData *data = NULL; + DBMap_impl *db = (DBMap_impl *)self; + DBNode node; + int c; + DBData *data = NULL; - DB_COUNTSTAT(db_get); - 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_COUNTSTAT(db_get); + 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 + } - if (db->cache && db->cmp(key, db->cache->key, db->maxlen) == 0) { + if (db->cache && db->cmp(key, db->cache->key, db->maxlen) == 0) { #if defined(DEBUG) - if (db->cache->deleted) { - ShowDebug("db_get: Cache contains a deleted node. Please report this!!!\n"); - return NULL; - } + if (db->cache->deleted) { + ShowDebug("db_get: Cache contains a deleted node. Please report this!!!\n"); + return NULL; + } #endif - return &db->cache->data; // cache hit - } - - 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) { - if (!(node->deleted)) { - data = &node->data; - db->cache = node; - } - break; - } - if (c < 0) - node = node->left; - else - node = node->right; - } - db_free_unlock(db); - return data; + return &db->cache->data; // cache hit + } + + 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) { + if (!(node->deleted)) { + data = &node->data; + db->cache = node; + } + break; + } + if (c < 0) + node = node->left; + else + node = node->right; + } + db_free_unlock(db); + return data; } /** @@ -1510,7 +1505,7 @@ static DBData* db_obj_get(DBMap* self, DBKey key) * It puts a maximum of <code>max</code> entries into <code>buf</code>. * If <code>buf</code> is NULL, it only counts the matches. * Returns the number of entries that matched. - * NOTE: if the value returned is greater than <code>max</code>, only the + * NOTE: if the value returned is greater than <code>max</code>, only the * first <code>max</code> entries found are put into the buffer. * @param self Interface of the database * @param buf Buffer to put the data of the matched entries @@ -1521,58 +1516,58 @@ static DBData* db_obj_get(DBMap* self, DBKey key) * @protected * @see DBMap#vgetall */ -static unsigned int db_obj_vgetall(DBMap* self, DBData **buf, unsigned int max, DBMatcher match, va_list args) -{ - DBMap_impl* db = (DBMap_impl*)self; - unsigned int i; - DBNode node; - DBNode parent; - unsigned int ret = 0; - - DB_COUNTSTAT(db_vgetall); - 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) { - - if (!(node->deleted)) { - va_list argscopy; - va_copy(argscopy, args); - if (match(node->key, node->data, argscopy) == 0) { - if (buf && ret < max) - buf[ret] = &node->data; - ret++; - } - va_end(argscopy); - } - - 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; +static unsigned int db_obj_vgetall(DBMap *self, DBData **buf, unsigned int max, DBMatcher match, va_list args) +{ + DBMap_impl *db = (DBMap_impl *)self; + unsigned int i; + DBNode node; + DBNode parent; + unsigned int ret = 0; + + DB_COUNTSTAT(db_vgetall); + 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) { + + if (!(node->deleted)) { + va_list argscopy; + va_copy(argscopy, args); + if (match(node->key, node->data, argscopy) == 0) { + if (buf && ret < max) + buf[ret] = &node->data; + ret++; + } + va_end(argscopy); + } + + 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; } /** @@ -1581,7 +1576,7 @@ static unsigned int db_obj_vgetall(DBMap* self, DBData **buf, unsigned int max, * It puts a maximum of <code>max</code> entries into <code>buf</code>. * If <code>buf</code> is NULL, it only counts the matches. * Returns the number of entries that matched. - * NOTE: if the value returned is greater than <code>max</code>, only the + * NOTE: if the value returned is greater than <code>max</code>, only the * first <code>max</code> entries found are put into the buffer. * @param self Interface of the database * @param buf Buffer to put the data of the matched entries @@ -1593,23 +1588,23 @@ static unsigned int db_obj_vgetall(DBMap* self, DBData **buf, unsigned int max, * @see DBMap#vgetall * @see DBMap#getall */ -static unsigned int db_obj_getall(DBMap* self, DBData **buf, unsigned int max, DBMatcher match, ...) +static unsigned int db_obj_getall(DBMap *self, DBData **buf, unsigned int max, DBMatcher match, ...) { - va_list args; - unsigned int ret; + va_list args; + unsigned int ret; - DB_COUNTSTAT(db_getall); - if (self == NULL) return 0; // nullpo candidate + DB_COUNTSTAT(db_getall); + if (self == NULL) return 0; // nullpo candidate - va_start(args, match); - ret = self->vgetall(self, buf, max, match, args); - va_end(args); - return ret; + 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 + * 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 @@ -1619,96 +1614,96 @@ static unsigned int db_obj_getall(DBMap* self, DBData **buf, unsigned int max, D * @protected * @see DBMap#vensure */ -static DBData* db_obj_vensure(DBMap* self, DBKey key, DBCreateData create, va_list args) -{ - DBMap_impl* db = (DBMap_impl*)self; - DBNode node; - DBNode parent = NULL; - unsigned int hash; - int c = 0; - DBData *data = NULL; - - DB_COUNTSTAT(db_vensure); - 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 - } - - if (db->cache && db->cmp(key, db->cache->key, db->maxlen) == 0) - return &db->cache->data; // cache hit - - 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) { - va_list argscopy; - if (db->item_count == UINT32_MAX) { - ShowError("db_vensure: item_count overflow, aborting item insertion.\n" - "Database allocated at %s:%d", - db->alloc_file, db->alloc_line); - return NULL; - } - DB_COUNTSTAT(db_node_alloc); - 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; - } - va_copy(argscopy, args); - node->data = create(key, argscopy); - va_end(argscopy); - } - data = &node->data; - db->cache = node; - db_free_unlock(db); - return data; +static DBData *db_obj_vensure(DBMap *self, DBKey key, DBCreateData create, va_list args) +{ + DBMap_impl *db = (DBMap_impl *)self; + DBNode node; + DBNode parent = NULL; + unsigned int hash; + int c = 0; + DBData *data = NULL; + + DB_COUNTSTAT(db_vensure); + 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 + } + + if (db->cache && db->cmp(key, db->cache->key, db->maxlen) == 0) + return &db->cache->data; // cache hit + + 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) { + va_list argscopy; + if (db->item_count == UINT32_MAX) { + ShowError("db_vensure: item_count overflow, aborting item insertion.\n" + "Database allocated at %s:%d", + db->alloc_file, db->alloc_line); + return NULL; + } + DB_COUNTSTAT(db_node_alloc); + 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; + } + va_copy(argscopy, args); + node->data = create(key, argscopy); + va_end(argscopy); + } + data = &node->data; + db->cache = node; + db_free_unlock(db); + return data; } /** * Just calls {@link DBMap#vensure}. * Get the data of the entry identified by the key. - * If the entry does not exist, an entry is added with the data returned by + * If the entry does not exist, an entry is added with the data returned by * <code>create</code>. * @param self Interface of the database * @param key Key that identifies the entry @@ -1719,18 +1714,18 @@ static DBData* db_obj_vensure(DBMap* self, DBKey key, DBCreateData create, va_li * @see DBMap#vensure * @see DBMap#ensure */ -static DBData* db_obj_ensure(DBMap* self, DBKey key, DBCreateData create, ...) +static DBData *db_obj_ensure(DBMap *self, DBKey key, DBCreateData create, ...) { - va_list args; - DBData *ret = NULL; + va_list args; + DBData *ret = NULL; - DB_COUNTSTAT(db_ensure); - if (self == NULL) return NULL; // nullpo candidate + DB_COUNTSTAT(db_ensure); + if (self == NULL) return NULL; // nullpo candidate - va_start(args, create); - ret = self->vensure(self, key, create, args); - va_end(args); - return ret; + va_start(args, create); + ret = self->vensure(self, key, create, args); + va_end(args); + return ret; } /** @@ -1746,97 +1741,97 @@ static DBData* db_obj_ensure(DBMap* self, DBKey key, DBCreateData create, ...) * @see #db_malloc_dbn(void) * @see DBMap#put */ -static int db_obj_put(DBMap* self, DBKey key, DBData data, DBData *out_data) -{ - DBMap_impl* db = (DBMap_impl*)self; - DBNode node; - DBNode parent = NULL; - int c = 0, retval = 0; - unsigned int hash; - - DB_COUNTSTAT(db_put); - if (db == NULL) return 0; // 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 0; // 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 0; // nullpo candidate - } - if (!(db->options&DB_OPT_ALLOW_NULL_DATA) && (data.type == DB_DATA_PTR && data.u.ptr == NULL)) { - ShowError("db_put: Attempted to use non-allowed NULL data for db allocated at %s:%d\n",db->alloc_file, db->alloc_line); - return 0; // nullpo candidate - } - - if (db->item_count == UINT32_MAX) { - ShowError("db_put: item_count overflow, aborting item insertion.\n" - "Database allocated at %s:%d", - db->alloc_file, db->alloc_line); - return 0; - } - // 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); - if (out_data) - memcpy(out_data, &node->data, sizeof(*out_data)); - retval = 1; - } - break; - } - parent = node; - if (c < 0) { - node = node->left; - } else { - node = node->right; - } - } - // allocate a new node if necessary - if (node == NULL) { - DB_COUNTSTAT(db_node_alloc); - 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->cache = node; - db_free_unlock(db); - return retval; +static int db_obj_put(DBMap *self, DBKey key, DBData data, DBData *out_data) +{ + DBMap_impl *db = (DBMap_impl *)self; + DBNode node; + DBNode parent = NULL; + int c = 0, retval = 0; + unsigned int hash; + + DB_COUNTSTAT(db_put); + if (db == NULL) return 0; // 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 0; // 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 0; // nullpo candidate + } + if (!(db->options&DB_OPT_ALLOW_NULL_DATA) && (data.type == DB_DATA_PTR && data.u.ptr == NULL)) { + ShowError("db_put: Attempted to use non-allowed NULL data for db allocated at %s:%d\n",db->alloc_file, db->alloc_line); + return 0; // nullpo candidate + } + + if (db->item_count == UINT32_MAX) { + ShowError("db_put: item_count overflow, aborting item insertion.\n" + "Database allocated at %s:%d", + db->alloc_file, db->alloc_line); + return 0; + } + // 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); + if (out_data) + memcpy(out_data, &node->data, sizeof(*out_data)); + retval = 1; + } + break; + } + parent = node; + if (c < 0) { + node = node->left; + } else { + node = node->right; + } + } + // allocate a new node if necessary + if (node == NULL) { + DB_COUNTSTAT(db_node_alloc); + 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->cache = node; + db_free_unlock(db); + return retval; } /** @@ -1851,49 +1846,49 @@ static int db_obj_put(DBMap* self, DBKey key, DBData data, DBData *out_data) * @see #db_free_add(DBMap_impl*,DBNode,DBNode *) * @see DBMap#remove */ -static int db_obj_remove(DBMap* self, DBKey key, DBData *out_data) -{ - DBMap_impl* db = (DBMap_impl*)self; - DBNode node; - unsigned int hash; - int c = 0, retval = 0; - - DB_COUNTSTAT(db_remove); - if (db == NULL) return 0; // 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 0; // 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 0; // 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)) { - if (db->cache == node) - db->cache = NULL; - if (out_data) - memcpy(out_data, &node->data, sizeof(*out_data)); - retval = 1; - db->release(node->key, node->data, DB_RELEASE_DATA); - db_free_add(db, node, &db->ht[hash]); - } - break; - } - if (c < 0) - node = node->left; - else - node = node->right; - } - db_free_unlock(db); - return retval; +static int db_obj_remove(DBMap *self, DBKey key, DBData *out_data) +{ + DBMap_impl *db = (DBMap_impl *)self; + DBNode node; + unsigned int hash; + int c = 0, retval = 0; + + DB_COUNTSTAT(db_remove); + if (db == NULL) return 0; // 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 0; // 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 0; // 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)) { + if (db->cache == node) + db->cache = NULL; + if (out_data) + memcpy(out_data, &node->data, sizeof(*out_data)); + retval = 1; + db->release(node->key, node->data, DB_RELEASE_DATA); + db_free_add(db, node, &db->ht[hash]); + } + break; + } + if (c < 0) + node = node->left; + else + node = node->right; + } + db_free_unlock(db); + return retval; } /** @@ -1906,52 +1901,52 @@ static int db_obj_remove(DBMap* self, DBKey key, DBData *out_data) * @protected * @see DBMap#vforeach */ -static int db_obj_vforeach(DBMap* self, DBApply func, va_list args) -{ - DBMap_impl* db = (DBMap_impl*)self; - unsigned int i; - int sum = 0; - DBNode node; - DBNode parent; - - DB_COUNTSTAT(db_vforeach); - 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) { - if (!(node->deleted)) { - va_list argscopy; - va_copy(argscopy, args); - sum += func(node->key, &node->data, argscopy); - va_end(argscopy); - } - 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; +static int db_obj_vforeach(DBMap *self, DBApply func, va_list args) +{ + DBMap_impl *db = (DBMap_impl *)self; + unsigned int i; + int sum = 0; + DBNode node; + DBNode parent; + + DB_COUNTSTAT(db_vforeach); + 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) { + if (!(node->deleted)) { + va_list argscopy; + va_copy(argscopy, args); + sum += func(node->key, &node->data, argscopy); + va_end(argscopy); + } + 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; } /** @@ -1966,18 +1961,18 @@ static int db_obj_vforeach(DBMap* self, DBApply func, va_list args) * @see DBMap#vforeach * @see DBMap#foreach */ -static int db_obj_foreach(DBMap* self, DBApply func, ...) +static int db_obj_foreach(DBMap *self, DBApply func, ...) { - va_list args; - int ret; + va_list args; + int ret; - DB_COUNTSTAT(db_foreach); - if (self == NULL) return 0; // nullpo candidate + DB_COUNTSTAT(db_foreach); + if (self == NULL) return 0; // nullpo candidate - va_start(args, func); - ret = self->vforeach(self, func, args); - va_end(args); - return ret; + va_start(args, func); + ret = self->vforeach(self, func, args); + va_end(args); + return ret; } /** @@ -1992,62 +1987,61 @@ static int db_obj_foreach(DBMap* self, DBApply func, ...) * @protected * @see DBMap#vclear */ -static int db_obj_vclear(DBMap* self, DBApply func, va_list args) -{ - DBMap_impl* db = (DBMap_impl*)self; - int sum = 0; - unsigned int i; - DBNode node; - DBNode parent; - - DB_COUNTSTAT(db_vclear); - if (db == NULL) return 0; // nullpo candidate - - db_free_lock(db); - db->cache = NULL; - 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) - { - va_list argscopy; - va_copy(argscopy, args); - sum += func(node->key, &node->data, argscopy); - va_end(argscopy); - } - db->release(node->key, node->data, DB_RELEASE_BOTH); - node->deleted = 1; - } - DB_COUNTSTAT(db_node_free); - if (parent) { - if (parent->left == node) - parent->left = NULL; - else - parent->right = NULL; - } - ers_free(db->nodes, node); - node = parent; - } - db->ht[i] = NULL; - } - db->free_count = 0; - db->item_count = 0; - db_free_unlock(db); - return sum; +static int db_obj_vclear(DBMap *self, DBApply func, va_list args) +{ + DBMap_impl *db = (DBMap_impl *)self; + int sum = 0; + unsigned int i; + DBNode node; + DBNode parent; + + DB_COUNTSTAT(db_vclear); + if (db == NULL) return 0; // nullpo candidate + + db_free_lock(db); + db->cache = NULL; + 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) { + va_list argscopy; + va_copy(argscopy, args); + sum += func(node->key, &node->data, argscopy); + va_end(argscopy); + } + db->release(node->key, node->data, DB_RELEASE_BOTH); + node->deleted = 1; + } + DB_COUNTSTAT(db_node_free); + if (parent) { + if (parent->left == node) + parent->left = NULL; + else + parent->right = NULL; + } + ers_free(db->nodes, node); + node = parent; + } + db->ht[i] = NULL; + } + db->free_count = 0; + db->item_count = 0; + db_free_unlock(db); + return sum; } /** @@ -2056,7 +2050,7 @@ static int db_obj_vclear(DBMap* self, DBApply func, va_list args) * Before deleting an entry, func is applied to it. * Releases the key and the data. * Returns the sum of values returned by func, if it exists. - * NOTE: This locks the database globally. Any attempt to insert or remove + * NOTE: This locks the database globally. Any attempt to insert or remove * a database entry will give an error and be aborted (except for clearing). * @param self Interface of the database * @param func Function to be applied to every entry before deleting @@ -2066,25 +2060,25 @@ static int db_obj_vclear(DBMap* self, DBApply func, va_list args) * @see DBMap#vclear * @see DBMap#clear */ -static int db_obj_clear(DBMap* self, DBApply func, ...) +static int db_obj_clear(DBMap *self, DBApply func, ...) { - va_list args; - int ret; + va_list args; + int ret; - DB_COUNTSTAT(db_clear); - if (self == NULL) return 0; // nullpo candidate + DB_COUNTSTAT(db_clear); + if (self == NULL) return 0; // nullpo candidate - va_start(args, func); - ret = self->vclear(self, func, args); - va_end(args); - return ret; + 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 applied to it. * Returns the sum of values returned by func, if it exists. - * NOTE: This locks the database globally. Any attempt to insert or remove + * NOTE: This locks the database globally. Any attempt to insert or remove * a database entry will give an error and be aborted (except for clearing). * @param self Interface of the database * @param func Function to be applied to every entry before deleting @@ -2093,42 +2087,50 @@ static int db_obj_clear(DBMap* self, DBApply func, ...) * @protected * @see DBMap#vdestroy */ -static int db_obj_vdestroy(DBMap* self, DBApply func, va_list args) +static int db_obj_vdestroy(DBMap *self, DBApply func, va_list args) { - DBMap_impl* db = (DBMap_impl*)self; - int sum; + DBMap_impl *db = (DBMap_impl *)self; + int sum; - DB_COUNTSTAT(db_vdestroy); - 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->free_lock, db->alloc_file, db->alloc_line); + DB_COUNTSTAT(db_vdestroy); + 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->free_lock, db->alloc_file, db->alloc_line); #ifdef DB_ENABLE_STATS - switch (db->type) { - case DB_INT: DB_COUNTSTAT(db_int_destroy); break; - case DB_UINT: DB_COUNTSTAT(db_uint_destroy); break; - case DB_STRING: DB_COUNTSTAT(db_string_destroy); break; - case DB_ISTRING: DB_COUNTSTAT(db_istring_destroy); break; - } + switch (db->type) { + case DB_INT: + DB_COUNTSTAT(db_int_destroy); + break; + case DB_UINT: + DB_COUNTSTAT(db_uint_destroy); + break; + case DB_STRING: + DB_COUNTSTAT(db_string_destroy); + break; + case DB_ISTRING: + DB_COUNTSTAT(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; + 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; } /** @@ -2137,7 +2139,7 @@ static int db_obj_vdestroy(DBMap* self, DBApply func, va_list args) * Before deleting an entry, func is applied to it. * Releases the key and the data. * Returns the sum of values returned by func, if it exists. - * NOTE: This locks the database globally. Any attempt to insert or remove + * NOTE: This locks the database globally. Any attempt to insert or remove * a database entry will give an error and be aborted. * @param self Database * @param func Function to be applied to every entry before deleting @@ -2147,18 +2149,18 @@ static int db_obj_vdestroy(DBMap* self, DBApply func, va_list args) * @see DBMap#vdestroy * @see DBMap#destroy */ -static int db_obj_destroy(DBMap* self, DBApply func, ...) +static int db_obj_destroy(DBMap *self, DBApply func, ...) { - va_list args; - int ret; + va_list args; + int ret; - DB_COUNTSTAT(db_destroy); - if (self == NULL) return 0; // nullpo candidate + DB_COUNTSTAT(db_destroy); + if (self == NULL) return 0; // nullpo candidate - va_start(args, func); - ret = self->vdestroy(self, func, args); - va_end(args); - return ret; + va_start(args, func); + ret = self->vdestroy(self, func, args); + va_end(args); + return ret; } /** @@ -2169,19 +2171,19 @@ static int db_obj_destroy(DBMap* self, DBApply func, ...) * @see DBMap_impl#item_count * @see DBMap#size */ -static unsigned int db_obj_size(DBMap* self) +static unsigned int db_obj_size(DBMap *self) { - DBMap_impl* db = (DBMap_impl*)self; - unsigned int item_count; + DBMap_impl *db = (DBMap_impl *)self; + unsigned int item_count; - DB_COUNTSTAT(db_size); - if (db == NULL) return 0; // nullpo candidate + DB_COUNTSTAT(db_size); + if (db == NULL) return 0; // nullpo candidate - db_free_lock(db); - item_count = db->item_count; - db_free_unlock(db); + db_free_lock(db); + item_count = db->item_count; + db_free_unlock(db); - return item_count; + return item_count; } /** @@ -2192,19 +2194,19 @@ static unsigned int db_obj_size(DBMap* self) * @see DBMap_impl#type * @see DBMap#type */ -static DBType db_obj_type(DBMap* self) +static DBType db_obj_type(DBMap *self) { - DBMap_impl* db = (DBMap_impl*)self; - DBType type; + DBMap_impl *db = (DBMap_impl *)self; + DBType type; - DB_COUNTSTAT(db_type); - if (db == NULL) return (DBType)-1; // nullpo candidate - TODO what should this return? + DB_COUNTSTAT(db_type); + if (db == NULL) return (DBType)-1; // nullpo candidate - TODO what should this return? - db_free_lock(db); - type = db->type; - db_free_unlock(db); + db_free_lock(db); + type = db->type; + db_free_unlock(db); - return type; + return type; } /** @@ -2215,19 +2217,19 @@ static DBType db_obj_type(DBMap* self) * @see DBMap_impl#options * @see DBMap#options */ -static DBOptions db_obj_options(DBMap* self) +static DBOptions db_obj_options(DBMap *self) { - DBMap_impl* db = (DBMap_impl*)self; - DBOptions options; + DBMap_impl *db = (DBMap_impl *)self; + DBOptions options; - DB_COUNTSTAT(db_options); - if (db == NULL) return DB_OPT_BASE; // nullpo candidate - TODO what should this return? + DB_COUNTSTAT(db_options); + 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); + db_free_lock(db); + options = db->options; + db_free_unlock(db); - return options; + return options; } /*****************************************************************************\ @@ -2264,18 +2266,18 @@ static DBOptions db_obj_options(DBMap* self) */ DBOptions db_fix_options(DBType type, DBOptions options) { - DB_COUNTSTAT(db_fix_options); - switch (type) { - case DB_INT: - case DB_UINT: // Numeric database, do nothing with the keys - return (DBOptions)(options&~(DB_OPT_DUP_KEY|DB_OPT_RELEASE_KEY)); + DB_COUNTSTAT(db_fix_options); + switch (type) { + case DB_INT: + case DB_UINT: // Numeric database, do nothing with the keys + return (DBOptions)(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; - } + 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; + } } /** @@ -2290,16 +2292,20 @@ DBOptions db_fix_options(DBType type, DBOptions options) */ DBComparator db_default_cmp(DBType type) { - DB_COUNTSTAT(db_default_cmp); - 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; - } + DB_COUNTSTAT(db_default_cmp); + 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; + } } /** @@ -2314,20 +2320,24 @@ DBComparator db_default_cmp(DBType type) */ DBHasher db_default_hash(DBType type) { - DB_COUNTSTAT(db_default_hash); - 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; - } + DB_COUNTSTAT(db_default_hash); + 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 + * 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. @@ -2343,16 +2353,16 @@ DBHasher db_default_hash(DBType type) */ DBReleaser db_default_release(DBType type, DBOptions options) { - DB_COUNTSTAT(db_default_release); - 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 + DB_COUNTSTAT(db_default_release); + 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 } /** @@ -2368,16 +2378,20 @@ DBReleaser db_default_release(DBType type, DBOptions options) */ DBReleaser db_custom_release(DBRelease which) { - DB_COUNTSTAT(db_custom_release); - 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; - } + DB_COUNTSTAT(db_custom_release); + 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; + } } /** @@ -2388,75 +2402,83 @@ DBReleaser db_custom_release(DBRelease which) * @param line Line of the file where the database is being allocated * @param type Type of database * @param options Options of the database - * @param maxlen Maximum length of the string to be used as key in string + * @param maxlen Maximum length of the string to be used as key in string * databases. If 0, the maximum number of maxlen is used (64K). * @return The interface of the database * @public * @see #DBMap_impl * @see #db_fix_options(DBType,DBOptions) */ -DBMap* db_alloc(const char *file, int line, DBType type, DBOptions options, unsigned short maxlen) +DBMap *db_alloc(const char *file, int line, DBType type, DBOptions options, unsigned short maxlen) { - DBMap_impl* db; - unsigned int i; + DBMap_impl *db; + unsigned int i; #ifdef DB_ENABLE_STATS - DB_COUNTSTAT(db_alloc); - switch (type) { - case DB_INT: DB_COUNTSTAT(db_int_alloc); break; - case DB_UINT: DB_COUNTSTAT(db_uint_alloc); break; - case DB_STRING: DB_COUNTSTAT(db_string_alloc); break; - case DB_ISTRING: DB_COUNTSTAT(db_istring_alloc); break; - } + DB_COUNTSTAT(db_alloc); + switch (type) { + case DB_INT: + DB_COUNTSTAT(db_int_alloc); + break; + case DB_UINT: + DB_COUNTSTAT(db_uint_alloc); + break; + case DB_STRING: + DB_COUNTSTAT(db_string_alloc); + break; + case DB_ISTRING: + DB_COUNTSTAT(db_istring_alloc); + break; + } #endif /* DB_ENABLE_STATS */ - CREATE(db, struct DBMap_impl, 1); - - options = db_fix_options(type, options); - /* Interface of the database */ - db->vtable.iterator = db_obj_iterator; - db->vtable.exists = db_obj_exists; - db->vtable.get = db_obj_get; - db->vtable.getall = db_obj_getall; - db->vtable.vgetall = db_obj_vgetall; - db->vtable.ensure = db_obj_ensure; - db->vtable.vensure = db_obj_vensure; - db->vtable.put = db_obj_put; - db->vtable.remove = db_obj_remove; - db->vtable.foreach = db_obj_foreach; - db->vtable.vforeach = db_obj_vforeach; - db->vtable.clear = db_obj_clear; - db->vtable.vclear = db_obj_vclear; - db->vtable.destroy = db_obj_destroy; - db->vtable.vdestroy = db_obj_vdestroy; - db->vtable.size = db_obj_size; - db->vtable.type = db_obj_type; - db->vtable.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(sizeof(struct dbn),"db.c::db_alloc",ERS_OPT_NONE); - 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->cache = NULL; - db->type = type; - db->options = options; - db->item_count = 0; - db->maxlen = maxlen; - db->global_lock = 0; - - if( db->maxlen == 0 && (type == DB_STRING || type == DB_ISTRING) ) - db->maxlen = UINT16_MAX; - - return &db->vtable; + CREATE(db, struct DBMap_impl, 1); + + options = db_fix_options(type, options); + /* Interface of the database */ + db->vtable.iterator = db_obj_iterator; + db->vtable.exists = db_obj_exists; + db->vtable.get = db_obj_get; + db->vtable.getall = db_obj_getall; + db->vtable.vgetall = db_obj_vgetall; + db->vtable.ensure = db_obj_ensure; + db->vtable.vensure = db_obj_vensure; + db->vtable.put = db_obj_put; + db->vtable.remove = db_obj_remove; + db->vtable.foreach = db_obj_foreach; + db->vtable.vforeach = db_obj_vforeach; + db->vtable.clear = db_obj_clear; + db->vtable.vclear = db_obj_vclear; + db->vtable.destroy = db_obj_destroy; + db->vtable.vdestroy = db_obj_vdestroy; + db->vtable.size = db_obj_size; + db->vtable.type = db_obj_type; + db->vtable.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(sizeof(struct dbn),"db.c::db_alloc",ERS_OPT_NONE); + 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->cache = NULL; + db->type = type; + db->options = options; + db->item_count = 0; + db->maxlen = maxlen; + db->global_lock = 0; + + if (db->maxlen == 0 && (type == DB_STRING || type == DB_ISTRING)) + db->maxlen = UINT16_MAX; + + return &db->vtable; } /** @@ -2467,11 +2489,11 @@ DBMap* db_alloc(const char *file, int line, DBType type, DBOptions options, unsi */ DBKey db_i2key(int key) { - DBKey ret; + DBKey ret; - DB_COUNTSTAT(db_i2key); - ret.i = key; - return ret; + DB_COUNTSTAT(db_i2key); + ret.i = key; + return ret; } /** @@ -2482,11 +2504,11 @@ DBKey db_i2key(int key) */ DBKey db_ui2key(unsigned int key) { - DBKey ret; + DBKey ret; - DB_COUNTSTAT(db_ui2key); - ret.ui = key; - return ret; + DB_COUNTSTAT(db_ui2key); + ret.ui = key; + return ret; } /** @@ -2497,11 +2519,11 @@ DBKey db_ui2key(unsigned int key) */ DBKey db_str2key(const char *key) { - DBKey ret; + DBKey ret; - DB_COUNTSTAT(db_str2key); - ret.str = key; - return ret; + DB_COUNTSTAT(db_str2key); + ret.str = key; + return ret; } /** @@ -2512,12 +2534,12 @@ DBKey db_str2key(const char *key) */ DBData db_i2data(int data) { - DBData ret; + DBData ret; - DB_COUNTSTAT(db_i2data); - ret.type = DB_DATA_INT; - ret.u.i = data; - return ret; + DB_COUNTSTAT(db_i2data); + ret.type = DB_DATA_INT; + ret.u.i = data; + return ret; } /** @@ -2528,12 +2550,12 @@ DBData db_i2data(int data) */ DBData db_ui2data(unsigned int data) { - DBData ret; + DBData ret; - DB_COUNTSTAT(db_ui2data); - ret.type = DB_DATA_UINT; - ret.u.ui = data; - return ret; + DB_COUNTSTAT(db_ui2data); + ret.type = DB_DATA_UINT; + ret.u.ui = data; + return ret; } /** @@ -2544,12 +2566,12 @@ DBData db_ui2data(unsigned int data) */ DBData db_ptr2data(void *data) { - DBData ret; + DBData ret; - DB_COUNTSTAT(db_ptr2data); - ret.type = DB_DATA_PTR; - ret.u.ptr = data; - return ret; + DB_COUNTSTAT(db_ptr2data); + ret.type = DB_DATA_PTR; + ret.u.ptr = data; + return ret; } /** @@ -2561,10 +2583,10 @@ DBData db_ptr2data(void *data) */ int db_data2i(DBData *data) { - DB_COUNTSTAT(db_data2i); - if (data && DB_DATA_INT == data->type) - return data->u.i; - return 0; + DB_COUNTSTAT(db_data2i); + if (data && DB_DATA_INT == data->type) + return data->u.i; + return 0; } /** @@ -2576,10 +2598,10 @@ int db_data2i(DBData *data) */ unsigned int db_data2ui(DBData *data) { - DB_COUNTSTAT(db_data2ui); - if (data && DB_DATA_UINT == data->type) - return data->u.ui; - return 0; + DB_COUNTSTAT(db_data2ui); + if (data && DB_DATA_UINT == data->type) + return data->u.ui; + return 0; } /** @@ -2589,12 +2611,12 @@ unsigned int db_data2ui(DBData *data) * @return Void* value of the data. * @public */ -void* db_data2ptr(DBData *data) +void *db_data2ptr(DBData *data) { - DB_COUNTSTAT(db_data2ptr); - if (data && DB_DATA_PTR == data->type) - return data->u.ptr; - return NULL; + DB_COUNTSTAT(db_data2ptr); + if (data && DB_DATA_PTR == data->type) + return data->u.ptr; + return NULL; } /** @@ -2604,7 +2626,7 @@ void* db_data2ptr(DBData *data) */ void db_init(void) { - DB_COUNTSTAT(db_init); + DB_COUNTSTAT(db_init); } /** @@ -2615,208 +2637,208 @@ void db_init(void) void db_final(void) { #ifdef DB_ENABLE_STATS - DB_COUNTSTAT(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" - "dbit_first %10u, dbit_last %10u,\n" - "dbit_next %10u, dbit_prev %10u,\n" - "dbit_exists %10u, dbit_remove %10u,\n" - "dbit_destroy %10u, db_iterator %10u,\n" - "db_exits %10u, 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_i2data %10u, db_ui2data %10u,\n" - "db_ptr2data %10u, db_data2i %10u,\n" - "db_data2ui %10u, db_data2ptr %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.dbit_first, stats.dbit_last, - stats.dbit_next, stats.dbit_prev, - stats.dbit_exists, stats.dbit_remove, - stats.dbit_destroy, stats.db_iterator, - stats.db_exists, 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_i2data, stats.db_ui2data, - stats.db_ptr2data, stats.db_data2i, - stats.db_data2ui, stats.db_data2ptr, - stats.db_init, stats.db_final); + DB_COUNTSTAT(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" + "dbit_first %10u, dbit_last %10u,\n" + "dbit_next %10u, dbit_prev %10u,\n" + "dbit_exists %10u, dbit_remove %10u,\n" + "dbit_destroy %10u, db_iterator %10u,\n" + "db_exits %10u, 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_i2data %10u, db_ui2data %10u,\n" + "db_ptr2data %10u, db_data2i %10u,\n" + "db_data2ui %10u, db_data2ptr %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.dbit_first, stats.dbit_last, + stats.dbit_next, stats.dbit_prev, + stats.dbit_exists, stats.dbit_remove, + stats.dbit_destroy, stats.db_iterator, + stats.db_exists, 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_i2data, stats.db_ui2data, + stats.db_ptr2data, stats.db_data2i, + stats.db_data2ui, stats.db_data2ptr, + 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 = (struct linkdb_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_foreach( struct linkdb_node** head, LinkDBFunc func, ... ) -{ - struct linkdb_node *node; - if( head == NULL ) return; - node = *head; - while ( node ) { - va_list args; - va_start(args, func); - func( node->key, node->data, args ); - va_end(args); - node = node->next; - } -} - -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 ) { - //Moving the head in order to improve processing efficiency - 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 ) { - //Moving the head in order to improve processing efficiency - 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++; - } - //Insert because it can not find - 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; +void linkdb_insert(struct linkdb_node **head, void *key, void *data) +{ + struct linkdb_node *node; + if (head == NULL) return ; + node = (struct linkdb_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_foreach(struct linkdb_node **head, LinkDBFunc func, ...) +{ + struct linkdb_node *node; + if (head == NULL) return; + node = *head; + while (node) { + va_list args; + va_start(args, func); + func(node->key, node->data, args); + va_end(args); + node = node->next; + } +} + +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) { + //Moving the head in order to improve processing efficiency + 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) { + //Moving the head in order to improve processing efficiency + 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++; + } + //Insert because it can not find + 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; } |