Mercurial > vba-linux

annotate src/win32/7zip/7z/CPP/Common/MyMap.cpp @ 1:f9f4f1b99eed

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
importing src directory
author Robert McIntyre <rlm@mit.edu>
date Sat, 03 Mar 2012 10:31:27 -0600
parents
children
rev   line source
rlm@1 1 // MyMap.cpp
rlm@1 2
rlm@1 3 #include "StdAfx.h"
rlm@1 4
rlm@1 5 #include "MyMap.h"
rlm@1 6
rlm@1 7 static const unsigned kNumBitsMax = sizeof(UInt32) * 8;
rlm@1 8
rlm@1 9 static UInt32 GetSubBits(UInt32 value, unsigned startPos, unsigned numBits)
rlm@1 10 {
rlm@1 11 if (startPos == sizeof(value) * 8)
rlm@1 12 return 0;
rlm@1 13 value >>= startPos;
rlm@1 14 if (numBits == sizeof(value) * 8)
rlm@1 15 return value;
rlm@1 16 return value & (((UInt32)1 << numBits) - 1);
rlm@1 17 }
rlm@1 18
rlm@1 19 static inline unsigned GetSubBit(UInt32 v, unsigned n) { return (unsigned)(v >> n) & 1; }
rlm@1 20
rlm@1 21 bool CMap32::Find(UInt32 key, UInt32 &valueRes) const
rlm@1 22 {
rlm@1 23 valueRes = (UInt32)(Int32)-1;
rlm@1 24 if (Nodes.Size() == 0)
rlm@1 25 return false;
rlm@1 26 if (Nodes.Size() == 1)
rlm@1 27 {
rlm@1 28 const CNode &n = Nodes[0];
rlm@1 29 if (n.Len == kNumBitsMax)
rlm@1 30 {
rlm@1 31 valueRes = n.Values[0];
rlm@1 32 return (key == n.Key);
rlm@1 33 }
rlm@1 34 }
rlm@1 35
rlm@1 36 int cur = 0;
rlm@1 37 unsigned bitPos = kNumBitsMax;
rlm@1 38 for (;;)
rlm@1 39 {
rlm@1 40 const CNode &n = Nodes[cur];
rlm@1 41 bitPos -= n.Len;
rlm@1 42 if (GetSubBits(key, bitPos, n.Len) != GetSubBits(n.Key, bitPos, n.Len))
rlm@1 43 return false;
rlm@1 44 unsigned bit = GetSubBit(key, --bitPos);
rlm@1 45 if (n.IsLeaf[bit])
rlm@1 46 {
rlm@1 47 valueRes = n.Values[bit];
rlm@1 48 return (key == n.Keys[bit]);
rlm@1 49 }
rlm@1 50 cur = (int)n.Keys[bit];
rlm@1 51 }
rlm@1 52 }
rlm@1 53
rlm@1 54 bool CMap32::Set(UInt32 key, UInt32 value)
rlm@1 55 {
rlm@1 56 if (Nodes.Size() == 0)
rlm@1 57 {
rlm@1 58 CNode n;
rlm@1 59 n.Key = n.Keys[0] = n.Keys[1] = key;
rlm@1 60 n.Values[0] = n.Values[1] = value;
rlm@1 61 n.IsLeaf[0] = n.IsLeaf[1] = 1;
rlm@1 62 n.Len = kNumBitsMax;
rlm@1 63 Nodes.Add(n);
rlm@1 64 return false;
rlm@1 65 }
rlm@1 66 if (Nodes.Size() == 1)
rlm@1 67 {
rlm@1 68 CNode &n = Nodes[0];
rlm@1 69 if (n.Len == kNumBitsMax)
rlm@1 70 {
rlm@1 71 if (key == n.Key)
rlm@1 72 {
rlm@1 73 n.Values[0] = n.Values[1] = value;
rlm@1 74 return true;
rlm@1 75 }
rlm@1 76 unsigned i = kNumBitsMax - 1;
rlm@1 77 for (;GetSubBit(key, i) == GetSubBit(n.Key, i); i--);
rlm@1 78 n.Len = (UInt16)(kNumBitsMax - (1 + i));
rlm@1 79 unsigned newBit = GetSubBit(key, i);
rlm@1 80 n.Values[newBit] = value;
rlm@1 81 n.Keys[newBit] = key;
rlm@1 82 return false;
rlm@1 83 }
rlm@1 84 }
rlm@1 85
rlm@1 86 int cur = 0;
rlm@1 87 unsigned bitPos = kNumBitsMax;
rlm@1 88 for (;;)
rlm@1 89 {
rlm@1 90 CNode &n = Nodes[cur];
rlm@1 91 bitPos -= n.Len;
rlm@1 92 if (GetSubBits(key, bitPos, n.Len) != GetSubBits(n.Key, bitPos, n.Len))
rlm@1 93 {
rlm@1 94 unsigned i = n.Len - 1;
rlm@1 95 for (; GetSubBit(key, bitPos + i) == GetSubBit(n.Key, bitPos + i); i--);
rlm@1 96
rlm@1 97 CNode e2(n);
rlm@1 98 e2.Len = (UInt16)i;
rlm@1 99
rlm@1 100 n.Len = (UInt16)(n.Len - (1 + i));
rlm@1 101 unsigned newBit = GetSubBit(key, bitPos + i);
rlm@1 102 n.Values[newBit] = value;
rlm@1 103 n.IsLeaf[newBit] = 1;
rlm@1 104 n.IsLeaf[1 - newBit] = 0;
rlm@1 105 n.Keys[newBit] = key;
rlm@1 106 n.Keys[1 - newBit] = Nodes.Size();
rlm@1 107 Nodes.Add(e2);
rlm@1 108 return false;
rlm@1 109 }
rlm@1 110 unsigned bit = GetSubBit(key, --bitPos);
rlm@1 111
rlm@1 112 if (n.IsLeaf[bit])
rlm@1 113 {
rlm@1 114 if (key == n.Keys[bit])
rlm@1 115 {
rlm@1 116 n.Values[bit] = value;
rlm@1 117 return true;
rlm@1 118 }
rlm@1 119 unsigned i = bitPos - 1;
rlm@1 120 for (;GetSubBit(key, i) == GetSubBit(n.Keys[bit], i); i--);
rlm@1 121
rlm@1 122 CNode e2;
rlm@1 123
rlm@1 124 unsigned newBit = GetSubBit(key, i);
rlm@1 125 e2.Values[newBit] = value;
rlm@1 126 e2.Values[1 - newBit] = n.Values[bit];
rlm@1 127 e2.IsLeaf[newBit] = e2.IsLeaf[1 - newBit] = 1;
rlm@1 128 e2.Keys[newBit] = key;
rlm@1 129 e2.Keys[1 - newBit] = e2.Key = n.Keys[bit];
rlm@1 130 e2.Len = (UInt16)(bitPos - (1 + i));
rlm@1 131
rlm@1 132 n.IsLeaf[bit] = 0;
rlm@1 133 n.Keys[bit] = Nodes.Size();
rlm@1 134
rlm@1 135 Nodes.Add(e2);
rlm@1 136 return false;
rlm@1 137 }
rlm@1 138 cur = (int)n.Keys[bit];
rlm@1 139 }
rlm@1 140 }