From 98decfffefc49c82f20a0453cef823f7588e7654 Mon Sep 17 00:00:00 2001 From: Alexis211 Date: Tue, 22 Dec 2009 15:01:07 +0100 Subject: Added template class Map --- Melon.img | Bin 1474560 -> 1474560 bytes Source/Kernel/Core/kmain.wtf.cpp | 2 ++ Source/Library/Common/Map.class.cpp | 38 ++++++++++++++++++++++++++ Source/Library/Common/Map.class.h | 53 ++++++++++++++++++++++++++++++++++++ 4 files changed, 93 insertions(+) create mode 100644 Source/Library/Common/Map.class.cpp create mode 100644 Source/Library/Common/Map.class.h diff --git a/Melon.img b/Melon.img index 54e8877..8755cd0 100644 Binary files a/Melon.img and b/Melon.img differ diff --git a/Source/Kernel/Core/kmain.wtf.cpp b/Source/Kernel/Core/kmain.wtf.cpp index ad11eaf..069bf5f 100644 --- a/Source/Kernel/Core/kmain.wtf.cpp +++ b/Source/Kernel/Core/kmain.wtf.cpp @@ -33,6 +33,8 @@ #include #include +#include + #include extern u32int end; //Placement address diff --git a/Source/Library/Common/Map.class.cpp b/Source/Library/Common/Map.class.cpp new file mode 100644 index 0000000..d9a4e39 --- /dev/null +++ b/Source/Library/Common/Map.class.cpp @@ -0,0 +1,38 @@ +template +Map::Map() { + m_root = 0; +} + +template +Map::~Map() { + if (m_root != 0) delete m_root; +} + +template +bool Map::has(const K& key) { + return (find(key, m_root) != 0); +} + +template +void Map::set(const K& key, const V& value) { + item_t* i = find(key, m_root); + if (i == 0) m_root = insert(key, value, m_root); + else i->value = value; +} + +template +const V& Map::get(const K& key) { + item_t* i = find(key); + if (i == 0) return m_null; + return i->value; +} + +template +V& Map::operator[] (const K& key) { + item_t* i = find(key, m_root); + if (i == 0) { + m_root = insert(key, m_null, m_root); + i = find(key, m_root); + } + return i->value; +} diff --git a/Source/Library/Common/Map.class.h b/Source/Library/Common/Map.class.h new file mode 100644 index 0000000..1270752 --- /dev/null +++ b/Source/Library/Common/Map.class.h @@ -0,0 +1,53 @@ +#ifndef DEF_MAP_CLASS_H +#define DEF_MAP_CLASS_H + +template +class Map { + private: + V m_null; + struct item_t { + item_t *prev, *next; + K key; + V value; + item_t(const K& _key, const V& _value) : prev(0), next(0), key(_key), value(_value) {} + ~item_t() { + if (prev != 0) delete prev; + if (next != 0) delete next; + } + } *m_root; + + //Recursive functions for internal use + item_t* find(const K& key, item_t* start) { + if (start == 0) return 0; + if (start->key == key) return start; + if (start->key > key) return find(key, start->prev); + if (start->key < key) return find(key, start->next); + return 0; + } + item_t* insert(const K& key, const V& value, item_t* start) { + if (start == 0) return new item_t(key, value); + if (start->key == key) return 0; + if (start->key > key) { + start->prev = insert(key, value, start->prev); + return start; + } + if (start->key < key) { + start->next = insert(key, value, start->next); + return start; + } + return 0; + } + + public: + Map(); + ~Map(); + + bool has(const K& key); + void set(const K& key, const V& value); + const V& get(const K& key); + V& operator[] (const K& key); +}; + +#include "Map.class.cpp" + +#endif -- cgit v1.2.3