Mercurial > vba-linux

     1 // MyMap.cpp

     2 

     3 #include "StdAfx.h"

     4 

     5 #include "MyMap.h"

     6 

     7 static const unsigned kNumBitsMax = sizeof(UInt32) * 8;

     8 

     9 static UInt32 GetSubBits(UInt32 value, unsigned startPos, unsigned numBits)

    10 {

    11   if (startPos == sizeof(value) * 8)

    12     return 0;

    13   value >>= startPos;

    14   if (numBits == sizeof(value) * 8)

    15     return value;

    16   return value & (((UInt32)1 << numBits) - 1);

    17 }

    18 

    19 static inline unsigned GetSubBit(UInt32 v, unsigned n) { return (unsigned)(v >> n) & 1; }

    20 

    21 bool CMap32::Find(UInt32 key, UInt32 &valueRes) const

    22 {

    23   valueRes = (UInt32)(Int32)-1;

    24   if (Nodes.Size() == 0)

    25     return false;

    26   if (Nodes.Size() == 1)

    27   {

    28     const CNode &n = Nodes[0];

    29     if (n.Len == kNumBitsMax)

    30     {

    31       valueRes = n.Values[0];

    32       return (key == n.Key);

    33     }

    34   }

    35 

    36   int cur = 0;

    37   unsigned bitPos = kNumBitsMax;

    38   for (;;)

    39   {

    40     const CNode &n = Nodes[cur];

    41     bitPos -= n.Len;

    42     if (GetSubBits(key, bitPos, n.Len) != GetSubBits(n.Key, bitPos, n.Len))

    43       return false;

    44     unsigned bit = GetSubBit(key, --bitPos);

    45     if (n.IsLeaf[bit])

    46     {

    47       valueRes = n.Values[bit];

    48       return (key == n.Keys[bit]);

    49     }

    50     cur = (int)n.Keys[bit];

    51   }

    52 }

    53 

    54 bool CMap32::Set(UInt32 key, UInt32 value)

    55 {

    56   if (Nodes.Size() == 0)

    57   {

    58     CNode n;

    59     n.Key = n.Keys[0] = n.Keys[1] = key;

    60     n.Values[0] = n.Values[1] = value;

    61     n.IsLeaf[0] = n.IsLeaf[1] = 1;

    62     n.Len = kNumBitsMax;

    63     Nodes.Add(n);

    64     return false;

    65   }

    66   if (Nodes.Size() == 1)

    67   {

    68     CNode &n = Nodes[0];

    69     if (n.Len == kNumBitsMax)

    70     {

    71       if (key == n.Key)

    72       {

    73         n.Values[0] = n.Values[1] = value;

    74         return true;

    75       }

    76       unsigned i = kNumBitsMax - 1;

    77       for (;GetSubBit(key, i) == GetSubBit(n.Key, i); i--);

    78       n.Len = (UInt16)(kNumBitsMax - (1 + i));

    79       unsigned newBit = GetSubBit(key, i);

    80       n.Values[newBit] = value;

    81       n.Keys[newBit] = key;

    82       return false;

    83     }

    84   }

    85 

    86   int cur = 0;

    87   unsigned bitPos = kNumBitsMax;

    88   for (;;)

    89   {

    90     CNode &n = Nodes[cur];

    91     bitPos -= n.Len;

    92     if (GetSubBits(key, bitPos, n.Len) != GetSubBits(n.Key, bitPos, n.Len))

    93     {

    94       unsigned i = n.Len - 1;

    95       for (; GetSubBit(key, bitPos + i) == GetSubBit(n.Key, bitPos + i); i--);

    96       

    97       CNode e2(n);

    98       e2.Len = (UInt16)i;

    99 

   100       n.Len = (UInt16)(n.Len - (1 + i));

   101       unsigned newBit = GetSubBit(key, bitPos + i);

   102       n.Values[newBit] = value;

   103       n.IsLeaf[newBit] = 1;

   104       n.IsLeaf[1 - newBit] = 0;

   105       n.Keys[newBit] = key;

   106       n.Keys[1 - newBit] = Nodes.Size();

   107       Nodes.Add(e2);

   108       return false;

   109     }

   110     unsigned bit = GetSubBit(key, --bitPos);

   111 

   112     if (n.IsLeaf[bit])

   113     {

   114       if (key == n.Keys[bit])

   115       {

   116         n.Values[bit] = value;

   117         return true;

   118       }

   119       unsigned i = bitPos - 1;

   120       for (;GetSubBit(key, i) == GetSubBit(n.Keys[bit], i); i--);

   121      

   122       CNode e2;

   123       

   124       unsigned newBit = GetSubBit(key, i);

   125       e2.Values[newBit] = value;

   126       e2.Values[1 - newBit] = n.Values[bit];

   127       e2.IsLeaf[newBit] = e2.IsLeaf[1 - newBit] = 1;

   128       e2.Keys[newBit] = key;

   129       e2.Keys[1 - newBit] = e2.Key = n.Keys[bit];

   130       e2.Len = (UInt16)(bitPos - (1 + i));

   131 

   132       n.IsLeaf[bit] = 0;

   133       n.Keys[bit] = Nodes.Size();

   134 

   135       Nodes.Add(e2);

   136       return false;

   137     }

   138     cur = (int)n.Keys[bit];

   139   }

   140 }
author	Robert McIntyre <rlm@mit.edu>
date	Sat, 03 Mar 2012 10:31:27 -0600
parents
children