* Added a database iterator to db.c/db.h.

git-svn-id: https://rathena.svn.sourceforge.net/svnroot/rathena/trunk@11701 54d463be-8e91-2dee-dedb-b68131a5f0ec

2 files changed, 442 insertions, 1 deletions

diff --git a/src/common/db.c b/src/common/db.c
index 27aa6776a..712b3ec7e 100644
--- a/src/common/db.c
+++ b/src/common/db.c
@@ -48,6 +48,7 @@
  *  - create a db that organizes itself by splaying
  *
  *  HISTORY:
+ *    2007/11/09 - Added an iterator to the database.
  *    2006/12/21 - Added 1-node cache to the database.
  *    2.1 (Athena build #???#) - Portability fix
  *      - Fixed the portability of casting to union and added the functions
@@ -189,6 +190,25 @@ typedef struct DBMap_impl {
 	unsigned global_lock : 1;
 } DBMap_impl;
 
+/**
+ * Complete iterator structure.
+ * @param vtable Interface of the iterator
+ * @param db Parent database
+ * @param ht_index Current index of the hashtable
+ * @param node Current node
+ * @private
+ * @see #DBIterator
+ * @see #DBMap_impl
+ * @see #DBNode
+ */
+typedef struct DBIterator_impl {
+	// Iterator interface
+	struct DBIterator vtable;
+	DBMap_impl* db;
+	int ht_index;
+	DBNode node;
+} DBIterator_impl;
+
 #if defined(DB_ENABLE_STATS)
 /**
  * Structure with what is counted when the database estatistics are enabled.
@@ -233,6 +253,14 @@ static struct db_stats {
 	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_get;
 	uint32 db_getall;
 	uint32 db_vgetall;
@@ -1039,7 +1067,16 @@ static void db_release_both(DBKey key, void *data, DBRelease which)
 
 /*****************************************************************************\
  *  (4) Section with protected functions used in the interface of the        *
- *  database.                                                                *
+ *  database and interface of the iterator.                                  *
+ *  dbit_obj_first   - Fetches the first entry from the database.            *
+ *  dbit_obj_last    - Fetches the last entry from the database.             *
+ *  dbit_obj_next    - Fetches the next entry from the database.             *
+ *  dbit_obj_prev    - Fetches the previous entry from the database.         *
+ *  dbit_obj_exists  - Returns true if the current entry exists.             *
+ *  dbit_obj_remove  - Remove the current entry from the database.           *
+ *  dbit_obj_destroy - Destroys the iterator, unlocking the database and     *
+ *           freeing used memory.                                            *
+ *  db_obj_iterator - Return a new databse iterator.                         *
  *  db_obj_get      - Get the data identified by the key.                    *
  *  db_obj_vgetall  - Get the data of the matched entries.                   *
  *  db_obj_getall   - Get the data of the matched entries.                   *
@@ -1061,6 +1098,300 @@ static void db_release_both(DBKey key, void *data, DBRelease which)
 \*****************************************************************************/
 
 /**
+ * Fetches the first entry in the database.
+ * Returns the data of the entry.
+ * Puts the key in out_key, if out_key is not NULL.
+ * @param self Iterator
+ * @param out_key Key of the entry
+ * @return Data of the entry
+ * @protected
+ * @see DBIterator#first
+ */
+void* 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);
+}
+
+/**
+ * Fetches the last entry in the database.
+ * Returns the data of the entry.
+ * Puts the key in out_key, if out_key is not NULL.
+ * @param self Iterator
+ * @param out_key Key of the entry
+ * @return Data of the entry
+ * @protected
+ * @see DBIterator#last
+ */
+void* 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);
+}
+
+/**
+ * Fetches the next entry in the database.
+ * Returns the data of the entry.
+ * Puts the key in out_key, if out_key is not NULL.
+ * @param self Iterator
+ * @param out_key Key of the entry
+ * @return Data of the entry
+ * @protected
+ * @see DBIterator#next
+ */
+void* 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
+}
+
+/**
+ * Fetches the previous entry in the database.
+ * Returns the data of the entry.
+ * Puts the key in out_key, if out_key is not NULL.
+ * @param self Iterator
+ * @param out_key Key of the entry
+ * @return Data of the entry
+ * @protected
+ * @see DBIterator#prev
+ */
+void* 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 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
+}
+
+/**
+ * Returns true if the fetched entry exists.
+ * The databases entries might have NULL data, so use this to to test if 
+ * the iterator is done.
+ * @param self Iterator
+ * @return true is the entry exists
+ * @protected
+ * @see DBIterator#exists
+ */
+bool dbit_obj_exists(DBIterator* self)
+{
+	DBIterator_impl* it = (DBIterator_impl*)self;
+
+	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 
+ *       is fethed
+ * Returns the data of the entry.
+ * @param self Iterator
+ * @return The data of the entry or NULL if not found
+ * @protected
+ * @see DBMap#remove
+ * @see DBIterator#remove
+ */
+void* dbit_obj_remove(DBIterator* self)
+{
+	DBIterator_impl* it = (DBIterator_impl*)self;
+	DBNode node;
+	void* data = NULL;
+
+	DB_COUNTSTAT(dbit_remove);
+	node = it->node;
+	if( node && !node->deleted )
+	{
+		DBMap_impl* db = it->db;
+		if( db->cache == node )
+			db->cache = NULL;
+		data = node->data;
+		db->release(node->key, node->data, DB_RELEASE_DATA);
+		db_free_add(db, node, &db->ht[it->ht_index]);
+	}
+	return data;
+}
+
+/**
+ * Destroys this iterator and unlocks the database.
+ * @param self Iterator
+ * @protected
+ */
+void dbit_obj_destroy(DBIterator* self)
+{
+	DBIterator_impl* it = (DBIterator_impl*)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 
+ * 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)
+{
+	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;
+}
+
+/**
  * Get the data of the entry identifid by the key.
  * @param self Interface of the database
  * @param key Key that identifies the entry
@@ -1981,6 +2312,7 @@ DBMap* db_alloc(const char *file, int line, DBType type, DBOptions options, unsi
 
 	options = db_fix_options(type, options);
 	/* Interface of the database */
+	db->vtable.iterator = db_obj_iterator;
 	db->vtable.get      = db_obj_get;
 	db->vtable.getall   = db_obj_getall;
 	db->vtable.vgetall  = db_obj_vgetall;
@@ -2119,6 +2451,10 @@ void db_final(void)
 			"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_get             %10u,\n"
 			"db_getall          %10u, db_vgetall         %10u,\n"
 			"db_ensure          %10u, db_vensure         %10u,\n"
@@ -2145,6 +2481,10 @@ void db_final(void)
 			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_get,
 			stats.db_getall,          stats.db_vgetall,
 			stats.db_ensure,          stats.db_vensure,
diff --git a/src/common/db.h b/src/common/db.h
index 45034c141..ecaed67af 100644
--- a/src/common/db.h
+++ b/src/common/db.h
@@ -21,6 +21,7 @@
  *  - see what functions need or should be added to the database interface   *
  *                                                                           *
  *  HISTORY:                                                                 *
+ *    2007/11/09 - Added an iterator to the database.
  *    2.1 (Athena build #???#) - Portability fix                             *
  *      - Fixed the portability of casting to union and added the functions  *
  *        {@link DBMap#ensure(DBMap,DBKey,DBCreateData,...)} and             *
@@ -56,6 +57,7 @@
  *  DBComparator - Format of the comparators used by the databases.          *
  *  DBHasher     - Format of the hashers used by the databases.              *
  *  DBReleaser   - Format of the releasers used by the databases.            *
+ *  DBIterator   - Database iterator.                                        *
  *  DBMap        - Database interface.                                       *
 \*****************************************************************************/
 
@@ -246,11 +248,99 @@ typedef void (*DBReleaser)(DBKey key, void* data, DBRelease which);
 
 
 
+typedef struct DBIterator DBIterator;
 typedef struct DBMap DBMap;
 
 
 
 /**
+ * Database iterator.
+ * Supports forward iteration, backward iteration and removing entries from the database.
+ * The iterator is initially positioned before the first entry of the database.
+ * While the iterator exists the database is locked internally, so invoke 
+ * {@link DBIterator#destroy} as soon as possible.
+ * @public
+ * @see #DBMap
+ */
+struct DBIterator
+{
+
+	/**
+	 * Fetches the first entry in the database.
+	 * Returns the data of the entry.
+	 * Puts the key in out_key, if out_key is not NULL.
+	 * @param self Iterator
+	 * @param out_key Key of the entry
+	 * @return Data of the entry
+	 * @protected
+	 */
+	void* (*first)(DBIterator* self, DBKey* out_key);
+
+	/**
+	 * Fetches the last entry in the database.
+	 * Returns the data of the entry.
+	 * Puts the key in out_key, if out_key is not NULL.
+	 * @param self Iterator
+	 * @param out_key Key of the entry
+	 * @return Data of the entry
+	 * @protected
+	 */
+	void* (*last)(DBIterator* self, DBKey* out_key);
+
+	/**
+	 * Fetches the next entry in the database.
+	 * Returns the data of the entry.
+	 * Puts the key in out_key, if out_key is not NULL.
+	 * @param self Iterator
+	 * @param out_key Key of the entry
+	 * @return Data of the entry
+	 * @protected
+	 */
+	void* (*next)(DBIterator* self, DBKey* out_key);
+
+	/**
+	 * Fetches the previous entry in the database.
+	 * Returns the data of the entry.
+	 * Puts the key in out_key, if out_key is not NULL.
+	 * @param self Iterator
+	 * @param out_key Key of the entry
+	 * @return Data of the entry
+	 * @protected
+	 */
+	void* (*prev)(DBIterator* self, DBKey* out_key);
+
+	/**
+	 * Returns true if the fetched entry exists.
+	 * The databases entries might have NULL data, so use this to to test if 
+	 * the iterator is done.
+	 * @param self Iterator
+	 * @return true is the entry exists
+	 * @protected
+	 */
+	bool (*exists)(DBIterator* self);
+
+	/**
+	 * Removes the current entry from the database.
+	 * NOTE: {@link DBIterator#exists} will return false until another entry 
+	 *       is fethed
+	 * Returns the data of the entry.
+	 * @param self Iterator
+	 * @return The data of the entry or NULL if not found
+	 * @protected
+	 * @see DBMap#remove
+	 */
+	void* (*remove)(DBIterator* self);
+
+	/**
+	 * Destroys this iterator and unlocks the database.
+	 * @param self Iterator
+	 * @protected
+	 */
+	void (*destroy)(DBIterator* self);
+
+};
+
+/**
  * Public interface of a database. Only contains funtions.
  * All the functions take the interface as the first argument.
  * @public
@@ -259,6 +349,17 @@ typedef struct DBMap DBMap;
 struct DBMap {
 
 	/**
+	 * 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 
+	 * memory when unlocked, so destroy the iterator as soon as possible.
+	 * @param self Database
+	 * @return New iterator
+	 * @protected
+	 */
+	DBIterator* (*iterator)(DBMap* self);
+
+	/**
 	 * Get the data of the entry identifid by the key.
 	 * @param self Database
 	 * @param key Key that identifies the entry