私は C で柔軟な配列を実装しています。すべてのアイデアは、この小さなPaperに基づいています。私のエラーは、インデックス作成操作にあります。認めるにはあまりにも長い間ハッキングしていました。知識豊富な心と目を求める。
概要: データ構造は、データ ブロックへのポインタを保持する 1 つのフラット インデックス ブロックで構成されます。各データ ブロックのサイズは 2^(k/2) です。ここで、k は先頭のセット ビットです。したがって、要素「i」を検索すると、k は log_2(i+1) になります。
index = {
[0], -> [0]
[2], -> [0,1]
[2], -> [0,1]
[3], -> [0,1,2,3]
[4], -> [0,1,2,3]
....}
各データ ブロックのサイズは、クラスタ化される「スーパー ブロック」によって決まります。スーパーブロックは、同じサイズのデータブロックで構成されています。そう。インデックス 1,2 は同じスーパー ブロック (スーパー ブロック 1) 内にあります。0 (スーパーブロック 0) とインデックス 3 (スーパーブロック 2) は違います。
各スーパーブロックには 2^(floor(k/2)) データ ブロックがあり、これらの各データ ブロックのサイズは 2^(ceil(k/2)) になります。
問題
r = 2 の累乗の場合、インデックスは本来あるべきものをスキップします。3 を検索するときのようにindex [2][0]、 ではなくindex[3][0]. なぜこれが起こるのですか？それを回避する方法はありますか？「off by 1」というエラーが表示されていませんか??
コード ここにあるのは単一のメイン関数testcaseです。これは明確でシンプルで、インデックス 3 の要素を取得しようとすると失敗します。
検索インデックス i の簡略化されたコードは次のとおりです。
/* Edited from the actual test case for extra clarity */
/* all vars int */
r= i+1
k = first_set_bit(r) - 1; // ex: r = 5, 5 = "00000101"b so k is (3-1) = 2
b = first_subset_of_r(floor(k/2)); // floor(k/2) bits of r immediately after first set;
e = last_subset_of_r(ceil(k/2); // last ceil(k/2) bits of r
p = (1 << k) -1 ; // 2^k -1
// Index supposed to be found with. . .
return index[p+b][e];
これは実際の出力です。最初に配列の内容をインデックスとデータ ブロックで出力し、次に 4 回の出力でインデックスを試行します。
最初の部分は 2 次元配列をダンプします。バーの前の数字はインデックス ブロックのインデックスであり、後の部分はインデックス ブロックが指す配列に含まれる要素です。すべての配列のインデックスはゼロです。
[clemensm@gaia:23]> ./a.out
Index block | element number (Not it's index!)
0 | 0
1 | 1 2
2 | 3 4
3 | 5 6
4 | 7 8 9 10
5 | 11 12 13 14
6 | 15 16 17 18
7 | 19 20 21 22
8 | 23 24 25 26
9 | 27 28 29 30
10 | 31 32 33 34 35 36 37 38
11 | 39 40 41 42 43 44 45 46
12 | 47 48 49 50 51 52 53 54
13 | 55 56 57 58 59 60 61 62
14 | 63 64 65 66 67 68 69 70
15 | 71 72 73 74 75 76 77 78
16 | 79 80 81 82 83 84 85 86
17 | 87 88 89 90 91 92 93 94
18 | 95 96 97 98 99 100 101 102
19 | 103 104 105 106 107 108 109 110
Finished element dump
Trying to get 0
R: [1]b
k/2=[0], Ceil(k,2)=[0]
K: [0] is the leading 1 bit
B: [0]
E: [0]
P: [0] data blocks prior to our superblock
p+b,e : [0,0]
Trying to get 1
R: [10]b
k/2=[0], Ceil(k,2)=[1]
K: [1] is the leading 1 bit
B: [0]
E: [0]
P: [1] data blocks prior to our superblock
p+b,e : [1,0]
Trying to get 2
R: [11]b
k/2=[0], Ceil(k,2)=[1]
K: [1] is the leading 1 bit
B: [0]
E: [1]
P: [1] data blocks prior to our superblock
p+b,e : [1,1]
Trying to get 3
R: [100]b
k/2=[1], Ceil(k,2)=[1]
K: [2] is the leading 1 bit
B: [0]
E: [0]
P: [3] data blocks prior to our superblock
p+b,e : [3,0]
a.out: test_array.c:81: main: Assertion `get_index(3)==3' failed.
Abort (core dumped)