From 09cc146211148a3b2568261c41a804a802c31d4c Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Wed, 13 Jul 2022 20:31:51 -0600 Subject: re-organize some things between files --- lib/rbtree/print_test.go | 45 -------------- lib/rbtree/rbtree.go | 42 +++++++++++++ lib/rbtree/rbtree_test.go | 37 ++++++++++++ lib/rbtree/rbtree_util.go | 52 ---------------- lib/util/generic.go | 147 ---------------------------------------------- lib/util/maputil.go | 23 ++++++++ lib/util/ordered.go | 41 +++++++++++++ lib/util/sliceutil.go | 69 ++++++++++++++++++++++ lib/util/syncmap.go | 40 +++++++++++++ 9 files changed, 252 insertions(+), 244 deletions(-) delete mode 100644 lib/rbtree/print_test.go delete mode 100644 lib/rbtree/rbtree_util.go delete mode 100644 lib/util/generic.go create mode 100644 lib/util/maputil.go create mode 100644 lib/util/ordered.go create mode 100644 lib/util/sliceutil.go create mode 100644 lib/util/syncmap.go (limited to 'lib') diff --git a/lib/rbtree/print_test.go b/lib/rbtree/print_test.go deleted file mode 100644 index fe2d2bd..0000000 --- a/lib/rbtree/print_test.go +++ /dev/null @@ -1,45 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package rbtree - -import ( - "fmt" - "io" - "strings" -) - -func (t *Tree[K, V]) ASCIIArt() string { - var out strings.Builder - t.root.asciiArt(&out, "", "", "") - return out.String() -} - -func (node *Node[V]) String() string { - switch { - case node == nil: - return "nil" - case node.Color == Red: - return fmt.Sprintf("R(%v)", node.Value) - default: - return fmt.Sprintf("B(%v)", node.Value) - } -} - -func (node *Node[V]) asciiArt(w io.Writer, u, m, l string) { - if node == nil { - fmt.Fprintf(w, "%snil\n", m) - return - } - - node.Right.asciiArt(w, u+" ", u+" ,--", u+" | ") - - if node.Color == Red { - fmt.Fprintf(w, "%s%v\n", m, node) - } else { - fmt.Fprintf(w, "%s%v\n", m, node) - } - - node.Left.asciiArt(w, l+" | ", l+" `--", l+" ") -} diff --git a/lib/rbtree/rbtree.go b/lib/rbtree/rbtree.go index 575a9ca..25f3b1c 100644 --- a/lib/rbtree/rbtree.go +++ b/lib/rbtree/rbtree.go @@ -6,6 +6,7 @@ package rbtree import ( "fmt" + "reflect" "git.lukeshu.com/btrfs-progs-ng/lib/util" ) @@ -180,6 +181,47 @@ func (cur *Node[V]) prev() *Node[V] { return parent } +// SearchRange is like Search, but returns all nodes that match the +// function; assuming that they are contiguous. +func (t *Tree[K, V]) SearchRange(fn func(V) int) []V { + middle := t.Search(fn) + if middle == nil { + return nil + } + ret := []V{middle.Value} + for node := t.Prev(middle); node != nil && fn(node.Value) == 0; node = t.Prev(node) { + ret = append(ret, node.Value) + } + util.ReverseSlice(ret) + for node := t.Next(middle); node != nil && fn(node.Value) == 0; node = t.Next(node) { + ret = append(ret, node.Value) + } + return ret +} + +func (t *Tree[K, V]) Equal(u *Tree[K, V]) bool { + if (t == nil) != (u == nil) { + return false + } + if t == nil { + return true + } + + var tSlice []V + _ = t.Walk(func(node *Node[V]) error { + tSlice = append(tSlice, node.Value) + return nil + }) + + var uSlice []V + _ = u.Walk(func(node *Node[V]) error { + uSlice = append(uSlice, node.Value) + return nil + }) + + return reflect.DeepEqual(tSlice, uSlice) +} + func (t *Tree[K, V]) parentChild(node *Node[V]) **Node[V] { switch { case node.Parent == nil: diff --git a/lib/rbtree/rbtree_test.go b/lib/rbtree/rbtree_test.go index 999eb6f..e6007e1 100644 --- a/lib/rbtree/rbtree_test.go +++ b/lib/rbtree/rbtree_test.go @@ -5,7 +5,10 @@ package rbtree import ( + "fmt" + "io" "sort" + "strings" "testing" "github.com/stretchr/testify/require" @@ -14,6 +17,40 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/util" ) +func (t *Tree[K, V]) ASCIIArt() string { + var out strings.Builder + t.root.asciiArt(&out, "", "", "") + return out.String() +} + +func (node *Node[V]) String() string { + switch { + case node == nil: + return "nil" + case node.Color == Red: + return fmt.Sprintf("R(%v)", node.Value) + default: + return fmt.Sprintf("B(%v)", node.Value) + } +} + +func (node *Node[V]) asciiArt(w io.Writer, u, m, l string) { + if node == nil { + fmt.Fprintf(w, "%snil\n", m) + return + } + + node.Right.asciiArt(w, u+" ", u+" ,--", u+" | ") + + if node.Color == Red { + fmt.Fprintf(w, "%s%v\n", m, node) + } else { + fmt.Fprintf(w, "%s%v\n", m, node) + } + + node.Left.asciiArt(w, l+" | ", l+" `--", l+" ") +} + func checkTree[K constraints.Ordered, V any](t *testing.T, expectedSet map[K]struct{}, tree *Tree[util.NativeOrdered[K], V]) { // 1. Every node is either red or black diff --git a/lib/rbtree/rbtree_util.go b/lib/rbtree/rbtree_util.go deleted file mode 100644 index cee5508..0000000 --- a/lib/rbtree/rbtree_util.go +++ /dev/null @@ -1,52 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package rbtree - -import ( - "reflect" - - "git.lukeshu.com/btrfs-progs-ng/lib/util" -) - -// SearchRange is like Search, but returns all nodes that match the -// function; assuming that they are contiguous. -func (t *Tree[K, V]) SearchRange(fn func(V) int) []V { - middle := t.Search(fn) - if middle == nil { - return nil - } - ret := []V{middle.Value} - for node := t.Prev(middle); node != nil && fn(node.Value) == 0; node = t.Prev(node) { - ret = append(ret, node.Value) - } - util.ReverseSlice(ret) - for node := t.Next(middle); node != nil && fn(node.Value) == 0; node = t.Next(node) { - ret = append(ret, node.Value) - } - return ret -} - -func (t *Tree[K, V]) Equal(u *Tree[K, V]) bool { - if (t == nil) != (u == nil) { - return false - } - if t == nil { - return true - } - - var tSlice []V - _ = t.Walk(func(node *Node[V]) error { - tSlice = append(tSlice, node.Value) - return nil - }) - - var uSlice []V - _ = u.Walk(func(node *Node[V]) error { - uSlice = append(uSlice, node.Value) - return nil - }) - - return reflect.DeepEqual(tSlice, uSlice) -} diff --git a/lib/util/generic.go b/lib/util/generic.go deleted file mode 100644 index a63a814..0000000 --- a/lib/util/generic.go +++ /dev/null @@ -1,147 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package util - -import ( - "sort" - "sync" - - "golang.org/x/exp/constraints" -) - -func InSlice[T comparable](needle T, haystack []T) bool { - for _, straw := range haystack { - if needle == straw { - return true - } - } - return false -} - -func RemoveAllFromSlice[T comparable](haystack []T, needle T) []T { - for i, straw := range haystack { - if needle == straw { - return append( - haystack[:i], - RemoveAllFromSlice(haystack[i+1:], needle)...) - } - } - return haystack -} - -func RemoveAllFromSliceFunc[T any](haystack []T, f func(T) bool) []T { - for i, straw := range haystack { - if f(straw) { - return append( - haystack[:i], - RemoveAllFromSliceFunc(haystack[i+1:], f)...) - } - } - return haystack -} - -func ReverseSlice[T any](slice []T) { - for i := 0; i < len(slice)/2; i++ { - j := (len(slice) - 1) - i - slice[i], slice[j] = slice[j], slice[i] - } -} - -func Max[T constraints.Ordered](a, b T) T { - if a > b { - return a - } - return b -} - -func Min[T constraints.Ordered](a, b T) T { - if a < b { - return a - } - return b -} - -func MapKeys[K comparable, V any](m map[K]V) []K { - ret := make([]K, 0, len(m)) - for k := range m { - ret = append(ret, k) - } - return ret -} - -func SortSlice[T constraints.Ordered](slice []T) { - sort.Slice(slice, func(i, j int) bool { - return slice[i] < slice[j] - }) -} - -func SortedMapKeys[K constraints.Ordered, V any](m map[K]V) []K { - ret := MapKeys(m) - SortSlice(ret) - return ret -} - -func CmpUint[T constraints.Unsigned](a, b T) int { - switch { - case a < b: - return -1 - case a == b: - return 0 - default: - return 1 - } -} - -type SyncMap[K comparable, V any] struct { - inner sync.Map -} - -func (m *SyncMap[K, V]) Delete(key K) { m.inner.Delete(key) } -func (m *SyncMap[K, V]) Load(key K) (value V, ok bool) { - _value, ok := m.inner.Load(key) - if ok { - value = _value.(V) - } - return value, ok -} -func (m *SyncMap[K, V]) LoadAndDelete(key K) (value V, loaded bool) { - _value, ok := m.inner.LoadAndDelete(key) - if ok { - value = _value.(V) - } - return value, ok -} -func (m *SyncMap[K, V]) LoadOrStore(key K, value V) (actual V, loaded bool) { - _actual, loaded := m.inner.LoadOrStore(key, value) - actual = _actual.(V) - return actual, loaded -} -func (m *SyncMap[K, V]) Range(f func(key K, value V) bool) { - m.inner.Range(func(key, value any) bool { - return f(key.(K), value.(V)) - }) -} -func (m *SyncMap[K, V]) Store(key K, value V) { m.inner.Store(key, value) } - -type Ordered[T interface{ Cmp(T) int }] interface { - Cmp(T) int -} - -type NativeOrdered[T constraints.Ordered] struct { - Val T -} - -func (a NativeOrdered[T]) Cmp(b NativeOrdered[T]) int { - switch { - case a.Val < b.Val: - return -1 - case a.Val > b.Val: - return 1 - default: - return 0 - } -} - -var _ Ordered[NativeOrdered[int]] = NativeOrdered[int]{} diff --git a/lib/util/maputil.go b/lib/util/maputil.go new file mode 100644 index 0000000..d7f1727 --- /dev/null +++ b/lib/util/maputil.go @@ -0,0 +1,23 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package util + +import ( + "golang.org/x/exp/constraints" +) + +func MapKeys[K comparable, V any](m map[K]V) []K { + ret := make([]K, 0, len(m)) + for k := range m { + ret = append(ret, k) + } + return ret +} + +func SortedMapKeys[K constraints.Ordered, V any](m map[K]V) []K { + ret := MapKeys(m) + SortSlice(ret) + return ret +} diff --git a/lib/util/ordered.go b/lib/util/ordered.go new file mode 100644 index 0000000..fc5b5ee --- /dev/null +++ b/lib/util/ordered.go @@ -0,0 +1,41 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package util + +import ( + "golang.org/x/exp/constraints" +) + +func CmpUint[T constraints.Unsigned](a, b T) int { + switch { + case a < b: + return -1 + case a == b: + return 0 + default: + return 1 + } +} + +type Ordered[T interface{ Cmp(T) int }] interface { + Cmp(T) int +} + +type NativeOrdered[T constraints.Ordered] struct { + Val T +} + +func (a NativeOrdered[T]) Cmp(b NativeOrdered[T]) int { + switch { + case a.Val < b.Val: + return -1 + case a.Val > b.Val: + return 1 + default: + return 0 + } +} + +var _ Ordered[NativeOrdered[int]] = NativeOrdered[int]{} diff --git a/lib/util/sliceutil.go b/lib/util/sliceutil.go new file mode 100644 index 0000000..6e0ce76 --- /dev/null +++ b/lib/util/sliceutil.go @@ -0,0 +1,69 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package util + +import ( + "sort" + + "golang.org/x/exp/constraints" +) + +func InSlice[T comparable](needle T, haystack []T) bool { + for _, straw := range haystack { + if needle == straw { + return true + } + } + return false +} + +func RemoveAllFromSlice[T comparable](haystack []T, needle T) []T { + for i, straw := range haystack { + if needle == straw { + return append( + haystack[:i], + RemoveAllFromSlice(haystack[i+1:], needle)...) + } + } + return haystack +} + +func RemoveAllFromSliceFunc[T any](haystack []T, f func(T) bool) []T { + for i, straw := range haystack { + if f(straw) { + return append( + haystack[:i], + RemoveAllFromSliceFunc(haystack[i+1:], f)...) + } + } + return haystack +} + +func ReverseSlice[T any](slice []T) { + for i := 0; i < len(slice)/2; i++ { + j := (len(slice) - 1) - i + slice[i], slice[j] = slice[j], slice[i] + } +} + +func Max[T constraints.Ordered](a, b T) T { + if a > b { + return a + } + return b +} + +func Min[T constraints.Ordered](a, b T) T { + if a < b { + return a + } + return b +} + +func SortSlice[T constraints.Ordered](slice []T) { + sort.Slice(slice, func(i, j int) bool { + return slice[i] < slice[j] + }) +} diff --git a/lib/util/syncmap.go b/lib/util/syncmap.go new file mode 100644 index 0000000..a281f2d --- /dev/null +++ b/lib/util/syncmap.go @@ -0,0 +1,40 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package util + +import ( + "sync" +) + +type SyncMap[K comparable, V any] struct { + inner sync.Map +} + +func (m *SyncMap[K, V]) Delete(key K) { m.inner.Delete(key) } +func (m *SyncMap[K, V]) Load(key K) (value V, ok bool) { + _value, ok := m.inner.Load(key) + if ok { + value = _value.(V) + } + return value, ok +} +func (m *SyncMap[K, V]) LoadAndDelete(key K) (value V, loaded bool) { + _value, ok := m.inner.LoadAndDelete(key) + if ok { + value = _value.(V) + } + return value, ok +} +func (m *SyncMap[K, V]) LoadOrStore(key K, value V) (actual V, loaded bool) { + _actual, loaded := m.inner.LoadOrStore(key, value) + actual = _actual.(V) + return actual, loaded +} +func (m *SyncMap[K, V]) Range(f func(key K, value V) bool) { + m.inner.Range(func(key, value any) bool { + return f(key.(K), value.(V)) + }) +} +func (m *SyncMap[K, V]) Store(key K, value V) { m.inner.Store(key, value) } -- cgit v1.2.3-2-g168b