diff options
Diffstat (limited to 'src/libs/7zip/win/CPP/Common/MyMap.cpp')
-rw-r--r-- | src/libs/7zip/win/CPP/Common/MyMap.cpp | 140 |
1 files changed, 0 insertions, 140 deletions
diff --git a/src/libs/7zip/win/CPP/Common/MyMap.cpp b/src/libs/7zip/win/CPP/Common/MyMap.cpp deleted file mode 100644 index 0ee11e8cd..000000000 --- a/src/libs/7zip/win/CPP/Common/MyMap.cpp +++ /dev/null @@ -1,140 +0,0 @@ -// MyMap.cpp - -#include "StdAfx.h" - -#include "MyMap.h" - -static const unsigned kNumBitsMax = sizeof(UInt32) * 8; - -static UInt32 GetSubBits(UInt32 value, unsigned startPos, unsigned numBits) -{ - if (startPos == sizeof(value) * 8) - return 0; - value >>= startPos; - if (numBits == sizeof(value) * 8) - return value; - return value & (((UInt32)1 << numBits) - 1); -} - -static inline unsigned GetSubBit(UInt32 v, unsigned n) { return (unsigned)(v >> n) & 1; } - -bool CMap32::Find(UInt32 key, UInt32 &valueRes) const -{ - valueRes = (UInt32)(Int32)-1; - if (Nodes.Size() == 0) - return false; - if (Nodes.Size() == 1) - { - const CNode &n = Nodes[0]; - if (n.Len == kNumBitsMax) - { - valueRes = n.Values[0]; - return (key == n.Key); - } - } - - int cur = 0; - unsigned bitPos = kNumBitsMax; - for (;;) - { - const CNode &n = Nodes[cur]; - bitPos -= n.Len; - if (GetSubBits(key, bitPos, n.Len) != GetSubBits(n.Key, bitPos, n.Len)) - return false; - unsigned bit = GetSubBit(key, --bitPos); - if (n.IsLeaf[bit]) - { - valueRes = n.Values[bit]; - return (key == n.Keys[bit]); - } - cur = (int)n.Keys[bit]; - } -} - -bool CMap32::Set(UInt32 key, UInt32 value) -{ - if (Nodes.Size() == 0) - { - CNode n; - n.Key = n.Keys[0] = n.Keys[1] = key; - n.Values[0] = n.Values[1] = value; - n.IsLeaf[0] = n.IsLeaf[1] = 1; - n.Len = kNumBitsMax; - Nodes.Add(n); - return false; - } - if (Nodes.Size() == 1) - { - CNode &n = Nodes[0]; - if (n.Len == kNumBitsMax) - { - if (key == n.Key) - { - n.Values[0] = n.Values[1] = value; - return true; - } - unsigned i = kNumBitsMax - 1; - for (;GetSubBit(key, i) == GetSubBit(n.Key, i); i--); - n.Len = (UInt16)(kNumBitsMax - (1 + i)); - unsigned newBit = GetSubBit(key, i); - n.Values[newBit] = value; - n.Keys[newBit] = key; - return false; - } - } - - int cur = 0; - unsigned bitPos = kNumBitsMax; - for (;;) - { - CNode &n = Nodes[cur]; - bitPos -= n.Len; - if (GetSubBits(key, bitPos, n.Len) != GetSubBits(n.Key, bitPos, n.Len)) - { - unsigned i = n.Len - 1; - for (; GetSubBit(key, bitPos + i) == GetSubBit(n.Key, bitPos + i); i--); - - CNode e2(n); - e2.Len = (UInt16)i; - - n.Len = (UInt16)(n.Len - (1 + i)); - unsigned newBit = GetSubBit(key, bitPos + i); - n.Values[newBit] = value; - n.IsLeaf[newBit] = 1; - n.IsLeaf[1 - newBit] = 0; - n.Keys[newBit] = key; - n.Keys[1 - newBit] = Nodes.Size(); - Nodes.Add(e2); - return false; - } - unsigned bit = GetSubBit(key, --bitPos); - - if (n.IsLeaf[bit]) - { - if (key == n.Keys[bit]) - { - n.Values[bit] = value; - return true; - } - unsigned i = bitPos - 1; - for (;GetSubBit(key, i) == GetSubBit(n.Keys[bit], i); i--); - - CNode e2; - - unsigned newBit = GetSubBit(key, i); - e2.Values[newBit] = value; - e2.Values[1 - newBit] = n.Values[bit]; - e2.IsLeaf[newBit] = e2.IsLeaf[1 - newBit] = 1; - e2.Keys[newBit] = key; - e2.Keys[1 - newBit] = e2.Key = n.Keys[bit]; - e2.Len = (UInt16)(bitPos - (1 + i)); - - n.IsLeaf[bit] = 0; - n.Keys[bit] = Nodes.Size(); - - Nodes.Add(e2); - return false; - } - cur = (int)n.Keys[bit]; - } -} |