1package goja
2
3import (
4	"hash/maphash"
5)
6
7type mapEntry struct {
8	key, value Value
9
10	iterPrev, iterNext *mapEntry
11	hNext              *mapEntry
12}
13
14type orderedMap struct {
15	hash                *maphash.Hash
16	hashTable           map[uint64]*mapEntry
17	iterFirst, iterLast *mapEntry
18	size                int
19}
20
21type orderedMapIter struct {
22	m   *orderedMap
23	cur *mapEntry
24}
25
26func (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
36func (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
61func (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
70func (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		// remove from the doubly-linked list
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		// remove from the hashTable
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
106func (m *orderedMap) has(key Value) bool {
107	_, entry, _ := m.lookup(key)
108	return entry != nil
109}
110
111func (iter *orderedMapIter) next() *mapEntry {
112	if iter.m == nil {
113		// closed iterator
114		return nil
115	}
116
117	cur := iter.cur
118	// if the current item was deleted, track back to find the latest that wasn't
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
138func (iter *orderedMapIter) close() {
139	iter.m = nil
140	iter.cur = nil
141}
142
143func newOrderedMap(h *maphash.Hash) *orderedMap {
144	return &orderedMap{
145		hash:      h,
146		hashTable: make(map[uint64]*mapEntry),
147	}
148}
149
150func (m *orderedMap) newIter() *orderedMapIter {
151	iter := &orderedMapIter{
152		m: m,
153	}
154	return iter
155}
156
157func (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