1 files changed, 75 insertions, 14 deletions

diff --git a/vendor/github.com/bytedance/sonic/ast/buffer.go b/vendor/github.com/bytedance/sonic/ast/buffer.go
index bccbf4814..04701ef5b 100644
--- a/vendor/github.com/bytedance/sonic/ast/buffer.go
+++ b/vendor/github.com/bytedance/sonic/ast/buffer.go
@@ -17,8 +17,10 @@
 package ast
 
 import (
-    `sort`
-    `unsafe`
+	"sort"
+	"unsafe"
+
+	"github.com/bytedance/sonic/internal/caching"
 )
 
 type nodeChunk [_DEFAULT_NODE_CAP]Node
@@ -90,18 +92,11 @@ func (self *linkedNodes) Pop() {
     self.size--
 }
 
-func (self *linkedPairs) Pop() {
-    if self == nil || self.size == 0 {
-        return
-    }
-    self.Set(self.size-1, Pair{})
-    self.size--
-}
-
 func (self *linkedNodes) Push(v Node) {
     self.Set(self.size, v)
 }
 
+
 func (self *linkedNodes) Set(i int, v Node) {
     if i < _DEFAULT_NODE_CAP {
         self.head[i] = v
@@ -195,11 +190,22 @@ func (self *linkedNodes) FromSlice(con []Node) {
 type pairChunk [_DEFAULT_NODE_CAP]Pair
 
 type linkedPairs struct {
+    index map[uint64]int
     head pairChunk
     tail []*pairChunk
     size int
 }
 
+func (self *linkedPairs) BuildIndex() {
+    if self.index == nil {
+        self.index = make(map[uint64]int, self.size)
+    }
+    for i:=0; i<self.size; i++ {
+        p := self.At(i)
+        self.index[p.hash] = i
+    }
+}
+
 func (self *linkedPairs) Cap() int {
     if self == nil {
         return 0
@@ -233,7 +239,31 @@ func (self *linkedPairs) Push(v Pair) {
     self.Set(self.size, v)
 }
 
+func (self *linkedPairs) Pop() {
+    if self == nil || self.size == 0 {
+        return
+    }
+    self.Unset(self.size-1)
+    self.size--
+}
+
+func (self *linkedPairs) Unset(i int) {
+    if self.index != nil {
+        p := self.At(i)
+        delete(self.index, p.hash)
+    }
+    self.set(i, Pair{}) 
+}
+
 func (self *linkedPairs) Set(i int, v Pair) {
+    if self.index != nil {
+        h := v.hash
+        self.index[h] = i
+    }
+    self.set(i, v)
+}
+
+func (self *linkedPairs) set(i int, v Pair) {
     if i < _DEFAULT_NODE_CAP {
         self.head[i] = v
         if self.size <= i {
@@ -276,6 +306,21 @@ func (self *linkedPairs) growTailLength(l int) {
 
 // linear search
 func (self *linkedPairs) Get(key string) (*Pair, int) {
+    if self.index != nil {
+        // fast-path
+        i, ok := self.index[caching.StrHash(key)]
+        if ok {
+            n := self.At(i)
+            if n.Key == key {
+                return n, i
+            }
+            // hash conflicts
+            goto linear_search
+        } else {
+            return nil, -1
+        }
+    }
+linear_search:
     for i:=0; i<self.size; i++ {
         if n := self.At(i); n.Key == key {
             return n, i
@@ -313,15 +358,27 @@ func (self *linkedPairs) ToMap(con map[string]Node) {
     }
 }
 
+func (self *linkedPairs) copyPairs(to []Pair, from []Pair, l int) {
+    copy(to, from)
+    if self.index != nil {
+        for i:=0; i<l; i++ {
+            // NOTICE: in case of user not pass hash, just cal it
+            h := caching.StrHash(from[i].Key)
+            from[i].hash = h
+            self.index[h] = i
+        }
+    }
+}
+
 func (self *linkedPairs) FromSlice(con []Pair) {
     self.size = len(con)
     i := self.size-1
     a, b := i/_DEFAULT_NODE_CAP-1, i%_DEFAULT_NODE_CAP
     if a < 0 {
-        copy(self.head[:b+1], con)
+        self.copyPairs(self.head[:b+1], con, b+1)
         return
     } else {
-        copy(self.head[:], con)
+        self.copyPairs(self.head[:], con, len(self.head))
         con = con[_DEFAULT_NODE_CAP:]
     }
 
@@ -333,12 +390,12 @@ func (self *linkedPairs) FromSlice(con []Pair) {
 
     for i:=0; i<a; i++ {
         self.tail[i] = new(pairChunk)
-        copy(self.tail[i][:], con)
+        self.copyPairs(self.tail[i][:], con, len(self.tail[i]))
         con = con[_DEFAULT_NODE_CAP:]
     }
 
     self.tail[a] = new(pairChunk)
-    copy(self.tail[a][:b+1], con)
+    self.copyPairs(self.tail[a][:b+1], con, b+1)
 }
 
 func (self *linkedPairs) Less(i, j int) bool {
@@ -347,6 +404,10 @@ func (self *linkedPairs) Less(i, j int) bool {
 
 func (self *linkedPairs) Swap(i, j int) {
     a, b := self.At(i), self.At(j)
+    if self.index != nil {
+        self.index[a.hash] = j
+        self.index[b.hash] = i
+    }
     *a, *b = *b, *a
 }