1 /** 2 Defines a string based multi-map with conserved insertion order. 3 4 Copyright: © 2012-2014 RejectedSoftware e.K. 5 License: Subject to the terms of the MIT license, as written in the included LICENSE.txt file. 6 Authors: Sönke Ludwig 7 */ 8 module vibe.utils.dictionarylist; 9 10 import vibe.utils.array : removeFromArrayIdx; 11 import vibe.utils.string : icmp2; 12 import std.exception : enforce; 13 14 15 /** 16 Behaves similar to $(D VALUE[string]) but the insertion order is not changed 17 and multiple values per key are supported. 18 19 This kind of map is used for MIME headers (e.g. for HTTP, see 20 vibe.inet.message.InetHeaderMap), or for form data 21 (vibe.inet.webform.FormFields). Note that the map can contain fields with 22 the same key multiple times if addField is used for insertion. Insertion 23 order is preserved. 24 25 Note that despite case not being relevant for matching keyse, iterating 26 over the map will yield the original case of the key that was put in. 27 28 Insertion and lookup has O(n) complexity. 29 */ 30 struct DictionaryList(VALUE, bool case_sensitive = true, size_t NUM_STATIC_FIELDS = 32, bool USE_HASHSUM = false) { 31 import std.typecons : Tuple; 32 33 private { 34 alias KeyValue = Tuple!(string, "key", ValueType, "value"); 35 36 static struct Field { 37 static if (USE_HASHSUM) uint keyCheckSum; 38 else { 39 enum keyCheckSum = 0; 40 this(uint, string key, VALUE value) { this.key = key; this.value = value; } 41 } 42 KeyValue tuple; 43 @property ref inout(string) key() inout { return tuple.key; } 44 @property ref inout(VALUE) value() inout { return tuple.value; } 45 } 46 Field[NUM_STATIC_FIELDS] m_fields; 47 size_t m_fieldCount = 0; 48 Field[] m_extendedFields; 49 50 enum bool safeValueCopy = __traits(compiles, (VALUE v) @safe { VALUE vc; vc = v; }); 51 template typedGet(T) { 52 enum typedGet = __traits(compiles, (VALUE v) { return v.get!T; }); 53 } 54 template canAssign(T) { 55 enum canAssign = __traits(compiles, (T t) { VALUE v = t; }); 56 } 57 } 58 59 alias ValueType = VALUE; 60 61 struct FieldTuple { string key; ValueType value; } 62 63 /** The number of fields present in the map. 64 */ 65 @property size_t length() const { return m_fieldCount + m_extendedFields.length; } 66 67 /// Supports serialization using vibe.data.serialization. 68 static DictionaryList fromRepresentation(FieldTuple[] array) 69 { 70 DictionaryList ret; 71 foreach (ref v; array) ret.addField(v.key, v.value); 72 return ret; 73 } 74 /// ditto 75 FieldTuple[] toRepresentation() { 76 FieldTuple[] ret; 77 foreach (k, ref v; this) ret ~= FieldTuple(k, v); 78 return ret; 79 } 80 81 /** Generates an associative-array equivalent string representation of the dictionary. 82 */ 83 void toString(scope void delegate(const(char)[] str) @safe sink) 84 const { 85 sink("["); 86 bool first = true; 87 88 foreach (k, v; this.byKeyValue) { 89 if (!first) sink(", "); 90 else first = false; 91 () @trusted { 92 import std.format : formattedWrite; 93 string[] ka = (&k)[0 .. 1]; 94 ValueType[] va = (&v)[0 .. 1]; 95 sink.formattedWrite("%(%s%): %(%s%)", ka, va); 96 } (); 97 } 98 sink("]"); 99 } 100 /// ditto 101 void toString(scope void delegate(const(char)[] str) @system sink) 102 const { 103 toString(cast(void delegate(const(char)[]) @safe)sink); 104 } 105 /// ditto 106 string toString() 107 const { 108 import std.array : appender; 109 auto ret = appender!string(); 110 toString((s) { ret.put(s); }); 111 return ret.data; 112 } 113 114 /** Removes the first field that matches the given key. 115 */ 116 void remove(string key) 117 { 118 static if (USE_HASHSUM) auto keysum = computeCheckSumI(key); 119 enum keysum = 0; 120 auto idx = getIndex(m_fields[0 .. m_fieldCount], key, keysum); 121 if( idx >= 0 ){ 122 auto slice = m_fields[0 .. m_fieldCount]; 123 removeFromArrayIdx(slice, idx); 124 m_fieldCount--; 125 } else { 126 idx = getIndex(m_extendedFields, key, keysum); 127 enforce(idx >= 0); 128 removeFromArrayIdx(m_extendedFields, idx); 129 } 130 } 131 132 /** Removes all fields that matches the given key. 133 */ 134 void removeAll(string key) 135 { 136 static if (USE_HASHSUM) auto keysum = computeCheckSumI(key); 137 else enum keysum = 0; 138 for (size_t i = 0; i < m_fieldCount;) { 139 if (m_fields[i].keyCheckSum == keysum && matches(m_fields[i].key, key)) { 140 auto slice = m_fields[0 .. m_fieldCount]; 141 removeFromArrayIdx(slice, i); 142 m_fieldCount--; 143 } else i++; 144 } 145 146 for (size_t i = 0; i < m_extendedFields.length;) { 147 if (m_fields[i].keyCheckSum == keysum && matches(m_fields[i].key, key)) 148 removeFromArrayIdx(m_extendedFields, i); 149 else i++; 150 } 151 } 152 153 /** Adds a new field to the map. 154 155 The new field will be added regardless of any existing fields that 156 have the same key, possibly resulting in duplicates. Use opIndexAssign 157 if you want to avoid duplicates. 158 */ 159 void addField(string key, ValueType value) 160 { 161 static if (USE_HASHSUM) auto keysum = computeCheckSumI(key); 162 else enum keysum = 0; 163 if (m_fieldCount < m_fields.length) 164 m_fields[m_fieldCount++] = Field(keysum, key, value); 165 else m_extendedFields ~= Field(keysum, key, value); 166 } 167 168 void addField(T)(string key, T value) 169 if (canAssign!T) 170 { 171 ValueType convertedValue = value; 172 addField(key, convertedValue); 173 } 174 175 /** Returns the first field that matches the given key. 176 177 If no field is found, def_val is returned. 178 */ 179 inout(ValueType) get(string key, lazy inout(ValueType) def_val = ValueType.init) 180 inout { 181 if (auto pv = key in this) return *pv; 182 return def_val; 183 } 184 185 // DMD bug: cannot set T.init as default value for def_val parameter, 186 // because compilation fails with message: 187 // Error: undefined identifier 'T' 188 /// ditto 189 inout(T) get(T)(string key, lazy inout(T) def_val) 190 inout if (typedGet!T) { 191 if (auto pv = key in this) return (*pv).get!T; 192 return def_val; 193 } 194 195 /// ditto 196 inout(T) get(T)(string key) // Work around DMD bug 197 inout if (typedGet!T) { 198 return get!T(key, T.init); 199 } 200 201 /** Returns all values matching the given key. 202 203 Note that the version returning an array will allocate for each call. 204 */ 205 const(ValueType)[] getAll(string key) 206 const @trusted { // appender 207 import std.array; 208 auto ret = appender!(const(ValueType)[])(); 209 getAll(key, (v) @trusted { ret.put(v); }); 210 return ret.data; 211 } 212 /// ditto 213 void getAll(string key, scope void delegate(const(ValueType)) @safe del) 214 const { 215 static if (USE_HASHSUM) uint keysum = computeCheckSumI(key); 216 else enum keysum = 0; 217 foreach (ref f; m_fields[0 .. m_fieldCount]) { 218 static if (USE_HASHSUM) 219 if (f.keyCheckSum != keysum) continue; 220 if (matches(f.key, key)) del(f.value); 221 } 222 foreach (ref f; m_extendedFields) { 223 static if (USE_HASHSUM) 224 if (f.keyCheckSum != keysum) continue; 225 if (matches(f.key, key)) del(f.value); 226 } 227 } 228 229 /** Returns the first value matching the given key. 230 */ 231 inout(ValueType) opIndex(string key) 232 inout { 233 auto pitm = key in this; 234 enforce(pitm !is null, "Accessing non-existent key '"~key~"'."); 235 return *pitm; 236 } 237 238 /** Adds or replaces the given field with a new value. 239 */ 240 ValueType opIndexAssign(ValueType val, string key) 241 { 242 static if (USE_HASHSUM) auto keysum = computeCheckSumI(key); 243 else enum keysum = 0; 244 auto pitm = key in this; 245 if (pitm) *pitm = val; 246 else if (m_fieldCount < m_fields.length) m_fields[m_fieldCount++] = Field(keysum, key, val); 247 else m_extendedFields ~= Field(keysum, key, val); 248 return val; 249 } 250 251 /// ditto 252 ValueType opIndexAssign(T)(T val, string key) 253 if (canAssign!T) 254 { 255 ValueType convertedVal = val; 256 return opIndexAssign(convertedVal, key); 257 } 258 259 /** Returns a pointer to the first field that matches the given key. 260 */ 261 inout(ValueType)* opBinaryRight(string op)(string key) inout if(op == "in") 262 { 263 static if (USE_HASHSUM) uint keysum = computeCheckSumI(key); 264 else enum keysum = 0; 265 auto idx = getIndex(m_fields[0 .. m_fieldCount], key, keysum); 266 if (idx >= 0) return &m_fields[idx].tuple[1]; 267 idx = getIndex(m_extendedFields, key, keysum); 268 if (idx >= 0) return &m_extendedFields[idx].tuple[1]; 269 return null; 270 } 271 /// ditto 272 bool opBinaryRight(string op)(string key) inout if(op == "!in") { 273 return !(key in this); 274 } 275 276 /** Iterates over all fields, including duplicates. 277 */ 278 auto byKeyValue() {return Rng!false(&this, 0); } 279 /// ditto 280 auto byKeyValue() const { return Rng!true(&this, 0); } 281 /// ditto 282 auto byKey() inout { import std.algorithm.iteration : map; return byKeyValue().map!(p => p[0]); } 283 /// ditto 284 auto byValue() inout { import std.algorithm.iteration : map; return byKeyValue().map!(p => p[1]); } 285 286 /// Deprecated in favor of `.byKeyValue` - enables foreach iteration over a `DictionaryList` with two loop variables. 287 deprecated("Iterate over .byKeyValue instead.") 288 alias byKeyValue this; 289 290 static if (is(typeof({ const(ValueType) v; ValueType w; w = v; }))) { 291 /** Duplicates the header map. 292 */ 293 @property DictionaryList dup() 294 const { 295 DictionaryList ret; 296 ret.m_fields[0 .. m_fieldCount] = m_fields[0 .. m_fieldCount]; 297 ret.m_fieldCount = m_fieldCount; 298 ret.m_extendedFields = m_extendedFields.dup; 299 return ret; 300 } 301 } 302 303 private ptrdiff_t getIndex(in Field[] map, string key, uint keysum) 304 const { 305 foreach (i, ref const(Field) entry; map) { 306 static if (USE_HASHSUM) if (entry.keyCheckSum != keysum) continue; 307 if (matches(entry.key, key)) return i; 308 } 309 return -1; 310 } 311 312 private static bool matches(string a, string b) 313 { 314 static if (case_sensitive) return a == b; 315 else return a.length == b.length && icmp2(a, b) == 0; 316 } 317 318 // very simple check sum function with a good chance to match 319 // strings with different case equal 320 static if (USE_HASHSUM) private static uint computeCheckSumI(string s) 321 @trusted { 322 uint csum = 0; 323 immutable(char)* pc = s.ptr, pe = s.ptr + s.length; 324 for (; pc != pe; pc++) { 325 static if (case_sensitive) csum ^= *pc; 326 else csum ^= *pc & 0x1101_1111; 327 csum = (csum << 1) | (csum >> 31); 328 } 329 return csum; 330 } 331 332 private static struct Rng(bool CONST) { 333 @safe nothrow @nogc: 334 static if (CONST) { 335 alias KVT = const(KeyValue); 336 const(DictionaryList)* list; 337 } else { 338 alias KVT = KeyValue; 339 DictionaryList* list; 340 } 341 size_t idx; 342 343 @property bool empty() const { return idx >= list.length; } 344 @property ref KVT front() { 345 if (idx < list.m_fieldCount) 346 return list.m_fields[idx].tuple; 347 return list.m_extendedFields[idx - list.m_fieldCount].tuple; 348 } 349 void popFront() { idx++; } 350 } 351 } 352 353 static assert(DictionaryList!(string, true, 2).safeValueCopy); 354 355 @safe unittest { 356 DictionaryList!(int, true) a; 357 a.addField("a", 1); 358 a.addField("a", 2); 359 assert(a["a"] == 1); 360 assert(a.getAll("a") == [1, 2]); 361 a["a"] = 3; 362 assert(a["a"] == 3); 363 assert(a.getAll("a") == [3, 2]); 364 a.removeAll("a"); 365 assert(a.getAll("a").length == 0); 366 assert(a.get("a", 4) == 4); 367 a.addField("b", 2); 368 a.addField("b", 1); 369 a.remove("b"); 370 assert(a.getAll("b") == [1]); 371 372 DictionaryList!(int, false) b; 373 b.addField("a", 1); 374 b.addField("A", 2); 375 assert(b["A"] == 1); 376 assert(b.getAll("a") == [1, 2]); 377 } 378 379 unittest { 380 import std.variant : Variant; 381 DictionaryList!(Variant) c; 382 c["a"] = true; 383 c["b"] = "Hello"; 384 assert(c.get("a").type == typeid(bool)); 385 assert(c.get!string("b") == "Hello"); 386 assert(c.get!int("c") == int.init); 387 c.addField("d", 9); 388 c.addField("d", "bar"); 389 assert(c.getAll("d") == [ cast(Variant) 9, cast(Variant) "bar" ]); 390 } 391 392 @safe unittest { 393 import std.conv : text; 394 DictionaryList!int l; 395 l["foo"] = 42; 396 l["bar"] = 43; 397 assert(text(l) == `["foo": 42, "bar": 43]`, text(l)); 398 assert(l.toString() == `["foo": 42, "bar": 43]`, l.toString()); 399 }