SCI: Removed sbtree code by Common::Hashmap

svn-id: r39439

7 files changed, 57 insertions, 741 deletions

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<int, gfx_resource_t *> 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<void *>(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 *) &params, 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 *)&params, 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 *) &params, 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 *) &params, 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 <jameson@linuxgames.com>\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 \