mapiter.go (6103B)
1 /* 2 * Copyright 2021 ByteDance Inc. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package encoder 18 19 import ( 20 "encoding" 21 "reflect" 22 "sync" 23 "unsafe" 24 25 "github.com/bytedance/sonic/internal/native" 26 "github.com/bytedance/sonic/internal/rt" 27 ) 28 29 type _MapPair struct { 30 k string // when the map key is integer, k is pointed to m 31 v unsafe.Pointer 32 m [32]byte 33 } 34 35 type _MapIterator struct { 36 it rt.GoMapIterator // must be the first field 37 kv rt.GoSlice // slice of _MapPair 38 ki int 39 } 40 41 var ( 42 iteratorPool = sync.Pool{} 43 iteratorPair = rt.UnpackType(reflect.TypeOf(_MapPair{})) 44 ) 45 46 func init() { 47 if unsafe.Offsetof(_MapIterator{}.it) != 0 { 48 panic("_MapIterator.it is not the first field") 49 } 50 } 51 52 53 func newIterator() *_MapIterator { 54 if v := iteratorPool.Get(); v == nil { 55 return new(_MapIterator) 56 } else { 57 return resetIterator(v.(*_MapIterator)) 58 } 59 } 60 61 func resetIterator(p *_MapIterator) *_MapIterator { 62 p.ki = 0 63 p.it = rt.GoMapIterator{} 64 p.kv.Len = 0 65 return p 66 } 67 68 func (self *_MapIterator) at(i int) *_MapPair { 69 return (*_MapPair)(unsafe.Pointer(uintptr(self.kv.Ptr) + uintptr(i) * unsafe.Sizeof(_MapPair{}))) 70 } 71 72 func (self *_MapIterator) add() (p *_MapPair) { 73 p = self.at(self.kv.Len) 74 self.kv.Len++ 75 return 76 } 77 78 func (self *_MapIterator) data() (p []_MapPair) { 79 *(*rt.GoSlice)(unsafe.Pointer(&p)) = self.kv 80 return 81 } 82 83 func (self *_MapIterator) append(t *rt.GoType, k unsafe.Pointer, v unsafe.Pointer) (err error) { 84 p := self.add() 85 p.v = v 86 87 /* check for strings */ 88 if tk := t.Kind(); tk != reflect.String { 89 return self.appendGeneric(p, t, tk, k) 90 } 91 92 /* fast path for strings */ 93 p.k = *(*string)(k) 94 return nil 95 } 96 97 func (self *_MapIterator) appendGeneric(p *_MapPair, t *rt.GoType, v reflect.Kind, k unsafe.Pointer) error { 98 switch v { 99 case reflect.Int : p.k = rt.Mem2Str(p.m[:native.I64toa(&p.m[0], int64(*(*int)(k)))]) ; return nil 100 case reflect.Int8 : p.k = rt.Mem2Str(p.m[:native.I64toa(&p.m[0], int64(*(*int8)(k)))]) ; return nil 101 case reflect.Int16 : p.k = rt.Mem2Str(p.m[:native.I64toa(&p.m[0], int64(*(*int16)(k)))]) ; return nil 102 case reflect.Int32 : p.k = rt.Mem2Str(p.m[:native.I64toa(&p.m[0], int64(*(*int32)(k)))]) ; return nil 103 case reflect.Int64 : p.k = rt.Mem2Str(p.m[:native.I64toa(&p.m[0], *(*int64)(k))]) ; return nil 104 case reflect.Uint : p.k = rt.Mem2Str(p.m[:native.U64toa(&p.m[0], uint64(*(*uint)(k)))]) ; return nil 105 case reflect.Uint8 : p.k = rt.Mem2Str(p.m[:native.U64toa(&p.m[0], uint64(*(*uint8)(k)))]) ; return nil 106 case reflect.Uint16 : p.k = rt.Mem2Str(p.m[:native.U64toa(&p.m[0], uint64(*(*uint16)(k)))]) ; return nil 107 case reflect.Uint32 : p.k = rt.Mem2Str(p.m[:native.U64toa(&p.m[0], uint64(*(*uint32)(k)))]) ; return nil 108 case reflect.Uint64 : p.k = rt.Mem2Str(p.m[:native.U64toa(&p.m[0], *(*uint64)(k))]) ; return nil 109 case reflect.Uintptr : p.k = rt.Mem2Str(p.m[:native.U64toa(&p.m[0], uint64(*(*uintptr)(k)))]) ; return nil 110 case reflect.Interface : return self.appendInterface(p, t, k) 111 case reflect.Struct, reflect.Ptr : return self.appendConcrete(p, t, k) 112 default : panic("unexpected map key type") 113 } 114 } 115 116 func (self *_MapIterator) appendConcrete(p *_MapPair, t *rt.GoType, k unsafe.Pointer) (err error) { 117 // compiler has already checked that the type implements the encoding.MarshalText interface 118 if !t.Indirect() { 119 k = *(*unsafe.Pointer)(k) 120 } 121 eface := rt.GoEface{Value: k, Type: t}.Pack() 122 out, err := eface.(encoding.TextMarshaler).MarshalText() 123 if err != nil { 124 return err 125 } 126 p.k = rt.Mem2Str(out) 127 return 128 } 129 130 func (self *_MapIterator) appendInterface(p *_MapPair, t *rt.GoType, k unsafe.Pointer) (err error) { 131 if len(rt.IfaceType(t).Methods) == 0 { 132 panic("unexpected map key type") 133 } else if p.k, err = asText(k); err == nil { 134 return nil 135 } else { 136 return 137 } 138 } 139 140 func iteratorStop(p *_MapIterator) { 141 iteratorPool.Put(p) 142 } 143 144 func iteratorNext(p *_MapIterator) { 145 i := p.ki 146 t := &p.it 147 148 /* check for unordered iteration */ 149 if i < 0 { 150 mapiternext(t) 151 return 152 } 153 154 /* check for end of iteration */ 155 if p.ki >= p.kv.Len { 156 t.K = nil 157 t.V = nil 158 return 159 } 160 161 /* update the key-value pair, and increase the pointer */ 162 t.K = unsafe.Pointer(&p.at(p.ki).k) 163 t.V = p.at(p.ki).v 164 p.ki++ 165 } 166 167 func iteratorStart(t *rt.GoMapType, m *rt.GoMap, fv uint64) (*_MapIterator, error) { 168 it := newIterator() 169 mapiterinit(t, m, &it.it) 170 171 /* check for key-sorting, empty map don't need sorting */ 172 if m.Count == 0 || (fv & uint64(SortMapKeys)) == 0 { 173 it.ki = -1 174 return it, nil 175 } 176 177 /* pre-allocate space if needed */ 178 if m.Count > it.kv.Cap { 179 it.kv = growslice(iteratorPair, it.kv, m.Count) 180 } 181 182 /* dump all the key-value pairs */ 183 for ; it.it.K != nil; mapiternext(&it.it) { 184 if err := it.append(t.Key, it.it.K, it.it.V); err != nil { 185 iteratorStop(it) 186 return nil, err 187 } 188 } 189 190 /* sort the keys, map with only 1 item don't need sorting */ 191 if it.ki = 1; m.Count > 1 { 192 radixQsort(it.data(), 0, maxDepth(it.kv.Len)) 193 } 194 195 /* load the first pair into iterator */ 196 it.it.V = it.at(0).v 197 it.it.K = unsafe.Pointer(&it.at(0).k) 198 return it, nil 199 }