1 package goja
2
3 import (
4 "hash/maphash"
5 )
6
7 type mapEntry struct {
8 key, value Value
9
10 iterPrev, iterNext *mapEntry
11 hNext *mapEntry
12 }
13
14 type orderedMap struct {
15 hash *maphash.Hash
16 hashTable map[uint64]*mapEntry
17 iterFirst, iterLast *mapEntry
18 size int
19 }
20
21 type orderedMapIter struct {
22 m *orderedMap
23 cur *mapEntry
24 }
25
26 func (m *orderedMap) lookup(key Value) (h uint64, entry, hPrev *mapEntry) {
27 if key == _negativeZero {
28 key = intToValue(0)
29 }
30 h = key.hash(m.hash)
31 for entry = m.hashTable[h]; entry != nil && !entry.key.SameAs(key); hPrev, entry = entry, entry.hNext {
32 }
33 return
34 }
35
36 func (m *orderedMap) set(key, value Value) {
37 h, entry, hPrev := m.lookup(key)
38 if entry != nil {
39 entry.value = value
40 } else {
41 if key == _negativeZero {
42 key = intToValue(0)
43 }
44 entry = &mapEntry{key: key, value: value}
45 if hPrev == nil {
46 m.hashTable[h] = entry
47 } else {
48 hPrev.hNext = entry
49 }
50 if m.iterLast != nil {
51 entry.iterPrev = m.iterLast
52 m.iterLast.iterNext = entry
53 } else {
54 m.iterFirst = entry
55 }
56 m.iterLast = entry
57 m.size++
58 }
59 }
60
61 func (m *orderedMap) get(key Value) Value {
62 _, entry, _ := m.lookup(key)
63 if entry != nil {
64 return entry.value
65 }
66
67 return nil
68 }
69
70 func (m *orderedMap) remove(key Value) bool {
71 h, entry, hPrev := m.lookup(key)
72 if entry != nil {
73 entry.key = nil
74 entry.value = nil
75
76
77 if entry.iterPrev != nil {
78 entry.iterPrev.iterNext = entry.iterNext
79 } else {
80 m.iterFirst = entry.iterNext
81 }
82 if entry.iterNext != nil {
83 entry.iterNext.iterPrev = entry.iterPrev
84 } else {
85 m.iterLast = entry.iterPrev
86 }
87
88
89 if hPrev == nil {
90 if entry.hNext == nil {
91 delete(m.hashTable, h)
92 } else {
93 m.hashTable[h] = entry.hNext
94 }
95 } else {
96 hPrev.hNext = entry.hNext
97 }
98
99 m.size--
100 return true
101 }
102
103 return false
104 }
105
106 func (m *orderedMap) has(key Value) bool {
107 _, entry, _ := m.lookup(key)
108 return entry != nil
109 }
110
111 func (iter *orderedMapIter) next() *mapEntry {
112 if iter.m == nil {
113
114 return nil
115 }
116
117 cur := iter.cur
118
119 for cur != nil && cur.key == nil {
120 cur = cur.iterPrev
121 }
122
123 if cur != nil {
124 cur = cur.iterNext
125 } else {
126 cur = iter.m.iterFirst
127 }
128
129 if cur == nil {
130 iter.close()
131 } else {
132 iter.cur = cur
133 }
134
135 return cur
136 }
137
138 func (iter *orderedMapIter) close() {
139 iter.m = nil
140 iter.cur = nil
141 }
142
143 func newOrderedMap(h *maphash.Hash) *orderedMap {
144 return &orderedMap{
145 hash: h,
146 hashTable: make(map[uint64]*mapEntry),
147 }
148 }
149
150 func (m *orderedMap) newIter() *orderedMapIter {
151 iter := &orderedMapIter{
152 m: m,
153 }
154 return iter
155 }
156
157 func (m *orderedMap) clear() {
158 for item := m.iterFirst; item != nil; item = item.iterNext {
159 item.key = nil
160 item.value = nil
161 if item.iterPrev != nil {
162 item.iterPrev.iterNext = nil
163 }
164 }
165 m.iterFirst = nil
166 m.iterLast = nil
167 m.hashTable = make(map[uint64]*mapEntry)
168 m.size = 0
169 }
170
View as plain text