rlm@1: // MyMap.cpp
rlm@1: 
rlm@1: #include "StdAfx.h"
rlm@1: 
rlm@1: #include "MyMap.h"
rlm@1: 
rlm@1: static const unsigned kNumBitsMax = sizeof(UInt32) * 8;
rlm@1: 
rlm@1: static UInt32 GetSubBits(UInt32 value, unsigned startPos, unsigned numBits)
rlm@1: {
rlm@1:   if (startPos == sizeof(value) * 8)
rlm@1:     return 0;
rlm@1:   value >>= startPos;
rlm@1:   if (numBits == sizeof(value) * 8)
rlm@1:     return value;
rlm@1:   return value & (((UInt32)1 << numBits) - 1);
rlm@1: }
rlm@1: 
rlm@1: static inline unsigned GetSubBit(UInt32 v, unsigned n) { return (unsigned)(v >> n) & 1; }
rlm@1: 
rlm@1: bool CMap32::Find(UInt32 key, UInt32 &valueRes) const
rlm@1: {
rlm@1:   valueRes = (UInt32)(Int32)-1;
rlm@1:   if (Nodes.Size() == 0)
rlm@1:     return false;
rlm@1:   if (Nodes.Size() == 1)
rlm@1:   {
rlm@1:     const CNode &n = Nodes[0];
rlm@1:     if (n.Len == kNumBitsMax)
rlm@1:     {
rlm@1:       valueRes = n.Values[0];
rlm@1:       return (key == n.Key);
rlm@1:     }
rlm@1:   }
rlm@1: 
rlm@1:   int cur = 0;
rlm@1:   unsigned bitPos = kNumBitsMax;
rlm@1:   for (;;)
rlm@1:   {
rlm@1:     const CNode &n = Nodes[cur];
rlm@1:     bitPos -= n.Len;
rlm@1:     if (GetSubBits(key, bitPos, n.Len) != GetSubBits(n.Key, bitPos, n.Len))
rlm@1:       return false;
rlm@1:     unsigned bit = GetSubBit(key, --bitPos);
rlm@1:     if (n.IsLeaf[bit])
rlm@1:     {
rlm@1:       valueRes = n.Values[bit];
rlm@1:       return (key == n.Keys[bit]);
rlm@1:     }
rlm@1:     cur = (int)n.Keys[bit];
rlm@1:   }
rlm@1: }
rlm@1: 
rlm@1: bool CMap32::Set(UInt32 key, UInt32 value)
rlm@1: {
rlm@1:   if (Nodes.Size() == 0)
rlm@1:   {
rlm@1:     CNode n;
rlm@1:     n.Key = n.Keys[0] = n.Keys[1] = key;
rlm@1:     n.Values[0] = n.Values[1] = value;
rlm@1:     n.IsLeaf[0] = n.IsLeaf[1] = 1;
rlm@1:     n.Len = kNumBitsMax;
rlm@1:     Nodes.Add(n);
rlm@1:     return false;
rlm@1:   }
rlm@1:   if (Nodes.Size() == 1)
rlm@1:   {
rlm@1:     CNode &n = Nodes[0];
rlm@1:     if (n.Len == kNumBitsMax)
rlm@1:     {
rlm@1:       if (key == n.Key)
rlm@1:       {
rlm@1:         n.Values[0] = n.Values[1] = value;
rlm@1:         return true;
rlm@1:       }
rlm@1:       unsigned i = kNumBitsMax - 1;
rlm@1:       for (;GetSubBit(key, i) == GetSubBit(n.Key, i); i--);
rlm@1:       n.Len = (UInt16)(kNumBitsMax - (1 + i));
rlm@1:       unsigned newBit = GetSubBit(key, i);
rlm@1:       n.Values[newBit] = value;
rlm@1:       n.Keys[newBit] = key;
rlm@1:       return false;
rlm@1:     }
rlm@1:   }
rlm@1: 
rlm@1:   int cur = 0;
rlm@1:   unsigned bitPos = kNumBitsMax;
rlm@1:   for (;;)
rlm@1:   {
rlm@1:     CNode &n = Nodes[cur];
rlm@1:     bitPos -= n.Len;
rlm@1:     if (GetSubBits(key, bitPos, n.Len) != GetSubBits(n.Key, bitPos, n.Len))
rlm@1:     {
rlm@1:       unsigned i = n.Len - 1;
rlm@1:       for (; GetSubBit(key, bitPos + i) == GetSubBit(n.Key, bitPos + i); i--);
rlm@1:       
rlm@1:       CNode e2(n);
rlm@1:       e2.Len = (UInt16)i;
rlm@1: 
rlm@1:       n.Len = (UInt16)(n.Len - (1 + i));
rlm@1:       unsigned newBit = GetSubBit(key, bitPos + i);
rlm@1:       n.Values[newBit] = value;
rlm@1:       n.IsLeaf[newBit] = 1;
rlm@1:       n.IsLeaf[1 - newBit] = 0;
rlm@1:       n.Keys[newBit] = key;
rlm@1:       n.Keys[1 - newBit] = Nodes.Size();
rlm@1:       Nodes.Add(e2);
rlm@1:       return false;
rlm@1:     }
rlm@1:     unsigned bit = GetSubBit(key, --bitPos);
rlm@1: 
rlm@1:     if (n.IsLeaf[bit])
rlm@1:     {
rlm@1:       if (key == n.Keys[bit])
rlm@1:       {
rlm@1:         n.Values[bit] = value;
rlm@1:         return true;
rlm@1:       }
rlm@1:       unsigned i = bitPos - 1;
rlm@1:       for (;GetSubBit(key, i) == GetSubBit(n.Keys[bit], i); i--);
rlm@1:      
rlm@1:       CNode e2;
rlm@1:       
rlm@1:       unsigned newBit = GetSubBit(key, i);
rlm@1:       e2.Values[newBit] = value;
rlm@1:       e2.Values[1 - newBit] = n.Values[bit];
rlm@1:       e2.IsLeaf[newBit] = e2.IsLeaf[1 - newBit] = 1;
rlm@1:       e2.Keys[newBit] = key;
rlm@1:       e2.Keys[1 - newBit] = e2.Key = n.Keys[bit];
rlm@1:       e2.Len = (UInt16)(bitPos - (1 + i));
rlm@1: 
rlm@1:       n.IsLeaf[bit] = 0;
rlm@1:       n.Keys[bit] = Nodes.Size();
rlm@1: 
rlm@1:       Nodes.Add(e2);
rlm@1:       return false;
rlm@1:     }
rlm@1:     cur = (int)n.Keys[bit];
rlm@1:   }
rlm@1: }