[Scummvm-cvs-logs] SF.net SVN: scummvm:[38763] scummvm/trunk/engines/sci
fingolfin at users.sourceforge.net
fingolfin at users.sourceforge.net
Sat Feb 21 23:54:15 CET 2009
Revision: 38763
http://scummvm.svn.sourceforge.net/scummvm/?rev=38763&view=rev
Author: fingolfin
Date: 2009-02-21 22:54:15 +0000 (Sat, 21 Feb 2009)
Log Message:
-----------
SCI: Moved aatree.* files together into engine/
Modified Paths:
--------------
scummvm/trunk/engines/sci/engine/kpathing.cpp
scummvm/trunk/engines/sci/module.mk
Added Paths:
-----------
scummvm/trunk/engines/sci/engine/aatree.cpp
scummvm/trunk/engines/sci/engine/aatree.h
Removed Paths:
-------------
scummvm/trunk/engines/sci/include/aatree.h
scummvm/trunk/engines/sci/scicore/aatree.cpp
Copied: scummvm/trunk/engines/sci/engine/aatree.cpp (from rev 38760, scummvm/trunk/engines/sci/scicore/aatree.cpp)
===================================================================
--- scummvm/trunk/engines/sci/engine/aatree.cpp (rev 0)
+++ scummvm/trunk/engines/sci/engine/aatree.cpp 2009-02-21 22:54:15 UTC (rev 38763)
@@ -0,0 +1,162 @@
+/* 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$
+ *
+ */
+
+#include "sci/engine/aatree.h"
+
+#include "sci/include/sci_memory.h"
+
+namespace Sci {
+
+struct aatree {
+ struct aatree *left, *right;
+ int level;
+ void *key;
+};
+
+// Sentinel node
+static aatree_t bottom = {&bottom, &bottom, 0, NULL};
+
+static void skew(aatree_t **t) {
+ if ((*t)->left->level == (*t)->level) {
+ // Rotate right
+ aatree_t *temp = *t;
+ *t = (*t)->left;
+ temp->left = (*t)->right;
+ (*t)->right = temp;
+ }
+}
+
+static void split(aatree_t **t) {
+ if ((*t)->right->right->level == (*t)->level) {
+ // Rotate left
+ aatree_t *temp = *t;
+ *t = (*t)->right;
+ temp->right = (*t)->left;
+ (*t)->left = temp;
+ (*t)->level++;
+ }
+}
+
+static int delete_node(void *x, aatree_t **t, aatree_t *deleted, int (*compar)(const void *, const void *)) {
+ int retval = -1;
+
+ if (*t != &bottom) {
+ // Search down the tree
+ aatree_t **n;
+
+ if (compar(x, (*t)->key) < 0)
+ n = &(*t)->left;
+ else {
+ n = &(*t)->right;
+ deleted = *t;
+ }
+
+ retval = delete_node(x, n, deleted, compar);
+
+ // At the bottom of the tree we remove the element (if it is present)
+ if ((*n == &bottom) && (deleted != &bottom) && (compar(x, deleted->key) == 0)) {
+ aatree_t *temp;
+ deleted->key = (*t)->key;
+ temp = *t;
+ *t = (*t)->right;
+ free(temp);
+ retval = 0;
+ } else if (((*t)->left->level < (*t)->level - 1) || ((*t)->right->level < (*t)->level - 1)) {
+ (*t)->level--;
+ if ((*t)->right->level > (*t)->level)
+ (*t)->right->level = (*t)->level;
+ skew(t);
+ skew(&(*t)->right);
+ skew(&(*t)->right->right);
+ split(t);
+ split(&(*t)->right);
+ }
+ }
+
+ return retval;
+}
+
+aatree_t *aatree_new() {
+ return ⊥
+}
+
+int aatree_insert(void *x, aatree_t **t, int (*compar)(const void *, const void *)) {
+ int retval = -1;
+ int c;
+
+ if (*t == &bottom) {
+ *t = (aatree_t *)sci_malloc(sizeof(aatree_t));
+
+ if (*t == NULL)
+ return 1;
+
+ (*t)->key = x;
+ (*t)->left = ⊥
+ (*t)->right = ⊥
+ (*t)->level = 1;
+ return 0;
+ }
+
+ c = compar(x, (*t)->key);
+
+ if (c < 0)
+ retval = aatree_insert(x, &(*t)->left, compar);
+ else if (c > 0)
+ retval = aatree_insert(x, &(*t)->right, compar);
+
+ skew(t);
+ split(t);
+ return retval;
+}
+
+int aatree_delete(void *x, aatree_t **t, int (*compar)(const void *, const void *)) {
+ return delete_node(x, t, &bottom, compar);
+}
+
+aatree_t *aatree_walk(aatree_t *t, int direction) {
+ if ((direction == AATREE_WALK_LEFT) && (t->left != &bottom))
+ return t->left;
+
+ if ((direction == AATREE_WALK_RIGHT) && (t->right != &bottom))
+ return t->right;
+
+ return NULL;
+}
+
+void *aatree_get_data(aatree_t *t) {
+ return t->key;
+}
+
+void aatree_free(aatree_t *t) {
+ if (t == &bottom)
+ return;
+
+ aatree_free(t->left);
+ aatree_free(t->right);
+
+ free(t);
+}
+
+} // End of namespace Sci
Copied: scummvm/trunk/engines/sci/engine/aatree.h (from rev 38760, scummvm/trunk/engines/sci/include/aatree.h)
===================================================================
--- scummvm/trunk/engines/sci/engine/aatree.h (rev 0)
+++ scummvm/trunk/engines/sci/engine/aatree.h 2009-02-21 22:54:15 UTC (rev 38763)
@@ -0,0 +1,87 @@
+/* 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$
+ *
+ */
+
+#ifndef _SCI_AATREE_H
+#define _SCI_AATREE_H
+
+namespace Sci {
+
+/* Andersson tree implementation. Stores data pointers in a balanced binary
+** tree. A user-supplied comparison function defines the ordering. For the
+** semantics of this function see qsort(3)
+*/
+
+typedef struct aatree aatree_t;
+
+// Left child
+#define AATREE_WALK_LEFT 0
+// Right child
+#define AATREE_WALK_RIGHT 1
+
+aatree_t *aatree_new();
+/* Allocates a new aatree
+** Parameters: (void)
+** Returns : (aatree_t *) A newly allocated aatree
+*/
+
+void aatree_free(aatree_t *t);
+/* Deallocates an aatree
+** Parameters: (aatree_t *) t: The aatree
+** Returns : (void)
+*/
+
+int aatree_delete(void *x, aatree_t **t, int (*compar)(const void *, const void *));
+/* Deletes a data element from an aatree
+** Parameters: (void *) x: The data element to delete
+** (aatree_t **) t: The aatree
+** compar: The comparison function
+** Returns : (int) 0 on success, -1 if x wasn't found in t
+*/
+
+int aatree_insert(void *x, aatree_t **t, int (*compar)(const void *, const void *));
+/* Inserts a data element into an aatree
+** Parameters: (void *) x: The data element to insert
+** (aatree_t **) t: The aatree
+** compar: The comparison function
+** Returns : (int) 0 on success, -1 if x already exists in t
+*/
+
+aatree_t *aatree_walk(aatree_t *t, int direction);
+/* Walks to either the left or right child of a node
+** Parameters: (aatree_t *) t: The node
+** (int) direction: AATREE_WALK_LEFT or AATREE_WALK_RIGHT
+** Returns : (aatree_t *) The requested child of t or NULL if it doesn't
+** exist
+*/
+
+void *aatree_get_data(aatree_t *t);
+/* Returns the data element of a node
+** Parameters: (aatree_t *) t: The node
+** Returns : (void *) The data element
+*/
+
+} // End of namespace Sci
+
+#endif // !_SCI_AATREE_H
Modified: scummvm/trunk/engines/sci/engine/kpathing.cpp
===================================================================
--- scummvm/trunk/engines/sci/engine/kpathing.cpp 2009-02-21 22:53:14 UTC (rev 38762)
+++ scummvm/trunk/engines/sci/engine/kpathing.cpp 2009-02-21 22:54:15 UTC (rev 38763)
@@ -28,7 +28,7 @@
*/
#include "sci/include/engine.h"
-#include "sci/include/aatree.h"
+#include "sci/engine/aatree.h"
#include "sci/include/list.h"
#include "sci/gfx/gfx_widgets.h"
Deleted: scummvm/trunk/engines/sci/include/aatree.h
===================================================================
--- scummvm/trunk/engines/sci/include/aatree.h 2009-02-21 22:53:14 UTC (rev 38762)
+++ scummvm/trunk/engines/sci/include/aatree.h 2009-02-21 22:54:15 UTC (rev 38763)
@@ -1,87 +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$
- *
- */
-
-#ifndef _SCI_AATREE_H
-#define _SCI_AATREE_H
-
-namespace Sci {
-
-/* Andersson tree implementation. Stores data pointers in a balanced binary
-** tree. A user-supplied comparison function defines the ordering. For the
-** semantics of this function see qsort(3)
-*/
-
-typedef struct aatree aatree_t;
-
-// Left child
-#define AATREE_WALK_LEFT 0
-// Right child
-#define AATREE_WALK_RIGHT 1
-
-aatree_t *aatree_new();
-/* Allocates a new aatree
-** Parameters: (void)
-** Returns : (aatree_t *) A newly allocated aatree
-*/
-
-void aatree_free(aatree_t *t);
-/* Deallocates an aatree
-** Parameters: (aatree_t *) t: The aatree
-** Returns : (void)
-*/
-
-int aatree_delete(void *x, aatree_t **t, int (*compar)(const void *, const void *));
-/* Deletes a data element from an aatree
-** Parameters: (void *) x: The data element to delete
-** (aatree_t **) t: The aatree
-** compar: The comparison function
-** Returns : (int) 0 on success, -1 if x wasn't found in t
-*/
-
-int aatree_insert(void *x, aatree_t **t, int (*compar)(const void *, const void *));
-/* Inserts a data element into an aatree
-** Parameters: (void *) x: The data element to insert
-** (aatree_t **) t: The aatree
-** compar: The comparison function
-** Returns : (int) 0 on success, -1 if x already exists in t
-*/
-
-aatree_t *aatree_walk(aatree_t *t, int direction);
-/* Walks to either the left or right child of a node
-** Parameters: (aatree_t *) t: The node
-** (int) direction: AATREE_WALK_LEFT or AATREE_WALK_RIGHT
-** Returns : (aatree_t *) The requested child of t or NULL if it doesn't
-** exist
-*/
-
-void *aatree_get_data(aatree_t *t);
-/* Returns the data element of a node
-** Parameters: (aatree_t *) t: The node
-** Returns : (void *) The data element
-*/
-
-} // End of namespace Sci
-
-#endif // !_SCI_AATREE_H
Modified: scummvm/trunk/engines/sci/module.mk
===================================================================
--- scummvm/trunk/engines/sci/module.mk 2009-02-21 22:53:14 UTC (rev 38762)
+++ scummvm/trunk/engines/sci/module.mk 2009-02-21 22:54:15 UTC (rev 38763)
@@ -6,6 +6,7 @@
exereader.o \
sci.o \
tools.o \
+ engine/aatree.o \
engine/game.o \
engine/gc.o \
engine/grammar.o \
@@ -52,7 +53,6 @@
gfx/resource/sci_resmgr.o \
gfx/resource/sci_view_0.o \
gfx/resource/sci_view_1.o \
- scicore/aatree.o \
scicore/sciconsole.o \
scicore/decompress0.o \
scicore/decompress01.o \
Deleted: scummvm/trunk/engines/sci/scicore/aatree.cpp
===================================================================
--- scummvm/trunk/engines/sci/scicore/aatree.cpp 2009-02-21 22:53:14 UTC (rev 38762)
+++ scummvm/trunk/engines/sci/scicore/aatree.cpp 2009-02-21 22:54:15 UTC (rev 38763)
@@ -1,162 +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$
- *
- */
-
-#include "sci/include/aatree.h"
-
-#include "sci/include/sci_memory.h"
-
-namespace Sci {
-
-struct aatree {
- struct aatree *left, *right;
- int level;
- void *key;
-};
-
-// Sentinel node
-static aatree_t bottom = {&bottom, &bottom, 0, NULL};
-
-static void skew(aatree_t **t) {
- if ((*t)->left->level == (*t)->level) {
- // Rotate right
- aatree_t *temp = *t;
- *t = (*t)->left;
- temp->left = (*t)->right;
- (*t)->right = temp;
- }
-}
-
-static void split(aatree_t **t) {
- if ((*t)->right->right->level == (*t)->level) {
- // Rotate left
- aatree_t *temp = *t;
- *t = (*t)->right;
- temp->right = (*t)->left;
- (*t)->left = temp;
- (*t)->level++;
- }
-}
-
-static int delete_node(void *x, aatree_t **t, aatree_t *deleted, int (*compar)(const void *, const void *)) {
- int retval = -1;
-
- if (*t != &bottom) {
- // Search down the tree
- aatree_t **n;
-
- if (compar(x, (*t)->key) < 0)
- n = &(*t)->left;
- else {
- n = &(*t)->right;
- deleted = *t;
- }
-
- retval = delete_node(x, n, deleted, compar);
-
- // At the bottom of the tree we remove the element (if it is present)
- if ((*n == &bottom) && (deleted != &bottom) && (compar(x, deleted->key) == 0)) {
- aatree_t *temp;
- deleted->key = (*t)->key;
- temp = *t;
- *t = (*t)->right;
- free(temp);
- retval = 0;
- } else if (((*t)->left->level < (*t)->level - 1) || ((*t)->right->level < (*t)->level - 1)) {
- (*t)->level--;
- if ((*t)->right->level > (*t)->level)
- (*t)->right->level = (*t)->level;
- skew(t);
- skew(&(*t)->right);
- skew(&(*t)->right->right);
- split(t);
- split(&(*t)->right);
- }
- }
-
- return retval;
-}
-
-aatree_t *aatree_new() {
- return ⊥
-}
-
-int aatree_insert(void *x, aatree_t **t, int (*compar)(const void *, const void *)) {
- int retval = -1;
- int c;
-
- if (*t == &bottom) {
- *t = (aatree_t *)sci_malloc(sizeof(aatree_t));
-
- if (*t == NULL)
- return 1;
-
- (*t)->key = x;
- (*t)->left = ⊥
- (*t)->right = ⊥
- (*t)->level = 1;
- return 0;
- }
-
- c = compar(x, (*t)->key);
-
- if (c < 0)
- retval = aatree_insert(x, &(*t)->left, compar);
- else if (c > 0)
- retval = aatree_insert(x, &(*t)->right, compar);
-
- skew(t);
- split(t);
- return retval;
-}
-
-int aatree_delete(void *x, aatree_t **t, int (*compar)(const void *, const void *)) {
- return delete_node(x, t, &bottom, compar);
-}
-
-aatree_t *aatree_walk(aatree_t *t, int direction) {
- if ((direction == AATREE_WALK_LEFT) && (t->left != &bottom))
- return t->left;
-
- if ((direction == AATREE_WALK_RIGHT) && (t->right != &bottom))
- return t->right;
-
- return NULL;
-}
-
-void *aatree_get_data(aatree_t *t) {
- return t->key;
-}
-
-void aatree_free(aatree_t *t) {
- if (t == &bottom)
- return;
-
- aatree_free(t->left);
- aatree_free(t->right);
-
- free(t);
-}
-
-} // End of namespace Sci
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
More information about the Scummvm-git-logs
mailing list