我正在用 C 实现一个灵活的数组。所有想法都基于这个小论文。我的错误在于索引操作。被黑客入侵太久了,无法承认。要求有知识的头脑和眼睛。
概述:数据结构由 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]
. 为什么会这样?有什么办法可以避免吗?我没有看到“关闭 1”错误吗?
这里的代码 是单个 main 函数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 的输出尝试进入索引
第一部分转储二维数组,其中 bar 之前的数字是索引块的索引,之后的部分是索引块指向的数组中包含的元素。所有数组都是零索引的。
[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)