1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
|
//! AFS B-tree Search Operations
const constants = @import("../constants/constants.zig");
const types = @import("../types/types.zig");
const node_ops = @import("node.zig");
const IndexKey = types.IndexKey;
const BTreeNodeDescriptor = types.BTreeNodeDescriptor;
const StackRecord = types.StackRecord;
const UnitRecord = types.UnitRecord;
const ThreadRecord = types.ThreadRecord;
/// Compare search key against a B-tree key
/// Returns: -1 if search < key, 0 if equal, 1 if search > key
pub fn compare_keys(parent_node_id: u32, identity: []const u16, key: *const IndexKey) i32 {
if (parent_node_id < key.parent_node_id) {
return -1;
}
if (parent_node_id > key.parent_node_id) {
return 1;
}
const key_identity_len = key.get_identity_length();
const min_len = if (identity.len < key_identity_len) identity.len else key_identity_len;
var i: usize = 0;
while (i < min_len) : (i += 1) {
const a = identity[i];
const b = key.identity[i];
if (a < b) {
return -1;
}
if (a > b) {
return 1;
}
}
if (identity.len < key_identity_len) {
return -1;
}
if (identity.len > key_identity_len) {
return 1;
}
return 0;
}
/// Search an index node for the child pointer to follow
pub fn search_index_node(
node_buffer: [*]const u8,
node_size: u32,
record_count: u16,
parent_node_id: u32,
identity: []const u16,
) ?u32 {
var i: u16 = 0;
while (i < record_count) : (i += 1) {
const record_ptr = node_ops.get_record_ptr_const(node_buffer, node_size, i);
const key: *const IndexKey = @ptrCast(@alignCast(record_ptr));
const cmp = compare_keys(parent_node_id, identity, key);
if (cmp <= 0) {
const child_ptr: *align(1) const u32 = @ptrCast(record_ptr + key.key_length + 2);
return child_ptr.*;
}
}
// Return last child pointer if search key is greater than all keys
if (record_count > 0) {
const last_record = node_ops.get_record_ptr_const(node_buffer, node_size, record_count - 1);
const last_key: *const IndexKey = @ptrCast(@alignCast(last_record));
const child_ptr: *align(1) const u32 = @ptrCast(last_record + last_key.key_length + 2);
return child_ptr.*;
}
return null;
}
/// Search a leaf node for a unit record
pub fn search_leaf_for_unit(
node_buffer: [*]const u8,
node_size: u32,
record_count: u16,
parent_node_id: u32,
identity: []const u16,
) ?*const UnitRecord {
var i: u16 = 0;
while (i < record_count) : (i += 1) {
const record_ptr = node_ops.get_record_ptr_const(node_buffer, node_size, i);
const key: *const IndexKey = @ptrCast(@alignCast(record_ptr));
const cmp = compare_keys(parent_node_id, identity, key);
if (cmp == 0) {
const record_start = record_ptr + key.key_length + 2;
const record_type_ptr: *align(1) const u16 = @ptrCast(record_start);
const record_type = record_type_ptr.*;
if (record_type == constants.records.index_unit) {
return @ptrCast(@alignCast(record_start));
}
}
}
return null;
}
/// Search a leaf node for a stack record
pub fn search_leaf_for_stack(
node_buffer: [*]const u8,
node_size: u32,
record_count: u16,
parent_node_id: u32,
identity: []const u16,
) ?*const StackRecord {
var i: u16 = 0;
while (i < record_count) : (i += 1) {
const record_ptr = node_ops.get_record_ptr_const(node_buffer, node_size, i);
const key: *const IndexKey = @ptrCast(@alignCast(record_ptr));
const cmp = compare_keys(parent_node_id, identity, key);
if (cmp == 0) {
const record_start = record_ptr + key.key_length + 2;
const record_type_ptr: *align(1) const u16 = @ptrCast(record_start);
const record_type = record_type_ptr.*;
if (record_type == constants.records.index_stack) {
return @ptrCast(@alignCast(record_start));
}
}
}
return null;
}
/// Search a leaf node for a thread record
pub fn search_leaf_for_thread(
node_buffer: [*]const u8,
node_size: u32,
record_count: u16,
node_id: u32,
identity: []const u16,
) ?*const ThreadRecord {
var i: u16 = 0;
while (i < record_count) : (i += 1) {
const record_ptr = node_ops.get_record_ptr_const(node_buffer, node_size, i);
const key: *const IndexKey = @ptrCast(@alignCast(record_ptr));
const cmp = compare_keys(node_id, identity, key);
if (cmp == 0) {
const record_start = record_ptr + key.key_length + 2;
const record_type_ptr: *align(1) const u16 = @ptrCast(record_start);
const record_type = record_type_ptr.*;
if (record_type == constants.records.index_stack_thread or
record_type == constants.records.index_unit_thread)
{
return @ptrCast(@alignCast(record_start));
}
}
}
return null;
}
|
