diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/common/db.c | 342 | ||||
| -rw-r--r-- | src/common/db.h | 101 |
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 |