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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
|
// ================================================================
// ORDERED MAP FROM STRING TO INTERFACE{}
//
// Quite like types.OrderedMap but only with interface{} keys. See orderedMap.go for
// more information.
// ================================================================
package lib
// ----------------------------------------------------------------
type OrderedMap struct {
FieldCount int64
Head *orderedMapEntry
Tail *orderedMapEntry
keysToEntries map[string]*orderedMapEntry
}
type orderedMapEntry struct {
Key string
Value interface{}
Prev *orderedMapEntry
Next *orderedMapEntry
}
// ----------------------------------------------------------------
func NewOrderedMap() *OrderedMap {
return &OrderedMap{
FieldCount: 0,
Head: nil,
Tail: nil,
keysToEntries: make(map[string]*orderedMapEntry),
}
}
// ----------------------------------------------------------------
// Value-copy is up to the caller -- PutReference and PutCopy
// are in the public OrderedMap API.
func newOrderedMapEntry(key *string, value interface{}) *orderedMapEntry {
return &orderedMapEntry{
*key,
value,
nil,
nil,
}
}
// ----------------------------------------------------------------
func (omap *OrderedMap) IsEmpty() bool {
return omap.FieldCount == 0
}
func (omap *OrderedMap) Has(key string) bool {
return omap.findEntry(&key) != nil
}
func (omap *OrderedMap) findEntry(key *string) *orderedMapEntry {
if omap.keysToEntries != nil {
return omap.keysToEntries[*key]
} else {
for pe := omap.Head; pe != nil; pe = pe.Next {
if pe.Key == *key {
return pe
}
}
return nil
}
}
// ----------------------------------------------------------------
func (omap *OrderedMap) Put(key string, value interface{}) {
pe := omap.findEntry(&key)
if pe == nil {
pe = newOrderedMapEntry(&key, value)
if omap.Head == nil {
omap.Head = pe
omap.Tail = pe
} else {
pe.Prev = omap.Tail
pe.Next = nil
omap.Tail.Next = pe
omap.Tail = pe
}
if omap.keysToEntries != nil {
omap.keysToEntries[key] = pe
}
omap.FieldCount++
} else {
pe.Value = value
}
}
// ----------------------------------------------------------------
func (omap *OrderedMap) Get(key string) interface{} {
pe := omap.findEntry(&key)
if pe == nil {
return nil
} else {
return pe.Value
}
}
// The Get is sufficient for pointer values -- the caller can check if the
// return value is nil. For int/string values (which are non-nullable) we have
// this method.
func (omap *OrderedMap) GetWithCheck(key string) (interface{}, bool) {
pe := omap.findEntry(&key)
if pe == nil {
return nil, false
} else {
return pe.Value, true
}
}
func (omap *OrderedMap) GetKeys() []string {
keys := make([]string, omap.FieldCount)
i := 0
for pe := omap.Head; pe != nil; pe = pe.Next {
keys[i] = pe.Key
i++
}
return keys
}
// Returns an array of keys, not including the ones specified. The ones
// specified are to be passed in as a map from string to bool, as Go
// doesn't have hash-sets.
func (omap *OrderedMap) GetKeysExcept(exceptions map[string]bool) []string {
keys := make([]string, 0)
for pe := omap.Head; pe != nil; pe = pe.Next {
if _, present := exceptions[pe.Key]; !present {
keys = append(keys, pe.Key)
}
}
return keys
}
// ----------------------------------------------------------------
func (omap *OrderedMap) Clear() {
omap.FieldCount = 0
omap.Head = nil
omap.Tail = nil
}
// ----------------------------------------------------------------
// Returns true if it was found and removed
func (omap *OrderedMap) Remove(key string) bool {
pe := omap.findEntry(&key)
if pe == nil {
return false
} else {
omap.unlink(pe)
return true
}
}
// ----------------------------------------------------------------
func (omap *OrderedMap) unlink(pe *orderedMapEntry) {
if pe == omap.Head {
if pe == omap.Tail {
omap.Head = nil
omap.Tail = nil
} else {
omap.Head = pe.Next
pe.Next.Prev = nil
}
} else {
pe.Prev.Next = pe.Next
if pe == omap.Tail {
omap.Tail = pe.Prev
} else {
pe.Next.Prev = pe.Prev
}
}
if omap.keysToEntries != nil {
delete(omap.keysToEntries, pe.Key)
}
omap.FieldCount--
}
|
