3 files changed, 112 insertions, 11 deletions

diff --git a/src/core/smallmap_type.hpp b/src/core/smallmap_type.hpp
new file mode 100644
index 000000000..681cacdff
--- /dev/null
+++ b/src/core/smallmap_type.hpp
@@ -0,0 +1,101 @@
+/* $Id$ */
+
+/** @file smallmap_type.hpp Simple mapping class targeted for small sets of data. Stored data shall be POD ("Plain Old Data")! */
+
+#ifndef SMALLMAP_TYPE_HPP
+#define SMALLMAP_TYPE_HPP
+
+#include "smallvec_type.hpp"
+
+/** Simple pair of data. Both types have to be POD ("Plain Old Data")! */
+template <typename T, typename U>
+struct SmallPair {
+	T first;
+	U second;
+
+	/** Initializes this Pair with data */
+	FORCEINLINE SmallPair(const T &first, const U &second) : first(first), second(second) { }
+};
+
+/** Implementation of simple mapping class. Both types have to be POD ("Plain Old Data")!
+ * It has inherited accessors from SmallVector().
+ * @see SmallVector
+ */
+template <typename T, typename U, uint S = 16>
+struct SmallMap : SmallVector<SmallPair<T, U>, S> {
+	typedef ::SmallPair<T, U> Pair;
+	typedef Pair *iterator;
+
+	/** Creates new SmallMap. Data are initialized in SmallVector constructor */
+	FORCEINLINE SmallMap() { }
+	/** Data are freed in SmallVector destructor */
+	FORCEINLINE ~SmallMap() { }
+
+	/** Finds given key in this map
+	 * @param key key to find
+	 * @return &Pair(key, data) if found, this->End() if not
+	 */
+	FORCEINLINE Pair *Find(const T &key)
+	{
+		for (uint i = 0; i < this->items; i++) {
+			if (key == this->data[i].first) return &this->data[i];
+		}
+		return this->End();
+	}
+
+	/** Removes given pair from this map
+	 * @param pair pair to remove
+	 * @return true iff key was found
+	 * @note it has to be pointer to pair in this map. It is overwritten by the last item.
+	 */
+	FORCEINLINE void Erase(Pair *pair)
+	{
+		assert(pair >= this->Begin() && pair < this->End());
+		*pair = this->data[--this->items];
+	}
+
+	/** Removes given key from this map
+	 * @param key key to remove
+	 * @return true iff key was found
+	 * @note last item is moved to its place, so don't increase your iterator if true is returned!
+	 */
+	FORCEINLINE bool Erase(const T &key)
+	{
+		for (uint i = 0; i < this->items; i++) {
+			if (key == this->data[i].first) {
+				this->data[i] = this->data[--this->items];
+				return true;
+			}
+		}
+		return false;
+	}
+
+	/** Adds new item to this map.
+	 * @param key key
+	 * @param data data
+	 * @return true iff the kay wasn't already present
+	 */
+	FORCEINLINE bool Insert(const T &key, const U &data)
+	{
+		if (this->Find(key) != this->End()) return false;
+		new (this->Append()) Pair(key, data);
+		return true;
+	}
+
+	/** Returns data belonging to this key
+	 * @param key key
+	 * @return data belonging to this key
+	 * @note if this key wasn't present, new entry is created
+	 */
+	FORCEINLINE U &operator[](const T &key)
+	{
+		for (uint i = 0; i < this->items; i++) {
+			if (key == this->data[i].first) return this->data[i].second;
+		}
+		Pair *n = this->Append();
+		n->first = key;
+		return n->second;
+	}
+};
+
+#endif /* SMALLMAP_TYPE_HPP */
diff --git a/src/newgrf_engine.cpp b/src/newgrf_engine.cpp
index 1f07ab663..3b950dc8a 100644
--- a/src/newgrf_engine.cpp
+++ b/src/newgrf_engine.cpp
@@ -28,8 +28,7 @@
 #include "rail.h"
 #include "settings_type.h"
 #include "aircraft.h"
-#include "core/smallvec_type.hpp"
-#include <map>
+#include "core/smallmap_type.hpp"
 
 
 int _traininfo_vehicle_pitch = 0;
@@ -1093,7 +1092,7 @@ void AlterVehicleListOrder(EngineID engine, EngineID target)
 void CommitVehicleListOrderChanges()
 {
 	/* List position to Engine map */
-	typedef std::map<uint16, Engine*> ListPositionMap;
+	typedef SmallMap<uint16, Engine *, 16> ListPositionMap;
 	ListPositionMap lptr_map;
 
 	const ListOrderChange *end = _list_order_changes.End();
@@ -1120,7 +1119,8 @@ void CommitVehicleListOrderChanges()
 			uint16 target_position = target_e->list_position;
 
 			bool moving = false;
-			for (ListPositionMap::iterator it = lptr_map.begin(); it != lptr_map.end(); ++it) {
+			const ListPositionMap::Pair *end = lptr_map.End();
+			for (ListPositionMap::Pair *it = lptr_map.Begin(); it != end; ++it) {
 				if (it->first == target_position) moving = true;
 				if (moving) it->second->list_position++;
 			}
@@ -1128,7 +1128,7 @@ void CommitVehicleListOrderChanges()
 			source_e->list_position = target_position;
 		}
 
-		lptr_map.clear();
+		lptr_map.Clear();
 	}
 
 	/* Clear out the queue */
diff --git a/src/town_cmd.cpp b/src/town_cmd.cpp
index de3531557..f660b2fe4 100644
--- a/src/town_cmd.cpp
+++ b/src/town_cmd.cpp
@@ -48,7 +48,7 @@
 #include "functions.h"
 #include "animated_tile_func.h"
 #include "date_func.h"
-#include <map>
+#include "core/smallmap_type.hpp"
 
 #include "table/strings.h"
 #include "table/sprites.h"
@@ -2504,14 +2504,14 @@ Town *ClosestTownFromTile(TileIndex tile, uint threshold)
 }
 
 static bool _town_rating_test = false;
-std::map<const Town *, int> _town_test_ratings;
+SmallMap<const Town *, int, 4> _town_test_ratings;
 
 void SetTownRatingTestMode(bool mode)
 {
 	static int ref_count = 0;
 	if (mode) {
 		if (ref_count == 0) {
-			_town_test_ratings.clear();
+			_town_test_ratings.Clear();
 		}
 		ref_count++;
 	} else {
@@ -2524,9 +2524,9 @@ void SetTownRatingTestMode(bool mode)
 static int GetRating(const Town *t)
 {
 	if (_town_rating_test) {
-		std::map<const Town *, int>::iterator it = _town_test_ratings.find(t);
-		if (it != _town_test_ratings.end()) {
-			return (*it).second;
+		SmallMap<const Town *, int>::iterator it = _town_test_ratings.Find(t);
+		if (it != _town_test_ratings.End()) {
+			return it->second;
 		}
 	}
 	return t->ratings[_current_company];