[Scummvm-cvs-logs] SF.net SVN: scummvm:[35851] residual/trunk/common
aquadran at users.sourceforge.net
aquadran at users.sourceforge.net
Tue Jan 13 23:25:34 CET 2009
Revision: 35851
http://scummvm.svn.sourceforge.net/scummvm/?rev=35851&view=rev
Author: aquadran
Date: 2009-01-13 22:25:33 +0000 (Tue, 13 Jan 2009)
Log Message:
-----------
synced some parts of scummvm "common" code
Modified Paths:
--------------
residual/trunk/common/debug.cpp
residual/trunk/common/debug.h
residual/trunk/common/func.h
residual/trunk/common/hash-str.h
residual/trunk/common/hashmap.cpp
residual/trunk/common/hashmap.h
residual/trunk/common/keyboard.h
residual/trunk/common/list.h
residual/trunk/common/memorypool.cpp
residual/trunk/common/memorypool.h
residual/trunk/common/ptr.h
residual/trunk/common/rect.h
residual/trunk/common/str.cpp
residual/trunk/common/str.h
residual/trunk/common/sys.h
residual/trunk/common/util.h
Modified: residual/trunk/common/debug.cpp
===================================================================
--- residual/trunk/common/debug.cpp 2009-01-13 21:08:22 UTC (rev 35850)
+++ residual/trunk/common/debug.cpp 2009-01-13 22:25:33 UTC (rev 35851)
@@ -82,7 +82,7 @@
fflush(stdout);
}
-void CDECL debug(const char *s, ...) {
+void debug(const char *s, ...) {
char buf[STRINGBUFLEN];
va_list va;
@@ -93,7 +93,7 @@
debugHelper(buf);
}
-void CDECL debug(int level, const char *s, ...) {
+void debug(int level, const char *s, ...) {
char buf[STRINGBUFLEN];
va_list va;
@@ -107,7 +107,7 @@
debugHelper(buf);
}
-void NORETURN CDECL error(const char *s, ...) {
+void NORETURN error(const char *s, ...) {
char buf_input[STRINGBUFLEN];
char buf_output[STRINGBUFLEN];
va_list va;
@@ -153,7 +153,7 @@
exit(1);
}
-void CDECL warning(const char *fmt, ...) {
+void warning(const char *fmt, ...) {
char buf[STRINGBUFLEN];
va_list va;
Modified: residual/trunk/common/debug.h
===================================================================
--- residual/trunk/common/debug.h 2009-01-13 21:08:22 UTC (rev 35850)
+++ residual/trunk/common/debug.h 2009-01-13 22:25:33 UTC (rev 35851)
@@ -55,7 +55,7 @@
void warning(const char *fmt, ...);
void error(const char *fmt, ...);
-void CDECL debug(int level, const char *s, ...);
-void CDECL debug(const char *s, ...);
+void debug(int level, const char *s, ...);
+void debug(const char *s, ...);
#endif
Modified: residual/trunk/common/func.h
===================================================================
--- residual/trunk/common/func.h 2009-01-13 21:08:22 UTC (rev 35850)
+++ residual/trunk/common/func.h 2009-01-13 22:25:33 UTC (rev 35851)
@@ -29,12 +29,18 @@
namespace Common {
+/**
+ * Generic unary function.
+ */
template<class Arg, class Result>
struct UnaryFunction {
typedef Arg ArgumenType;
typedef Result ResultType;
};
+/**
+ * Generic binary function.
+ */
template<class Arg1, class Arg2, class Result>
struct BinaryFunction {
typedef Arg1 FirstArgumentType;
@@ -42,16 +48,25 @@
typedef Result ResultType;
};
+/**
+ * Predicate to check for equallity of two data elements.
+ */
template<class T>
struct EqualTo : public BinaryFunction<T, T, bool> {
bool operator()(const T &x, const T &y) const { return x == y; }
};
+/**
+ * Predicate to check for x being less than y.
+ */
template<class T>
struct Less : public BinaryFunction<T, T, bool> {
bool operator()(const T &x, const T &y) const { return x < y; }
};
+/**
+ * Predicate to check for x being greater than y.
+ */
template<class T>
struct Greater : public BinaryFunction<T, T, bool> {
bool operator()(const T &x, const T &y) const { return x > y; }
@@ -63,15 +78,19 @@
Op _op;
typename Op::FirstArgumentType _arg1;
public:
- Binder1st(const Op &op, const typename Op::FirstArgumentType &arg1) : _op(op), _arg1(arg1) {}
+ Binder1st(const Op &op, typename Op::FirstArgumentType arg1) : _op(op), _arg1(arg1) {}
typename Op::ResultType operator()(typename Op::SecondArgumentType v) const {
return _op(_arg1, v);
}
};
-template<class Op, class T>
-inline Binder1st<Op> bind1st(const Op &op, const T &t) {
+/**
+ * Transforms a binary function object into an unary function object.
+ * To achieve that the first parameter is bound to the passed value t.
+ */
+template<class Op>
+inline Binder1st<Op> bind1st(const Op &op, typename Op::FirstArgumentType t) {
return Binder1st<Op>(op, t);
}
@@ -81,15 +100,19 @@
Op _op;
typename Op::SecondArgumentType _arg2;
public:
- Binder2nd(const Op &op, const typename Op::SecondArgumentType &arg2) : _op(op), _arg2(arg2) {}
+ Binder2nd(const Op &op, typename Op::SecondArgumentType arg2) : _op(op), _arg2(arg2) {}
typename Op::ResultType operator()(typename Op::FirstArgumentType v) const {
return _op(v, _arg2);
}
};
-template<class Op, class T>
-inline Binder2nd<Op> bind2nd(const Op &op, const T &t) {
+/**
+ * Transforms a binary function object into an unary function object.
+ * To achieve that the first parameter is bound to the passed value t.
+ */
+template<class Op>
+inline Binder2nd<Op> bind2nd(const Op &op, typename Op::SecondArgumentType t) {
return Binder2nd<Op>(op, t);
}
@@ -119,18 +142,24 @@
}
};
+/**
+ * Creates an unary function object from a function pointer.
+ */
template<class Arg, class Result>
inline PointerToUnaryFunc<Arg, Result> ptr_fun(Result (*func)(Arg)) {
return PointerToUnaryFunc<Arg, Result>(func);
}
+/**
+ * Creates an binary function object from a function pointer.
+ */
template<class Arg1, class Arg2, class Result>
inline PointerToBinaryFunc<Arg1, Arg2, Result> ptr_fun(Result (*func)(Arg1, Arg2)) {
return PointerToBinaryFunc<Arg1, Arg2, Result>(func);
}
template<class Result, class T>
-class MemFunc0 : public UnaryFunction<T*, Result> {
+class MemFunc0 : public UnaryFunction<T *, Result> {
private:
Result (T::*_func)();
public:
@@ -143,20 +172,20 @@
};
template<class Result, class T>
-class ConstMemFunc0 : public UnaryFunction<T*, Result> {
+class ConstMemFunc0 : public UnaryFunction<T *, Result> {
private:
Result (T::*_func)() const;
public:
typedef Result (T::*FuncType)() const;
ConstMemFunc0(const FuncType &func) : _func(func) {}
- Result operator()(T *v) const {
+ Result operator()(const T *v) const {
return (v->*_func)();
}
};
template<class Result, class Arg, class T>
-class MemFunc1 : public BinaryFunction<T*, Arg, Result> {
+class MemFunc1 : public BinaryFunction<T *, Arg, Result> {
private:
Result (T::*_func)(Arg);
public:
@@ -169,40 +198,166 @@
};
template<class Result, class Arg, class T>
-class ConstMemFunc1 : public BinaryFunction<T*, Arg, Result> {
+class ConstMemFunc1 : public BinaryFunction<T *, Arg, Result> {
private:
Result (T::*_func)(Arg) const;
public:
typedef Result (T::*FuncType)(Arg) const;
ConstMemFunc1(const FuncType &func) : _func(func) {}
- Result operator()(T *v1, Arg v2) const {
+ Result operator()(const T *v1, Arg v2) const {
return (v1->*_func)(v2);
}
};
+/**
+ * Creates a unary function object from a class member function pointer.
+ * The parameter passed to the function object is the 'this' pointer to
+ * be used for the function call.
+ */
template<class Result, class T>
inline MemFunc0<Result, T> mem_fun(Result (T::*f)()) {
return MemFunc0<Result, T>(f);
}
+/**
+ * Creates a unary function object from a class member function pointer.
+ * The parameter passed to the function object is the 'this' pointer to
+ * be used for the function call.
+ */
template<class Result, class T>
inline ConstMemFunc0<Result, T> mem_fun(Result (T::*f)() const) {
return ConstMemFunc0<Result, T>(f);
}
+/**
+ * Creates a binary function object from a class member function pointer.
+ * The first parameter passed to the function object is the 'this' pointer to
+ * be used for the function call.
+ * The second one is the parameter passed to the member function.
+ */
template<class Result, class Arg, class T>
inline MemFunc1<Result, Arg, T> mem_fun(Result (T::*f)(Arg)) {
return MemFunc1<Result, Arg, T>(f);
}
+/**
+ * Creates a binary function object from a class member function pointer.
+ * The first parameter passed to the function object is the 'this' pointer to
+ * be used for the function call.
+ * The second one is the parameter passed to the member function.
+ */
template<class Result, class Arg, class T>
inline ConstMemFunc1<Result, Arg, T> mem_fun(Result (T::*f)(Arg) const) {
return ConstMemFunc1<Result, Arg, T>(f);
}
+template<class Result, class T>
+class MemFuncRef0 : public UnaryFunction<T &, Result> {
+private:
+ Result (T::*_func)();
+public:
+ typedef Result (T::*FuncType)();
+
+ MemFuncRef0(const FuncType &func) : _func(func) {}
+ Result operator()(T &v) const {
+ return (v.*_func)();
+ }
+};
+
+template<class Result, class T>
+class ConstMemFuncRef0 : public UnaryFunction<T &, Result> {
+private:
+ Result (T::*_func)() const;
+public:
+ typedef Result (T::*FuncType)() const;
+
+ ConstMemFuncRef0(const FuncType &func) : _func(func) {}
+ Result operator()(const T &v) const {
+ return (v.*_func)();
+ }
+};
+
+template<class Result, class Arg, class T>
+class MemFuncRef1 : public BinaryFunction<T &, Arg, Result> {
+private:
+ Result (T::*_func)(Arg);
+public:
+ typedef Result (T::*FuncType)(Arg);
+
+ MemFuncRef1(const FuncType &func) : _func(func) {}
+ Result operator()(T &v1, Arg v2) const {
+ return (v1.*_func)(v2);
+ }
+};
+
+template<class Result, class Arg, class T>
+class ConstMemFuncRef1 : public BinaryFunction<T &, Arg, Result> {
+private:
+ Result (T::*_func)(Arg) const;
+public:
+ typedef Result (T::*FuncType)(Arg) const;
+
+ ConstMemFuncRef1(const FuncType &func) : _func(func) {}
+ Result operator()(const T &v1, Arg v2) const {
+ return (v1.*_func)(v2);
+ }
+};
+
+/**
+ * Creates a unary function object from a class member function pointer.
+ * The parameter passed to the function object is the object instance to
+ * be used for the function call. Note unlike mem_fun, it takes a reference
+ * as parameter. Note unlike mem_fun, it takes a reference
+ * as parameter.
+ */
+template<class Result, class T>
+inline MemFuncRef0<Result, T> mem_fun_ref(Result (T::*f)()) {
+ return MemFuncRef0<Result, T>(f);
+}
+
+/**
+ * Creates a unary function object from a class member function pointer.
+ * The parameter passed to the function object is the object instance to
+ * be used for the function call. Note unlike mem_fun, it takes a reference
+ * as parameter.
+ */
+template<class Result, class T>
+inline ConstMemFuncRef0<Result, T> mem_fun_Ref(Result (T::*f)() const) {
+ return ConstMemFuncRef0<Result, T>(f);
+}
+
+/**
+ * Creates a binary function object from a class member function pointer.
+ * The first parameter passed to the function object is the object instance to
+ * be used for the function call. Note unlike mem_fun, it takes a reference
+ * as parameter.
+ * The second one is the parameter passed to the member function.
+ */
+template<class Result, class Arg, class T>
+inline MemFuncRef1<Result, Arg, T> mem_fun_ref(Result (T::*f)(Arg)) {
+ return MemFuncRef1<Result, Arg, T>(f);
+}
+
+/**
+ * Creates a binary function object from a class member function pointer.
+ * The first parameter passed to the function object is the object instance to
+ * be used for the function call. Note unlike mem_fun, it takes a reference
+ * as parameter.
+ * The second one is the parameter passed to the member function.
+ */
+template<class Result, class Arg, class T>
+inline ConstMemFuncRef1<Result, Arg, T> mem_fun_ref(Result (T::*f)(Arg) const) {
+ return ConstMemFuncRef1<Result, Arg, T>(f);
+}
+
// functor code
+/**
+ * Generic functor object for function objects without parameters.
+ *
+ * @see Functor1
+ */
template<class Res>
struct Functor0 {
virtual ~Functor0() {}
@@ -211,6 +366,18 @@
virtual Res operator()() const = 0;
};
+/**
+ * Functor object for a class member function without parameter.
+ *
+ * Example creation:
+ *
+ * Foo bar;
+ * Functor0Men<void, Foo> myFunctor(&bar, &Foo::myFunc);
+ *
+ * Example usage:
+ *
+ * myFunctor();
+ */
template<class Res, class T>
class Functor0Mem : public Functor0<Res> {
public:
@@ -218,7 +385,7 @@
Functor0Mem(T *t, const FuncType &func) : _t(t), _func(func) {}
- bool isValid() const { return _func != 0; }
+ bool isValid() const { return _func != 0 && _t != 0; }
Res operator()() const {
return (_t->*_func)();
}
@@ -227,6 +394,38 @@
const FuncType _func;
};
+/**
+ * Generic functor object for unary function objects.
+ *
+ * A typical usage for an unary function object is for executing opcodes
+ * in a script interpreter. To achieve that one can create an Common::Array
+ * object with 'Functor1<Arg, Res> *' as type. Now after the right engine version
+ * has been determined and the opcode table to use is found one could easily
+ * add the opcode implementations like this:
+ *
+ * Common::Array<Functor1<ScriptState, void> *> opcodeTable;
+ * opcodeTable[0] = new Functor1Mem<ScriptState, void, MyEngine_v1>(&myEngine, &MyEngine_v1::o1_foo);
+ * opcodeTable[1] = new Functor1Mem<ScriptState, void, MyEngine_v2>(&myEngine, &MyEngine_v2::o2_foo);
+ * // unimplemented/unused opcode
+ * opcodeTable[2] = 0;
+ * etc.
+ *
+ * This makes it easy to add member functions of different classes as
+ * opcode functions to the function table. Since with the generic
+ * Functor1<ScriptState, void> object the only requirement for an
+ * function to be used is 'ScriptState' as argument and 'void' as return
+ * value.
+ *
+ * Now for calling the opcodes one has simple to do:
+ * if (opcodeTable[opcodeNum] && opcodeTable[opcodeNum]->isValid())
+ * (*opcodeTable[opcodeNum])(scriptState);
+ * else
+ * warning("Unimplemented opcode %d", opcodeNum);
+ *
+ * If you want to see an real world example check the kyra engine.
+ * Files: engines/kyra/script.cpp and .h and engine/kyra/script_*.cpp
+ * are interesting for that matter.
+ */
template<class Arg, class Res>
struct Functor1 : public Common::UnaryFunction<Arg, Res> {
virtual ~Functor1() {}
@@ -235,6 +434,13 @@
virtual Res operator()(Arg) const = 0;
};
+/**
+ * Functor object for an unary class member function.
+ * Usage is like with Functor0Mem. The resulting functor object
+ * will take one parameter though.
+ *
+ * @see Functor0Men
+ */
template<class Arg, class Res, class T>
class Functor1Mem : public Functor1<Arg, Res> {
public:
@@ -242,7 +448,7 @@
Functor1Mem(T *t, const FuncType &func) : _t(t), _func(func) {}
- bool isValid() const { return _func != 0; }
+ bool isValid() const { return _func != 0 && _t != 0; }
Res operator()(Arg v1) const {
return (_t->*_func)(v1);
}
@@ -251,6 +457,11 @@
const FuncType _func;
};
+/**
+ * Generic functor object for binary function objects.
+ *
+ * @see Functor1
+ */
template<class Arg1, class Arg2, class Res>
struct Functor2 : public Common::BinaryFunction<Arg1, Arg2, Res> {
virtual ~Functor2() {}
@@ -259,6 +470,13 @@
virtual Res operator()(Arg1, Arg2) const = 0;
};
+/**
+ * Functor object for a binary class member function.
+ * Usage is like with Functor0Mem. The resulting functor object
+ * will take two parameter though.
+ *
+ * @see Functor0Men
+ */
template<class Arg1, class Arg2, class Res, class T>
class Functor2Mem : public Functor2<Arg1, Arg2, Res> {
public:
@@ -266,7 +484,7 @@
Functor2Mem(T *t, const FuncType &func) : _t(t), _func(func) {}
- bool isValid() const { return _func != 0; }
+ bool isValid() const { return _func != 0 && _t != 0; }
Res operator()(Arg1 v1, Arg2 v2) const {
return (_t->*_func)(v1, v2);
}
Modified: residual/trunk/common/hash-str.h
===================================================================
--- residual/trunk/common/hash-str.h 2009-01-13 21:08:22 UTC (rev 35850)
+++ residual/trunk/common/hash-str.h 2009-01-13 22:25:33 UTC (rev 35851)
@@ -39,7 +39,7 @@
// FIXME: The following functors obviously are not consistently named
struct CaseSensitiveString_EqualTo {
- bool operator()(const String& x, const String& y) const { return strcmp(x.c_str(), y.c_str()) == 0; }
+ bool operator()(const String& x, const String& y) const { return x.equals(y); }
};
struct CaseSensitiveString_Hash {
@@ -48,7 +48,7 @@
struct IgnoreCase_EqualTo {
- bool operator()(const String& x, const String& y) const { return strcasecmp(x.c_str(), y.c_str()) == 0; }
+ bool operator()(const String& x, const String& y) const { return x.equalsIgnoreCase(y); }
};
struct IgnoreCase_Hash {
@@ -77,7 +77,6 @@
}
};
-
// String map -- by default case insensitive
typedef HashMap<String, String, IgnoreCase_Hash, IgnoreCase_EqualTo> StringMap;
Modified: residual/trunk/common/hashmap.cpp
===================================================================
--- residual/trunk/common/hashmap.cpp 2009-01-13 21:08:22 UTC (rev 35850)
+++ residual/trunk/common/hashmap.cpp 2009-01-13 22:25:33 UTC (rev 35851)
@@ -24,70 +24,86 @@
*/
// The hash map (associative array) implementation in this file is
-// based on code by Andrew Y. Ng, 1996:
+// based on the PyDict implementation of CPython. The erase() method
+// is based on example code in the Wikipedia article on Hash tables.
-/*
- * Copyright (c) 1998-2003 Massachusetts Institute of Technology.
- * This code was developed as part of the Haystack research project
- * (http://haystack.lcs.mit.edu/). Permission is hereby granted,
- * free of charge, to any person obtaining a copy of this software
- * and associated documentation files (the "Software"), to deal in
- * the Software without restriction, including without limitation
- * the rights to use, copy, modify, merge, publish, distribute,
- * sublicense, and/or sell copies of the Software, and to permit
- * persons to whom the Software is furnished to do so, subject to
- * the following conditions:
- *
- * The above copyright notice and this permission notice shall be
- * included in all copies or substantial portions of the Software.
- *
- * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
- * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
- * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
- * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
- * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
- * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
- * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
- * OTHER DEALINGS IN THE SOFTWARE.
- */
-
#include "common/hashmap.h"
namespace Common {
-// const char *:
+// Hash function for strings, taken from CPython.
uint hashit(const char *p) {
- uint hash = 0;
+ uint hash = *p << 7;
byte c;
- while ((c = *p++))
- hash = (hash * 31 + c);
- return hash;
+ int size = 0;
+ while ((c = *p++)) {
+ hash = (1000003 * hash) ^ c;
+ size++;
+ }
+ return hash ^ size;
}
+// Like hashit, but converts every char to lowercase before hashing.
uint hashit_lower(const char *p) {
- uint hash = 0;
+ uint hash = tolower(*p) << 7;
byte c;
- while ((c = *p++))
- hash = (hash * 31 + tolower(c));
- return hash;
+ int size = 0;
+ while ((c = *p++)) {
+ hash = (1000003 * hash) ^ tolower(c);
+ size++;
+ }
+ return hash ^ size;
}
-// The following table is taken from the GNU ISO C++ Library's hashtable.h file.
-static const uint primes[] = {
- 53ul, 97ul, 193ul, 389ul, 769ul,
- 1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
- 49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
- 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
- 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
- 1610612741ul, 3221225473ul, 4294967291ul
-};
+#ifdef DEBUG_HASH_COLLISIONS
+static double
+ g_collisions = 0,
+ g_lookups = 0,
+ g_collPerLook = 0,
+ g_capacity = 0,
+ g_size = 0;
+static int g_max_capacity = 0, g_max_size = 0;
+static int g_totalHashmaps = 0;
+static int g_stats[4] = {0,0,0,0};
-uint nextTableSize(uint x) {
- int i = 0;
- while (x >= primes[i])
- i++;
- return primes[i];
+void updateHashCollisionStats(int collisions, int lookups, int arrsize, int nele) {
+ g_collisions += collisions;
+ g_lookups += lookups;
+ if (lookups)
+ g_collPerLook += (double)collisions / (double)lookups;
+ g_capacity += arrsize;
+ g_size += nele;
+ g_totalHashmaps++;
+
+ if (3*nele <= 2*8)
+ g_stats[0]++;
+ if (3*nele <= 2*16)
+ g_stats[1]++;
+ if (3*nele <= 2*32)
+ g_stats[2]++;
+ if (3*nele <= 2*64)
+ g_stats[3]++;
+
+ g_max_capacity = MAX(g_max_capacity, arrsize);
+ g_max_size = MAX(g_max_size, nele);
+
+ fprintf(stdout, "%d hashmaps: colls %.1f; lookups %.1f; ratio %.3f%%; size %f (max: %d); capacity %f (max: %d)\n",
+ g_totalHashmaps,
+ g_collisions / g_totalHashmaps,
+ g_lookups / g_totalHashmaps,
+ 100 * g_collPerLook / g_totalHashmaps,
+ g_size / g_totalHashmaps, g_max_size,
+ g_capacity / g_totalHashmaps, g_max_capacity);
+ fprintf(stdout, " %d less than %d; %d less than %d; %d less than %d; %d less than %d\n",
+ g_stats[0], 2*8/3,
+ g_stats[1],2*16/3,
+ g_stats[2],2*32/3,
+ g_stats[3],2*64/3);
+
+ // TODO:
+ // * Should record the maximal size of the map during its lifetime, not that at its death
+ // * Should do some statistics: how many maps are less than 2/3*8, 2/3*16, 2/3*32, ...
}
+#endif
-
} // End of namespace Common
Modified: residual/trunk/common/hashmap.h
===================================================================
--- residual/trunk/common/hashmap.h 2009-01-13 21:08:22 UTC (rev 35850)
+++ residual/trunk/common/hashmap.h 2009-01-13 22:25:33 UTC (rev 35851)
@@ -51,6 +51,10 @@
* OTHER DEALINGS IN THE SOFTWARE.
*/
+// The hash map (associative array) implementation in this file is
+// based on the PyDict implementation of CPython. The erase() method
+// is based on example code in the Wikipedia article on Hash tables.
+
#ifndef COMMON_HASHMAP_H
#define COMMON_HASHMAP_H
@@ -58,29 +62,13 @@
#include "common/str.h"
#include "common/util.h"
-// FIXME: Since this define is very system dependant,
-// it should be moved to the appropriate H file instead.
-// Portdefs might be a good location for example
-#if !defined(__SYMBIAN32__)
#define USE_HASHMAP_MEMORY_POOL
-#endif
-
#ifdef USE_HASHMAP_MEMORY_POOL
#include "common/memorypool.h"
-// FIXME: we sadly can't assume standard C++ to be present
-// on every system we support, so we should get rid of this.
-// The solution should be to write a simple placement new
-// on our own.
-#include <new>
#endif
namespace Common {
-// The table sizes ideally are primes. We use a helper function to find
-// suitable table sizes.
-uint nextTableSize(uint x);
-
-
// Enable the following #define if you want to check how many collisions the
// code produces (many collisions indicate either a bad hash function, or a
// hash table that is too small).
@@ -115,31 +103,35 @@
Node(const Key &key) : _key(key), _value() {}
};
+ enum {
+ HASHMAP_PERTURB_SHIFT = 5,
+ HASHMAP_MIN_CAPACITY = 16,
-#ifdef USE_HASHMAP_MEMORY_POOL
- MemoryPool _nodePool;
+ // The quotient of the next two constants controls how much the
+ // internal storage of the hashmap may fill up before being
+ // increased automatically.
+ // Note: the quotient of these two must be between and different
+ // from 0 and 1.
+ HASHMAP_LOADFACTOR_NUMERATOR = 2,
+ HASHMAP_LOADFACTOR_DENOMINATOR = 3,
+ HASHMAP_MEMORYPOOL_SIZE = HASHMAP_MIN_CAPACITY * HASHMAP_LOADFACTOR_NUMERATOR / HASHMAP_LOADFACTOR_DENOMINATOR
+ };
+
+
+ ObjectPool<Node, HASHMAP_MEMORYPOOL_SIZE> _nodePool;
+
Node *allocNode(const Key &key) {
- void* mem = _nodePool.malloc();
- return new (mem) Node(key);
- }
-
- void freeNode(Node *node) {
- node->~Node();
- _nodePool.free(node);
+ return new (_nodePool) Node(key);
}
-#else
- Node* allocNode(const Key &key) {
- return new Node(key);
- }
void freeNode(Node *node) {
- delete node;
+ _nodePool.deleteChunk(node);
}
-#endif
- Node **_arr; // hashtable of size arrsize.
- uint _arrsize, _nele;
+ Node **_storage; // hashtable of size arrsize.
+ uint _mask; /**< Capacity of the HashMap minus one; must be a power of two of minus one */
+ uint _size;
HashFunc _hash;
EqualFunc _equal;
@@ -154,7 +146,7 @@
void assign(const HM_t &map);
int lookup(const Key &key) const;
int lookupAndCreateIfMissing(const Key &key);
- void expand_array(uint newsize);
+ void expandStorage(uint newCapacity);
template<class T> friend class IteratorImpl;
@@ -176,8 +168,8 @@
NodeType *deref() const {
assert(_hashmap != 0);
- assert(_idx < _hashmap->_arrsize);
- Node *node = _hashmap->_arr[_idx];
+ assert(_idx <= _hashmap->_mask);
+ Node *node = _hashmap->_storage[_idx];
assert(node != 0);
return node;
}
@@ -197,8 +189,8 @@
assert(_hashmap);
do {
_idx++;
- } while (_idx < _hashmap->_arrsize && _hashmap->_arr[_idx] == 0);
- if (_idx >= _hashmap->_arrsize)
+ } while (_idx <= _hashmap->_mask && _hashmap->_storage[_idx] == 0);
+ if (_idx > _hashmap->_mask)
_idx = (uint)-1;
return *this;
@@ -225,7 +217,7 @@
// Remove the previous content and ...
clear();
- delete[] _arr;
+ delete[] _storage;
// ... copy the new stuff.
assign(map);
return *this;
@@ -244,12 +236,12 @@
void erase(const Key &key);
- uint size() const { return _nele; }
+ uint size() const { return _size; }
iterator begin() {
// Find and return the _key non-empty entry
- for (uint ctr = 0; ctr < _arrsize; ++ctr) {
- if (_arr[ctr])
+ for (uint ctr = 0; ctr <= _mask; ++ctr) {
+ if (_storage[ctr])
return iterator(ctr, this);
}
return end();
@@ -260,8 +252,8 @@
const_iterator begin() const {
// Find and return the first non-empty entry
- for (uint ctr = 0; ctr < _arrsize; ++ctr) {
- if (_arr[ctr])
+ for (uint ctr = 0; ctr <= _mask; ++ctr) {
+ if (_storage[ctr])
return const_iterator(ctr, this);
}
return end();
@@ -272,14 +264,14 @@
iterator find(const Key &key) {
uint ctr = lookup(key);
- if (_arr[ctr])
+ if (_storage[ctr])
return iterator(ctr, this);
return end();
}
const_iterator find(const Key &key) const {
uint ctr = lookup(key);
- if (_arr[ctr])
+ if (_storage[ctr])
return const_iterator(ctr, this);
return end();
}
@@ -287,7 +279,7 @@
// TODO: insert() method?
bool empty() const {
- return (_nele == 0);
+ return (_size == 0);
}
};
@@ -299,16 +291,13 @@
*/
template<class Key, class Val, class HashFunc, class EqualFunc>
HashMap<Key, Val, HashFunc, EqualFunc>::HashMap() :
-#ifdef USE_HASHMAP_MEMORY_POOL
- _nodePool(sizeof(Node)),
-#endif
_defaultVal() {
- _arrsize = nextTableSize(0);
- _arr = new Node *[_arrsize];
- assert(_arr != NULL);
- memset(_arr, 0, _arrsize * sizeof(Node *));
+ _mask = HASHMAP_MIN_CAPACITY - 1;
+ _storage = new Node *[HASHMAP_MIN_CAPACITY];
+ assert(_storage != NULL);
+ memset(_storage, 0, HASHMAP_MIN_CAPACITY * sizeof(Node *));
- _nele = 0;
+ _size = 0;
#ifdef DEBUG_HASH_COLLISIONS
_collisions = 0;
@@ -322,10 +311,7 @@
* to heap buffers for the internal storage.
*/
template<class Key, class Val, class HashFunc, class EqualFunc>
-HashMap<Key, Val, HashFunc, EqualFunc>::HashMap(const HM_t &map) :
-#ifdef USE_HASHMAP_MEMORY_POOL
- _nodePool(sizeof(Node)),
-#endif
+HashMap<Key, Val, HashFunc, EqualFunc>::HashMap(const HM_t &map) :
_defaultVal() {
assign(map);
}
@@ -335,11 +321,15 @@
*/
template<class Key, class Val, class HashFunc, class EqualFunc>
HashMap<Key, Val, HashFunc, EqualFunc>::~HashMap() {
- for (uint ctr = 0; ctr < _arrsize; ++ctr)
- if (_arr[ctr] != NULL)
- freeNode(_arr[ctr]);
+ for (uint ctr = 0; ctr <= _mask; ++ctr)
+ if (_storage[ctr] != NULL)
+ freeNode(_storage[ctr]);
- delete[] _arr;
+ delete[] _storage;
+#ifdef DEBUG_HASH_COLLISIONS
+ extern void updateHashCollisionStats(int, int, int, int);
+ updateHashCollisionStats(_collisions, _lookups, _mask+1, _size);
+#endif
}
/**
@@ -351,95 +341,102 @@
*/
template<class Key, class Val, class HashFunc, class EqualFunc>
void HashMap<Key, Val, HashFunc, EqualFunc>::assign(const HM_t &map) {
- _arrsize = map._arrsize;
- _arr = new Node *[_arrsize];
- assert(_arr != NULL);
- memset(_arr, 0, _arrsize * sizeof(Node *));
+ _mask = map._mask;
+ _storage = new Node *[_mask+1];
+ assert(_storage != NULL);
+ memset(_storage, 0, (_mask+1) * sizeof(Node *));
// Simply clone the map given to us, one by one.
- _nele = 0;
- for (uint ctr = 0; ctr < _arrsize; ++ctr) {
- if (map._arr[ctr] != NULL) {
- _arr[ctr] = allocNode(map._arr[ctr]->_key);
- _arr[ctr]->_value = map._arr[ctr]->_value;
- _nele++;
+ _size = 0;
+ for (uint ctr = 0; ctr <= _mask; ++ctr) {
+ if (map._storage[ctr] != NULL) {
+ _storage[ctr] = allocNode(map._storage[ctr]->_key);
+ _storage[ctr]->_value = map._storage[ctr]->_value;
+ _size++;
}
}
// Perform a sanity check (to help track down hashmap corruption)
- assert(_nele == map._nele);
+ assert(_size == map._size);
}
template<class Key, class Val, class HashFunc, class EqualFunc>
void HashMap<Key, Val, HashFunc, EqualFunc>::clear(bool shrinkArray) {
- for (uint ctr = 0; ctr < _arrsize; ++ctr) {
- if (_arr[ctr] != NULL) {
- freeNode(_arr[ctr]);
- _arr[ctr] = NULL;
+ for (uint ctr = 0; ctr <= _mask; ++ctr) {
+ if (_storage[ctr] != NULL) {
+ freeNode(_storage[ctr]);
+ _storage[ctr] = NULL;
}
}
- if (shrinkArray && _arrsize > nextTableSize(0)) {
- delete[] _arr;
+#ifdef USE_HASHMAP_MEMORY_POOL
+ _nodePool.freeUnusedPages();
+#endif
- _arrsize = nextTableSize(0);
- _arr = new Node *[_arrsize];
- assert(_arr != NULL);
- memset(_arr, 0, _arrsize * sizeof(Node *));
+ if (shrinkArray && _mask >= HASHMAP_MIN_CAPACITY) {
+ delete[] _storage;
+
+ _mask = HASHMAP_MIN_CAPACITY;
+ _storage = new Node *[HASHMAP_MIN_CAPACITY];
+ assert(_storage != NULL);
+ memset(_storage, 0, HASHMAP_MIN_CAPACITY * sizeof(Node *));
}
- _nele = 0;
+ _size = 0;
}
template<class Key, class Val, class HashFunc, class EqualFunc>
-void HashMap<Key, Val, HashFunc, EqualFunc>::expand_array(uint newsize) {
- assert(newsize > _arrsize);
- uint ctr, dex;
+void HashMap<Key, Val, HashFunc, EqualFunc>::expandStorage(uint newCapacity) {
+ assert(newCapacity > _mask+1);
- const uint old_nele = _nele;
- const uint old_arrsize = _arrsize;
- Node **old_arr = _arr;
+ const uint old_size = _size;
+ const uint old_mask = _mask;
+ Node **old_storage = _storage;
// allocate a new array
- _nele = 0;
- _arrsize = newsize;
- _arr = new Node *[_arrsize];
- assert(_arr != NULL);
- memset(_arr, 0, _arrsize * sizeof(Node *));
+ _size = 0;
+ _mask = newCapacity - 1;
+ _storage = new Node *[newCapacity];
+ assert(_storage != NULL);
+ memset(_storage, 0, newCapacity * sizeof(Node *));
// rehash all the old elements
- for (ctr = 0; ctr < old_arrsize; ++ctr) {
- if (old_arr[ctr] == NULL)
+ for (uint ctr = 0; ctr <= old_mask; ++ctr) {
+ if (old_storage[ctr] == NULL)
continue;
// Insert the element from the old table into the new table.
// Since we know that no key exists twice in the old table, we
// can do this slightly better than by calling lookup, since we
// don't have to call _equal().
- dex = _hash(old_arr[ctr]->_key) % _arrsize;
- while (_arr[dex] != NULL) {
- dex = (dex + 1) % _arrsize;
+ const uint hash = _hash(old_storage[ctr]->_key);
+ uint idx = hash & _mask;
+ for (uint perturb = hash; _storage[idx] != NULL; perturb >>= HASHMAP_PERTURB_SHIFT) {
+ idx = (5 * idx + perturb + 1) & _mask;
}
- _arr[dex] = old_arr[ctr];
- _nele++;
+ _storage[idx] = old_storage[ctr];
+ _size++;
}
// Perform a sanity check: Old number of elements should match the new one!
// This check will fail if some previous operation corrupted this hashmap.
- assert(_nele == old_nele);
+ assert(_size == old_size);
- delete[] old_arr;
+ delete[] old_storage;
return;
}
template<class Key, class Val, class HashFunc, class EqualFunc>
int HashMap<Key, Val, HashFunc, EqualFunc>::lookup(const Key &key) const {
- uint ctr = _hash(key) % _arrsize;
+ const uint hash = _hash(key);
+ uint ctr = hash & _mask;
+ for (uint perturb = hash; ; perturb >>= HASHMAP_PERTURB_SHIFT) {
+ if (_storage[ctr] == NULL || _equal(_storage[ctr]->_key, key))
+ break;
- while (_arr[ctr] != NULL && !_equal(_arr[ctr]->_key, key)) {
- ctr = (ctr + 1) % _arrsize;
+ ctr = (5 * ctr + perturb + 1) & _mask;
#ifdef DEBUG_HASH_COLLISIONS
_collisions++;
@@ -450,7 +447,7 @@
_lookups++;
fprintf(stderr, "collisions %d, lookups %d, ratio %f in HashMap %p; size %d num elements %d\n",
_collisions, _lookups, ((double) _collisions / (double)_lookups),
- (const void *)this, _arrsize, _nele);
+ (const void *)this, _mask+1, _size);
#endif
return ctr;
@@ -460,13 +457,15 @@
int HashMap<Key, Val, HashFunc, EqualFunc>::lookupAndCreateIfMissing(const Key &key) {
uint ctr = lookup(key);
- if (_arr[ctr] == NULL) {
- _arr[ctr] = allocNode(key);
- _nele++;
+ if (_storage[ctr] == NULL) {
+ _storage[ctr] = allocNode(key);
+ _size++;
- // Keep the load factor below 75%.
- if (_nele > _arrsize * 75 / 100) {
- expand_array(nextTableSize(_arrsize));
+ // Keep the load factor below a certain threshold.
+ uint capacity = _mask + 1;
+ if (_size * HASHMAP_LOADFACTOR_DENOMINATOR > capacity * HASHMAP_LOADFACTOR_NUMERATOR) {
+ capacity = capacity < 500 ? (capacity * 4) : (capacity * 2);
+ expandStorage(capacity);
ctr = lookup(key);
}
}
@@ -478,7 +477,7 @@
template<class Key, class Val, class HashFunc, class EqualFunc>
bool HashMap<Key, Val, HashFunc, EqualFunc>::contains(const Key &key) const {
uint ctr = lookup(key);
- return (_arr[ctr] != NULL);
+ return (_storage[ctr] != NULL);
}
template<class Key, class Val, class HashFunc, class EqualFunc>
@@ -494,15 +493,15 @@
template<class Key, class Val, class HashFunc, class EqualFunc>
Val &HashMap<Key, Val, HashFunc, EqualFunc>::getVal(const Key &key) {
uint ctr = lookupAndCreateIfMissing(key);
- assert(_arr[ctr] != NULL);
- return _arr[ctr]->_value;
+ assert(_storage[ctr] != NULL);
+ return _storage[ctr]->_value;
}
template<class Key, class Val, class HashFunc, class EqualFunc>
const Val &HashMap<Key, Val, HashFunc, EqualFunc>::getVal(const Key &key) const {
uint ctr = lookup(key);
- if (_arr[ctr] != NULL)
- return _arr[ctr]->_value;
+ if (_storage[ctr] != NULL)
+ return _storage[ctr]->_value;
else
return _defaultVal;
}
@@ -510,38 +509,50 @@
template<class Key, class Val, class HashFunc, class EqualFunc>
void HashMap<Key, Val, HashFunc, EqualFunc>::setVal(const Key &key, const Val &val) {
uint ctr = lookupAndCreateIfMissing(key);
- assert(_arr[ctr] != NULL);
- _arr[ctr]->_value = val;
+ assert(_storage[ctr] != NULL);
+ _storage[ctr]->_value = val;
}
template<class Key, class Val, class HashFunc, class EqualFunc>
void HashMap<Key, Val, HashFunc, EqualFunc>::erase(const Key &key) {
// This is based on code in the Wikipedia article on Hash tables.
- uint i = lookup(key);
- if (_arr[i] == NULL)
+
+ const uint hash = _hash(key);
+ uint i = hash & _mask;
+ uint perturb;
+
+ for (perturb = hash; ; perturb >>= HASHMAP_PERTURB_SHIFT) {
+ if (_storage[i] == NULL || _equal(_storage[i]->_key, key))
+ break;
+
+ i = (5 * i + perturb + 1) & _mask;
+ }
+
+ if (_storage[i] == NULL)
return; // key wasn't present, so no work has to be done
+
// If we remove a key, we must check all subsequent keys and possibly
// reinsert them.
uint j = i;
- freeNode(_arr[i]);
- _arr[i] = NULL;
- while (true) {
+ freeNode(_storage[i]);
+ _storage[i] = NULL;
+ for (perturb = hash; ; perturb >>= HASHMAP_PERTURB_SHIFT) {
// Look at the next table slot
- j = (j + 1) % _arrsize;
+ j = (5 * j + perturb + 1) & _mask;
// If the next slot is empty, we are done
- if (_arr[j] == NULL)
+ if (_storage[j] == NULL)
break;
// Compute the slot where the content of the next slot should normally be,
// assuming an empty table, and check whether we have to move it.
- uint k = _hash(_arr[j]->_key) % _arrsize;
+ uint k = _hash(_storage[j]->_key) & _mask;
if ((j > i && (k <= i || k > j)) ||
(j < i && (k <= i && k > j)) ) {
- _arr[i] = _arr[j];
+ _storage[i] = _storage[j];
i = j;
}
}
- _arr[i] = NULL;
- _nele--;
+ _storage[i] = NULL;
+ _size--;
return;
}
Modified: residual/trunk/common/keyboard.h
===================================================================
--- residual/trunk/common/keyboard.h 2009-01-13 21:08:22 UTC (rev 35850)
+++ residual/trunk/common/keyboard.h 2009-01-13 22:25:33 UTC (rev 35851)
@@ -182,7 +182,7 @@
};
/**
- * List of certan special and some fake 'ascii' values used in keyboard events.
+ * List of certain special and some fake 'ascii' values used in keyboard events.
* The values for the function keys listed here are based on what certain SCUMM
* games expect in their scripts.
* @todo Get rid of the function key values, and instead enforce that engines use
@@ -259,6 +259,10 @@
keycode = KEYCODE_INVALID;
ascii = flags = 0;
}
+
+ bool operator ==(const KeyState &x) const {
+ return keycode == x.keycode && ascii == x.ascii && flags == x.flags;
+ }
};
} // End of namespace Common
Modified: residual/trunk/common/list.h
===================================================================
--- residual/trunk/common/list.h 2009-01-13 21:08:22 UTC (rev 35850)
+++ residual/trunk/common/list.h 2009-01-13 22:25:33 UTC (rev 35851)
@@ -210,7 +210,12 @@
++i;
}
+ void pop_front() {
+ iterator i = begin();
+ i = erase(i);
+ }
+
List<t_T> &operator=(const List<t_T> &list) {
if (this != &list) {
iterator i;
Modified: residual/trunk/common/memorypool.cpp
===================================================================
--- residual/trunk/common/memorypool.cpp 2009-01-13 21:08:22 UTC (rev 35850)
+++ residual/trunk/common/memorypool.cpp 2009-01-13 22:25:33 UTC (rev 35851)
@@ -28,22 +28,11 @@
namespace Common {
-static const size_t CHUNK_PAGE_SIZE = 32;
+enum {
+ INITIAL_CHUNKS_PER_PAGE = 8
+};
-void* MemoryPool::allocPage() {
- void* result = ::malloc(CHUNK_PAGE_SIZE * _chunkSize);
- _pages.push_back(result);
- void* current = result;
- for (size_t i = 1; i < CHUNK_PAGE_SIZE; ++i) {
- void* next = ((char*)current + _chunkSize);
- *(void**)current = next;
- current = next;
- }
- *(void**)current = NULL;
- return result;
-}
-
MemoryPool::MemoryPool(size_t chunkSize) {
// You must at least fit the pointer in the node (technically unneeded considering the next rounding statement)
_chunkSize = MAX(chunkSize, sizeof(void*));
@@ -52,38 +41,71 @@
_chunkSize = (_chunkSize + sizeof(void*) - 1) & (~(sizeof(void*) - 1));
_next = NULL;
+
+ _chunksPerPage = INITIAL_CHUNKS_PER_PAGE;
}
MemoryPool::~MemoryPool() {
- for (size_t i = 0; i<_pages.size(); ++i)
- ::free(_pages[i]);
+ for (size_t i = 0; i < _pages.size(); ++i)
+ ::free(_pages[i].start);
}
-void* MemoryPool::malloc() {
-#if 1
- if (!_next)
- _next = allocPage();
+void MemoryPool::allocPage() {
+ Page page;
- void* result = _next;
+ // Allocate a new page
+ page.numChunks = _chunksPerPage;
+ assert(page.numChunks * _chunkSize < 16*1024*1024); // Refuse to allocate pages bigger than 16 MB
+
+ page.start = ::malloc(page.numChunks * _chunkSize);
+ assert(page.start);
+ _pages.push_back(page);
+
+
+ // Next time, we'll alocate a page twice as big as this one.
+ _chunksPerPage *= 2;
+
+ // Add the page to the pool of free chunk
+ addPageToPool(page);
+}
+
+void MemoryPool::addPageToPool(const Page &page) {
+
+ // Add all chunks of the new page to the linked list (pool) of free chunks
+ void *current = page.start;
+ for (size_t i = 1; i < page.numChunks; ++i) {
+ void *next = ((char*)current + _chunkSize);
+ *(void **)current = next;
+
+ current = next;
+ }
+
+ // Last chunk points to the old _next
+ *(void**)current = _next;
+
+ // From now on, the first free chunk is the first chunk of the new page
+ _next = page.start;
+}
+
+void *MemoryPool::allocChunk() {
+ if (!_next) // No free chunks left? Allocate a new page
+ allocPage();
+
+ assert(_next);
+ void *result = _next;
_next = *(void**)result;
return result;
-#else
- return ::malloc(_chunkSize);
-#endif
}
-void MemoryPool::free(void* ptr) {
-#if 1
+void MemoryPool::freeChunk(void *ptr) {
+ // Add the chunk back to (the start of) the list of free chunks
*(void**)ptr = _next;
_next = ptr;
-#else
- ::free(ptr);
-#endif
}
// Technically not compliant C++ to compare unrelated pointers. In practice...
-bool MemoryPool::isPointerInPage(void* ptr, void* page) {
- return (ptr >= page) && (ptr < (char*)page + CHUNK_PAGE_SIZE * _chunkSize);
+bool MemoryPool::isPointerInPage(void *ptr, const Page &page) {
+ return (ptr >= page.start) && (ptr < (char*)page.start + page.numChunks * _chunkSize);
}
void MemoryPool::freeUnusedPages() {
@@ -94,9 +116,10 @@
numberOfFreeChunksPerPage[i] = 0;
}
- void* iterator = _next;
+ // Compute for each page how many chunks in it are still in use.
+ void *iterator = _next;
while (iterator) {
- // This should be a binary search
+ // TODO: This should be a binary search (requiring us to keep _pages sorted)
for (size_t i = 0; i < _pages.size(); ++i) {
if (isPointerInPage(iterator, _pages[i])) {
++numberOfFreeChunksPerPage[i];
@@ -106,16 +129,41 @@
iterator = *(void**)iterator;
}
+ // Free all pages which are not in use.
size_t freedPagesCount = 0;
- for (size_t i = 0; i < _pages.size(); ++i) {
- if (numberOfFreeChunksPerPage[i] == CHUNK_PAGE_SIZE) {
- ::free(_pages[i]);
- _pages[i] = NULL; // TODO : Remove NULL values
+ for (size_t i = 0; i < _pages.size(); ++i) {
+ if (numberOfFreeChunksPerPage[i] == _pages[i].numChunks) {
+ // Remove all chunks of this page from the list of free chunks
+ void **iter2 = &_next;
+ while (*iter2) {
+ if (isPointerInPage(*iter2, _pages[i]))
+ *iter2 = **(void***)iter2;
+ else
+ iter2 = *(void***)iter2;
+ }
+ ::free(_pages[i].start);
++freedPagesCount;
+ _pages[i].start = NULL;
}
}
- //printf("%d freed pages\n", freedPagesCount);
+// printf("freed %d pages out of %d\n", (int)freedPagesCount, (int)_pages.size());
+
+ for (size_t i = 0; i < _pages.size(); ) {
+ if (_pages[i].start == NULL) {
+ _pages.remove_at(i);
+ // We just removed an entry, so we do not advance "i"
+ } else {
+ ++i;
+ }
+ }
+
+ // Reset _chunksPerPage
+ _chunksPerPage = INITIAL_CHUNKS_PER_PAGE;
+ for (size_t i = 0; i < _pages.size(); ++i) {
+ if (_chunksPerPage < _pages[i].numChunks)
+ _chunksPerPage = _pages[i].numChunks;
+ }
}
} // End of namespace Common
Modified: residual/trunk/common/memorypool.h
===================================================================
--- residual/trunk/common/memorypool.h 2009-01-13 21:08:22 UTC (rev 35850)
+++ residual/trunk/common/memorypool.h 2009-01-13 22:25:33 UTC (rev 35851)
@@ -32,26 +32,86 @@
namespace Common {
class MemoryPool {
-private:
+protected:
MemoryPool(const MemoryPool&);
MemoryPool& operator=(const MemoryPool&);
+ struct Page {
+ void *start;
+ size_t numChunks;
+ };
+
size_t _chunkSize;
- Array<void*> _pages;
- void* _next;
+ Array<Page> _pages;
+ void *_next;
+ size_t _chunksPerPage;
- void* allocPage();
- bool isPointerInPage(void* ptr, void* page);
+ void allocPage();
+ void addPageToPool(const Page &page);
+ bool isPointerInPage(void *ptr, const Page &page);
+
public:
MemoryPool(size_t chunkSize);
~MemoryPool();
- void* malloc();
- void free(void* ptr);
+ void *allocChunk();
+ void freeChunk(void *ptr);
void freeUnusedPages();
+
+ size_t getChunkSize() const { return _chunkSize; }
};
+template<size_t CHUNK_SIZE, size_t NUM_INTERNAL_CHUNKS = 32>
+class FixedSizeMemoryPool : public MemoryPool {
+private:
+ enum {
+ REAL_CHUNK_SIZE = (CHUNK_SIZE + sizeof(void*) - 1) & (~(sizeof(void*) - 1))
+ };
+
+ byte _storage[NUM_INTERNAL_CHUNKS * REAL_CHUNK_SIZE];
+public:
+ FixedSizeMemoryPool() : MemoryPool(CHUNK_SIZE) {
+ assert(REAL_CHUNK_SIZE == _chunkSize);
+ // Insert some static storage
+ Page internalPage = { _storage, NUM_INTERNAL_CHUNKS };
+ addPageToPool(internalPage);
+ }
+};
+
+template<size_t CHUNK_SIZE>
+class FixedSizeMemoryPool<CHUNK_SIZE,0> : public MemoryPool {
+public:
+ FixedSizeMemoryPool() : MemoryPool(CHUNK_SIZE) {}
+};
+
+
+template<class T, size_t NUM_INTERNAL_CHUNKS = 32>
+class ObjectPool : public FixedSizeMemoryPool<sizeof(T), NUM_INTERNAL_CHUNKS> {
+public:
+ void deleteChunk(T *ptr) {
+ ptr->~T();
+ freeChunk(ptr);
+ }
+};
+
} // End of namespace Common
+// Provide a custom placement new operator, using an arbitrary
+// MemoryPool.
+//
+// This *should* work with all C++ implementations, but may not.
+//
+// For details on using placement new for custom allocators, see e.g.
+// <http://www.parashift.com/c++-faq-lite/dtors.html#faq-11.14>
+
+inline void* operator new(size_t nbytes, Common::MemoryPool& pool) {
+ assert(nbytes <= pool.getChunkSize());
+ return pool.allocChunk();
+}
+
+inline void operator delete(void* p, Common::MemoryPool& pool) {
+ pool.freeChunk(p);
+}
+
#endif
Modified: residual/trunk/common/ptr.h
===================================================================
--- residual/trunk/common/ptr.h 2009-01-13 21:08:22 UTC (rev 35850)
+++ residual/trunk/common/ptr.h 2009-01-13 22:25:33 UTC (rev 35851)
@@ -70,7 +70,7 @@
* To achieve that the object implements an internal reference counting.
* Thus you should try to avoid using the plain pointer after assigning
* it to a SharedPtr object for the first time. If you still use the
- * plain pointer be sure you do not delete it on your own. You may also
+ * plain pointer be sure you do not delete it on your own. You may also
* not use the plain pointer to create a new SharedPtr object, since that
* would result in a double deletion of the pointer sooner or later.
*
@@ -95,7 +95,7 @@
*
* The class has implicit upcast support, so if you got a class B derived
* from class A, you can assign a pointer to B without any problems to a
- * SharedPtr object with template parameter A. The very same applies to
+ * SharedPtr object with template parameter A. The very same applies to
* assignment of a SharedPtr<B> object to a SharedPtr<A> object.
*
* There are also operators != and == to compare two SharedPtr objects
@@ -121,7 +121,7 @@
~SharedPtr() { decRef(); }
- SharedPtr &operator =(const SharedPtr &r) {
+ SharedPtr &operator=(const SharedPtr &r) {
if (r._refCount)
++(*r._refCount);
decRef();
@@ -134,7 +134,7 @@
}
template<class T2>
- SharedPtr &operator =(const SharedPtr<T2> &r) {
+ SharedPtr &operator=(const SharedPtr<T2> &r) {
if (r._refCount)
++(*r._refCount);
decRef();
@@ -146,8 +146,8 @@
return *this;
}
- ValueType &operator *() const { assert(_pointer); return *_pointer; }
- Pointer operator ->() const { assert(_pointer); return _pointer; }
+ ValueType &operator*() const { assert(_pointer); return *_pointer; }
+ Pointer operator->() const { assert(_pointer); return _pointer; }
/**
* Returns the plain pointer value. Be sure you know what you
@@ -171,6 +171,16 @@
bool unique() const { return refCount() == 1; }
/**
+ * Resets the SharedPtr object to a NULL pointer.
+ */
+ void reset() {
+ decRef();
+ _deletion = 0;
+ _refCount = 0;
+ _pointer = 0;
+ }
+
+ /**
* Returns the number of references to the assigned pointer.
* This should just be used for debugging purposes.
*/
@@ -199,17 +209,13 @@
} // end of namespace Common
template<class T1, class T2>
-bool operator ==(const Common::SharedPtr<T1> &l, const Common::SharedPtr<T2> &r) {
+bool operator==(const Common::SharedPtr<T1> &l, const Common::SharedPtr<T2> &r) {
return l.get() == r.get();
}
template<class T1, class T2>
-bool operator !=(const Common::SharedPtr<T1> &l, const Common::SharedPtr<T2> &r) {
+bool operator!=(const Common::SharedPtr<T1> &l, const Common::SharedPtr<T2> &r) {
return l.get() != r.get();
}
-
#endif
-
-
-
Modified: residual/trunk/common/rect.h
===================================================================
--- residual/trunk/common/rect.h 2009-01-13 21:08:22 UTC (rev 35850)
+++ residual/trunk/common/rect.h 2009-01-13 22:25:33 UTC (rev 35851)
@@ -31,10 +31,9 @@
namespace Common {
-/*! @brief simple class for handling both 2D position and size
-
- This small class is an helper for position and size values.
-*/
+/**
+ * Simple class for handling both 2D position and size.
+ */
struct Point {
int16 x; //!< The horizontal part of the point
int16 y; //!< The vertical part of the point
@@ -65,23 +64,23 @@
}
};
-/*! @brief simple class for handling a rectangular zone.
-
- This small class is an helper for rectangles.
- Note: This implementation is built around the assumption that (top,left) is
- part of the rectangle, but (bottom,right) is not! This is reflected in
- various methods, including contains(), intersects() and others.
-
- Another very wide spread approach to rectangle classes treats (bottom,right)
- also as a part of the rectangle.
-
- Coneptually, both are sound, but the approach we use saves many intermediate
- computations (like computing the height in our case is done by doing this:
- height = bottom - top;
- while in the alternate system, it would be
- height = bottom - top + 1;
-
- When writing code using our Rect class, always keep this principle in mind!
+/**
+ * Simple class for handling a rectangular zone.
+ *
+ * Note: This implementation is built around the assumption that (top,left) is
+ * part of the rectangle, but (bottom,right) is not. This is reflected in
+ * various methods, including contains(), intersects() and others.
+ *
+ * Another very wide spread approach to rectangle classes treats (bottom,right)
+ * also as a part of the rectangle.
+ *
+ * Conceptually, both are sound, but the approach we use saves many intermediate
+ * computations (like computing the height in our case is done by doing this:
+ * height = bottom - top;
+ * while in the alternate system, it would be
+ * height = bottom - top + 1;
+ *
+ * When writing code using our Rect class, always keep this principle in mind!
*/
struct Rect {
int16 top, left; //!< The point at the top left of the rectangle (part of the rect).
@@ -103,41 +102,56 @@
bottom = top + aHeight;
}
- /*! @brief check if given position is inside this rectangle
-
- @param x the horizontal position to check
- @param y the vertical position to check
-
- @return true if the given position is inside this rectangle, false otherwise
- */
+ /**
+ * Check if given position is inside this rectangle.
+ *
+ * @param x the horizontal position to check
+ * @param y the vertical position to check
+ *
+ * @return true if the given position is inside this rectangle, false otherwise
+ */
bool contains(int16 x, int16 y) const {
return (left <= x) && (x < right) && (top <= y) && (y < bottom);
}
- /*! @brief check if given point is inside this rectangle
-
- @param p the point to check
-
- @return true if the given point is inside this rectangle, false otherwise
- */
+ /**
+ * Check if given point is inside this rectangle.
+ *
+ * @param p the point to check
+ *
+ * @return true if the given point is inside this rectangle, false otherwise
+ */
bool contains(const Point &p) const {
return contains(p.x, p.y);
}
- /*! @brief check if given rectangle intersects with this rectangle
+ /**
+ * Check if the given rect is _fully_ contained inside this rectangle.
+ *
+ * @param r The rectangle to check
+ *
+ * @return true if the given rect is inside, false otherwise
+ */
+ bool contains(const Rect &r) const {
+ return (left < r.left) && (right > r.right) && (top < r.top) && (bottom > r.bottom);
+ }
- @param r the rectangle to check
-
- @return true if the given rectangle is inside the rectangle, false otherwise
- */
+ /**
+ * Check if given rectangle intersects with this rectangle
+ *
+ * @param r the rectangle to check
+ *
+ * @return true if the given rectangle is inside the rectangle, false otherwise
+ */
bool intersects(const Rect &r) const {
return (left < r.right) && (r.left < right) && (top < r.bottom) && (r.top < bottom);
}
- /*! @brief extend this rectangle so that it contains r
-
- @param r the rectangle to extend by
- */
+ /**
+ * Extend this rectangle so that it contains r
+ *
+ * @param r the rectangle to extend by
+ */
void extend(const Rect &r) {
left = MIN(left, r.left);
right = MAX(right, r.right);
@@ -145,10 +159,11 @@
bottom = MAX(bottom, r.bottom);
}
- /*! @brief extend this rectangle in all four directions by the given number of pixels
-
- @param offset the size to grow by
- */
+ /**
+ * Extend this rectangle in all four directions by the given number of pixels
+ *
+ * @param offset the size to grow by
+ */
void grow(int16 offset) {
top -= offset;
left -= offset;
@@ -205,7 +220,9 @@
debug(debuglevel, "%s %d, %d, %d, %d", caption, left, top, right, bottom);
}
- /*! @brief create a rectangle around the given center */
+ /**
+ * Create a rectangle around the given center.
+ */
static Rect center(int16 cx, int16 cy, int16 w, int16 h) {
w /= 2;
h /= 2;
Modified: residual/trunk/common/str.cpp
===================================================================
--- residual/trunk/common/str.cpp 2009-01-13 21:08:22 UTC (rev 35850)
+++ residual/trunk/common/str.cpp 2009-01-13 22:25:33 UTC (rev 35851)
@@ -34,28 +34,27 @@
const char *String::emptyString = "";
#endif
-static int computeCapacity(int len) {
- // By default, for the capacity we use the nearest multiple of 32
- // that leaves at least 16 chars of extra space (in case the string
- // grows a bit).
- // Finally, we subtract 1 to compensate for the trailing zero byte.
- len += 16;
- return ((len + 32 - 1) & ~0x1F) - 1;
+
+MemoryPool *g_refCountPool = 0; // FIXME: This is never freed right now
+
+static uint32 computeCapacity(uint32 len) {
+ // By default, for the capacity we use the next multiple of 32
+ return ((len + 32 - 1) & ~0x1F);
}
-String::String(const char *str) : _len(0), _str(_storage) {
+String::String(const char *str) : _size(0), _str(_storage) {
if (str == 0) {
_storage[0] = 0;
- _len = 0;
+ _size = 0;
} else
initWithCStr(str, strlen(str));
}
-String::String(const char *str, uint32 len) : _len(0), _str(_storage) {
+String::String(const char *str, uint32 len) : _size(0), _str(_storage) {
initWithCStr(str, len);
}
-String::String(const char *beginP, const char *endP) : _len(0), _str(_storage) {
+String::String(const char *beginP, const char *endP) : _size(0), _str(_storage) {
assert(endP >= beginP);
initWithCStr(beginP, endP - beginP);
}
@@ -67,13 +66,13 @@
// for GCC 2.95.x compatibility (see also tracker item #1602879).
_storage[0] = 0;
- _len = len;
+ _size = len;
if (len >= _builtinCapacity) {
// Not enough internal storage, so allocate more
- _extern._capacity = computeCapacity(len);
+ _extern._capacity = computeCapacity(len+1);
_extern._refCount = 0;
- _str = (char *)malloc(_extern._capacity+1);
+ _str = (char *)malloc(_extern._capacity);
assert(_str != 0);
}
@@ -83,28 +82,30 @@
}
String::String(const String &str)
- : _len(str._len), _str(str.isStorageIntern() ? _storage : str._str) {
+ : _size(str._size) {
if (str.isStorageIntern()) {
// String in internal storage: just copy it
memcpy(_storage, str._storage, _builtinCapacity);
+ _str = _storage;
} else {
// String in external storage: use refcount mechanism
str.incRefCount();
_extern._refCount = str._extern._refCount;
_extern._capacity = str._extern._capacity;
+ _str = str._str;
}
assert(_str != 0);
}
String::String(char c)
-: _len(0), _str(_storage) {
+: _size(0), _str(_storage) {
_storage[0] = c;
_storage[1] = 0;
// TODO/FIXME: There is no reason for the following check -- we *do*
// allow strings to contain 0 bytes!
- _len = (c == 0) ? 0 : 1;
+ _size = (c == 0) ? 0 : 1;
}
String::~String() {
@@ -112,16 +113,16 @@
}
void String::makeUnique() {
- ensureCapacity(_len, true);
+ ensureCapacity(_size, true);
}
/**
- * Ensure that enough storage is available to store at least new_len
+ * Ensure that enough storage is available to store at least new_size
* characters plus a null byte. In addition, if we currently share
* the storage with another string, unshare it, so that we can safely
* write to the storage.
*/
-void String::ensureCapacity(uint32 new_len, bool keep_old) {
+void String::ensureCapacity(uint32 new_size, bool keep_old) {
bool isShared;
uint32 curCapacity, newCapacity;
char *newStorage;
@@ -129,7 +130,7 @@
if (isStorageIntern()) {
isShared = false;
- curCapacity = _builtinCapacity - 1;
+ curCapacity = _builtinCapacity;
} else {
isShared = (oldRefCount && *oldRefCount > 1);
curCapacity = _extern._capacity;
@@ -137,30 +138,30 @@
// Special case: If there is enough space, and we do not share
// the storage, then there is nothing to do.
- if (!isShared && new_len <= curCapacity)
+ if (!isShared && new_size < curCapacity)
return;
- if (isShared && new_len <= _builtinCapacity - 1) {
+ if (isShared && new_size < _builtinCapacity) {
// We share the storage, but there is enough internal storage: Use that.
newStorage = _storage;
- newCapacity = _builtinCapacity - 1;
+ newCapacity = _builtinCapacity;
} else {
// We need to allocate storage on the heap!
// Compute a suitable new capacity limit
- newCapacity = computeCapacity(new_len);
+ newCapacity = MAX(curCapacity * 2, computeCapacity(new_size+1));
// Allocate new storage
- newStorage = (char *)malloc(newCapacity+1);
+ newStorage = (char *)malloc(newCapacity);
assert(newStorage);
}
// Copy old data if needed, elsewise reset the new storage.
if (keep_old) {
- assert(_len <= newCapacity);
- memcpy(newStorage, _str, _len + 1);
+ assert(_size < newCapacity);
+ memcpy(newStorage, _str, _size + 1);
} else {
- _len = 0;
+ _size = 0;
newStorage[0] = 0;
}
@@ -182,7 +183,11 @@
void String::incRefCount() const {
assert(!isStorageIntern());
if (_extern._refCount == 0) {
- _extern._refCount = new int(2);
+ if (g_refCountPool == 0)
+ g_refCountPool = new MemoryPool(sizeof(int));
+
+ _extern._refCount = (int *)g_refCountPool->allocChunk();
+ *_extern._refCount = 2;
} else {
++(*_extern._refCount);
}
@@ -198,7 +203,10 @@
if (!oldRefCount || *oldRefCount <= 0) {
// The ref count reached zero, so we free the string storage
// and the ref count storage.
- delete oldRefCount;
+ if (oldRefCount) {
+ assert(g_refCountPool);
+ g_refCountPool->freeChunk(oldRefCount);
+ }
free(_str);
// Even though _str points to a freed memory block now,
@@ -210,7 +218,7 @@
String& String::operator =(const char *str) {
uint32 len = strlen(str);
ensureCapacity(len, false);
- _len = len;
+ _size = len;
memmove(_str, str, len + 1);
return *this;
}
@@ -221,16 +229,16 @@
if (str.isStorageIntern()) {
decRefCount(_extern._refCount);
- _len = str._len;
+ _size = str._size;
_str = _storage;
- memcpy(_str, str._str, _len + 1);
+ memcpy(_str, str._str, _size + 1);
} else {
str.incRefCount();
decRefCount(_extern._refCount);
_extern._refCount = str._extern._refCount;
_extern._capacity = str._extern._capacity;
- _len = str._len;
+ _size = str._size;
_str = str._str;
}
@@ -240,7 +248,7 @@
String& String::operator =(char c) {
decRefCount(_extern._refCount);
_str = _storage;
- _len = 1;
+ _size = 1;
_str[0] = c;
_str[1] = 0;
return *this;
@@ -249,30 +257,30 @@
String &String::operator +=(const char *str) {
int len = strlen(str);
if (len > 0) {
- ensureCapacity(_len + len, true);
+ ensureCapacity(_size + len, true);
- memcpy(_str + _len, str, len + 1);
- _len += len;
+ memcpy(_str + _size, str, len + 1);
+ _size += len;
}
return *this;
}
String &String::operator +=(const String &str) {
- int len = str._len;
+ int len = str._size;
if (len > 0) {
- ensureCapacity(_len + len, true);
+ ensureCapacity(_size + len, true);
- memcpy(_str + _len, str._str, len + 1);
- _len += len;
+ memcpy(_str + _size, str._str, len + 1);
+ _size += len;
}
return *this;
}
String &String::operator +=(char c) {
- ensureCapacity(_len + 1, true);
+ ensureCapacity(_size + 1, true);
- _str[_len++] = c;
- _str[_len] = 0;
+ _str[_size++] = c;
+ _str[_size] = 0;
return *this;
}
@@ -293,10 +301,10 @@
bool String::hasSuffix(const char *x) const {
assert(x != 0);
// Compare x with the end of _str.
- const uint32 x_len = strlen(x);
- if (x_len > _len)
+ const uint32 x_size = strlen(x);
+ if (x_size > _size)
return false;
- const char *y = c_str() + _len - x_len;
+ const char *y = c_str() + _size - x_size;
while (*x && *x == *y) {
++x;
++y;
@@ -315,66 +323,75 @@
return strchr(c_str(), x) != NULL;
}
+bool String::matchString(const char *pat) const {
+ return Common::matchString(c_str(), pat);
+}
+
+bool String::matchString(const String &pat) const {
+ return Common::matchString(c_str(), pat.c_str());
+}
+
void String::deleteLastChar() {
- deleteChar(_len - 1);
+ if (_size > 0)
+ deleteChar(_size - 1);
}
void String::deleteChar(uint32 p) {
- assert(p < _len);
+ assert(p < _size);
makeUnique();
- while (p++ < _len)
+ while (p++ < _size)
_str[p-1] = _str[p];
- _len--;
+ _size--;
}
void String::clear() {
decRefCount(_extern._refCount);
- _len = 0;
+ _size = 0;
_str = _storage;
_storage[0] = 0;
}
void String::setChar(char c, uint32 p) {
- assert(p <= _len);
+ assert(p <= _size);
makeUnique();
_str[p] = c;
}
void String::insertChar(char c, uint32 p) {
- assert(p <= _len);
+ assert(p <= _size);
- ensureCapacity(_len + 1, true);
- _len++;
- for (uint32 i = _len; i > p; --i)
+ ensureCapacity(_size + 1, true);
+ _size++;
+ for (uint32 i = _size; i > p; --i)
_str[i] = _str[i-1];
_str[p] = c;
}
void String::toLowercase() {
makeUnique();
- for (uint32 i = 0; i < _len; ++i)
+ for (uint32 i = 0; i < _size; ++i)
_str[i] = tolower(_str[i]);
}
void String::toUppercase() {
makeUnique();
- for (uint32 i = 0; i < _len; ++i)
+ for (uint32 i = 0; i < _size; ++i)
_str[i] = toupper(_str[i]);
}
void String::trim() {
- if (_len == 0)
+ if (_size == 0)
return;
makeUnique();
// Trim trailing whitespace
- while (_len >= 1 && isspace(_str[_len-1]))
- _len--;
- _str[_len] = 0;
+ while (_size >= 1 && isspace(_str[_size-1]))
+ _size--;
+ _str[_size] = 0;
// Trim leading whitespace
char *t = _str;
@@ -382,8 +399,8 @@
t++;
if (t != _str) {
- _len -= t - _str;
- memmove(_str, t, _len + 1);
+ _size -= t - _str;
+ memmove(_str, t, _size + 1);
}
}
@@ -524,4 +541,112 @@
return rtrim(ltrim(t));
}
+Common::String lastPathComponent(const Common::String &path, const char sep) {
+ const char *str = path.c_str();
+ const char *last = str + path.size();
+
+ // Skip over trailing slashes
+ while (last > str && *(last-1) == sep)
+ --last;
+
+ // Path consisted of only slashes -> return empty string
+ if (last == str)
+ return Common::String();
+
+ // Now scan the whole component
+ const char *first = last - 1;
+ while (first >= str && *first != sep)
+ --first;
+
+ if (*first == sep)
+ first++;
+
+ return Common::String(first, last);
+}
+
+Common::String normalizePath(const Common::String &path, const char sep) {
+ if (path.empty())
+ return path;
+
+ const char *cur = path.c_str();
+ Common::String result;
+
+ // If there is a leading slash, preserve that:
+ if (*cur == sep) {
+ result += sep;
+ while (*cur == sep)
+ ++cur;
+ }
+
+ // Scan till the end of the String
+ while (*cur != 0) {
+ const char *start = cur;
+
+ // Scan till the next path separator resp. the end of the string
+ while (*cur != sep && *cur != 0)
+ cur++;
+
+ const Common::String component(start, cur);
+
+ // Skip empty components and dot components, add all others
+ if (!component.empty() && component != ".") {
+ // Add a separator before the component, unless the result
+ // string already ends with one (which happens only if the
+ // path *starts* with a separator).
+ if (!result.empty() && result.lastChar() != sep)
+ result += sep;
+
+ // Add the component
+ result += component;
+ }
+
+ // Skip over separator chars
+ while (*cur == sep)
+ cur++;
+ }
+
+ return result;
+}
+
+bool matchString(const char *str, const char *pat) {
+ assert(str);
+ assert(pat);
+
+ const char *p = 0;
+ const char *q = 0;
+
+ for (;;) {
+ switch (*pat) {
+ case '*':
+ // Record pattern / string possition for backtracking
+ p = ++pat;
+ q = str;
+ // If pattern ended with * -> match
+ if (!*pat)
+ return true;
+ break;
+
+ default:
+ if (*pat != *str) {
+ if (p) {
+ // No match, oops -> try to backtrack
+ pat = p;
+ str = ++q;
+ if (!*str)
+ return !*pat;
+ break;
+ }
+ else
+ return false;
+ }
+ // fallthrough
+ case '?':
+ if (!*str)
+ return !*pat;
+ pat++;
+ str++;
+ }
+ }
+}
+
} // End of namespace Common
Modified: residual/trunk/common/str.h
===================================================================
--- residual/trunk/common/str.h 2009-01-13 21:08:22 UTC (rev 35850)
+++ residual/trunk/common/str.h 2009-01-13 22:25:33 UTC (rev 35851)
@@ -54,14 +54,14 @@
* than 8 makes no sense, since that's the size of member _extern
* (on 32 bit machines; 12 bytes on systems with 64bit pointers).
*/
- static const uint32 _builtinCapacity = 32;
+ static const uint32 _builtinCapacity = 32 - sizeof(uint32) - sizeof(char*);
/**
* Length of the string. Stored to avoid having to call strlen
* a lot. Yes, we limit ourselves to strings shorter than 4GB --
* on purpose :-).
*/
- uint32 _len;
+ uint32 _size;
/**
* Pointer to the actual string storage. Either points to _storage,
@@ -97,22 +97,22 @@
#endif
/** Construct a new empty string. */
- String() : _len(0), _str(_storage) { _storage[0] = 0; }
+ String() : _size(0), _str(_storage) { _storage[0] = 0; }
/** Construct a new string from the given NULL-terminated C string. */
String(const char *str);
/** Construct a new string containing exactly len characters read from address str. */
String(const char *str, uint32 len);
-
+
/** Construct a new string containing the characters between beginP (including) and endP (excluding). */
String(const char *beginP, const char *endP);
-
+
/** Construct a copy of the given string. */
String(const String &str);
-
+
/** Construct a string consisting of the given character. */
- String(char c);
+ explicit String(char c);
~String();
@@ -149,20 +149,44 @@
bool contains(const char *x) const;
bool contains(char x) const;
+ /**
+ * Simple DOS-style pattern matching function (understands * and ? like used in DOS).
+ * Taken from exult/files/listfiles.cc
+ *
+ * Token meaning:
+ * "*": any character, any amount of times.
+ * "?": any character, only once.
+ *
+ * Example strings/patterns:
+ * String: monkey.s01 Pattern: monkey.s?? => true
+ * String: monkey.s101 Pattern: monkey.s?? => false
+ * String: monkey.s99 Pattern: monkey.s?1 => false
+ * String: monkey.s101 Pattern: monkey.s* => true
+ * String: monkey.s99 Pattern: monkey.s*1 => false
+ *
+ * @param str Text to be matched against the given pattern.
+ * @param pat Glob pattern.
+ *
+ * @return true if str matches the pattern, false otherwise.
+ */
+ bool matchString(const char *pat) const;
+ bool matchString(const String &pat) const;
+
+
inline const char *c_str() const { return _str; }
- inline uint size() const { return _len; }
+ inline uint size() const { return _size; }
- inline bool empty() const { return (_len == 0); }
- char lastChar() const { return (_len > 0) ? _str[_len-1] : 0; }
+ inline bool empty() const { return (_size == 0); }
+ char lastChar() const { return (_size > 0) ? _str[_size-1] : 0; }
char operator [](int idx) const {
- assert(_str && idx >= 0 && idx < (int)_len);
+ assert(_str && idx >= 0 && idx < (int)_size);
return _str[idx];
}
/** Remove the last character from the string. */
void deleteLastChar();
-
+
/** Remove the character at position p from the string. */
void deleteChar(uint32 p);
@@ -172,11 +196,19 @@
/** Set character c at position p. */
void insertChar(char c, uint32 p);
+ /** Clears the string, making it empty. */
void clear();
+ /** Convert all characters in the string to lowercase. */
void toLowercase();
+
+ /** Convert all characters in the string to uppercase. */
void toUppercase();
-
+
+ /**
+ * Removes trailing and leading whitespaces. Uses isspace() to decide
+ * what is whitespace and what not.
+ */
void trim();
uint hash() const;
@@ -203,7 +235,7 @@
protected:
void makeUnique();
- void ensureCapacity(uint32 new_len, bool keep_old);
+ void ensureCapacity(uint32 new_size, bool keep_old);
void incRefCount() const;
void decRefCount(int *oldRefCount);
void initWithCStr(const char *str, uint32 len);
@@ -218,7 +250,7 @@
String operator +(const String &x, char y);
String operator +(char x, const String &y);
-// Some useful additional comparision operators for Strings
+// Some useful additional comparison operators for Strings
bool operator == (const char *x, const String &y);
bool operator != (const char *x, const String &y);
@@ -227,16 +259,67 @@
extern char *rtrim(char *t);
extern char *trim(char *t);
+
+/**
+ * Returns the last component of a given path.
+ *
+ * Examples:
+ * /foo/bar.txt would return 'bar.txt'
+ * /foo/bar/ would return 'bar'
+ * /foo/./bar// would return 'bar'
+ *
+ * @param path the path of which we want to know the last component
+ * @param sep character used to separate path components
+ * @return The last component of the path.
+ */
+Common::String lastPathComponent(const Common::String &path, const char sep);
+
+/**
+ * Normalize a gien path to a canonical form. In particular:
+ * - trailing separators are removed: /foo/bar/ -> /foo/bar
+ * - double separators (= empty components) are removed: /foo//bar -> /foo/bar
+ * - dot components are removed: /foo/./bar -> /foo/bar
+ *
+ * @todo remove double dot components: /foo/baz/../bar -> /foo/bar
+ *
+ * @param path the path to normalize
+ * @param sep the separator token (usually '/' on Unix-style systems, or '\\' on Windows based stuff)
+ * @return the normalized path
+ */
+Common::String normalizePath(const Common::String &path, const char sep);
+
+
+/**
+ * Simple DOS-style pattern matching function (understands * and ? like used in DOS).
+ * Taken from exult/files/listfiles.cc
+ *
+ * Token meaning:
+ * "*": any character, any amount of times.
+ * "?": any character, only once.
+ *
+ * Example strings/patterns:
+ * String: monkey.s01 Pattern: monkey.s?? => true
+ * String: monkey.s101 Pattern: monkey.s?? => false
+ * String: monkey.s99 Pattern: monkey.s?1 => false
+ * String: monkey.s101 Pattern: monkey.s* => true
+ * String: monkey.s99 Pattern: monkey.s*1 => false
+ *
+ * @param str Text to be matched against the given pattern.
+ * @param pat Glob pattern.
+ *
+ * @return true if str matches the pattern, false otherwise.
+ */
+bool matchString(const char *str, const char *pat);
+
+
class StringList : public Array<String> {
public:
void push_back(const char *str) {
- ensureCapacity(_size + 1);
- _data[_size++] = str;
+ Array<String>::push_back(str);
}
void push_back(const String &str) {
- ensureCapacity(_size + 1);
- _data[_size++] = str;
+ Array<String>::push_back(str);
}
};
Modified: residual/trunk/common/sys.h
===================================================================
--- residual/trunk/common/sys.h 2009-01-13 21:08:22 UTC (rev 35850)
+++ residual/trunk/common/sys.h 2009-01-13 22:25:33 UTC (rev 35851)
@@ -284,10 +284,6 @@
#define MAXPATHLEN 256
#endif
-#ifndef CDECL
-#define CDECL
-#endif
-
#ifndef NORETURN
#define NORETURN
#endif
Modified: residual/trunk/common/util.h
===================================================================
--- residual/trunk/common/util.h 2009-01-13 21:08:22 UTC (rev 35850)
+++ residual/trunk/common/util.h 2009-01-13 22:25:33 UTC (rev 35851)
@@ -91,20 +91,20 @@
/**
* Generates a random unsigned integer in the interval [0, max].
* @param max the upper bound
- * @return a random number in the interval [0, max].
+ * @return a random number in the interval [0, max]
*/
uint getRandomNumber(uint max);
/**
- * Generates a random unsigned integer in the interval [0, 1].
+ * Generates a random bit, i.e. either 0 or 1.
* Identical to getRandomNumber(1), but faster, hopefully.
- * @return a random number in the interval [0, max].
+ * @return a random bit, either 0 or 1
*/
uint getRandomBit(void);
/**
* Generates a random unsigned integer in the interval [min, max].
* @param min the lower bound
* @param max the upper bound
- * @return a random number in the interval [min, max].
+ * @return a random number in the interval [min, max]
*/
uint getRandomNumberRng(uint min, uint max);
};
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