Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Added gomarkdown for ulist/ #48

Merged
merged 1 commit into from
Aug 2, 2023
Merged
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
1 change: 1 addition & 0 deletions README.md
Original file line number Diff line number Diff line change
@@ -29,6 +29,7 @@ This package implements some generic data structures.
versions of the rope with only a little extra time or memory.
* [`stack`](./stack): a LIFO stack.
* [`trie`](./trie): a ternary search trie.
* [`ulist`](./ulist): an un-rolled doubly-linked list.

See each subpackage for documentation and examples. The top-level `generic`
package provides some useful types and constraints. See [DOC.md](DOC.md) for
200 changes: 200 additions & 0 deletions ulist/README.md
Original file line number Diff line number Diff line change
@@ -0,0 +1,200 @@
<!-- Code generated by gomarkdoc. DO NOT EDIT -->

# ulist

```go
import "github.com/zyedidia/generic/ulist"
```

<details><summary>Example</summary>
<p>



```go
// Ideally 'entriesPerBlock' is the size of a cache line (64) or multiples there of.
entriesPerBlock := int(64 / unsafe.Sizeof(int(0)))
ul := New[int](entriesPerBlock)
ul.PushBack(1)
ul.PushBack(2)
ul.PushFront(0)

for iter := ul.Begin(); iter.IsValid(); iter.Next() {
fmt.Printf("%d\n", iter.Get())
}
// Output:
// 0
// 1
// 2
```

#### Output

```
0
1
2
```

</p>
</details>

## Index

- [type UList](<#UList>)
- [func New\[V any\]\(entriesPerBlock int\) \*UList\[V\]](<#New>)
- [func \(ul \*UList\[V\]\) AddAfter\(iter \*UListIter\[V\], v V\)](<#UList[V].AddAfter>)
- [func \(ul \*UList\[V\]\) AddBefore\(iter \*UListIter\[V\], v V\)](<#UList[V].AddBefore>)
- [func \(ul \*UList\[V\]\) Begin\(\) \*UListIter\[V\]](<#UList[V].Begin>)
- [func \(ul \*UList\[V\]\) End\(\) \*UListIter\[V\]](<#UList[V].End>)
- [func \(ul \*UList\[V\]\) PushBack\(v V\)](<#UList[V].PushBack>)
- [func \(ul \*UList\[V\]\) PushFront\(v V\)](<#UList[V].PushFront>)
- [func \(ul \*UList\[V\]\) Remove\(iter \*UListIter\[V\]\)](<#UList[V].Remove>)
- [func \(ul \*UList\[V\]\) Size\(\) int](<#UList[V].Size>)
- [type UListIter](<#UListIter>)
- [func \(iter \*UListIter\[V\]\) Get\(\) V](<#UListIter[V].Get>)
- [func \(iter \*UListIter\[V\]\) IsValid\(\) bool](<#UListIter[V].IsValid>)
- [func \(iter \*UListIter\[V\]\) Next\(\) bool](<#UListIter[V].Next>)
- [func \(iter \*UListIter\[V\]\) Prev\(\) bool](<#UListIter[V].Prev>)


<a name="UList"></a>
## type UList

UList implements a doubly\-linked unolled list.

```go
type UList[V any] struct {
// contains filtered or unexported fields
}
```

<a name="New"></a>
### func New

```go
func New[V any](entriesPerBlock int) *UList[V]
```

New returns an empty unrolled linked list. 'entriesPerBlock' is the number of entries to store in each block. This value should ideally be the size of a cache\-line or multiples there\-of. See: https://en.wikipedia.org/wiki/Unrolled_linked_list

<a name="UList[V].AddAfter"></a>
### func \(\*UList\[V\]\) AddAfter

```go
func (ul *UList[V]) AddAfter(iter *UListIter[V], v V)
```

AddAfter adds 'v' to 'ul' after the entry pointed to by 'iter'. 'iter' is expected to be valid, i.e. iter\-\>IsValid\(\) == true. 'iter' is updated to now point to the new entry added, such that iter\-\>Get\(\) == 'v'.

<a name="UList[V].AddBefore"></a>
### func \(\*UList\[V\]\) AddBefore

```go
func (ul *UList[V]) AddBefore(iter *UListIter[V], v V)
```

AddBefore adds 'v' to 'ul' before the entry pointed to by 'iter'. 'iter' is expected to be valid, i.e. iter\-\>IsValid\(\) == true. 'iter' is updated to now point to the new entry added, such that iter\-\>Get\(\) == 'v'.

<a name="UList[V].Begin"></a>
### func \(\*UList\[V\]\) Begin

```go
func (ul *UList[V]) Begin() *UListIter[V]
```

Begin returns an UListIter pointing to the first entry in the UList.

<a name="UList[V].End"></a>
### func \(\*UList\[V\]\) End

```go
func (ul *UList[V]) End() *UListIter[V]
```

End returns an UListIter pointing to the last entry in the UList.

<a name="UList[V].PushBack"></a>
### func \(\*UList\[V\]\) PushBack

```go
func (ul *UList[V]) PushBack(v V)
```

PushBack adds 'v' to the end of the ulist.

<a name="UList[V].PushFront"></a>
### func \(\*UList\[V\]\) PushFront

```go
func (ul *UList[V]) PushFront(v V)
```

PushFront adds 'v' to the beginning of the ulist.

<a name="UList[V].Remove"></a>
### func \(\*UList\[V\]\) Remove

```go
func (ul *UList[V]) Remove(iter *UListIter[V])
```

Remove deletes the entry in 'ul' pointed to by 'iter'. 'iter' is moved forward in the process. i.e. iter.Get\(\) returns the element in 'ul' that occurs after the deleted entry.

<a name="UList[V].Size"></a>
### func \(\*UList\[V\]\) Size

```go
func (ul *UList[V]) Size() int
```

Size returns the number of entries in 'ul'.

<a name="UListIter"></a>
## type UListIter

A UListIter points to an element in the UList.

```go
type UListIter[V any] struct {
// contains filtered or unexported fields
}
```

<a name="UListIter[V].Get"></a>
### func \(\*UListIter\[V\]\) Get

```go
func (iter *UListIter[V]) Get() V
```

Get returns the entry in the UList that the 'iter' is pointing to. This call should only ever be made when iter.IsValid\(\) is true.

<a name="UListIter[V].IsValid"></a>
### func \(\*UListIter\[V\]\) IsValid

```go
func (iter *UListIter[V]) IsValid() bool
```

IsValid returns true if the iterator points to a valid entry in the UList.

<a name="UListIter[V].Next"></a>
### func \(\*UListIter\[V\]\) Next

```go
func (iter *UListIter[V]) Next() bool
```

Next moves the iterator one step forward and returns true if the iterator is valid.

<a name="UListIter[V].Prev"></a>
### func \(\*UListIter\[V\]\) Prev

```go
func (iter *UListIter[V]) Prev() bool
```

Prev moves the iterator one step back and returns true if the iterator is valid.

Generated by [gomarkdoc](<https://github.com/princjef/gomarkdoc>)
18 changes: 18 additions & 0 deletions ulist/ulist_test.go
Original file line number Diff line number Diff line change
@@ -1,12 +1,30 @@
package ulist

import (
"fmt"
"reflect"
"runtime/debug"
"testing"
"unsafe"
)

func Example() {
// Ideally 'entriesPerBlock' is the size of a cache line (64) or multiples there of.
entriesPerBlock := int(64 / unsafe.Sizeof(int(0)))
ul := New[int](entriesPerBlock)
ul.PushBack(1)
ul.PushBack(2)
ul.PushFront(0)

for iter := ul.Begin(); iter.IsValid(); iter.Next() {
fmt.Printf("%d\n", iter.Get())
}
// Output:
// 0
// 1
// 2
}

func TestUList(t *testing.T) {
entriesPerBlock := int(64 / unsafe.Sizeof(int(1)))
ul := New[int](entriesPerBlock)