1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/win32/7zip/7z/CPP/Common/MyMap.cpp	Sat Mar 03 10:31:27 2012 -0600
     1.3 @@ -0,0 +1,140 @@
     1.4 +// MyMap.cpp
     1.5 +
     1.6 +#include "StdAfx.h"
     1.7 +
     1.8 +#include "MyMap.h"
     1.9 +
    1.10 +static const unsigned kNumBitsMax = sizeof(UInt32) * 8;
    1.11 +
    1.12 +static UInt32 GetSubBits(UInt32 value, unsigned startPos, unsigned numBits)
    1.13 +{
    1.14 +  if (startPos == sizeof(value) * 8)
    1.15 +    return 0;
    1.16 +  value >>= startPos;
    1.17 +  if (numBits == sizeof(value) * 8)
    1.18 +    return value;
    1.19 +  return value & (((UInt32)1 << numBits) - 1);
    1.20 +}
    1.21 +
    1.22 +static inline unsigned GetSubBit(UInt32 v, unsigned n) { return (unsigned)(v >> n) & 1; }
    1.23 +
    1.24 +bool CMap32::Find(UInt32 key, UInt32 &valueRes) const
    1.25 +{
    1.26 +  valueRes = (UInt32)(Int32)-1;
    1.27 +  if (Nodes.Size() == 0)
    1.28 +    return false;
    1.29 +  if (Nodes.Size() == 1)
    1.30 +  {
    1.31 +    const CNode &n = Nodes[0];
    1.32 +    if (n.Len == kNumBitsMax)
    1.33 +    {
    1.34 +      valueRes = n.Values[0];
    1.35 +      return (key == n.Key);
    1.36 +    }
    1.37 +  }
    1.38 +
    1.39 +  int cur = 0;
    1.40 +  unsigned bitPos = kNumBitsMax;
    1.41 +  for (;;)
    1.42 +  {
    1.43 +    const CNode &n = Nodes[cur];
    1.44 +    bitPos -= n.Len;
    1.45 +    if (GetSubBits(key, bitPos, n.Len) != GetSubBits(n.Key, bitPos, n.Len))
    1.46 +      return false;
    1.47 +    unsigned bit = GetSubBit(key, --bitPos);
    1.48 +    if (n.IsLeaf[bit])
    1.49 +    {
    1.50 +      valueRes = n.Values[bit];
    1.51 +      return (key == n.Keys[bit]);
    1.52 +    }
    1.53 +    cur = (int)n.Keys[bit];
    1.54 +  }
    1.55 +}
    1.56 +
    1.57 +bool CMap32::Set(UInt32 key, UInt32 value)
    1.58 +{
    1.59 +  if (Nodes.Size() == 0)
    1.60 +  {
    1.61 +    CNode n;
    1.62 +    n.Key = n.Keys[0] = n.Keys[1] = key;
    1.63 +    n.Values[0] = n.Values[1] = value;
    1.64 +    n.IsLeaf[0] = n.IsLeaf[1] = 1;
    1.65 +    n.Len = kNumBitsMax;
    1.66 +    Nodes.Add(n);
    1.67 +    return false;
    1.68 +  }
    1.69 +  if (Nodes.Size() == 1)
    1.70 +  {
    1.71 +    CNode &n = Nodes[0];
    1.72 +    if (n.Len == kNumBitsMax)
    1.73 +    {
    1.74 +      if (key == n.Key)
    1.75 +      {
    1.76 +        n.Values[0] = n.Values[1] = value;
    1.77 +        return true;
    1.78 +      }
    1.79 +      unsigned i = kNumBitsMax - 1;
    1.80 +      for (;GetSubBit(key, i) == GetSubBit(n.Key, i); i--);
    1.81 +      n.Len = (UInt16)(kNumBitsMax - (1 + i));
    1.82 +      unsigned newBit = GetSubBit(key, i);
    1.83 +      n.Values[newBit] = value;
    1.84 +      n.Keys[newBit] = key;
    1.85 +      return false;
    1.86 +    }
    1.87 +  }
    1.88 +
    1.89 +  int cur = 0;
    1.90 +  unsigned bitPos = kNumBitsMax;
    1.91 +  for (;;)
    1.92 +  {
    1.93 +    CNode &n = Nodes[cur];
    1.94 +    bitPos -= n.Len;
    1.95 +    if (GetSubBits(key, bitPos, n.Len) != GetSubBits(n.Key, bitPos, n.Len))
    1.96 +    {
    1.97 +      unsigned i = n.Len - 1;
    1.98 +      for (; GetSubBit(key, bitPos + i) == GetSubBit(n.Key, bitPos + i); i--);
    1.99 +      
   1.100 +      CNode e2(n);
   1.101 +      e2.Len = (UInt16)i;
   1.102 +
   1.103 +      n.Len = (UInt16)(n.Len - (1 + i));
   1.104 +      unsigned newBit = GetSubBit(key, bitPos + i);
   1.105 +      n.Values[newBit] = value;
   1.106 +      n.IsLeaf[newBit] = 1;
   1.107 +      n.IsLeaf[1 - newBit] = 0;
   1.108 +      n.Keys[newBit] = key;
   1.109 +      n.Keys[1 - newBit] = Nodes.Size();
   1.110 +      Nodes.Add(e2);
   1.111 +      return false;
   1.112 +    }
   1.113 +    unsigned bit = GetSubBit(key, --bitPos);
   1.114 +
   1.115 +    if (n.IsLeaf[bit])
   1.116 +    {
   1.117 +      if (key == n.Keys[bit])
   1.118 +      {
   1.119 +        n.Values[bit] = value;
   1.120 +        return true;
   1.121 +      }
   1.122 +      unsigned i = bitPos - 1;
   1.123 +      for (;GetSubBit(key, i) == GetSubBit(n.Keys[bit], i); i--);
   1.124 +     
   1.125 +      CNode e2;
   1.126 +      
   1.127 +      unsigned newBit = GetSubBit(key, i);
   1.128 +      e2.Values[newBit] = value;
   1.129 +      e2.Values[1 - newBit] = n.Values[bit];
   1.130 +      e2.IsLeaf[newBit] = e2.IsLeaf[1 - newBit] = 1;
   1.131 +      e2.Keys[newBit] = key;
   1.132 +      e2.Keys[1 - newBit] = e2.Key = n.Keys[bit];
   1.133 +      e2.Len = (UInt16)(bitPos - (1 + i));
   1.134 +
   1.135 +      n.IsLeaf[bit] = 0;
   1.136 +      n.Keys[bit] = Nodes.Size();
   1.137 +
   1.138 +      Nodes.Add(e2);
   1.139 +      return false;
   1.140 +    }
   1.141 +    cur = (int)n.Keys[bit];
   1.142 +  }
   1.143 +}