1 // UniqBlocks.cpp
2 
3 #include "StdAfx.h"
4 
5 #include <string.h>
6 
7 #include "UniqBlocks.h"
8 
AddUniq(const Byte * data,size_t size)9 unsigned CUniqBlocks::AddUniq(const Byte *data, size_t size)
10 {
11   unsigned left = 0, right = Sorted.Size();
12   while (left != right)
13   {
14     unsigned mid = (left + right) / 2;
15     unsigned index = Sorted[mid];
16     const CByteBuffer &buf = Bufs[index];
17     size_t sizeMid = buf.Size();
18     if (size < sizeMid)
19       right = mid;
20     else if (size > sizeMid)
21       left = mid + 1;
22     else
23     {
24       if (size == 0)
25         return index;
26       int cmp = memcmp(data, buf, size);
27       if (cmp == 0)
28         return index;
29       if (cmp < 0)
30         right = mid;
31       else
32         left = mid + 1;
33     }
34   }
35   unsigned index = Bufs.Size();
36   Sorted.Insert(left, index);
37   Bufs.AddNew().CopyFrom(data, size);
38   return index;
39 }
40 
GetTotalSizeInBytes() const41 UInt64 CUniqBlocks::GetTotalSizeInBytes() const
42 {
43   UInt64 size = 0;
44   FOR_VECTOR (i, Bufs)
45     size += Bufs[i].Size();
46   return size;
47 }
48 
GetReverseMap()49 void CUniqBlocks::GetReverseMap()
50 {
51   unsigned num = Sorted.Size();
52   BufIndexToSortedIndex.ClearAndSetSize(num);
53   unsigned *p = &BufIndexToSortedIndex[0];
54   const unsigned *sorted = &Sorted[0];
55   for (unsigned i = 0; i < num; i++)
56     p[sorted[i]] = i;
57 }
58