Repository navigation
Expand file tree
/
Copy pathmap.v
More file actions
163 lines (148 loc) · 2.88 KB
/
Copy pathmap.v
File metadata and controls
163 lines (148 loc) · 2.88 KB
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
// Copyright (c) 2019 Alexander Medvednikov. All rights reserved.
// Use of this source code is governed by an MIT license
// that can be found in the LICENSE file.
module builtin
struct map {
// cap int
// keys []string
// table byteptr
// keys_table *string
// table *Entry
element_size int
// collisions []Entry
pub:
entries []Entry
is_sorted bool
}
struct Entry {
pub:
key string
val voidptr
// linked list for collisions
// next *Entry
}
fn new_map(cap int, elm_size int) map {
res := map {
// len: len,
element_size: elm_size
// entries:
// keys: []string
}
return res
}
fn (m &map) new_entry(key string, val voidptr) Entry {
new_e := Entry {
key: key
val: malloc(m.element_size)
// next: 0
}
C.memcpy(new_e.val, val, m.element_size)
return new_e
}
fn (m mut map) _set(key string, val voidptr) {
e := m.new_entry(key, val)
for i := 0; i < m.entries.len; i++ {
entry := m.entries[i]
if entry.key == key {
// e := Entry2{key: key, val: val}
m.entries[i] = e
return
}
}
m.entries << e// m.new_entry(key, val)
m.is_sorted = false
}
fn volt_abs(n int) int {
// println('volt_abs($n)')
if n < 0 {
// println('< 0: -($n)')
return -n
}
return n
}
fn (m map) bs(query string, start, end int, out voidptr) {
// println('bs "$query" $start -> $end')
mid := start + ((end - start) / 2)
if end - start == 0 {
last := m.entries[end]
C.memcpy(out, last.val, m.element_size)
return
}
if end - start == 1 {
first := m.entries[start]
C.memcpy(out, first.val, m.element_size)
return
}
if mid >= m.entries.len {
return
}
mid_msg := m.entries[mid]
// println('mid.key=$mid_msg.key')
if query < mid_msg.key {
m.bs(query, start, mid, out)
return
}
m.bs(query, mid, end, out)
}
fn compare_map(a, b *Entry) int {
if a.key < b.key {
return -1
}
if a.key > b.key {
return 1
}
return 0
}
pub fn (m mut map) sort() {
m.entries.sort_with_compare(compare_map)
m.is_sorted = true
}
fn (m map) get(key string, out voidptr) bool {
if m.is_sorted {
// println('\n\nget "$key" sorted')
m.bs(key, 0, m.entries.len, out)
return true
}
for i := 0; i < m.entries.len; i++ {
entry := m.entries[i]
if entry.key == key {
C.memcpy(out, entry.val, m.element_size)
return true
}
}
return false
}
fn (m map) print() {
println('<<<<<<<<')
for i := 0; i < m.entries.len; i++ {
// entry := m.entries[i]
// println('$entry.key => $entry.val')
}
/*
for i := 0; i < m.cap * m.element_size; i++ {
b := m.table[i]
print('$i: ')
C.printf('%02x', b)
println('')
}
*/
println('>>>>>>>>>>')
}
fn (m map) free() {
// C.free(m.table)
// C.free(m.keys_table)
}
fn (m map_string) str() string {
// return 'not impl'
if m.entries.len == 0 {
return '{}'
}
// TODO use bytes buffer
mut s := '{\n'
for entry in m.entries {
val := m[entry.key]
s += ' "$entry.key" => "$val"\n'
}
s += '}'
return s
}