diff options
Diffstat (limited to 'v_windows/v/vlib/builtin/sorted_map.v')
| -rw-r--r-- | v_windows/v/vlib/builtin/sorted_map.v | 457 |
1 files changed, 457 insertions, 0 deletions
diff --git a/v_windows/v/vlib/builtin/sorted_map.v b/v_windows/v/vlib/builtin/sorted_map.v new file mode 100644 index 0000000..0f31424 --- /dev/null +++ b/v_windows/v/vlib/builtin/sorted_map.v @@ -0,0 +1,457 @@ +// Copyright (c) 2019-2021 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 + +// import strings + +// B-trees are balanced search trees with all leaves at +// the same level. B-trees are generally faster than +// binary search trees due to the better locality of +// reference, since multiple keys are stored in one node. + +// The number for `degree` has been picked through vigor- +// ous benchmarking but can be changed to any number > 1. +// `degree` determines the maximum length of each node. +const ( + degree = 6 + mid_index = degree - 1 + max_len = 2 * degree - 1 + children_bytes = sizeof(voidptr) * (max_len + 1) +) + +pub struct SortedMap { + value_bytes int +mut: + root &mapnode +pub mut: + len int +} + +struct mapnode { +mut: + children &voidptr + len int + keys [11]string // TODO: Should use `max_len` + values [11]voidptr // TODO: Should use `max_len` +} + +fn new_sorted_map(n int, value_bytes int) SortedMap { // TODO: Remove `n` + return SortedMap{ + value_bytes: value_bytes + root: new_node() + len: 0 + } +} + +fn new_sorted_map_init(n int, value_bytes int, keys &string, values voidptr) SortedMap { + mut out := new_sorted_map(n, value_bytes) + for i in 0 .. n { + unsafe { + out.set(keys[i], &byte(values) + i * value_bytes) + } + } + return out +} + +// The tree is initialized with an empty node as root to +// avoid having to check whether the root is null for +// each insertion. +fn new_node() &mapnode { + return &mapnode{ + children: 0 + len: 0 + } +} + +// This implementation does proactive insertion, meaning +// that splits are done top-down and not bottom-up. +fn (mut m SortedMap) set(key string, value voidptr) { + mut node := m.root + mut child_index := 0 + mut parent := &mapnode(0) + for { + if node.len == max_len { + if isnil(parent) { + parent = new_node() + m.root = parent + } + parent.split_child(child_index, mut node) + if key == parent.keys[child_index] { + unsafe { + vmemcpy(parent.values[child_index], value, m.value_bytes) + } + return + } + if key < parent.keys[child_index] { + node = unsafe { &mapnode(parent.children[child_index]) } + } else { + node = unsafe { &mapnode(parent.children[child_index + 1]) } + } + } + mut i := 0 + for i < node.len && key > node.keys[i] { + i++ + } + if i != node.len && key == node.keys[i] { + unsafe { + vmemcpy(node.values[i], value, m.value_bytes) + } + return + } + if isnil(node.children) { + mut j := node.len - 1 + for j >= 0 && key < node.keys[j] { + node.keys[j + 1] = node.keys[j] + node.values[j + 1] = node.values[j] + j-- + } + node.keys[j + 1] = key + unsafe { + node.values[j + 1] = malloc(m.value_bytes) + vmemcpy(node.values[j + 1], value, m.value_bytes) + } + node.len++ + m.len++ + return + } + parent = node + child_index = i + node = unsafe { &mapnode(node.children[child_index]) } + } +} + +fn (mut n mapnode) split_child(child_index int, mut y mapnode) { + mut z := new_node() + z.len = mid_index + y.len = mid_index + for j := mid_index - 1; j >= 0; j-- { + z.keys[j] = y.keys[j + degree] + z.values[j] = y.values[j + degree] + } + if !isnil(y.children) { + z.children = unsafe { &voidptr(malloc(int(children_bytes))) } + for jj := degree - 1; jj >= 0; jj-- { + unsafe { + z.children[jj] = y.children[jj + degree] + } + } + } + unsafe { + if isnil(n.children) { + n.children = &voidptr(malloc(int(children_bytes))) + } + n.children[n.len + 1] = n.children[n.len] + } + for j := n.len; j > child_index; j-- { + n.keys[j] = n.keys[j - 1] + n.values[j] = n.values[j - 1] + unsafe { + n.children[j] = n.children[j - 1] + } + } + n.keys[child_index] = y.keys[mid_index] + n.values[child_index] = y.values[mid_index] + unsafe { + n.children[child_index] = voidptr(y) + n.children[child_index + 1] = voidptr(z) + } + n.len++ +} + +fn (m SortedMap) get(key string, out voidptr) bool { + mut node := m.root + for { + mut i := node.len - 1 + for i >= 0 && key < node.keys[i] { + i-- + } + if i != -1 && key == node.keys[i] { + unsafe { + vmemcpy(out, node.values[i], m.value_bytes) + } + return true + } + if isnil(node.children) { + break + } + node = unsafe { &mapnode(node.children[i + 1]) } + } + return false +} + +fn (m SortedMap) exists(key string) bool { + if isnil(m.root) { // TODO: find out why root can be nil + return false + } + mut node := m.root + for { + mut i := node.len - 1 + for i >= 0 && key < node.keys[i] { + i-- + } + if i != -1 && key == node.keys[i] { + return true + } + if isnil(node.children) { + break + } + node = unsafe { &mapnode(node.children[i + 1]) } + } + return false +} + +fn (n &mapnode) find_key(k string) int { + mut idx := 0 + for idx < n.len && n.keys[idx] < k { + idx++ + } + return idx +} + +fn (mut n mapnode) remove_key(k string) bool { + idx := n.find_key(k) + if idx < n.len && n.keys[idx] == k { + if isnil(n.children) { + n.remove_from_leaf(idx) + } else { + n.remove_from_non_leaf(idx) + } + return true + } else { + if isnil(n.children) { + return false + } + flag := if idx == n.len { true } else { false } + if unsafe { &mapnode(n.children[idx]) }.len < degree { + n.fill(idx) + } + + mut node := &mapnode(0) + if flag && idx > n.len { + node = unsafe { &mapnode(n.children[idx - 1]) } + } else { + node = unsafe { &mapnode(n.children[idx]) } + } + return node.remove_key(k) + } +} + +fn (mut n mapnode) remove_from_leaf(idx int) { + for i := idx + 1; i < n.len; i++ { + n.keys[i - 1] = n.keys[i] + n.values[i - 1] = n.values[i] + } + n.len-- +} + +fn (mut n mapnode) remove_from_non_leaf(idx int) { + k := n.keys[idx] + if unsafe { &mapnode(n.children[idx]) }.len >= degree { + mut current := unsafe { &mapnode(n.children[idx]) } + for !isnil(current.children) { + current = unsafe { &mapnode(current.children[current.len]) } + } + predecessor := current.keys[current.len - 1] + n.keys[idx] = predecessor + n.values[idx] = current.values[current.len - 1] + mut node := unsafe { &mapnode(n.children[idx]) } + node.remove_key(predecessor) + } else if unsafe { &mapnode(n.children[idx + 1]) }.len >= degree { + mut current := unsafe { &mapnode(n.children[idx + 1]) } + for !isnil(current.children) { + current = unsafe { &mapnode(current.children[0]) } + } + successor := current.keys[0] + n.keys[idx] = successor + n.values[idx] = current.values[0] + mut node := unsafe { &mapnode(n.children[idx + 1]) } + node.remove_key(successor) + } else { + n.merge(idx) + mut node := unsafe { &mapnode(n.children[idx]) } + node.remove_key(k) + } +} + +fn (mut n mapnode) fill(idx int) { + if idx != 0 && unsafe { &mapnode(n.children[idx - 1]) }.len >= degree { + n.borrow_from_prev(idx) + } else if idx != n.len && unsafe { &mapnode(n.children[idx + 1]) }.len >= degree { + n.borrow_from_next(idx) + } else if idx != n.len { + n.merge(idx) + } else { + n.merge(idx - 1) + } +} + +fn (mut n mapnode) borrow_from_prev(idx int) { + mut child := unsafe { &mapnode(n.children[idx]) } + mut sibling := unsafe { &mapnode(n.children[idx - 1]) } + for i := child.len - 1; i >= 0; i-- { + child.keys[i + 1] = child.keys[i] + child.values[i + 1] = child.values[i] + } + if !isnil(child.children) { + for i := child.len; i >= 0; i-- { + unsafe { + child.children[i + 1] = child.children[i] + } + } + } + child.keys[0] = n.keys[idx - 1] + child.values[0] = n.values[idx - 1] + if !isnil(child.children) { + unsafe { + child.children[0] = sibling.children[sibling.len] + } + } + n.keys[idx - 1] = sibling.keys[sibling.len - 1] + n.values[idx - 1] = sibling.values[sibling.len - 1] + child.len++ + sibling.len-- +} + +fn (mut n mapnode) borrow_from_next(idx int) { + mut child := unsafe { &mapnode(n.children[idx]) } + mut sibling := unsafe { &mapnode(n.children[idx + 1]) } + child.keys[child.len] = n.keys[idx] + child.values[child.len] = n.values[idx] + if !isnil(child.children) { + unsafe { + child.children[child.len + 1] = sibling.children[0] + } + } + n.keys[idx] = sibling.keys[0] + n.values[idx] = sibling.values[0] + for i := 1; i < sibling.len; i++ { + sibling.keys[i - 1] = sibling.keys[i] + sibling.values[i - 1] = sibling.values[i] + } + if !isnil(sibling.children) { + for i := 1; i <= sibling.len; i++ { + unsafe { + sibling.children[i - 1] = sibling.children[i] + } + } + } + child.len++ + sibling.len-- +} + +fn (mut n mapnode) merge(idx int) { + mut child := unsafe { &mapnode(n.children[idx]) } + sibling := unsafe { &mapnode(n.children[idx + 1]) } + child.keys[mid_index] = n.keys[idx] + child.values[mid_index] = n.values[idx] + for i in 0 .. sibling.len { + child.keys[i + degree] = sibling.keys[i] + child.values[i + degree] = sibling.values[i] + } + if !isnil(child.children) { + for i := 0; i <= sibling.len; i++ { + unsafe { + child.children[i + degree] = sibling.children[i] + } + } + } + for i := idx + 1; i < n.len; i++ { + n.keys[i - 1] = n.keys[i] + n.values[i - 1] = n.values[i] + } + for i := idx + 2; i <= n.len; i++ { + unsafe { + n.children[i - 1] = n.children[i] + } + } + child.len += sibling.len + 1 + n.len-- + // free(sibling) +} + +pub fn (mut m SortedMap) delete(key string) { + if m.root.len == 0 { + return + } + + removed := m.root.remove_key(key) + if removed { + m.len-- + } + + if m.root.len == 0 { + // tmp := t.root + if isnil(m.root.children) { + return + } else { + m.root = unsafe { &mapnode(m.root.children[0]) } + } + // free(tmp) + } +} + +// Insert all keys of the subtree into array `keys` +// starting at `at`. Keys are inserted in order. +fn (n &mapnode) subkeys(mut keys []string, at int) int { + mut position := at + if !isnil(n.children) { + // Traverse children and insert + // keys inbetween children + for i in 0 .. n.len { + child := unsafe { &mapnode(n.children[i]) } + position += child.subkeys(mut keys, position) + keys[position] = n.keys[i] + position++ + } + // Insert the keys of the last child + child := unsafe { &mapnode(n.children[n.len]) } + position += child.subkeys(mut keys, position) + } else { + // If leaf, insert keys + for i in 0 .. n.len { + keys[position + i] = n.keys[i] + } + position += n.len + } + // Return # of added keys + return position - at +} + +pub fn (m &SortedMap) keys() []string { + mut keys := []string{len: m.len} + if isnil(m.root) || m.root.len == 0 { + return keys + } + m.root.subkeys(mut keys, 0) + return keys +} + +fn (mut n mapnode) free() { + println('TODO') +} + +pub fn (mut m SortedMap) free() { + if isnil(m.root) { + return + } + m.root.free() +} + +pub fn (m SortedMap) print() { + println('TODO') +} + +// pub fn (m map_string) str() string { +// if m.len == 0 { +// return '{}' +// } +// mut sb := strings.new_builder(50) +// sb.writeln('{') +// for key, val in m { +// sb.writeln(' "$key" => "$val"') +// } +// sb.writeln('}') +// return sb.str() +// } |