1 /**
2  * Copyright (c) 2006-2016 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 
29 template<typename T, unsigned int SIZE>
30 class StringMap
31 {
32 public:
33 
34 	struct Entry
35 	{
36 		const char *key;
37 		T value;
38 	};
39 
StringMap(const Entry * entries,unsigned int num)40 	StringMap(const Entry *entries, unsigned int num)
41 	{
42 
43 		for (unsigned int i = 0; i < SIZE; ++i)
44 			reverse[i] = nullptr;
45 
46 		unsigned int n = num / sizeof(Entry);
47 
48 		for (unsigned int i = 0; i < n; ++i)
49 			add(entries[i].key, entries[i].value);
50 	}
51 
streq(const char * a,const char * b)52 	bool streq(const char *a, const char *b)
53 	{
54 		while (*a != 0 && *b != 0)
55 		{
56 			if (*a != *b)
57 				return false;
58 
59 			++a;
60 			++b;
61 		}
62 
63 		return (*a == 0 && *b == 0);
64 	}
65 
find(const char * key,T & t)66 	bool find(const char *key, T &t)
67 	{
68 		unsigned int str_hash = djb2(key);
69 
70 		for (unsigned int i = 0; i < MAX; ++i)
71 		{
72 			unsigned int str_i = (str_hash + i) % MAX;
73 
74 			if (!records[str_i].set)
75 				return false;
76 
77 			if (streq(records[str_i].key, key))
78 			{
79 				t = records[str_i].value;
80 				return true;
81 			}
82 		}
83 
84 		return false;
85 	}
86 
find(T key,const char * & str)87 	bool find(T key, const char *&str)
88 	{
89 		unsigned int index = (unsigned int) key;
90 
91 		if (index >= SIZE)
92 			return false;
93 
94 		if (reverse[index] != nullptr)
95 		{
96 			str = reverse[index];
97 			return true;
98 		}
99 		else
100 		{
101 			return false;
102 		}
103 	}
104 
add(const char * key,T value)105 	bool add(const char *key, T value)
106 	{
107 		unsigned int str_hash = djb2(key);
108 		bool inserted = false;
109 
110 		for (unsigned int i = 0; i < MAX; ++i)
111 		{
112 			unsigned int str_i = (str_hash + i) % MAX;
113 
114 			if (!records[str_i].set)
115 			{
116 				inserted = true;
117 				records[str_i].set = true;
118 				records[str_i].key = key;
119 				records[str_i].value = value;
120 				break;
121 			}
122 		}
123 
124 		unsigned int index = (unsigned int) value;
125 
126 		if (index >= SIZE)
127 		{
128 			printf("Constant %s out of bounds with %u!\n", key, index);
129 			return false;
130 		}
131 
132 		reverse[index] = key;
133 
134 		return inserted;
135 	}
136 
djb2(const char * key)137 	unsigned int djb2(const char *key)
138 	{
139 		unsigned int hash = 5381;
140 		int c;
141 
142 		while ((c = *key++))
143 			hash = ((hash << 5) + hash) + c;
144 
145 		return hash;
146 	}
147 
148 private:
149 
150 	struct Record
151 	{
152 		const char *key;
153 		T value;
154 		bool set;
RecordRecord155 		Record() : set(false) {}
156 	};
157 
158 	static const unsigned int MAX = SIZE * 2;
159 
160 	Record records[MAX];
161 	const char *reverse[SIZE];
162 
163 }; // StringMap
164 
165 } // love
166 
167 #endif // LOVE_STRING_MAP_H
168