1//
2// Copyright (c) Microsoft. All rights reserved.
3// Licensed under the MIT license. See LICENSE file in the project root for full license information.
4//
5
6//----------------------------------------------------------
7// LightWeightMap.h -
8// Notes:
9// improvements:
10// 1. we could pack the size down a bit with various encoding tricks (don't use 4 bytes for the numItems etc)
11// 2. Add() could find the right place to insert via binary search... though the list is normally very small
12// 3. Buffer encoding could easily be more compact
13//----------------------------------------------------------
14#ifndef _LightWeightMap
15#define _LightWeightMap
16
17#include "errorhandling.h"
18
19//#define DEBUG_LWM
20
21// Common base class that implements the raw buffer functionality.
22class LightWeightMapBuffer
23{
24public:
25 LightWeightMapBuffer()
26 {
27 InitialClear();
28 }
29
30 LightWeightMapBuffer(const LightWeightMapBuffer& lwm)
31 {
32 InitialClear();
33 bufferLength = lwm.bufferLength;
34
35 if ((lwm.buffer != nullptr) && (lwm.bufferLength > 0))
36 {
37 buffer = new unsigned char[lwm.bufferLength];
38 memcpy(buffer, lwm.buffer, lwm.bufferLength);
39 }
40 }
41
42 ~LightWeightMapBuffer()
43 {
44 delete[] buffer;
45 }
46
47 unsigned int AddBuffer(const unsigned char* buff, unsigned int len)
48 {
49 return AddBuffer(buff, len, false);
50 }
51
52 unsigned int AddBuffer(const unsigned char* buff, unsigned int len, bool forceUnique)
53 {
54 if (len == 0)
55 return -1;
56 if (buff == nullptr)
57 return -1;
58 int index = Contains(buff, len); // See if there is already a copy of this data in our buffer
59 if ((index != -1) && (!forceUnique))
60 return index;
61 if (locked)
62 {
63 LogError("Added item that extended the buffer after it was locked by a call to GetBuffer()");
64 __debugbreak();
65 }
66
67 unsigned int newbuffsize = bufferLength + sizeof(unsigned int) + len;
68 unsigned char* newbuffer = new unsigned char[newbuffsize];
69 unsigned int newOffset = bufferLength;
70 if (bufferLength > 0)
71 memcpy(newbuffer, buffer, bufferLength);
72 memcpy(newbuffer + bufferLength + sizeof(unsigned int), buff, len);
73 *((unsigned int*)(newbuffer + bufferLength)) = len;
74 bufferLength += sizeof(unsigned int) + len;
75 if (buffer != nullptr)
76 delete[] buffer;
77 buffer = newbuffer;
78 return newOffset + sizeof(unsigned int);
79 }
80
81 unsigned char* GetBuffer(unsigned int offset)
82 {
83 if (offset == (unsigned int)-1)
84 return nullptr;
85 AssertCodeMsg(offset < bufferLength, EXCEPTIONCODE_LWM, "Hit offset bigger than bufferLength %u >= %u", offset,
86 bufferLength);
87 locked = true;
88 // LogDebug("Address given %p", &buffer[offset]);
89 return &buffer[offset];
90 }
91
92 int Contains(const unsigned char* buff, unsigned int len)
93 {
94#ifdef DEBUG_LWM
95 LogDebug("New call to Contains %d {", len);
96 for (int i = 0; i < len; i++)
97 LogDebug("0x%02x ", buff[len]);
98 LogDebug("}");
99#endif
100 if (len == 0)
101 return -1;
102 if (bufferLength == 0)
103 return -1;
104 unsigned int offset = 0;
105 while ((offset + sizeof(unsigned int) + len) <= bufferLength)
106 {
107 unsigned int buffChunkLen = *(unsigned int*)(&buffer[offset]);
108#ifdef DEBUG_LWM
109 LogDebug("Investigating len %d @ %d", buffChunkLen, offset);
110#endif
111 if (buffChunkLen == len)
112 {
113#ifdef DEBUG_LWM
114 LogDebug("peering into {");
115 for (int i = 0; i < len; i++)
116 LogDebug("0x%02x ", buff[len]);
117 LogDebug("}");
118#endif
119 if (memcmp(&buffer[offset + sizeof(unsigned int)], buff, len) == 0)
120 {
121#ifdef DEBUG_LWM
122 LogDebug("Found!");
123#endif
124 return offset + sizeof(unsigned int);
125 }
126 }
127 offset += sizeof(unsigned int) + buffChunkLen;
128 }
129#ifdef DEBUG_LWM
130 LogDebug("NOT Found!");
131#endif
132 return -1;
133 }
134
135 void Unlock() // did you really mean to use this?
136 {
137 locked = false;
138 }
139
140protected:
141 void InitialClear()
142 {
143 buffer = nullptr;
144 bufferLength = 0;
145 locked = false;
146 }
147
148 unsigned char* buffer; // TODO-Cleanup: this should really be a linked list; we reallocate it with every call to
149 // AddBuffer().
150 unsigned int bufferLength;
151 bool locked;
152};
153
154template <typename _Key, typename _Item>
155class LightWeightMap : public LightWeightMapBuffer
156{
157public:
158 LightWeightMap()
159 {
160 InitialClear();
161 }
162
163 LightWeightMap(const LightWeightMap& lwm)
164 {
165 InitialClear();
166 numItems = lwm.numItems;
167 strideSize = lwm.strideSize;
168 bufferLength = lwm.bufferLength;
169 locked = false;
170
171 pKeys = nullptr;
172 pItems = nullptr;
173
174 if (lwm.pKeys != nullptr)
175 {
176 pKeys = new _Key[numItems];
177 memcpy(pKeys, lwm.pKeys, numItems * sizeof(_Key));
178 }
179 if (lwm.pItems != nullptr)
180 {
181 pItems = new _Item[numItems];
182 memcpy(pItems, lwm.pItems, numItems * sizeof(_Item));
183 }
184 if ((lwm.buffer != nullptr) && (lwm.bufferLength > 0))
185 {
186 buffer = new unsigned char[lwm.bufferLength];
187 memcpy(buffer, lwm.buffer, lwm.bufferLength);
188 }
189 }
190
191 ~LightWeightMap()
192 {
193 if (pKeys != nullptr)
194 delete[] pKeys;
195 if (pItems != nullptr)
196 delete[] pItems;
197 }
198
199 void ReadFromArray(const unsigned char* rawData, unsigned int size)
200 {
201 unsigned int sizeOfKey = sizeof(_Key);
202 unsigned int sizeOfItem = sizeof(_Item);
203 const unsigned char* ptr = rawData;
204
205 // The tag is optional, to roll forward previous formats which don't have
206 // the tag, but which also have the same format.
207 if (0 == memcmp(ptr, "LWM1", 4))
208 {
209 ptr += 4;
210 }
211
212 memcpy(&numItems, ptr, sizeof(unsigned int));
213 ptr += sizeof(unsigned int);
214 strideSize = numItems;
215
216 if (numItems > 0)
217 {
218 // Read the buffersize
219 memcpy(&bufferLength, ptr, sizeof(unsigned int));
220 ptr += sizeof(unsigned int);
221
222 AssertCodeMsg(pKeys == nullptr, EXCEPTIONCODE_LWM, "Found existing pKeys");
223 pKeys = new _Key[numItems];
224 // Set the Keys
225 memcpy(pKeys, ptr, sizeOfKey * numItems);
226 ptr += sizeOfKey * numItems;
227
228 AssertCodeMsg(pItems == nullptr, EXCEPTIONCODE_LWM, "Found existing pItems");
229 pItems = new _Item[numItems];
230 // Set the Items
231 memcpy(pItems, ptr, sizeOfItem * numItems);
232 ptr += sizeOfItem * numItems;
233
234 AssertCodeMsg(buffer == nullptr, EXCEPTIONCODE_LWM, "Found existing buffer");
235 buffer = new unsigned char[bufferLength];
236 // Read the buffer
237 memcpy(buffer, ptr, bufferLength * sizeof(unsigned char));
238 ptr += bufferLength * sizeof(unsigned char);
239 }
240
241 // If we have RTTI, we can make this assert report the correct type. No RTTI, though, when
242 // built with .NET Core, especially when built against the PAL.
243 AssertCodeMsg((ptr - rawData) == size, EXCEPTIONCODE_LWM, "%s - Ended with unexpected sizes %Ix != %x",
244 "Unknown type" /*typeid(_Item).name()*/, ptr - rawData, size);
245 }
246
247 unsigned int CalculateArraySize()
248 {
249 int size = 4 /* tag */ + sizeof(unsigned int) /* numItems */;
250 if (numItems > 0)
251 {
252 size += sizeof(unsigned int); // size of bufferLength
253 size += sizeof(_Key) * numItems; // size of keyset
254 size += sizeof(_Item) * numItems; // size of itemset
255 size += sizeof(unsigned char) * bufferLength; // bulk size of raw buffer
256 }
257 return size;
258 }
259
260 unsigned int DumpToArray(unsigned char* bytes)
261 {
262 unsigned char* ptr = bytes;
263 unsigned int size = CalculateArraySize();
264
265 // Write the tag
266 memcpy(ptr, "LWM1", 4);
267 ptr += 4;
268
269 // Write the header
270 memcpy(ptr, &numItems, sizeof(unsigned int));
271 ptr += sizeof(unsigned int);
272
273 if (numItems > 0)
274 {
275 unsigned int sizeOfKey = sizeof(_Key);
276 unsigned int sizeOfItem = sizeof(_Item);
277
278 // Write the buffersize
279 memcpy(ptr, &bufferLength, sizeof(unsigned int));
280 ptr += sizeof(unsigned int);
281
282 // Write the Keys
283 memcpy(ptr, pKeys, sizeOfKey * numItems);
284 ptr += sizeOfKey * numItems;
285
286 // Write the Items
287 memcpy(ptr, pItems, sizeOfItem * numItems);
288 ptr += sizeOfItem * numItems;
289
290 // Write the buffer
291 memcpy(ptr, buffer, bufferLength * sizeof(unsigned char));
292 ptr += bufferLength * sizeof(unsigned char);
293 }
294
295 // If we have RTTI, we can make this assert report the correct type. No RTTI, though, when
296 // built with .NET Core, especially when built against the PAL.
297 AssertCodeMsg((ptr - bytes) == size, EXCEPTIONCODE_LWM, "%s - Ended with unexpected sizes %p != %x",
298 "Unknown type" /*typeid(_Item).name()*/, (void*)(ptr - bytes), size);
299 return size;
300 }
301
302 // its worth noting that the acutal order of insert here doesnt meet what you migth expect. Its using memcmp, so
303 // since we are on a little endian machine we'd use the lowest 8 bits as the first part of the key. This is
304 // a side effect of using the same code for large structs and DWORDS etc...
305 bool Add(_Key key, _Item item)
306 {
307 // Make sure we have space left, expand if needed
308 if (numItems == strideSize)
309 {
310 _Key* tKeys = pKeys;
311 _Item* tItems = pItems;
312 pKeys = new _Key[(strideSize * 2) + 4];
313 memcpy(pKeys, tKeys, strideSize * sizeof(_Key));
314 pItems = new _Item[(strideSize * 2) + 4];
315 memcpy(pItems, tItems, strideSize * sizeof(_Item));
316 strideSize = (strideSize * 2) + 4;
317 delete[] tKeys;
318 delete[] tItems;
319 }
320 unsigned int insert = 0;
321 // Find the right place to insert O(n) version
322 /* for(;insert < numItems; insert++)
323 {
324 int res = memcmp(&pKeys[insert], &key, sizeof(_Key));
325 if(res == 0)
326 return false;
327 if(res>0)
328 break;
329 }
330 */
331 // O(log n) version
332 int first = 0;
333 int mid = 0;
334 int last = numItems - 1;
335 while (first <= last)
336 {
337 mid = (first + last) / 2; // compute mid point.
338 int res = memcmp(&pKeys[mid], &key, sizeof(_Key));
339
340 if (res < 0)
341 first = mid + 1; // repeat search in top half.
342 else if (res > 0)
343 last = mid - 1; // repeat search in bottom half.
344 else
345 return false; // found it. return position /////
346 }
347 insert = first;
348 if (insert != first)
349 {
350 LogDebug("index = %u f %u mid = %u l %u***************************", insert, first, mid, last);
351 __debugbreak();
352 }
353
354 if (numItems > 0)
355 {
356 for (unsigned int i = numItems; i > insert; i--)
357 {
358 pKeys[i] = pKeys[i - 1];
359 pItems[i] = pItems[i - 1];
360 }
361 }
362
363 pKeys[insert] = key;
364 pItems[insert] = item;
365 numItems++;
366 return true;
367 }
368
369 int GetIndex(_Key key)
370 {
371 AssertCodeMsg(this != nullptr, EXCEPTIONCODE_MC, "There is no such LWM (in GetIndex)");
372 if (numItems == 0)
373 return -1;
374
375 // O(log n) version
376 int first = 0;
377 int mid = 0;
378 int last = numItems - 1;
379 while (first <= last)
380 {
381 mid = (first + last) / 2; // compute mid point.
382 int res = memcmp(&pKeys[mid], &key, sizeof(_Key));
383
384 if (res < 0)
385 first = mid + 1; // repeat search in top half.
386 else if (res > 0)
387 last = mid - 1; // repeat search in bottom half.
388 else
389 return mid; // found it. return position /////
390 }
391 return -1; // Didn't find key
392 }
393
394 _Item GetItem(int index)
395 {
396 AssertCodeMsg(index != -1, EXCEPTIONCODE_LWM, "Didn't find Key");
397 return pItems[index]; // found it. return position /////
398 }
399
400 _Key GetKey(int index)
401 {
402 AssertCodeMsg(index != -1, EXCEPTIONCODE_LWM, "Didn't find Key (in GetKey)");
403 return pKeys[index];
404 }
405
406 _Item Get(_Key key)
407 {
408 int index = GetIndex(key);
409 AssertCodeMsg(index != -1, EXCEPTIONCODE_MC, "Didn't find Item (in Get)");
410 return GetItem(index);
411 }
412
413 _Item* GetRawItems()
414 {
415 return pItems;
416 }
417
418 _Key* GetRawKeys()
419 {
420 return pKeys;
421 }
422
423 unsigned int GetCount()
424 {
425 return numItems;
426 }
427
428private:
429 void InitialClear()
430 {
431 numItems = 0;
432 strideSize = 0;
433 pKeys = nullptr;
434 pItems = nullptr;
435 }
436
437 unsigned int numItems; // Number of active items in the pKeys and pItems arrays.
438 unsigned int strideSize; // Allocated count of items in the pKeys and pItems arrays.
439 _Key* pKeys;
440 _Item* pItems;
441};
442
443// Second implementation of LightWeightMap where the Key type is an unsigned int in the range [0 .. numItems - 1] (where
444// numItems is the number of items stored in the map). Keys are not stored, since the index into the pItems array is
445// the key. Appending to the end of the map is O(1), since we don't have to search for it, and we don't have to move
446// anything down.
447
448template <typename _Item>
449class DenseLightWeightMap : public LightWeightMapBuffer
450{
451public:
452 DenseLightWeightMap()
453 {
454 InitialClear();
455 }
456
457 DenseLightWeightMap(const DenseLightWeightMap& lwm)
458 {
459 InitialClear();
460 numItems = lwm.numItems;
461 strideSize = lwm.strideSize;
462 bufferLength = lwm.bufferLength;
463
464 if (lwm.pItems != nullptr)
465 {
466 pItems = new _Item[numItems];
467 memcpy(pItems, lwm.pItems, numItems * sizeof(_Item));
468 }
469 if ((lwm.buffer != nullptr) && (lwm.bufferLength > 0))
470 {
471 buffer = new unsigned char[lwm.bufferLength];
472 memcpy(buffer, lwm.buffer, lwm.bufferLength);
473 }
474 }
475
476 ~DenseLightWeightMap()
477 {
478 if (pItems != nullptr)
479 delete[] pItems;
480 }
481
482 void ReadFromArray(const unsigned char* rawData, unsigned int size)
483 {
484 unsigned int sizeOfItem = sizeof(_Item);
485 const unsigned char* ptr = rawData;
486
487 // Check tag; if this is a v1 LWM, convert it to a DenseLightWeightMap in memory
488 if (0 != memcmp(ptr, "DWM1", 4))
489 {
490 ReadFromArrayAndConvertLWM1(rawData, size);
491 return;
492 }
493 ptr += 4;
494
495 memcpy(&numItems, ptr, sizeof(unsigned int));
496 ptr += sizeof(unsigned int);
497 strideSize = numItems;
498
499 if (numItems > 0)
500 {
501 // Read the buffersize
502 memcpy(&bufferLength, ptr, sizeof(unsigned int));
503 ptr += sizeof(unsigned int);
504
505 AssertCodeMsg(pItems == nullptr, EXCEPTIONCODE_LWM, "Found existing pItems");
506 pItems = new _Item[numItems];
507 // Set the Items
508 memcpy(pItems, ptr, sizeOfItem * numItems);
509 ptr += sizeOfItem * numItems;
510
511 AssertCodeMsg(buffer == nullptr, EXCEPTIONCODE_LWM, "Found existing buffer");
512 buffer = new unsigned char[bufferLength];
513 // Read the buffer
514 memcpy(buffer, ptr, bufferLength * sizeof(unsigned char));
515 ptr += bufferLength * sizeof(unsigned char);
516 }
517
518 AssertCodeMsg((ptr - rawData) == size, EXCEPTIONCODE_LWM, "Ended with unexpected sizes %Ix != %x",
519 ptr - rawData, size);
520 }
521
522private:
523 void ReadFromArrayAndConvertLWM1(const unsigned char* rawData, unsigned int size)
524 {
525 unsigned int sizeOfKey = sizeof(DWORD);
526 unsigned int sizeOfItem = sizeof(_Item);
527 const unsigned char* ptr = rawData;
528
529 memcpy(&numItems, ptr, sizeof(unsigned int));
530 ptr += sizeof(unsigned int);
531 strideSize = numItems;
532
533 if (numItems > 0)
534 {
535 // Read the buffersize
536 memcpy(&bufferLength, ptr, sizeof(unsigned int));
537 ptr += sizeof(unsigned int);
538
539 DWORD* tKeys = new DWORD[numItems];
540 // Set the Keys
541 memcpy(tKeys, ptr, sizeOfKey * numItems);
542 ptr += sizeOfKey * numItems;
543
544 _Item* tItems = new _Item[numItems];
545 // Set the Items
546 memcpy(tItems, ptr, sizeOfItem * numItems);
547 ptr += sizeOfItem * numItems;
548
549 AssertCodeMsg(buffer == nullptr, EXCEPTIONCODE_LWM, "Found existing buffer");
550 buffer = new unsigned char[bufferLength];
551 // Read the buffer
552 memcpy(buffer, ptr, bufferLength * sizeof(unsigned char));
553 ptr += bufferLength * sizeof(unsigned char);
554
555 // Convert to new format
556 AssertCodeMsg(pItems == nullptr, EXCEPTIONCODE_LWM, "Found existing pItems");
557 bool* tKeySeen = new bool[numItems]; // Used for assert, below: keys must be unique.
558 for (unsigned int i = 0; i < numItems; i++)
559 {
560 tKeySeen[i] = false;
561 }
562 pItems = new _Item[numItems];
563 for (unsigned int index = 0; index < numItems; index++)
564 {
565 unsigned int key = tKeys[index];
566 AssertCodeMsg(key < numItems, EXCEPTIONCODE_LWM, "Illegal key %d, numItems == %d", key, numItems);
567 AssertCodeMsg(!tKeySeen[key], EXCEPTIONCODE_LWM, "Duplicate key %d", key);
568 tKeySeen[key] = true;
569 pItems[key] = tItems[index];
570 }
571
572 // Note that if we get here, we've seen every key [0 .. numItems - 1].
573 delete[] tKeySeen;
574 delete[] tKeys;
575 delete[] tItems;
576 }
577
578 AssertCodeMsg((ptr - rawData) == size, EXCEPTIONCODE_LWM, "Ended with unexpected sizes %Ix != %x",
579 ptr - rawData, size);
580 }
581
582public:
583 unsigned int CalculateArraySize()
584 {
585 int size = 4 /* tag */ + sizeof(unsigned int) /* numItems */;
586 if (numItems > 0)
587 {
588 size += sizeof(unsigned int); // size of bufferLength
589 size += sizeof(_Item) * numItems; // size of itemset
590 size += sizeof(unsigned char) * bufferLength; // bulk size of raw buffer
591 }
592 return size;
593 }
594
595 unsigned int DumpToArray(unsigned char* bytes)
596 {
597 unsigned char* ptr = bytes;
598 unsigned int size = CalculateArraySize();
599
600 // Write the tag
601 memcpy(ptr, "DWM1", 4);
602 ptr += 4;
603
604 // Write the header
605 memcpy(ptr, &numItems, sizeof(unsigned int));
606 ptr += sizeof(unsigned int);
607
608 if (numItems > 0)
609 {
610 unsigned int sizeOfItem = sizeof(_Item);
611
612 // Write the buffersize
613 memcpy(ptr, &bufferLength, sizeof(unsigned int));
614 ptr += sizeof(unsigned int);
615
616 // Write the Items
617 memcpy(ptr, pItems, sizeOfItem * numItems);
618 ptr += sizeOfItem * numItems;
619
620 // Write the buffer
621 memcpy(ptr, buffer, bufferLength * sizeof(unsigned char));
622 ptr += bufferLength * sizeof(unsigned char);
623 }
624
625 AssertCodeMsg((ptr - bytes) == size, EXCEPTIONCODE_LWM, "Ended with unexpected sizes %Ix != %x", ptr - bytes,
626 size);
627 return size;
628 }
629
630 bool Append(_Item item)
631 {
632 // Make sure we have space left, expand if needed
633 if (numItems == strideSize)
634 {
635 // NOTE: if this is the first allocation, we'll just allocate 4 items. ok?
636 _Item* tItems = pItems;
637 pItems = new _Item[(strideSize * 2) + 4];
638 memcpy(pItems, tItems, strideSize * sizeof(_Item));
639 strideSize = (strideSize * 2) + 4;
640 delete[] tItems;
641 }
642
643 pItems[numItems] = item;
644 numItems++;
645 return true;
646 }
647
648 int GetIndex(unsigned int key)
649 {
650 if (key >= numItems)
651 return -1;
652
653 return (int)key;
654 }
655
656 _Item GetItem(int index)
657 {
658 AssertCodeMsg(index != -1, EXCEPTIONCODE_LWM, "Didn't find Key");
659 return pItems[index]; // found it. return position /////
660 }
661
662 _Item Get(unsigned int key)
663 {
664 int index = GetIndex(key);
665 return GetItem(index);
666 }
667
668 _Item* GetRawItems()
669 {
670 return pItems;
671 }
672
673 unsigned int GetCount()
674 {
675 return numItems;
676 }
677
678private:
679 void InitialClear()
680 {
681 numItems = 0;
682 strideSize = 0;
683 pItems = nullptr;
684 }
685
686 static int CompareKeys(unsigned int key1, unsigned int key2)
687 {
688 if (key1 < key2)
689 return -1;
690 else if (key1 > key2)
691 return 1;
692 else
693 return 0; // equal
694 }
695
696 unsigned int numItems; // Number of active items in the pKeys and pItems arrays.
697 unsigned int strideSize; // Allocated count of items in the pKeys and pItems arrays.
698 _Item* pItems;
699};
700
701#define dumpLWM(ptr, mapName) \
702 if (ptr->mapName != nullptr) \
703 { \
704 printf("%s - %u\n", #mapName, ptr->mapName->GetCount()); \
705 for (unsigned int i = 0; i < ptr->mapName->GetCount(); i++) \
706 { \
707 printf("%u-", i); \
708 ptr->dmp##mapName(ptr->mapName->GetRawKeys()[i], ptr->mapName->GetRawItems()[i]); \
709 printf("\n"); \
710 } \
711 }
712
713#define dumpLWMDense(ptr, mapName) \
714 if (ptr->mapName != nullptr) \
715 { \
716 printf("%s - %u\n", #mapName, ptr->mapName->GetCount()); \
717 for (unsigned int i = 0; i < ptr->mapName->GetCount(); i++) \
718 { \
719 printf("%u-", i); \
720 ptr->dmp##mapName(i, ptr->mapName->GetRawItems()[i]); \
721 printf("\n"); \
722 } \
723 }
724
725#endif // _LightWeightMap
726