diff options
Diffstat (limited to 'installerbuilder/libinstaller/3rdparty/p7zip_9.04/unix/CPP/Common/MyMap.cpp')
-rw-r--r-- | installerbuilder/libinstaller/3rdparty/p7zip_9.04/unix/CPP/Common/MyMap.cpp | 140 |
1 files changed, 140 insertions, 0 deletions
diff --git a/installerbuilder/libinstaller/3rdparty/p7zip_9.04/unix/CPP/Common/MyMap.cpp b/installerbuilder/libinstaller/3rdparty/p7zip_9.04/unix/CPP/Common/MyMap.cpp new file mode 100644 index 000000000..0ee11e8cd --- /dev/null +++ b/installerbuilder/libinstaller/3rdparty/p7zip_9.04/unix/CPP/Common/MyMap.cpp @@ -0,0 +1,140 @@ +// 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]; + } +} |