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)9unsigned 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() const41UInt64 CUniqBlocks::GetTotalSizeInBytes() const 42 { 43 UInt64 size = 0; 44 FOR_VECTOR (i, Bufs) 45 size += Bufs[i].Size(); 46 return size; 47 } 48 GetReverseMap()49void 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