[Avida-SVN] r3563 - in development: Avida.xcodeproj source/platform source/tools
brysonda at myxo.css.msu.edu
brysonda at myxo.css.msu.edu
Thu Dec 17 11:39:57 PST 2009
Author: brysonda
Date: 2009-12-17 14:39:57 -0500 (Thu, 17 Dec 2009)
New Revision: 3563
Added:
development/source/tools/tBufferedList.h
Modified:
development/Avida.xcodeproj/project.pbxproj
development/source/platform/platform.h
Log:
Add new tBufferedList class to the tools. This class functions similar to tList externally, but uses backing buffers to store list nodes. Various search operations (Find, FindPtr, Remove) are aided by this architecture, yielding an almost 100% performance improvement on Intel processors(runtime of test case cut in half). Note, however, these search operations are not guaranteed to remove the 'first' matching item in list order, just 'a' matching item. Final note, tBufferedList is not a complete implementation of tList, lacking iterators and various other methods at the moment.
Modified: development/Avida.xcodeproj/project.pbxproj
===================================================================
--- development/Avida.xcodeproj/project.pbxproj 2009-12-16 17:09:47 UTC (rev 3562)
+++ development/Avida.xcodeproj/project.pbxproj 2009-12-17 19:39:57 UTC (rev 3563)
@@ -911,6 +911,7 @@
70C5BC6309059A970028A785 /* cWorld.cc */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = cWorld.cc; sourceTree = "<group>"; };
70C5BD690905CE5F0028A785 /* cHardwareManager.cc */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.cpp.cpp; path = cHardwareManager.cc; sourceTree = "<group>"; };
70C5BD6A0905CE5F0028A785 /* cHardwareManager.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; path = cHardwareManager.h; sourceTree = "<group>"; };
+ 70C8F2F110DABFDF005697AA /* tBufferedList.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = tBufferedList.h; sourceTree = "<group>"; };
70CA6EB208DB7F8200068AC2 /* cFitnessMatrix.cc */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.cpp.cpp; path = cFitnessMatrix.cc; sourceTree = "<group>"; };
70CA6EB408DB7F8200068AC2 /* cGenome.cc */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.cpp.cpp; path = cGenome.cc; sourceTree = "<group>"; };
70CA6EB508DB7F8200068AC2 /* cGenomeUtil.cc */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.cpp.cpp; path = cGenomeUtil.cc; sourceTree = "<group>"; };
@@ -1721,6 +1722,7 @@
DCC314D8076253A2008F7A48 /* tools */ = {
isa = PBXGroup;
children = (
+ 70C8F2F110DABFDF005697AA /* tBufferedList.h */,
7020828D0FB9F2DF00637AD6 /* cBitArray.cc */,
7020828E0FB9F2DF00637AD6 /* cBitArray.h */,
2A57A3FD0D6B954D00FC54C7 /* cProbDemeProbSchedule.cc */,
Modified: development/source/platform/platform.h
===================================================================
--- development/source/platform/platform.h 2009-12-16 17:09:47 UTC (rev 3562)
+++ development/source/platform/platform.h 2009-12-17 19:39:57 UTC (rev 3563)
@@ -52,7 +52,17 @@
# define AVIDA_PLATFORM_APPLE 1
#endif
+#if defined(__hppa__) || defined(__m68k__) || defined(mc68000) || defined(_M_M68K) || \
+ (defined(__MIPS__) && defined(__MISPEB__)) || defined(__ppc__) || defined(__POWERPC__) || defined(_M_PPC) || \
+ defined(__sparc__)
+# define AVIDA_PLATFORM_BIG_ENDIAN 1
+# define AVIDA_PLATFORM_LITTLE_ENDIAN 0
+#else
+# define AVIDA_PLATFORM_BIG_ENDIAN 0
+# define AVIDA_PLATFORM_LITTLE_ENDIAN 1
+#endif
+
#ifdef DEBUG
# include <cstdlib>
# include <iostream>
Added: development/source/tools/tBufferedList.h
===================================================================
--- development/source/tools/tBufferedList.h (rev 0)
+++ development/source/tools/tBufferedList.h 2009-12-17 19:39:57 UTC (rev 3563)
@@ -0,0 +1,244 @@
+/*
+ * tBufferedList.h
+ * Avida
+ *
+ * Created by David on 12/17/09.
+ * Copyright 2009 Michigan State University. All rights reserved.
+ *
+ *
+ * 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; version 2
+ * of the License.
+ *
+ * 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.
+ *
+ */
+
+#ifndef tBufferedList_h
+#define tBufferedList_h
+
+#ifndef platform_h
+#include "platform.h"
+#endif
+#ifndef tManagedPointerArray_h
+#include "tManagedPointerArray.h"
+#endif
+
+#ifndef NULL
+#define NULL 0
+#endif
+
+
+template <class T> class tBufferedList
+{
+protected:
+ typedef union {
+ unsigned int index;
+ struct {
+#if AVIDA_PLATFORM(LITTLE_ENDIAN)
+ unsigned int offset:6;
+ unsigned int num:26;
+#else
+ unsigned int num:26;
+ unsigned int offset:6;
+#endif
+ } buffer;
+ } ListIndex;
+
+ class cNode
+ {
+ public:
+ T* data;
+ cNode* next;
+ cNode* prev;
+ };
+
+ class cBuf
+ {
+ private:
+ cNode* m_nodes;
+
+ public:
+ cBuf() { m_nodes = new cNode[64]; }
+ ~cBuf() { delete [] m_nodes; }
+
+ cNode& operator[](int idx) { return m_nodes[idx]; }
+ const cNode& operator[](int idx) const { return m_nodes[idx]; }
+ };
+
+
+ tManagedPointerArray<cBuf> m_bufs;
+ ListIndex m_next;
+ cNode m_root;
+ int m_size;
+
+
+public:
+ tBufferedList() : m_bufs(1), m_size(0) { m_next.index = 0; m_root.next = &m_root; m_root.prev = &m_root; }
+ explicit tBufferedList(const tBufferedList& in_list) : m_size(0) { Clear(); Append(in_list); }
+ ~tBufferedList() { Clear(); }
+
+
+ inline int GetSize() const { return m_size; }
+
+ inline void Clear()
+ {
+ m_bufs.Resize(1);
+ m_next.index = 0;
+ m_root.next = &m_root;
+ m_root.prev = &m_root;
+ m_size = 0;
+ }
+
+
+ inline const T* GetFirst() const { return m_root.next->data; }
+ inline const T* GetLast() const { return m_root.prev->data; }
+ inline T* GetFirst() { return m_root.next->data; }
+ inline T* GetLast() { return m_root.prev->data; }
+
+ T* GetPos(int pos)
+ {
+ if (pos >= m_size) return NULL;
+ cNode* test_node = m_root.next;
+ for (int i = 0; i < pos; i++) test_node = test_node->next;
+ return test_node->data;
+ }
+
+ const T* GetPos(int pos) const
+ {
+ if (pos >= GetSize()) return NULL;
+ cNode* test_node = m_root.next;
+ for (int i = 0; i < pos; i++) test_node = test_node->next;
+ return test_node->data;
+ }
+
+
+ inline T* Pop() { return removeNode(m_root.next); }
+ inline T* PopRear() { return removeNode(m_root.prev); }
+ inline T* PopPos(int pos)
+ {
+ if (pos >= m_size) return NULL;
+ cNode* test_node = m_root.next;
+ for (int i = 0; i < pos; i++) test_node = test_node->next;
+ return removeNode(test_node);
+ }
+
+
+ void Push(T* val)
+ {
+ cNode& node = m_bufs[m_next.buffer.num][m_next.buffer.offset];
+ node.data = val;
+ node.next = m_root.next;
+ node.prev = &m_root;
+ m_root.next->prev = &node;
+ m_root.next = &node;
+ incSize();
+ }
+
+ void PushRear(T* val)
+ {
+ cNode& node = m_bufs[m_next.buffer.num][m_next.buffer.offset];
+ node.data = val;
+ node.next = &m_root;
+ node.prev = m_root.prev;
+ m_root.prev->next = &node;
+ m_root.prev = &node;
+ incSize();
+ }
+
+
+ inline void CircNext() { if (m_size > 0) PushRear(Pop()); }
+ inline void CircPrev() { if (m_size > 0) Push(PopRear()); }
+
+
+ T* Remove(T* ptr)
+ {
+ if (m_size == 0) return NULL;
+ ListIndex i;
+ for (i.index = 0; i.index < m_size; i.index++) {
+ if (m_bufs[i.buffer.num][i.buffer.offset].data == ptr) return removeNode(&m_bufs[i.buffer.num][i.buffer.offset]);
+ }
+ return NULL;
+ }
+
+
+ // Find by Pointer
+ T* FindPtr(T* ptr) const
+ {
+ if (m_size == 0) return NULL;
+ ListIndex i;
+ for (i.index = 0; i.index < m_size; i.index++) {
+ if (m_bufs[i.buffer.num][i.buffer.offset].data == ptr) return ptr;
+ }
+ return NULL;
+ }
+
+ // Find by Value
+ T* Find(T* val) const
+ {
+ if (m_size == 0) return NULL;
+ ListIndex i;
+ for (i.index = 0; i.index < m_size; i.index++) {
+ if (*m_bufs[i.buffer.num][i.buffer.offset].data == *val) return m_bufs[i.buffer.num][i.buffer.offset].data;
+ }
+ return NULL;
+ }
+
+
+ void Append(const tBufferedList<T>& in_list)
+ {
+ cNode* cur_node = in_list.root.next;
+ while (cur_node != &(in_list.root)) {
+ PushRear(cur_node->data);
+ cur_node = cur_node->next;
+ }
+ }
+
+ inline void Copy(const tBufferedList<T>& in_list) { Clear(); Append(in_list); }
+ inline tBufferedList& operator=(const tBufferedList& list) { Copy(list); return *this; }
+
+
+protected:
+ T* removeNode(cNode* out_node)
+ {
+ // Make sure we're not trying to delete the root node!
+ if (out_node == &m_root) return NULL;
+
+ // Save the data and patch up the linked list.
+ T* out_data = out_node->data;
+ out_node->prev->next = out_node->next;
+ out_node->next->prev = out_node->prev;
+
+ m_next.index--;
+ cNode* next_node = &m_bufs[m_next.buffer.num][m_next.buffer.offset];
+ if (next_node != out_node) {
+ *out_node = *next_node;
+ out_node->next->prev = out_node;
+ out_node->prev->next = out_node;
+ }
+ m_size--;
+
+ if (m_bufs.GetSize() > (m_next.buffer.num + 1) && m_next.buffer.offset < 61) m_bufs.Resize(m_bufs.GetSize() - 1);
+
+ return out_data;
+ }
+
+
+ void incSize()
+ {
+ m_next.index++;
+ if (m_bufs.GetSize() <= m_next.buffer.num) m_bufs.Resize(m_bufs.GetSize() + 1);
+ m_size++;
+ }
+
+};
+
+#endif
More information about the Avida-cvs
mailing list