blob: bb533800f84694b120cee56a72540fad0a602799 [file] [log] [blame]
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package trie
import (
"strings"
)
import (
"github.com/pkg/errors"
)
import (
"github.com/apache/dubbo-go-pixiu/pixiu/pkg/common/util/stringutil"
"github.com/apache/dubbo-go-pixiu/pixiu/pkg/logger"
)
// Trie
type Trie struct {
root Node
}
// NewTrie
func NewTrie() Trie {
return Trie{root: Node{endOfPath: false, matchStr: ""}}
}
// NewTrieWithDefault
func NewTrieWithDefault(path string, defVal interface{}) Trie {
ret := Trie{root: Node{endOfPath: false, matchStr: ""}}
_, _ = ret.Put(path, defVal)
return ret
}
// Node
type Node struct {
matchStr string // abc match abc, :a match all words as a variable names a , * match all words ,** match all words and children.
children map[string]*Node // in path /a/b/c , b is child of a , c is child of b
PathVariablesSet map[string]*Node // in path /:a/b/c/:d , :a is a path variable node of level1 , :d is path variable node of level4
PathVariableNode *Node // in path /:a/b/c/:d , /b/c/:d is a child tree of pathVariable node :a ,and some special logic for match pathVariable it better not store in children.
MatchAllNode *Node // /a/b/** /** is a match all Node.
endOfPath bool // if true means a real path exists , /a/b/c/d only node of d is true, a,b,c is false.
bizInfo interface{} // route info and any other info store here.
}
func (trie *Trie) Clear() bool {
return trie.root.Clear()
}
// IsEmpty put key and values into trie as map.
func (trie *Trie) IsEmpty() bool {
return trie.root.IsEmpty()
}
// Put put key and values into trie as map.
func (trie *Trie) Put(withOutHost string, bizInfo interface{}) (bool, error) {
if bizInfo == nil {
return false, errors.Errorf("data to put should not be nil.")
}
parts := stringutil.Split(withOutHost)
return trie.root.internalPut(parts, bizInfo)
}
// Put put key and values into trie as map.
func (trie *Trie) PutOrUpdate(withOutHost string, bizInfo interface{}) (bool, error) {
if bizInfo == nil {
return false, errors.Errorf("data to put should not be nil.")
}
parts := stringutil.Split(withOutHost)
if _, err := trie.Remove(withOutHost); err != nil {
logger.Infof("PutOrUpdate function remote (withOutHost{%s}) = error{%v}", withOutHost, err)
}
//if n != nil {
// //TODO: log n.bizInfo for trouble shooting
//}
return trie.root.internalPut(parts, bizInfo)
}
// Get get values according key.pathVariable not supported.
func (trie Trie) Get(withOutHost string) (*Node, []string, bool, error) {
parts := stringutil.Split(withOutHost)
node, param, ok, e := trie.root.Get(parts)
length := len(param)
for i := 0; i < length/2; i++ {
temp := param[length-1-i]
param[length-1-i] = param[i]
param[i] = temp
}
return node, param, ok, e
}
// Match get values according url , pathVariable supported.
// returns:
// *Node this node in path, if not exists return nil
// []string reversed array of pathVariable value /valA/valB/valC matchs /:aa/:bb/:cc returns array of (valC,valB,valA)
// bool is ok
// error
func (trie Trie) Match(withOutHost string) (*Node, []string, bool) {
withOutHost = strings.Split(withOutHost, "?")[0]
parts := stringutil.Split(withOutHost)
node, param, ok := trie.root.Match(parts)
length := len(param)
for i := 0; i < length/2; i++ {
temp := param[length-1-i]
param[length-1-i] = param[i]
param[i] = temp
}
return node, param, ok
}
// Remove remove key and value from trie. logic delete can't release memory, rebuild if necessary when lake of memory.
func (trie Trie) Remove(withOutHost string) (*Node, error) {
n, _, _, e := trie.Get(withOutHost)
if e != nil {
return nil, e
}
if n != nil {
n.endOfPath = false
}
return n, nil
}
// Contains return if key exists in trie
func (trie Trie) Contains(withOutHost string) (bool, error) {
parts := stringutil.Split(withOutHost)
ret, _, _, e := trie.root.Get(parts)
if e != nil {
return true, e
}
return !(ret == nil), nil
}
// Put node put
func (node *Node) internalPut(keys []string, bizInfo interface{}) (bool, error) {
// empty node initialization
if node.children == nil {
node.children = map[string]*Node{}
}
if len(keys) == 0 {
return true, nil
}
key := keys[0]
// isReal is the end of url path, means node is a place of url end,so the path with parentNode has a real url exists.
isReal := len(keys) == 1
isSuccess := node.put(key, isReal, bizInfo)
if !isSuccess {
return false, nil
}
childKeys := keys[1:]
if stringutil.IsPathVariableOrWildcard(key) {
return node.PathVariableNode.internalPut(childKeys, bizInfo)
} else if stringutil.IsMatchAll(key) {
return isSuccess, nil
} else {
return node.children[key].internalPut(childKeys, bizInfo)
}
}
func (node *Node) Clear() bool {
*node = Node{}
return true
}
// IsEmpty return true if empty
func (node *Node) IsEmpty() bool {
if node.children == nil && node.matchStr == "" && node.PathVariableNode == nil && node.PathVariablesSet == nil {
return true
}
return false
}
// GetBizInfo get info
func (node *Node) GetBizInfo() interface{} {
return node.bizInfo
}
//Match node match
func (node *Node) Match(parts []string) (*Node, []string, bool) {
key := parts[0]
childKeys := parts[1:]
// isEnd is the end of url path, means node is a place of url end,so the path with parentNode has a real url exists.
isEnd := len(childKeys) == 0
if isEnd {
if node.children != nil && node.children[key] != nil && node.children[key].endOfPath {
return node.children[key], []string{}, true
}
//consider trie node :/aaa/bbb/xxxxx/ccc/ddd /aaa/bbb/:id/ccc and request url is :/aaa/bbb/xxxxx/ccc
if node.PathVariableNode != nil {
if node.PathVariableNode.endOfPath {
return node.PathVariableNode, []string{key}, true
}
}
} else {
if node.children != nil && node.children[key] != nil {
n, param, ok := node.children[key].Match(childKeys)
if ok {
return n, param, ok
}
}
if node.PathVariableNode != nil {
n, param, ok := node.PathVariableNode.Match(childKeys)
param = append(param, key)
if ok {
return n, param, ok
}
}
}
if node.children != nil && node.children[key] != nil && node.children[key].MatchAllNode != nil {
return node.children[key].MatchAllNode, []string{}, true
}
if node.MatchAllNode != nil {
return node.MatchAllNode, []string{}, true
}
return nil, nil, false
}
// Get node get
// returns:
// *Node this node in path, if not exists return nil
// []string key reversed array of pathVariable /:aa/:bb/:cc returns array of (cc,bb,aa)
// bool is ok
// error
func (node *Node) Get(keys []string) (*Node, []string, bool, error) {
key := keys[0]
childKeys := keys[1:]
isReal := len(childKeys) == 0
if isReal {
// exit condition
if stringutil.IsPathVariableOrWildcard(key) {
if node.PathVariableNode == nil || !node.PathVariableNode.endOfPath {
return nil, nil, false, nil
}
return node.PathVariableNode, []string{stringutil.VariableName(key)}, true, nil
} else if stringutil.IsMatchAll(key) {
return node.MatchAllNode, nil, true, nil
} else {
if node.children == nil {
return nil, nil, false, nil
}
return node.children[key], nil, true, nil
}
} else {
if stringutil.IsPathVariableOrWildcard(key) {
if node.PathVariableNode == nil {
return nil, nil, false, nil
}
retNode, pathVariableList, ok, e := node.PathVariableNode.Get(childKeys)
newList := []string{key}
copy(newList[1:], pathVariableList)
return retNode, newList, ok, e
} else if stringutil.IsMatchAll(key) {
return nil, nil, false, errors.Errorf("router configuration is empty")
} else {
if node.children == nil || node.children[key] == nil {
return nil, nil, false, nil
}
return node.children[key].Get(childKeys)
}
}
}
func (node *Node) put(key string, isReal bool, bizInfo interface{}) bool {
if !stringutil.IsPathVariableOrWildcard(key) {
if stringutil.IsMatchAll(key) {
return node.putMatchAllNode(key, isReal, bizInfo)
} else {
return node.putNode(key, isReal, bizInfo)
}
}
pathVariable := stringutil.VariableName(key)
return node.putPathVariable(pathVariable, isReal, bizInfo)
}
func (node *Node) putPathVariable(pathVariable string, isReal bool, bizInfo interface{}) bool {
//path variable put
if node.PathVariableNode == nil {
node.PathVariableNode = &Node{endOfPath: false}
}
if node.PathVariableNode.endOfPath && isReal {
//has a node with same path exists. conflicted.
return false
}
if isReal {
node.PathVariableNode.bizInfo = bizInfo
node.PathVariableNode.matchStr = pathVariable
}
node.PathVariableNode.endOfPath = node.PathVariableNode.endOfPath || isReal
if node.PathVariablesSet == nil {
node.PathVariablesSet = map[string]*Node{}
}
node.PathVariablesSet[pathVariable] = node.PathVariableNode
return true
}
func (node *Node) putNode(matchStr string, isReal bool, bizInfo interface{}) bool {
selfNode := &Node{endOfPath: isReal, matchStr: matchStr}
old := node.children[matchStr]
if old != nil {
if old.endOfPath && isReal {
// already has one same path url
return false
}
selfNode = old
} else {
old = selfNode
}
if isReal {
selfNode.bizInfo = bizInfo
}
selfNode.endOfPath = isReal || old.endOfPath
node.children[matchStr] = selfNode
return true
}
func (node *Node) putMatchAllNode(matchStr string, isReal bool, bizInfo interface{}) bool {
selfNode := &Node{endOfPath: isReal, matchStr: matchStr}
old := node.MatchAllNode
if old != nil {
if old.endOfPath && isReal {
// already has one same path url
return false
}
selfNode = old
} else {
old = selfNode
}
if isReal {
selfNode.bizInfo = bizInfo
}
selfNode.endOfPath = selfNode.endOfPath || old.endOfPath
node.MatchAllNode = selfNode
return true
}