-
Notifications
You must be signed in to change notification settings - Fork 4
/
map.go
133 lines (121 loc) · 3.65 KB
/
map.go
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
package surge
import (
"reflect"
"sort"
"unsafe"
)
func sizeHintReflectedMap(v reflect.Value) int {
sizeHint := SizeHintU32
iter := v.MapRange()
for iter.Next() {
sizeHint += sizeHintReflected(iter.Key())
sizeHint += sizeHintReflected(iter.Value())
}
return sizeHint
}
func marshalReflectedMap(v reflect.Value, buf []byte, rem int) ([]byte, int, error) {
buf, rem, err := MarshalLen(uint32(v.Len()), buf, rem)
if err != nil {
return buf, rem, err
}
// Define a local key/value type that can be used to sort the key/value
// pairs. It is worth noting, the key is explicitly defined to be bytes, so
// we will need to marshal all keys and then convert those bytes to strings.
// This guarantees that, regardless of the key type, we can sort the keys
// deterministically.
type KeyValue struct {
keyData []byte
key reflect.Value
}
// Allocate a slice for storing the key/value pairs. This is needed so that
// we can then sort the slice, ensuring that the key/value ordering is
// deterministic.
n := v.Len() * int(unsafe.Sizeof(KeyValue{}))
if n < 0 || n < v.Len() {
return buf, rem, ErrLengthOverflow
}
if rem < n {
return buf, rem, ErrUnexpectedEndOfBuffer
}
rem -= n
keyValues := make([]KeyValue, 0, v.Len())
for _, key := range v.MapKeys() {
// Marshal the key into bytes, so that we can guarantee that the keys
// can be compared.
sizeHint := sizeHintReflected(key)
if rem < sizeHint {
return buf, rem, ErrUnexpectedEndOfBuffer
}
rem -= sizeHint
keyValue := KeyValue{
keyData: make([]byte, sizeHint),
key: key,
}
if _, rem, err = marshalReflected(key, keyValue.keyData, rem+sizeHint); err != nil {
return buf, rem, err
}
// Search and insert to ensure that the key/values are always in sorted
// order.
i := sort.Search(len(keyValues), func(i int) bool {
other := keyValues[i]
if len(keyValue.keyData) < len(other.keyData) {
return true
}
if len(keyValue.keyData) > len(other.keyData) {
return false
}
for j := range keyValue.keyData {
if keyValue.keyData[j] < other.keyData[j] {
return true
}
if keyValue.keyData[j] > other.keyData[j] {
return false
}
}
return true
})
keyValues = append(keyValues, KeyValue{})
copy(keyValues[i+1:], keyValues[i:])
keyValues[i] = keyValue
}
for _, keyValue := range keyValues {
// Marshal the key. This is the second time we are doing it, so we do
// not check/decrement rem again. This is the first time we are actually
// writing out to the buffer though, so we do need to check buffer
// lengths.
keyDataLen := len(keyValue.keyData)
if len(buf) < keyDataLen {
return buf, rem, ErrUnexpectedEndOfBuffer
}
copy(buf, keyValue.keyData)
buf = buf[keyDataLen:]
// Marshal the value.
if buf, rem, err = marshalReflected(v.MapIndex(keyValue.key), buf, rem); err != nil {
return buf, rem, err
}
}
return buf, rem, nil
}
func unmarshalReflectedMap(v reflect.Value, buf []byte, rem int) ([]byte, int, error) {
var err error
mapLen := uint32(0)
elem := v.Elem()
size := int(elem.Type().Key().Size() + elem.Type().Elem().Size())
if buf, rem, err = UnmarshalLen(&mapLen, size, buf, rem); err != nil {
return buf, rem, err
}
rem -= int(mapLen) * size
elem.Set(reflect.MakeMapWithSize(elem.Type(), int(mapLen)))
for i := uint32(0); i < mapLen; i++ {
k := reflect.New(elem.Type().Key())
v := reflect.New(elem.Type().Elem())
if buf, rem, err = unmarshalReflected(k, buf, rem); err != nil {
return buf, rem, err
}
if buf, rem, err = unmarshalReflected(v, buf, rem); err != nil {
return buf, rem, err
}
elem.SetMapIndex(reflect.Indirect(k), reflect.Indirect(v))
}
return buf, rem, nil
}