From c5e8c48c5e1a4c3af266a71c500f57c2f93c42d3 Mon Sep 17 00:00:00 2001 From: Max Horn Date: Mon, 16 Mar 2009 05:44:20 +0000 Subject: SCI: Removed sbtree code by Common::Hashmap svn-id: r39439 --- engines/sci/gfx/gfx_resmgr.h | 20 +- engines/sci/gfx/gfx_test.cpp | 26 -- engines/sci/gfx/resmgr.cpp | 186 ++++---------- engines/sci/gfx/resource/res_manager.cpp | 40 --- engines/sci/gfx/sbtree.cpp | 424 ------------------------------- engines/sci/gfx/sbtree.h | 101 -------- engines/sci/module.mk | 1 - 7 files changed, 57 insertions(+), 741 deletions(-) delete mode 100644 engines/sci/gfx/sbtree.cpp delete mode 100644 engines/sci/gfx/sbtree.h (limited to 'engines') diff --git a/engines/sci/gfx/gfx_resmgr.h b/engines/sci/gfx/gfx_resmgr.h index 21bbf517b8..df6484627e 100644 --- a/engines/sci/gfx/gfx_resmgr.h +++ b/engines/sci/gfx/gfx_resmgr.h @@ -31,9 +31,10 @@ // or something like that. #include "sci/gfx/gfx_resource.h" -#include "sci/gfx/sbtree.h" #include "sci/scicore/resource.h" +#include "common/hashmap.h" + namespace Sci { struct gfx_bitmap_font_t; @@ -81,6 +82,8 @@ struct gfx_resource_t { struct gfx_options_t; +typedef Common::HashMap IntResMap; + struct gfx_resstate_t { int version; /* Interpreter version */ gfx_options_t *options; @@ -92,7 +95,7 @@ struct gfx_resstate_t { */ int tag_lock_counter; /* lock counter value at tag time */ - sbtree_t *resource_trees[GFX_RESOURCE_TYPES_NR]; + IntResMap _resourceMaps[GFX_RESOURCE_TYPES_NR]; ResourceManager *resManager; }; @@ -238,19 +241,6 @@ int gfxr_interpreter_options_hash(gfx_resource_type_t type, int version, ** (Yes, this isn't really a "hash" in the traditional sense...) */ -int *gfxr_interpreter_get_resources(ResourceManager& resourceManager, gfx_resource_type_t type, - int version, int *entries_nr); -/* Retreives all resources of a specified type that are available from the interpreter -** Parameters: (gfx_resstate_t *) state: The relevant resource state -** (gfx_respirce_type_t) type: The resource type to query -** (int) version: The interpreter version -** (int *) entries_nr: The variable the number of entries will eventually be stored in -** Returns : (int *) An array of resource numbers -** Unsupported/non-existing resources should return NULL here; this is equivalent to supported -** resources of which zero are available. -** The returned structure (if non-zero) must be freed by the querying code (the resource manager). -*/ - gfxr_pic_t *gfxr_interpreter_init_pic(int version, gfx_mode_t *mode, int ID); /* Initializes a pic ** Parameters: (int) version: Interpreter version to use diff --git a/engines/sci/gfx/gfx_test.cpp b/engines/sci/gfx/gfx_test.cpp index cec4bb50c0..68d3852373 100644 --- a/engines/sci/gfx/gfx_test.cpp +++ b/engines/sci/gfx/gfx_test.cpp @@ -183,32 +183,6 @@ int *arrdup(int *src, int count) { return retval; } -int *gfxr_interpreter_get_resources(gfx_resstate_t *resstate, gfx_resource_type_t type, - int version, int *entries_nr, void *internal) { - switch (type) { - - case GFX_RESOURCE_TYPE_VIEW: - *entries_nr = TEST_VIEWS_NR; - return arrdup(test_views, TEST_VIEWS_NR); - - case GFX_RESOURCE_TYPE_PIC: - *entries_nr = TEST_PICS_NR; - return arrdup(test_pics, TEST_PICS_NR); - - case GFX_RESOURCE_TYPE_FONT: - *entries_nr = TEST_FONTS_NR; - return arrdup(test_fonts, TEST_FONTS_NR); - - case GFX_RESOURCE_TYPE_CURSOR: - *entries_nr = TEST_CURSORS_NR; - return arrdup(test_cursors, TEST_CURSORS_NR); - - default: - fprintf(stderr, "Attept to get resource list for invalid resource type %d\n", type); - return NULL; - } -} - #define PIC_COLORS_NR 32 gfx_pixmap_color_t pic_colors[PIC_COLORS_NR] = { diff --git a/engines/sci/gfx/resmgr.cpp b/engines/sci/gfx/resmgr.cpp index a42ff298c7..1c6e50da2a 100644 --- a/engines/sci/gfx/resmgr.cpp +++ b/engines/sci/gfx/resmgr.cpp @@ -51,8 +51,7 @@ struct param_struct { }; gfx_resstate_t *gfxr_new_resource_manager(int version, gfx_options_t *options, gfx_driver_t *driver, ResourceManager *resManager) { - gfx_resstate_t *state = (gfx_resstate_t *)sci_malloc(sizeof(gfx_resstate_t)); - int ii; + gfx_resstate_t *state = new gfx_resstate_t(); state->version = version; state->options = options; @@ -61,23 +60,6 @@ gfx_resstate_t *gfxr_new_resource_manager(int version, gfx_options_t *options, g state->static_palette = 0; state->tag_lock_counter = state->lock_counter = 0; - for (ii = 0; ii < GFX_RESOURCE_TYPES_NR; ii++) { - gfx_resource_type_t i = (gfx_resource_type_t) ii; - sbtree_t *tree; - int entries_nr; - int *resources = gfxr_interpreter_get_resources(*(state->resManager), i, version, &entries_nr); - - if (!resources) - state->resource_trees[i] = NULL; - else { - tree = sbtree_new(entries_nr, resources); - if (!tree) { - GFXWARN("Failed to allocate tree for %d entries of resource type %d!\n", entries_nr, i); - } - state->resource_trees[i] = tree; - free(resources); - } - } return state; } @@ -127,78 +109,18 @@ void gfxr_free_resource(gfx_driver_t *driver, gfx_resource_t *resource, int type free(resource); } -#undef FREECMD - -void *gfxr_sbtree_free_func(sbtree_t *tree, const int key, const void *value, void *args) { - struct param_struct *params = (struct param_struct *) args; - int type = params->args[0]; - gfx_driver_t *driver = params->driver; - - if (value) - gfxr_free_resource(driver, (gfx_resource_t *) value, type); - - return NULL; -} - -#define SBTREE_FREE_TAGGED_ARG_TYPE 0 -#define SBTREE_FREE_TAGGED_ARG_TAGVALUE 1 -#define SBTREE_FREE_TAGGED_ARG_ACTION 2 - -#define ARG_ACTION_RESET 0 -#define ARG_ACTION_DECREMENT 1 - -void *gfxr_sbtree_free_tagged_func(sbtree_t *tree, const int key, const void *value, void *args) { - struct param_struct *params = (struct param_struct *) args; - int type = params->args[SBTREE_FREE_TAGGED_ARG_TYPE]; - int tag_value = params->args[SBTREE_FREE_TAGGED_ARG_TAGVALUE]; - int action = params->args[SBTREE_FREE_TAGGED_ARG_ACTION]; - gfx_driver_t *driver = params->driver; - gfx_resource_t *resource = (gfx_resource_t *) value; - if (resource) { - if (resource->lock_sequence_nr < tag_value) { - gfxr_free_resource(driver, (gfx_resource_t *) value, type); - return NULL; - } else { - if (action == ARG_ACTION_RESET) - resource->lock_sequence_nr = 0; - else - (resource->lock_sequence_nr)--; - // FIXME: const_cast does not sound like a good idea, - // maybe we should just make the value parameter - // non const instead? - return const_cast(value); - } - } else - return NULL; -} - void gfxr_free_all_resources(gfx_driver_t *driver, gfx_resstate_t *state) { - struct param_struct params; - int i; - sbtree_t *tree = NULL; - - for (i = 0; i < GFX_RESOURCE_TYPES_NR; i++) - if ((tree = state->resource_trees[i])) { - params.args[0] = i; - params.driver = driver; - sbtree_foreach(tree, (void *) ¶ms, gfxr_sbtree_free_func); + for (int type = 0; type < GFX_RESOURCE_TYPES_NR; ++type) { + for (IntResMap::iterator iter = state->_resourceMaps[type].begin(); iter != state->_resourceMaps[type].end(); ++iter) { + gfxr_free_resource(driver, iter->_value, type); + iter->_value = 0; } + } } void gfxr_free_resource_manager(gfx_driver_t *driver, gfx_resstate_t *state) { - struct param_struct params; - int i; - sbtree_t *tree = NULL; - - for (i = 0; i < GFX_RESOURCE_TYPES_NR; i++) - if ((tree = state->resource_trees[i])) { - params.args[0] = i; - params.driver = driver; - sbtree_foreach(tree, (void *)¶ms, gfxr_sbtree_free_func); - sbtree_free(tree); - } - - free(state); + gfxr_free_all_resources(driver, state); + delete state; } void gfxr_tag_resources(gfx_resstate_t *state) { @@ -207,22 +129,37 @@ void gfxr_tag_resources(gfx_resstate_t *state) { void gfxr_free_tagged_resources(gfx_driver_t *driver, gfx_resstate_t *state) { // Current heuristics: free tagged views and old pics - struct param_struct params; - - if (state->resource_trees[GFX_RESOURCE_TYPE_VIEW]) { - params.args[SBTREE_FREE_TAGGED_ARG_TYPE] = GFX_RESOURCE_TYPE_VIEW; - params.args[SBTREE_FREE_TAGGED_ARG_TAGVALUE] = state->tag_lock_counter; - params.args[SBTREE_FREE_TAGGED_ARG_ACTION] = ARG_ACTION_RESET; - params.driver = driver; - sbtree_foreach(state->resource_trees[GFX_RESOURCE_TYPE_VIEW], (void *) ¶ms, gfxr_sbtree_free_tagged_func); + + IntResMap::iterator iter; + int type; + const int tmp = state->tag_lock_counter; + + type = GFX_RESOURCE_TYPE_VIEW; + for (iter = state->_resourceMaps[type].begin(); iter != state->_resourceMaps[type].end(); ++iter) { + gfx_resource_t *resource = iter->_value; + + if (resource) { + if (resource->lock_sequence_nr < tmp) { + gfxr_free_resource(driver, resource, type); + iter->_value = 0; + } else { + resource->lock_sequence_nr = 0; + } + } } - if (state->resource_trees[GFX_RESOURCE_TYPE_PIC]) { - params.args[SBTREE_FREE_TAGGED_ARG_TYPE] = GFX_RESOURCE_TYPE_PIC; - params.args[SBTREE_FREE_TAGGED_ARG_TAGVALUE] = 0; - params.args[SBTREE_FREE_TAGGED_ARG_ACTION] = ARG_ACTION_DECREMENT; - params.driver = driver; - sbtree_foreach(state->resource_trees[GFX_RESOURCE_TYPE_PIC], (void *) ¶ms, gfxr_sbtree_free_tagged_func); + type = GFX_RESOURCE_TYPE_PIC; + for (iter = state->_resourceMaps[type].begin(); iter != state->_resourceMaps[type].end(); ++iter) { + gfx_resource_t *resource = iter->_value; + + if (resource) { + if (resource->lock_sequence_nr < 0) { + gfxr_free_resource(driver, resource, type); + iter->_value = 0; + } else { + resource->lock_sequence_nr--; + } + } } state->tag_lock_counter = 0; @@ -257,18 +194,15 @@ static gfxr_pic_t *gfxr_pic_xlate_common(gfx_resource_t *res, int maps, int scal gfxr_pic_t *gfxr_get_pic(gfx_resstate_t *state, int nr, int maps, int flags, int default_palette, int scaled) { gfxr_pic_t *npic = NULL; gfx_resource_type_t restype = GFX_RESOURCE_TYPE_PIC; - sbtree_t *tree = state->resource_trees[restype]; + IntResMap &resMap = state->_resourceMaps[restype]; gfx_resource_t *res = NULL; int hash = gfxr_interpreter_options_hash(restype, state->version, state->options, 0); int must_post_process_pic = 0; int need_unscaled = (state->driver->mode->xfact != 1 || state->driver->mode->yfact != 1); - if (!tree) - return NULL; - hash |= (flags << 20) | ((default_palette & 0x7) << 28); - res = (gfx_resource_t *) sbtree_get(tree, nr); + res = resMap.contains(nr) ? resMap[nr] : NULL; if (!res || res->mode != hash) { gfxr_pic_t *pic; @@ -317,7 +251,7 @@ gfxr_pic_t *gfxr_get_pic(gfx_resstate_t *state, int nr, int maps, int flags, int res = (gfx_resource_t *)sci_malloc(sizeof(gfx_resource_t)); res->ID = GFXR_RES_ID(restype, nr); res->lock_sequence_nr = state->options->buffer_pics_nr; - sbtree_set(tree, nr, (void *)res); + resMap[nr] = res; } else { gfxr_free_pic(state->driver, res->scaled_data.pic); if (res->unscaled_data.pic) @@ -395,23 +329,18 @@ static void _gfxr_unscale_pixmap_index_data(gfx_pixmap_t *pxm, gfx_mode_t *mode) gfxr_pic_t *gfxr_add_to_pic(gfx_resstate_t *state, int old_nr, int new_nr, int maps, int flags, int old_default_palette, int default_palette, int scaled) { gfx_resource_type_t restype = GFX_RESOURCE_TYPE_PIC; - sbtree_t *tree = state->resource_trees[restype]; + IntResMap &resMap = state->_resourceMaps[restype]; gfxr_pic_t *pic = NULL; gfx_resource_t *res = NULL; int hash = gfxr_interpreter_options_hash(restype, state->version, state->options, 0); int need_unscaled = !(state->options->pic0_unscaled) && (state->driver->mode->xfact != 1 || state->driver->mode->yfact != 1); - if (!tree) { - GFXERROR("No pics registered\n"); - return NULL; - } - - res = (gfx_resource_t *)sbtree_get(tree, old_nr); + res = resMap.contains(old_nr) ? resMap[old_nr] : NULL; if (!res || (res->mode != MODE_INVALID && res->mode != hash)) { gfxr_get_pic(state, old_nr, 0, flags, old_default_palette, scaled); - res = (gfx_resource_t *)sbtree_get(tree, old_nr); + res = resMap.contains(old_nr) ? resMap[old_nr] : NULL; if (!res) { GFXWARN("Attempt to add pic %d to non-existing pic %d\n", new_nr, old_nr); @@ -446,17 +375,14 @@ gfxr_pic_t *gfxr_add_to_pic(gfx_resstate_t *state, int old_nr, int new_nr, int m gfxr_view_t *gfxr_get_view(gfx_resstate_t *state, int nr, int *loop, int *cel, int palette) { gfx_resource_type_t restype = GFX_RESOURCE_TYPE_VIEW; - sbtree_t *tree = state->resource_trees[restype]; + IntResMap &resMap = state->_resourceMaps[restype]; gfx_resource_t *res = NULL; int hash = gfxr_interpreter_options_hash(restype, state->version, state->options, palette); gfxr_view_t *view = NULL; gfxr_loop_t *loop_data = NULL; gfx_pixmap_t *cel_data = NULL; - if (!tree) - return NULL; - - res = (gfx_resource_t *) sbtree_get(tree, nr); + res = resMap.contains(nr) ? resMap[nr] : NULL; if (!res || res->mode != hash) { view = gfxr_interpreter_get_view(*(state->resManager), nr, palette, state->static_palette, state->version); @@ -470,7 +396,7 @@ gfxr_view_t *gfxr_get_view(gfx_resstate_t *state, int nr, int *loop, int *cel, i res->ID = GFXR_RES_ID(restype, nr); res->lock_sequence_nr = state->tag_lock_counter; res->mode = hash; - sbtree_set(tree, nr, (void *)res); + resMap[nr] = res; } else { gfxr_free_view(state->driver, res->unscaled_data.view); } @@ -529,18 +455,13 @@ gfxr_view_t *gfxr_get_view(gfx_resstate_t *state, int nr, int *loop, int *cel, i gfx_bitmap_font_t *gfxr_get_font(ResourceManager& resourceManager, gfx_resstate_t *state, int nr, int scaled) { gfx_resource_type_t restype = GFX_RESOURCE_TYPE_FONT; - sbtree_t *tree = NULL; + IntResMap &resMap = state->_resourceMaps[restype]; gfx_resource_t *res = NULL; int hash; - tree = state->resource_trees[restype]; - hash = gfxr_interpreter_options_hash(restype, state->version, state->options, 0); - if (!tree) - return NULL; - - res = (gfx_resource_t *)sbtree_get(tree, nr); + res = resMap.contains(nr) ? resMap[nr] : NULL; if (!res || res->mode != hash) { gfx_bitmap_font_t *font = gfxr_interpreter_get_font(resourceManager, nr); @@ -554,7 +475,7 @@ gfx_bitmap_font_t *gfxr_get_font(ResourceManager& resourceManager, gfx_resstate_ res->ID = GFXR_RES_ID(restype, nr); res->lock_sequence_nr = state->tag_lock_counter; res->mode = hash; - sbtree_set(tree, nr, (void *)res); + resMap[nr] = res; } else { gfxr_free_font(res->unscaled_data.font); } @@ -573,14 +494,11 @@ gfx_bitmap_font_t *gfxr_get_font(ResourceManager& resourceManager, gfx_resstate_ gfx_pixmap_t *gfxr_get_cursor(gfx_resstate_t *state, int nr) { gfx_resource_type_t restype = GFX_RESOURCE_TYPE_CURSOR; - sbtree_t *tree = state->resource_trees[restype]; + IntResMap &resMap = state->_resourceMaps[restype]; gfx_resource_t *res = NULL; int hash = gfxr_interpreter_options_hash(restype, state->version, state->options, 0); - if (!tree) - return NULL; - - res = (gfx_resource_t *)sbtree_get(tree, nr); + res = resMap.contains(nr) ? resMap[nr] : NULL; if (!res || res->mode != hash) { gfx_pixmap_t *cursor = gfxr_interpreter_get_cursor(*(state->resManager), nr, state->version); @@ -594,7 +512,7 @@ gfx_pixmap_t *gfxr_get_cursor(gfx_resstate_t *state, int nr) { res->ID = GFXR_RES_ID(restype, nr); res->lock_sequence_nr = state->tag_lock_counter; res->mode = hash; - sbtree_set(tree, nr, (void *)res); + resMap[nr] = res; } else { gfx_free_pixmap(state->driver, res->unscaled_data.pointer); } diff --git a/engines/sci/gfx/resource/res_manager.cpp b/engines/sci/gfx/resource/res_manager.cpp index dc264b74fd..e11fe188d0 100644 --- a/engines/sci/gfx/resource/res_manager.cpp +++ b/engines/sci/gfx/resource/res_manager.cpp @@ -202,46 +202,6 @@ gfx_pixmap_t *gfxr_interpreter_get_cursor(ResourceManager& resourceManager, int return gfxr_draw_cursor(resid, res->data, res->size, version != SCI_VERSION_0); } -int *gfxr_interpreter_get_resources(ResourceManager& resourceManager, gfx_resource_type_t type, int version, int *entries_nr) { - ResourceType restype; - int *resources; - int count = 0; - int top = sci_max_resource_nr[version] + 1; - int i; - switch (type) { - - case GFX_RESOURCE_TYPE_VIEW: - restype = kResourceTypeView; - break; - - case GFX_RESOURCE_TYPE_PIC: - restype = kResourceTypePic; - break; - - case GFX_RESOURCE_TYPE_CURSOR: - restype = kResourceTypeCursor; - break; - - case GFX_RESOURCE_TYPE_FONT: - restype = kResourceTypeFont; - break; - - default: - GFXDEBUG("Unsupported resource %d\n", type); - return NULL; - } - - resources = (int *)sci_malloc(sizeof(int) * top); - - for (i = 0; i < top; i++) - if (resourceManager.testResource(restype, i)) - resources[count++] = i; - - *entries_nr = count; - - return resources; -} - Palette *gfxr_interpreter_get_static_palette(ResourceManager& resourceManager, int version, int *colors_nr) { if (version >= SCI_VERSION_01_VGA) return gfxr_interpreter_get_palette(resourceManager, version, colors_nr, 999); diff --git a/engines/sci/gfx/sbtree.cpp b/engines/sci/gfx/sbtree.cpp deleted file mode 100644 index 711d7a9bb9..0000000000 --- a/engines/sci/gfx/sbtree.cpp +++ /dev/null @@ -1,424 +0,0 @@ -/* ScummVM - Graphic Adventure Engine - * - * ScummVM is the legal property of its developers, whose names - * are too numerous to list here. Please refer to the COPYRIGHT - * file distributed with this source distribution. - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * $URL$ - * $Id$ - * - */ - -// Static binary lookup tree lookup - - -#include "sci/sci_memory.h" -#include "sci/gfx/sbtree.h" - -namespace Sci { - -#define NOT_A_KEY -1 - -struct sbcell_t { - int key; - void *value; -}; - -int int_compar(const void *a, const void *b) { - return (*((int *)a)) - (*((int *)b)); -} - -void insert_interval(sbcell_t *data, int start, int stop, int *keys, int plus) { - int center = start + ((stop - start) >> 1); - - data->key = keys[center]; - - if (start == stop) - return; - - if (center > start) - insert_interval(data + plus, start, center - 1, keys, plus << 1); - - if (center < stop) - insert_interval(data + plus + 1, center + 1, stop, keys, ((plus << 1) + 1)); -} - -sbtree_t *sbtree_new(int size, int *keys) { - int table_size = 2; - int levels = 0; - sbcell_t *table; - sbtree_t *tree; - int i; - - if (size < 0) - return NULL; - - while (table_size <= size) { - table_size <<= 1; - ++levels; - } - - if (table_size > 1) - --table_size; - - table = (sbcell_t *)sci_calloc(sizeof(sbcell_t), table_size); - for (i = 0; i < table_size; i++) - table[i].key = NOT_A_KEY; - - if (!table) { - fprintf(stderr, "SBTree: Out of memory: Could not allocate %d cells\n", table_size); - return NULL; - } - - tree = (sbtree_t *)sci_malloc(sizeof(sbtree_t)); - - if (!tree) { - fprintf(stderr, "SBTree: Could not allocate tree structure\n"); - free(table); - return NULL; - } - - qsort(keys, size, sizeof(int), int_compar); - - insert_interval(table, 0, size - 1, keys, 1); - - tree->levels = levels; - tree->entries_nr = size; - if ((tree->min_entry = keys[0]) < 0) { - fprintf(stderr, "SBTree: Error: Using negative keys\n"); - free(table); - free(tree); - return NULL; - } - tree->max_entry = keys[size - 1]; - tree->data = (void *) table; - tree->alloced_entries = table_size; - return tree; -} - -void sbtree_free(sbtree_t *tree) { - if (!tree) { - fprintf(stderr, "SBTree: Attempt to free NULL sbtree\n"); - return; - } - - free(tree->data); - free(tree); -} - -void sbtree_foreach(sbtree_t *tree, void *args, void *(*operation)(sbtree_t *, const int, const void *, void *)) { - int i; - sbcell_t *cell = (sbcell_t *) tree->data; - - for (i = 0; i < tree->alloced_entries; i++) { - if (cell->key != NOT_A_KEY) - cell->value = operation(tree, cell->key, cell->value, args); - cell = cell + 1; - } -} - -sbcell_t *locate(sbcell_t *start, int key, int level, int levels, int plus) { - int comparison; - - if (level >= levels && (level != levels || start->key == NOT_A_KEY)) - // For large tables, the speed improvement caused by this comparison - // scheme is almost (cough) measurable... - return NULL; - - comparison = key - start->key; - - if (!comparison) - return start; - - return locate(start + plus + (comparison > 0), key, level + 1, levels, (plus << 1) + (comparison > 0)); -} - -int sbtree_set(sbtree_t *tree, int key, void *value) { - sbcell_t *cell = locate((sbcell_t *) tree->data, key, 0, tree->levels, 1); - - if (cell) - cell->value = value; - else - return -1; - - return 0; -} - -void *sbtree_get(sbtree_t *tree, int key) { - sbcell_t *cell = locate((sbcell_t *) tree->data, key, 0, tree->levels, 1); - - if (cell) - return cell->value; - else - return NULL; -} - -#if 0 -static void sbtree_print(sbtree_t *tree) { - int l, i; - sbcell_t *cells = (sbcell_t *)tree->data; - - fprintf(stderr, "\tTree:\n"); - for (l = 0; l <= tree->levels; l++) { - fprintf(stderr, "\t "); - for (i = 0; i < (1 << l); i++) { - if (cells->key == NOT_A_KEY) - fprintf(stderr, "-- "); - else { - if (cells->value) - fprintf(stderr, "%d+ ", cells->key); - else - fprintf(stderr, "%d ", cells->key); - } - - cells = cells + 1; - } - fprintf(stderr, "\n"); - } - fprintf(stderr, "\n"); -} -#endif - -//**************************** TEST CODE ******************************* - - -#ifdef SBTREE_DEBUG - -static int any_error; - -void *foreach_double_func(sbtree_t *tree, const int key, const void *value, void *args) { - int *real_value = (int *) value; - - if (!real_value) - fprintf(stderr, "foreach_double_func(): key %d mapped to non-value!\n", key); - else - *real_value *= 2; - - return real_value; -} - -int *generate_linear_forward(int numbers) { - int i; - int *data = sci_malloc(sizeof(int) * numbers); - - for (i = 0; i < numbers; i++) - data[i] = i + 1; - - return data; -} - -int *generate_linear_backward(int numbers) { - int i; - int *data = sci_malloc(sizeof(int) * numbers); - - for (i = 0; i < numbers; i++) - data[i] = numbers - i; - - return data; -} - -int *generate_random(int numbers, int max) { - int i; - int *data = sci_malloc(sizeof(int) * numbers); - - for (i = 0; i < numbers; i++) - data[i] = 1 + (int)((rand() * 1.0 * max) / (RAND_MAX + 1.0)); - - return data; -} - -void insert_values(sbtree_t *tree, int nr, int *data) { - int i; - - for (i = 0; i < nr; i++) - if (sbtree_set(tree, data[i], (void *)(data + i))) { - fprintf(stderr, "While inserting: %d incorrectly deemed invalid\n", data[i]); - any_error = 1; - } -} - -#define MODE_LINEAR 0 -#define MODE_LINEAR_MAP 1 -#define MODE_RANDOM 2 -#define MODE_LINEAR_DOUBLE 3 - -void test_value(sbtree_t *tree, int times, int max, int numbers, int *data, int mode) { - int i; - int failed = 0; - - for (i = 0; i < times; i++) { - int key = (mode == MODE_LINEAR || mode == MODE_LINEAR_DOUBLE) ? i : - (mode == MODE_LINEAR_MAP) ? data[i % numbers] : - (int)((rand() * 1.0 * max) / (RAND_MAX + 1.0)); - int *value = (int *) sbtree_get(tree, (mode == MODE_LINEAR_DOUBLE) ? key >> 1 : key); - int found = 0; - int j; - - for (j = 0; j < numbers && !found; j++) - if (data[j] == key) - found = 1; - - if (found && !value) { - fprintf(stderr, "!%d ", key); - ++failed; - } else if (!found && found) { - fprintf(stderr, "?[%d]=%d ", key, *value); - ++failed; - } - } - - if (failed) - fprintf(stderr, "(%d/%d errors)\n", any_error = failed, times); - else - fprintf(stderr, "OK\n"); -} - -void test_boundary(sbtree_t *tree, int max, int random) { - int *value_too_low = sbtree_get(tree, 0); - int *value_too_high = sbtree_get(tree, max + 1); - int *value_low = sbtree_get(tree, 1); - int *value_high = sbtree_get(tree, max); - int failure = (value_too_low || value_too_high || (!random && (!value_low || !value_high))); - - if (!failure) - fprintf(stderr, "OK\n"); - else { - any_error = 1; - - fprintf(stderr, "Errors: "); - if (value_too_low) - fprintf(stderr, "too-low=%d ", *value_too_low); - if (value_too_high) - fprintf(stderr, "too-high=%d ", *value_too_high); - - if (!random) { - if (!value_low) - fprintf(stderr, "!low "); - if (!value_high) - fprintf(stderr, "!high "); - } - fprintf(stderr, "\n"); - } -} - -void test_empty(sbtree_t *tree, int count, int max) { - int i; - int errors = 0; - - for (i = 0; i < count; i++) { - int key = 1 + (int)((rand() * 1.0 * max) / (RAND_MAX + 1.0)); - int *value; - - if ((value = (int *) sbtree_get(tree, key))) { - fprintf(stderr, "?[%d]=%d\n", key, *value); - ++errors; - } - } - - if (errors) - fprintf(stderr, " (%d/%d errors)\n", any_error = errors, count); - else - fprintf(stderr, "OK\n"); -} - -void run_test(sbtree_t *tree, int entries, int *data, int random, int max_value) { - char *tests[] = {"\tLinear reference test: \t\t", "\tKey map reference test: \t", "\tRandom access test: \t\t"}; - int i; - - any_error = 0; - - fprintf(stderr, "\tEmpty test: \t\t\t"); - test_empty(tree, entries * 2, entries + 1); - insert_values(tree, entries, data); - fprintf(stderr, "\tBoundary test: \t\t\t"); - test_boundary(tree, max_value, random); - - for (i = 0; i < 3; i++) { - fprintf(stderr, tests[i]); - test_value(tree, entries * 2, entries * 2, entries, data, i); - } - - if (!random) { - i = data[0]; - sbtree_foreach(tree, NULL, foreach_double_func); - fprintf(stderr, "\tForeach test: \t\t\t"); - if (i * 2 != data[0]) { - fprintf(stderr, "Error: No effect: %d * 2 != %d\n", i, data[0]); - any_error = 1; - } else - test_value(tree, entries * 2, entries * 2, entries, data, MODE_LINEAR_DOUBLE); - } - - if (any_error) - sbtree_print(tree); - - free(data); - sbtree_free(tree); -} - -#define TESTS_NR 11 - -int main(int argc, char **argv) { - int tests_nr = TESTS_NR; - int test_sizes[TESTS_NR] = {1, 2, 3, 7, 8, 9, 1000, 16383, 16384, 16385, 1000000}; - int i; - fprintf(stderr, "sbtree.c Copyright (C) 2000 Christoph Reichenbach \n" - "This program is provided WITHOUT WARRANTY of any kind\n" - "Please refer to the file COPYING that should have come with this program\n"); - fprintf(stderr, "Static Binary Tree testing facility\n"); - - free(malloc(42)); // Make sure libefence's Copyright message is print here if we're using it - - fprintf(stderr, "\nsbtree.c: Running %d tests.\n", tests_nr); - - for (i = 0; i < tests_nr; i++) { - int entries = test_sizes[i]; - sbtree_t *tree; - int *data; - - fprintf(stderr, "Test #%d: %d entries\n", i + 1, entries); - - fprintf(stderr, "\t%da: Linear values\n", i + 1); - data = generate_linear_forward(entries); - tree = sbtree_new(entries, data); - run_test(tree, entries, data, 0, entries); - - fprintf(stderr, "\t%db: Reverse linear values\n", i + 1); - data = generate_linear_backward(entries); - tree = sbtree_new(entries, data); - run_test(tree, entries, data, 0, entries); - - fprintf(stderr, "\t%dc: Dense random values\n", i + 1); - data = generate_random(entries, 1 + (entries >> 2)); - tree = sbtree_new(entries, data); - run_test(tree, entries, data, 1, 1 + (entries >> 2)); - - fprintf(stderr, "\t%dc: Sparse random values\n", i + 1); - data = generate_random(entries, (entries << 2)); - tree = sbtree_new(entries, data); - run_test(tree, entries, data, 1, entries << 2); - - fprintf(stderr, "Test #%d completed.\n\n", i + 1); - } - - fprintf(stderr, "Test suite completed.\n"); - return 0; -} - -#endif // SBTREE_DEBUG - -} // End of namespace Sci diff --git a/engines/sci/gfx/sbtree.h b/engines/sci/gfx/sbtree.h deleted file mode 100644 index c00c543e72..0000000000 --- a/engines/sci/gfx/sbtree.h +++ /dev/null @@ -1,101 +0,0 @@ -/* ScummVM - Graphic Adventure Engine - * - * ScummVM is the legal property of its developers, whose names - * are too numerous to list here. Please refer to the COPYRIGHT - * file distributed with this source distribution. - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version 2 - * of the License, or (at your option) any later version. - - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * $URL$ - * $Id$ - * - */ - -/* Static binary tree header file */ - -/* Static binary trees are used to link ints to pointers. They are not capable -** of resizing after being initialized. -*/ - -#ifndef SCI_GFX_GFX_SBTREE_H -#define SCI_GFX_GFX_SBTREE_H - -namespace Sci { - -struct sbtree_t { - int entries_nr; - int min_entry; - int max_entry; - int levels; - int alloced_entries; - void *data; -}; - - -sbtree_t *sbtree_new(int size, int *keys); -/* Generates a new sbtree with the specified key set -** Parameters: (int) size: Number of entries in 'keys' -** (int *) keys: Array of 'size' integer keys -** Returns : (sbtree_t *) A new sbtree -** Only positive keys are allowed. Duplicates are not detected and will -** cause additional memory usage and slower access times if not removed -** beforehand. -*/ - -void sbtree_free(sbtree_t *tree); -/* Frees an sbtree -** Parameters: (sbtree_t *) tree: The tree to free -** Returns : (void) Nothing at all -*/ - -int sbtree_set(sbtree_t *tree, int key, void *value); -/* Sets a key to a value -** Parameters: (sbtree_t *) tree: The tree to modify -** (int) key: The key to set -** (void *) value: The value part of the (key,value) tuple -** Returns : (int) 0 if everything went OK, -1 if the key was invalid -** value may, of course, be NULL here. -*/ - -void *sbtree_get(sbtree_t *tree, int key); -/* Retreives a key -** Parameters: (sbtree_t *) tree: The tree to search in -** (int) key: The key to retrieve -** Returns : (void *) The value mapped to the key -** If key was not found/invalid, NULL is returned. Note that there is no -** way of distinguishing between keys mapped to NULL and invalid keys, -** short of attempting to set that key. -*/ - -void sbtree_foreach(sbtree_t *tree, void *args, void *(*operation)(sbtree_t *, const int, - const void *, void *)); -/* Operates once on each entry in the tree -** Parameters: (sbtree_t *) tree: The tree to operate on -** (void *) arguments: Additional arguments to pass to 'operation' -** (int (int, void *, void *)) operation: The operation to execute -** Returns : (void) -** The parameters of the function that is to be executed are as follows: -** operation (sbtree_t *tree, int key, void *value, void *args) -** Parameters: (sbtree_t *) tree: The tree the operation was executed on -** (int) key: Key of the entry the operation was invoked on -** (void *) value: Value of the entry the operation was invoked on -** (void *) args: The 'args' parameter passed to sbtree_foreach() -** Returns : (void *) The new value of this entry -** This function will only work properly the original data contained no duplicate keys. -*/ - -} // End of namespace Sci - -#endif // SCI_GFX_GFX_SBTREE_H diff --git a/engines/sci/module.mk b/engines/sci/module.mk index 1efcfb9a9f..4d0eeee0d0 100644 --- a/engines/sci/module.mk +++ b/engines/sci/module.mk @@ -46,7 +46,6 @@ MODULE_OBJS = \ gfx/operations.o \ gfx/palette.o \ gfx/resmgr.o \ - gfx/sbtree.o \ gfx/sci_widgets.o \ gfx/resource/res_cursor.o \ gfx/resource/res_font.o \ -- cgit v1.2.3