Optimal implementation of ordered maps for Golang - ie maps that remember the order in which keys were inserted.

Build Status

Goland Ordered Maps

Same as regular maps, but also remembers the order in which keys were inserted, akin to Python's collections.OrderedDicts.

It offers the following features:

  • optimal runtime performance (all operations are constant time)
  • optimal memory usage (only one copy of values, no unnecessary memory allocation)
  • allows iterating from newest or oldest keys indifferently, without memory copy, allowing to break the iteration, and in time linear to the number of keys iterated over rather than the total length of the ordered map
  • takes and returns generic interface{}s
  • idiomatic API, akin to that of container/list

Installation

go get -u github.com/wk8/go-ordered-map

Or use your favorite golang vendoring tool!

Documentation

The full documentation is available on godoc.org.

Example / usage

package main

import (
	"fmt"

	"github.com/wk8/go-ordered-map"
)

func main() {
	om := orderedmap.New()

	om.Set("foo", "bar")
	om.Set("bar", "baz")
	om.Set("coucou", "toi")

	fmt.Println(om.Get("foo"))          // => bar, true
	fmt.Println(om.Get("i dont exist")) // => <nil>, false

	// iterating pairs from oldest to newest:
	for pair := om.Oldest(); pair != nil; pair = pair.Next() {
		fmt.Printf("%s => %s\n", pair.Key, pair.Value)
	} // prints:
	// foo => bar
	// bar => baz
	// coucou => toi

	// iterating over the 2 newest pairs:
	i := 0
	for pair := om.Newest(); pair != nil; pair = pair.Prev() {
		fmt.Printf("%s => %s\n", pair.Key, pair.Value)
		i++
		if i >= 2 {
			break
		}
	} // prints:
	// coucou => toi
	// bar => baz
}

All of OrderedMap's methods accept and return interface{}s, so you can use any type of keys that regular maps accept, as well pack/unpack arbitrary values, e.g.:

type myStruct struct {
	payload string
}

func main() {
	om := orderedmap.New()

	om.Set(12, &myStruct{"foo"})
	om.Set(1, &myStruct{"bar"})

	value, present := om.Get(12)
	if !present {
		panic("should be there!")
	}
	fmt.Println(value.(*myStruct).payload) // => foo

	for pair := om.Oldest(); pair != nil; pair = pair.Next() {
		fmt.Printf("%d => %s\n", pair.Key, pair.Value.(*myStruct).payload)
	} // prints:
	// 12 => foo
	// 1 => bar
}

Alternatives

There are several other ordered map golang implementations out there, but I believe that at the time of writing none of them offer the same functionality as this library; more specifically:

  • iancoleman/orderedmap only accepts string keys, its Delete operations are linear
  • cevaris/ordered_map uses a channel for iterations, and leaks goroutines if the iteration is interrupted before fully traversing the map
  • mantyr/iterator also uses a channel for iterations, and its Delete operations are linear
  • samdolan/go-ordered-map adds unnecessary locking (users should add their own locking instead if they need it), its Delete and Get operations are linear, iterations trigger a linear memory allocation
Comments
  • Please bump v0.2.0 tag

    Please bump v0.2.0 tag

    Hi, Could you release a new tag please? go get -u github.com/wk8/go-ordered-map does not update, I had to specify the master branch go get -u github.com/wk8/go-ordered-map@master in order to update :-) like v0.2.0

    Thank you!

  • fix: ensure inner linker list is never nil before lazyInit

    fix: ensure inner linker list is never nil before lazyInit

    I am proposing this fix to the crash found in https://github.com/wk8/go-ordered-map/pull/19

    This is mostly for demonstration. Surely there's a cleaner fix to be found.

  • Fuzz un/marshall-ing methods after #16

    Fuzz un/marshall-ing methods after #16

    Run fuzzing with go test -fuzz=. -fuzztime=10s ./...

    --- FAIL: FuzzMarshalling (0.00s)
        --- FAIL: FuzzMarshalling/8093511184ad3e258aa13b957e75ff26c7fae64672dae0c0bc0a9fa5b61a05e7 (0.00s)
    panic: runtime error: invalid memory address or nil pointer dereference [recovered]
    	panic: runtime error: invalid memory address or nil pointer dereference [recovered]
    	panic: runtime error: invalid memory address or nil pointer dereference
    [signal SIGSEGV: segmentation violation code=0x1 addr=0x20 pc=0x610968]
    
    goroutine 7 [running]:
    testing.tRunner.func1.2({0x63f4e0, 0x84be00})
    	/snap/go/10008/src/testing/testing.go:1396 +0x24e
    testing.tRunner.func1()
    	/snap/go/10008/src/testing/testing.go:1399 +0x39f
    panic({0x63f4e0, 0x84be00})
    	/snap/go/10008/src/runtime/panic.go:884 +0x212
    encoding/json.(*encodeState).marshal.func1()
    	/snap/go/10008/src/encoding/json/encode.go:327 +0x6e
    panic({0x63f4e0, 0x84be00})
    	/snap/go/10008/src/runtime/panic.go:884 +0x212
    github.com/bahlo/generic-list-go.(*List[...]).Front(...)
    	/home/pete/wefwefwef/go/pkg/mod/github.com/bahlo/[email protected]/list.go:70
    github.com/wk8/go-ordered-map/v2.(*OrderedMap[...]).Oldest(...)
    	/home/pete/wefwefwef/go-ordered-map.git/orderedmap.go:102
    github.com/wk8/go-ordered-map/v2.(*OrderedMap[...]).MarshalJSON(0xc000069270)
    	/home/pete/wefwefwef/go-ordered-map.git/json.go:23 +0x88
    encoding/json.marshalerEncoder(0xc00015e600, {0x66f160?, 0xc000069270?, 0x30?}, {0x8?, 0x31?})
    	/snap/go/10008/src/encoding/json/encode.go:478 +0xbe
    encoding/json.(*encodeState).reflectValue(0x0?, {0x66f160?, 0xc000069270?, 0x40ef87?}, {0x78?, 0x0?})
    	/snap/go/10008/src/encoding/json/encode.go:359 +0x78
    encoding/json.(*encodeState).marshal(0x88?, {0x66f160?, 0xc000069270?}, {0x80?, 0xf6?})
    	/snap/go/10008/src/encoding/json/encode.go:331 +0xfa
    encoding/json.Marshal({0x66f160, 0xc000069270})
    	/snap/go/10008/src/encoding/json/encode.go:160 +0x45
    github.com/wk8/go-ordered-map/v2.FuzzMarshalling.func1(0x0?, {0xc00001cc60, 0x2, 0x8})
    	/home/pete/wefwefwef/go-ordered-map.git/fuzz_test.go:31 +0x1b4
    reflect.Value.call({0x634b40?, 0x6ab2a8?, 0x13?}, {0x67d806, 0x4}, {0xc0001097d0, 0x2, 0x2?})
    	/snap/go/10008/src/reflect/value.go:584 +0x8c5
    reflect.Value.Call({0x634b40?, 0x6ab2a8?, 0x51b?}, {0xc0001097d0?, 0x7ee0d8?, 0x825900?})
    	/snap/go/10008/src/reflect/value.go:368 +0xbc
    testing.(*F).Fuzz.func1.1(0x0?)
    	/snap/go/10008/src/testing/fuzz.go:337 +0x231
    testing.tRunner(0xc000134b60, 0xc000136090)
    	/snap/go/10008/src/testing/testing.go:1446 +0x10b
    created by testing.(*F).Fuzz.func1
    	/snap/go/10008/src/testing/fuzz.go:324 +0x5b9
    exit status 2
    FAIL	github.com/wk8/go-ordered-map/v2	0.006s
    
  • Feature request

    Feature request

    Can you add a set function or an option in New() with a LRU type feature, where the order is maintained as per update?

    I understand it's not the way an ordered map works but I am requesting an added functionality. OrderedMap where the order can be defined on update also rather than only on creation.

    It's not an issue but a feature request. I can add the desired piece of code.

  • Long values fail to serialize into JSON

    Long values fail to serialize into JSON

    	t.Run("int key", func(t *testing.T) {
    		om := New[int, any]()
    		om.Set(1, "bar")
    		om.Set(7, "baz")
    		om.Set(2, 28)
    		om.Set(3, 100)
    		om.Set(4, "baz")
    		om.Set(5, "28")
    		om.Set(6, "100")
    		om.Set(8, "baz")
    		om.Set(8, "baz")
    		om.Set(9, "Lorem ipsum dolor sit amet, consectetur adipiscing elit. Quisque auctor augue accumsan mi maximus, quis viverra massa pretium. Phasellus imperdiet sapien a interdum sollicitudin. Duis at commodo lectus, a lacinia sem.")
    
    		b, err := json.Marshal(om)
    		assert.NoError(t, err)
    		assert.Equal(t, `{"1":"bar","7":"baz","2":28,"3":100,"4":"baz","5":"28","6":"100","8":"baz", "9": "Lorem ipsum dolor sit amet, consectetur adipiscing elit. Quisque auctor augue accumsan mi maximus, quis viverra massa pretium. Phasellus imperdiet sapien a interdum sollicitudin. Duis at commodo lectus, a lacinia sem."}`, string(b))
    	})
    
    --- FAIL: TestMarshalJSON (0.00s)
        --- FAIL: TestMarshalJSON/int_key (0.00s)
            json_test.go:52: 
                    Error Trace:    json_test.go:52
                    Error:          Received unexpected error:
                                    json: error calling MarshalJSON for type *orderedmap.OrderedMap[int,interface {}]: invalid character 'g' in literal null (expecting 'u')
                    Test:           TestMarshalJSON/int_key
            json_test.go:53: 
                    Error Trace:    json_test.go:53
                    Error:          Not equal: 
                                    expected: "{\"1\":\"bar\",\"7\":\"baz\",\"2\":28,\"3\":100,\"4\":\"baz\",\"5\":\"28\",\"6\":\"100\",\"8\":\"baz\", \"9\": \"Lorem ipsum dolor sit amet, consectetur adipiscing elit. Quisque auctor augue accumsan mi maximus, quis viverra massa pretium. Phasellus imperdiet sapien a interdum sollicitudin. Duis at commodo lectus, a lacinia sem.\"}"
                                    actual  : ""
                                
                                    Diff:
                                    --- Expected
                                    +++ Actual
                                    @@ -1 +1 @@
                                    -{"1":"bar","7":"baz","2":28,"3":100,"4":"baz","5":"28","6":"100","8":"baz", "9": "Lorem ipsum dolor sit amet, consectetur adipiscing elit. Quisque auctor augue accumsan mi maximus, quis viverra massa pretium. Phasellus imperdiet sapien a interdum sollicitudin. Duis at commodo lectus, a lacinia sem."}
                                    +
                    Test:           TestMarshalJSON/int_key
    FAIL
    

    I believe this is due to returning jwriter.Writer.Buffer.Buf in MarshalJSON

  • Add alias function Load and Store, Expose Move function from list.List

    Add alias function Load and Store, Expose Move function from list.List

    1. Add alias function Load and Store sync.Map uses Load/Store but this uses Get() and Set(), so I added alias to make the API more consistency.

    2. Expose Move* function from list.List so that users cam move the order of the element in orderedMap directly.

    	om := New()
    	om.Set("1", "bar")
    	om.Set(2, 28)
    	om.Set(3, 100)
    	om.Set("4", "baz")
    	om.Set(5, "28")
    	om.Set(6, "100")
    	om.Set("7", "baz")
    	om.Set("8", "baz")
    
    	om.MoveAfter(2, 3)
    	om.MoveBefore(6, "4")
            om.MoveToBack(3)
    	om.MoveToFront(5)
    
  • Function Request - Copy, Clone, Reverse, First, Front, Back, Last, Size

    Function Request - Copy, Clone, Reverse, First, Front, Back, Last, Size

    This closes the function request issue #10 that I created.

    Additions:

    • Copy(): Produce a copy of a OrderedMap object
    • Reverse(): Reverse a certain OrderedMap object
    • First() and Front(): Alias for Oldest
    • Last() and Back(): Alias for Newest
    • Tests for Copy and Reverse

    Notes:

    • Copy could technically be optimized via some memory library but this should be performant enough without causing too much overhead.
    • Reverse could be more readable if the generic list library implemented a reverse function, nevertheless its just as efficient.
    • I decided against Keys() and Values() at least for now due to mis-interruptions and limited use cases.
    • You might notice that First, Front, Last, and Back are technically not aliases as they do not call Oldest and Newest. I leaned on the side of efficiency (bypassing the function call) because the definition is a one-line / straightforward.

    I am happy to make any changes upon request.

  • allow special character as keys

    allow special character as keys

    The offending bug was in quoteString:

    func quoteString(data []byte) []byte {
    	withQuotes := make([]byte, len(data)+2) //nolint:gomnd
    	copy(withQuotes[1:], data)
    	withQuotes[0] = '"'
    	withQuotes[len(data)+1] = '"'
    	return withQuotes
    }
    

    Which did not handle escaped characters. Since the key was quoted just to be un-quoted back to string, the code was refactored to set string type keys directly.

    This bug fix should work for any valid utf-8 string. Round trapping will return the exact same string and byte compatible with the official Golang JSON library.

    If a key string value is not valid utf-8, round trapping could change the key, I'm not sure what to do with that.

  • Add default handling for typed string key for json

    Add default handling for typed string key for json

    The use case is, sometimes we might want to use a typed string key type Foo string instead of string to increase the descriptiveness of our API. This saves writing UnmarshalText for most cases yet still allows UnmarshalText to be written if direct string conversion is not desired.

    I believe the use of reflect is necessary until type switch support ~ https://github.com/golang/go/issues/45380#issuecomment-813003118

    This is a backwards compatible change since it adds support for types previously returned error. There is also no performance impact on existing working code. There might be a risk that code used to return error could now panic, if someone more knowledgeable at the intersection of comparable types and reflect panic cases could review this code.

    I though about extending this to the integer types, but it's not obvious what the desirable behavior is if the typed integer is an enum or stringer or decimal like time.Duration. If not right the first time, it would require an breaking change to fix. So it's probably better to wait until a pressing need appears.

  • v2.1.2

    v2.1.2

    • Allowing to pass options to New, to give a capacity hint, or initial data
    • Allowing to deserialize nested ordered maps from JSON without having to explicitly instantiate them
    • Added the AddPairs method
    • tests on all of the above
  • Naming and Function Request

    Naming and Function Request

    Functions:

    • Copy() - built-in
    • Keys() - a note should be made to not use this for looping
    • Values() - a note should be made to not use this for looping
    • First() and Front() - both should act like Oldest()
    • Last() and Back() - both should act like Newest()

    I know that Oldest() and Newest() are to be more akin to python's OrderedDicts, but I do find them to be more confusing especially when you start re-arranging the order and when a certain map has been existing for awhile. Perhaps adding the other functions that act like them will make code a little more clear.

subtraction operations and also parentheses to indicate order of operations

basic parsing expose a Calculate method that accepts a string of addition / subtraction operations and also parentheses to indicate order of operation

Feb 22, 2022
Golang: unify nil and empty slices and maps

unifynil, unify nil and empty slices and maps in Golang Empty slices and maps can be nil or not nil in Go. It may become a nightmare in tests and JSON

Jan 16, 2022
A Go package for checking conditions for slices and maps.

check Go package The check package of Go helps one to check various conditions for slices: []int []float64 []string []bool maps: map[string]int map[st

Aug 26, 2022
Create deep copies (clones) of your maps and slices without using reflection.

DeepCopy DeepCopy helps you create deep copies (clones) of your maps and slices. Create deep copies (clones) of your objects The package is based on t

Nov 20, 2022
Access and modify property values in deeply nested maps, using dot-separated paths

Dig lets you access and modify property values in deeply nested, unstructured maps, using dot-separated paths: source := make(map[string]interface{})

May 7, 2022
Automatically creates & tiles .tmx format maps from a world map interface
Automatically creates & tiles .tmx format maps from a world map interface

Autotile Create tiled maps for an arbitrarily large world space from a simple interface, then add larger objects randomly with simple rules (eg. place

Aug 19, 2022
🍕 Enjoy a slice! A utility library for dealing with slices and maps that focuses on type safety and performance.

?? github.com/elliotchance/pie Enjoy a slice! pie is a library of utility functions for common operations on slices and maps. Quick Start FAQ What are

Dec 30, 2022
yaml-patch is a version of Evan Phoenix's json-patch, which is an implementation of JSON Patch, directly transposed to YAML

yaml-patch yaml-patch is a version of Evan Phoenix's json-patch, which is an implementation of JavaScript Object Notation (JSON) Patch, directly trans

Jan 15, 2022
Goridge is high performance PHP-to-Golang codec library which works over native PHP sockets and Golang net/rpc package.
Goridge is high performance PHP-to-Golang codec library which works over native PHP sockets and Golang net/rpc package.

Goridge is high performance PHP-to-Golang codec library which works over native PHP sockets and Golang net/rpc package. The library allows you to call Go service methods from PHP with a minimal footprint, structures and []byte support.

Dec 28, 2022
A lib of golang which contains many funny api;

A lib of golang which contains many funny api; I created it cause I could not find these more-effient apis from other repo.

Oct 27, 2021
Cpu-profiling - Basic example of CPU Profiling in Golang which shows the bottlenecks and how much time is spent per function

cpu-profiling Basic example of CPU Profiling in Golang which shows the bottlenec

Aug 2, 2022
Flock is a project which provides a Go solution for system level file locks for all platforms Golang supports.

Flock is a project which provides a Go solution for system level file locks for all platforms Golang supports.

Feb 8, 2022
This is a Pub/Sub for the Watermill project which uses the Bolt database.
This is a Pub/Sub for the Watermill project which uses the Bolt database.

Watermill Bolt Pub/Sub This is a Pub/Sub for the Watermill project which uses the Bolt database.

Jun 13, 2022
Simple go package which converts roman strings to integer

romanparse Simple go package which converts roman strings

Aug 11, 2022
Utility to restrict which package is allowed to import another package.

go-import-rules Utility to restrict which package is allowed to import another package. This tool will read import-rules.yaml or import-rules.yml in t

Jan 7, 2022
ms - 'my story' creates a secure password string which can be memorized with a technique shared by Max.

On 23.12.21 20:22, Stefan Claas wrote: [...] > > Yes, I am aware of that, but how can one memorize a key when traveling > and not taking any devices

Dec 24, 2021
Lightweight, Simple, Quick, Thread-Safe Golang Stack Implementation

stack Lightweight, Simple, Quick, Thread-Safe Golang Stack Implementation Purpose Provide a fast, thread safe, and generic Golang Stack API with minim

May 3, 2022
Sliding window counters Redis rate limiting implementation for Golang

Sliding window counters Redis rate limiting implementation for Golang (Based on the Figma API rate limit algorithm)

Dec 21, 2022
A pure Golang implementation of Rockchip rknand vendor storage interface.

go-rkvendorstorage A pure Golang implementation of Rockchip rknand vendor storage interface. Usage package main import ( "fmt" "github.com/jamesits

Nov 8, 2022