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