1 /**
2 * Copyright (c) 2006-2012 LOVE Development Team
3 *
4 * This software is provided 'as-is', without any express or implied
5 * warranty.  In no event will the authors be held liable for any damages
6 * arising from the use of this software.
7 *
8 * Permission is granted to anyone to use this software for any purpose,
9 * including commercial applications, and to alter it and redistribute it
10 * freely, subject to the following restrictions:
11 *
12 * 1. The origin of this software must not be misrepresented; you must not
13 *    claim that you wrote the original software. If you use this software
14 *    in a product, an acknowledgment in the product documentation would be
15 *    appreciated but is not required.
16 * 2. Altered source versions must be plainly marked as such, and must not be
17 *    misrepresented as being the original software.
18 * 3. This notice may not be removed or altered from any source distribution.
19 **/
20 
21 #ifndef LOVE_STRING_MAP_H
22 #define LOVE_STRING_MAP_H
23 
24 #include "Exception.h"
25 
26 namespace love
27 {
28 	template<typename T, unsigned SIZE>
29 	class StringMap
30 	{
31 	private:
32 
33 		struct Record
34 		{
35 			const char * key;
36 			T value;
37 			bool set;
RecordRecord38 			Record() : set(false) {}
39 		};
40 
41 		const static unsigned MAX = SIZE*2;
42 
43 		Record records[MAX];
44 		const char * reverse[SIZE];
45 
46 	public:
47 
48 		struct Entry
49 		{
50 			const char * key;
51 			T value;
52 		};
53 
StringMap(Entry * entries,unsigned num)54 		StringMap(Entry * entries, unsigned num)
55 		{
56 
57 			for (unsigned i = 0; i < SIZE; ++i)
58 				reverse[i] = 0;
59 
60 			unsigned n = num/sizeof(Entry);
61 
62 			for (unsigned i = 0; i < n; ++i)
63 			{
64 				add(entries[i].key, entries[i].value);
65 			}
66 		}
67 
streq(const char * a,const char * b)68 		bool streq(const char * a, const char * b)
69 		{
70 			while (*a != 0 && *b != 0)
71 			{
72 				if (*a != *b)
73 					return false;
74 				++a;
75 				++b;
76 			}
77 
78 			return (*a == 0 && *b == 0);
79 		}
80 
find(const char * key,T & t)81 		bool find(const char * key, T & t)
82 		{
83 			unsigned str_hash = djb2(key);
84 
85 			for (unsigned i = 0; i < MAX; ++i)
86 			{
87 				unsigned str_i = (str_hash + i) % MAX; //this isn't used, is this intentional?
88 
89 				if (!records[str_i].set)
90 					return false;
91 
92 				if (streq(records[str_i].key, key))
93 				{
94 					t = records[str_i].value;
95 					return true;
96 				}
97 			}
98 
99 			return false;
100 		}
101 
find(T key,const char * & str)102 		bool find(T key, const char *& str)
103 		{
104 			unsigned index = (unsigned)key;
105 
106 			if (index >= SIZE)
107 				return false;
108 
109 			if (reverse[index] != 0)
110 			{
111 				str = reverse[index];
112 				return true;
113 			}
114 			else
115 			{
116 				return false;
117 			}
118 		}
119 
add(const char * key,T value)120 		bool add(const char * key, T value)
121 		{
122 			unsigned str_hash = djb2(key);
123 			bool inserted = false;
124 
125 			for (unsigned i = 0; i < MAX; ++i)
126 			{
127 				unsigned str_i = (str_hash + i) % MAX;
128 
129 				if (!records[str_i].set)
130 				{
131 					inserted = true;
132 					records[str_i].set = true;
133 					records[str_i].key = key;
134 					records[str_i].value = value;
135 					break;
136 				}
137 			}
138 
139 			unsigned index = (unsigned)value;
140 
141 			if (index >= SIZE)
142 			{
143 				printf("\nConstant %s out of bounds with %i!\n", key, index);
144 				return false;
145 			}
146 
147 			reverse[index] = key;
148 
149 			return inserted;
150 		}
151 
djb2(const char * key)152 		unsigned djb2(const char * key)
153 		{
154 			unsigned hash = 5381;
155 			int c;
156 
157 			while ((c = *key++))
158 				hash = ((hash << 5) + hash) + c;
159 
160 			return hash;
161 		}
162 
163 	}; // StringMap
164 
165 } // love
166 
167 #endif // LOVE_STRING_MAP_H
168