Daily-Note 09-18

// -- main.go -- //
engine := gin.Default()
engine.GET("/test/abc")

// -- routergroup.go -- //
// GET is a shortcut for router.Handle("GET", path, handle).
func (group *RouterGroup) GET(relativePath string, handlers ...HandlerFunc) IRoutes {
	return group.handle(http.MethodGet, relativePath, handlers)
}

func (group *RouterGroup) handle(httpMethod, relativePath string, handlers HandlersChain) IRoutes {
 absolutePath := group.calculateAbsolutePath(relativePath)
 handlers = group.combineHandlers(handlers)
 group.engine.addRoute(httpMethod, absolutePath, handlers)
 return group.returnObj()
}

// -- gin.go -- //
func (engine *Engine) addRoute(method, path string, handlers HandlersChain) {
	// ... 
	root := engine.trees.get(method)
	if root == nil {
		root = new(node)
		root.fullPath = "/"
		engine.trees = append(engine.trees, methodTree{method: method, root: root})
	}
	root.addRoute(path, handlers)
	// ...
}

// -- tree.go -- //
// addRoute adds a node with the given handle to the path.
// Not concurrency-safe!
func (n *node) addRoute(path string, handlers HandlersChain) {
 fullPath := path
 n.priority++

 // Empty tree
 if len(n.path) == 0 && len(n.children) == 0 {
  n.insertChild(path, fullPath, handlers)
  n.nType = root
  return
 }

 parentFullPathIndex := 0

walk:
 for {
  // Find the longest common prefix.
  // This also implies that the common prefix contains no ':' or '*'
  // since the existing key can't contain those chars.
  i := longestCommonPrefix(path, n.path)

  // Split edge
  if i < len(n.path) {
   child := node{
    path:      n.path[i:],
    wildChild: n.wildChild,
    indices:   n.indices,
    children:  n.children,
    handlers:  n.handlers,
    priority:  n.priority - 1,
    fullPath:  n.fullPath,
   }

   n.children = []*node{&child}
   // []byte for proper unicode char conversion, see #65
   n.indices = bytesconv.BytesToString([]byte{n.path[i]})
   n.path = path[:i]
   n.handlers = nil
   n.wildChild = false
   n.fullPath = fullPath[:parentFullPathIndex+i]
  }

  // Make new node a child of this node
  if i < len(path) {
   path = path[i:]
   c := path[0]

   // '/' after param
   if n.nType == param && c == '/' && len(n.children) == 1 {
    parentFullPathIndex += len(n.path)
    n = n.children[0]
    n.priority++
    continue walk
   }

   // Check if a child with the next path byte exists
   for i, max := 0, len(n.indices); i < max; i++ {
    if c == n.indices[i] {
     parentFullPathIndex += len(n.path)
     i = n.incrementChildPrio(i)
     n = n.children[i]
     continue walk
    }
   }

   // Otherwise insert it
   if c != ':' && c != '*' && n.nType != catchAll {
    // []byte for proper unicode char conversion, see #65
    n.indices += bytesconv.BytesToString([]byte{c})
    child := &node{
     fullPath: fullPath,
    }
    n.addChild(child)
    n.incrementChildPrio(len(n.indices) - 1)
    n = child
   } else if n.wildChild {
    // inserting a wildcard node, need to check if it conflicts with the existing wildcard
    n = n.children[len(n.children)-1]
    n.priority++

    // Check if the wildcard matches
    if len(path) >= len(n.path) && n.path == path[:len(n.path)] &&
     // Adding a child to a catchAll is not possible
     n.nType != catchAll &&
     // Check for longer wildcard, e.g. :name and :names
     (len(n.path) >= len(path) || path[len(n.path)] == '/') {
     continue walk
    }

    // Wildcard conflict
    pathSeg := path
    if n.nType != catchAll {
     pathSeg = strings.SplitN(pathSeg, "/", 2)[0]
    }
    prefix := fullPath[:strings.Index(fullPath, pathSeg)] + n.path
    panic("'" + pathSeg +
     "' in new path '" + fullPath +
     "' conflicts with existing wildcard '" + n.path +
     "' in existing prefix '" + prefix +
     "'")
   }

   n.insertChild(path, fullPath, handlers)
   return
  }

  // Otherwise add handle to current node
  if n.handlers != nil {
   panic("handlers are already registered for path '" + fullPath + "'")
  }
  n.handlers = handlers
  n.fullPath = fullPath
  return
 }
}

type node struct {
	path      string // 当前自身路径
	indices   string // 子节点路由首字母 list
	wildChild bool // 
	nType     nodeType
	priority  uint32 // 优先级
	children  []*node // child nodes, at most 1 :param style node at the end of the array
	handlers  HandlersChain // 处理链
	fullPath  string // 完整路径
}

// addRoute adds a node with the given handle to the path.
// Not concurrency-safe!
func (n *node) addRoute(path string, // 绝对路径
                        handlers HandlersChain //需要注册到目标路径的处理器链
                       ) {
  fullPath := path // 存储绝对路径，path 在后续流程中改变
  n.priority++ // 提升当前节点的优先级，每当有一个路由注册到目标节点下，提升优先级
  // Empty tree 空树的情况
  if len(n.path) == 0 && len(n.children) == 0 {
   // 该方法在不考虑 wildcards 的情况下，直接将对应参数赋值给节点 n
   n.insertChild(path, fullPath, handlers) 
   n.nType = root
   return // 完成注册
  }
}

// -- main.go -- //
func main() {
	engine := gin.Default()
	engine.GET("/test/abc")
	engine.GET("/test/def")
}

// -- tree.go -- //
	// ...

  // Find the longest common prefix.
  // This also implies that the common prefix contains no ':' or '*'
  // since the existing key can't contain those chars.
  i := longestCommonPrefix(path, n.path) // 得到最长公共前缀的结束位置

  // Split edge
  if i < len(n.path) { // 这里判断公共前缀是否比自身路径短，如果更短则需要分裂
    child := node{ // 这里将自身节点分裂
      path:      n.path[i:],  // "abc"
      wildChild: n.wildChild,
      indices:   n.indices,
      children:  n.children,
      handlers:  n.handlers,
      priority:  n.priority - 1,
      fullPath:  n.fullPath,
    }

    n.children = []*node{&child}
    // []byte for proper unicode char conversion, see #65
    n.indices = bytesconv.BytesToString([]byte{n.path[i]})
    n.path = path[:i] // "/test/"
    n.handlers = nil // 释放引用
    n.wildChild = false
    n.fullPath = fullPath[:parentFullPathIndex+i]
  }

	if i < len(path) { // 在迭代判断剩余的路径是否需要插入新的节点
    path = path[i:]
    c := path[0]
    
    // ... 这里判断 wildcards 情况
    // ... 这里判断当前节点的子节点与目标路径有公共前缀
    
    // Otherwise insert it
			if c != ':' && c != '*' && n.nType != catchAll {
				// []byte for proper unicode char conversion, see #65
				n.indices += bytesconv.BytesToString([]byte{c})
				child := &node{
					fullPath: fullPath,
				}
				n.addChild(child) // 在这里插入目标路径
				n.incrementChildPrio(len(n.indices) - 1)
				n = child
  // ... 这里判断 wildcards 情况
  n.insertChild(path, fullPath, handlers)
  return

// -- tree.go -- //
// ...
// ... 这里判断当前节点的子节点与目标路径有公共前缀
// Check if a child with the next path byte exists
for i, max := 0, len(n.indices); i < max; i++ {
 if c == n.indices[i] {
  parentFullPathIndex += len(n.path)  // 公共前缀 "/test/"
  i = n.incrementChildPrio(i) // 提升子节点的优先级
  n = n.children[i] // 切换到子节点
  continue walk // 继续迭代
 }
}
// ...

// incrementChildPrio 提升子节点优先级
func (n *node) incrementChildPrio(pos int) int {
	cs := n.children
	cs[pos].priority++
	prio := cs[pos].priority

	// Adjust position (move to front)
	newPos := pos
	for ; newPos > 0 && cs[newPos-1].priority < prio; newPos-- {
		// Swap node positions
		cs[newPos-1], cs[newPos] = cs[newPos], cs[newPos-1]
	}

	// Build new index char string
	if newPos != pos {
		n.indices = n.indices[:newPos] + // Unchanged prefix, might be empty
			n.indices[pos:pos+1] + // The index char we move
			n.indices[newPos:pos] + n.indices[pos+1:] // Rest without char at 'pos'
	}

	return newPos
}

engine.GET("/test/:a/ok")
engine.GET("/test/*b")
engine.GET("/test/*b/err") // err

func (n *node) insertChild(path string, fullPath string, handlers HandlersChain) {
	for {
		// Find prefix until first wildcard
		wildcard, i, valid := findWildcard(path)
		if i < 0 { // No wildcard found
			break
		}

    // ... 判断通配符是否符合要求，具有名字并且只有一个 : 或 *

		if wildcard[0] == ':' { // param
			if i > 0 {
				// Insert prefix before the current wildcard
				n.path = path[:i]
				path = path[i:]
			}

			child := &node{
				nType:    param,
				path:     wildcard,
				fullPath: fullPath,
			}
			n.addChild(child)
			n.wildChild = true
			n = child
			n.priority++

			// if the path doesn't end with the wildcard, then there
			// will be another subpath starting with '/'
			if len(wildcard) < len(path) {
				path = path[len(wildcard):]

				child := &node{
					priority: 1,
					fullPath: fullPath,
				}
				n.addChild(child)
				n = child
				continue
			}

			// Otherwise we're done. Insert the handle in the new leaf
			n.handlers = handlers
			return
		}

		// 判断 * 通配符是否为最后位置

		// currently fixed width 1 for '/'
		i--
		if path[i] != '/' {
			panic("no / before catch-all in path '" + fullPath + "'")
		}

		n.path = path[:i]

		// First node: catchAll node with empty path
		child := &node{
			wildChild: true,
			nType:     catchAll,
			fullPath:  fullPath,
		}

		n.addChild(child)
		n.indices = string('/')
		n = child
		n.priority++

		// second node: node holding the variable
		child = &node{
			path:     path[i:],
			nType:    catchAll,
			handlers: handlers,
			priority: 1,
			fullPath: fullPath,
		}
		n.children = []*node{child}

		return
	}

	// If no wildcard was found, simply insert the path and handle
	n.path = path
	n.handlers = handlers
	n.fullPath = fullPath
}

// -- main.go -- //
package main

import "github.com/gin-gonic/gin"

func main() {
	engine := gin.Default()
	engine.GET("/test")
	engine.GET("/test/:ok2")
}

// -- tree.go -- //
// Otherwise insert it
// ...
if c != ':' && c != '*' && n.nType != catchAll {
  // []byte for proper unicode char conversion, see #65
  n.indices += bytesconv.BytesToString([]byte{c})
  child := &node{
    fullPath: fullPath,
  }
  n.addChild(child)
  n.incrementChildPrio(len(n.indices) - 1)
  n = child

  // ...
}
n.insertChild(path, fullPath, handlers)
return
// ...

package main

import "github.com/gin-gonic/gin"

func main() {
	engine := gin.Default()
	engine.GET("/test")
	engine.GET("/test/:ok")
	engine.GET("/test/:ok/ok2")
}

// Check if a child with the next path byte exists
for i, max := 0, len(n.indices); i < max; i++ {
  if c == n.indices[i] {
    parentFullPathIndex += len(n.path)
    i = n.incrementChildPrio(i)
    n = n.children[i]
    continue walk
  }
}

	// Otherwise insert it
if c != ':' && c != '*' && n.nType != catchAll {
 // ...
} else if n.wildChild {
  // inserting a wildcard node, need to check if it conflicts with the existing wildcard
  n = n.children[len(n.children)-1]
  n.priority++

  // Check if the wildcard matches
  if len(path) >= len(n.path) && n.path == path[:len(n.path)] &&
  // Adding a child to a catchAll is not possible
  n.nType != catchAll &&
  // Check for longer wildcard, e.g. :name and :names
  (len(n.path) >= len(path) || path[len(n.path)] == '/') {
    continue walk
  }

  // Wildcard conflict
  pathSeg := path
  if n.nType != catchAll {
    pathSeg = strings.SplitN(pathSeg, "/", 2)[0]
  }
  prefix := fullPath[:strings.Index(fullPath, pathSeg)] + n.path
  panic("'" + pathSeg +
        "' in new path '" + fullPath +
        "' conflicts with existing wildcard '" + n.path +
        "' in existing prefix '" + prefix +
        "'")
}

package main

import "github.com/gin-gonic/gin"

func main() {
	engine := gin.Default()
	engine.GET("/test")
	engine.GET("/test/:ok")
	engine.GET("/test/:ok/ok2")
	engine.GET("/test/:ok/ko2")
}

// ...
// '/' after param
// 发现当前节点为 param 且已经存在子路径，移动到子路径对应节点上进行插入。
if n.nType == param && c == '/' && len(n.children) == 1 {
  parentFullPathIndex += len(n.path)
  n = n.children[0]
  n.priority++
  continue walk
}
// ...

// ServeHTTP conforms to the http.Handler interface.
func (engine *Engine) ServeHTTP(w http.ResponseWriter, req *http.Request) {
	c := engine.pool.Get().(*Context) // get
	c.writermem.reset(w)
	c.Request = req
	c.reset() // clean !!!

	engine.handleHTTPRequest(c)

	engine.pool.Put(c) // put
}

type Mutex struct {
 state int32
 sema  uint32
}

mutexLocked = 1 << iota // mutex is locked 1 表示锁已经上锁
mutexWoken // 1 表示当前的锁已被唤醒
mutexStarving // 1 表示当前的锁处于饥饿状态
mutexWaiterShift = iota // 3 代表等待该锁的 goroutine 数量，占3 至 31 位

func (o *Once) Do(f func()) {
 // Note: Here is an incorrect implementation of Do:
 //
 // if atomic.CompareAndSwapUint32(&o.done, 0, 1) {
 //  f()
 // }
 //
 // Do guarantees that when it returns, f has finished.
 // This implementation would not implement that guarantee:
 // given two simultaneous calls, the winner of the cas would
 // call f, and the second would return immediately, without
 // waiting for the first's call to f to complete.
 // This is why the slow path falls back to a mutex, and why
 // the atomic.StoreUint32 must be delayed until after f returns.

 if atomic.LoadUint32(&o.done) == 0 {
  // Outlined slow-path to allow inlining of the fast-path.
  o.doSlow(f)
 }
}

func (o *Once) doSlow(f func()) {
 o.m.Lock()
 defer o.m.Unlock()
 if o.done == 0 {
  defer atomic.StoreUint32(&o.done, 1)
  f()
 }
}

type WaitGroup struct {
 noCopy noCopy

 // 64-bit value: high 32 bits are counter, low 32 bits are waiter count.
 // 64-bit atomic operations require 64-bit alignment, but 32-bit
 // compilers only guarantee that 64-bit fields are 32-bit aligned.
 // For this reason on 32 bit architectures we need to check in state()
 // if state1 is aligned or not, and dynamically "swap" the field order if
 // needed.
 state1 uint64 // 高 32 位存储 counter 数目，低 32 位存储 waiter 数目。
 state2 uint32
}

// Done decrements the WaitGroup counter by one.
func (wg *WaitGroup) Done() {
 wg.Add(-1)
}

func (wg *WaitGroup) Add(delta int) {
 statep, semap := wg.state()
 state := atomic.AddUint64(statep, uint64(delta)<<32)
 v := int32(state >> 32)
 w := uint32(state)
 // 如果 v(counter) 大于零并且 w(waiter) 等于零
 // 说明阻塞的 goroutine，此时直接返回
 if v > 0 || w == 0 { 
   return  
 }
 // counter 等于零此时，需要唤醒所有阻塞的 goroutine
 // Reset waiters count to 0.
 *statep = 0
  // 唤醒所有阻塞的 goroutine
 for ; w != 0; w-- {
  runtime_Semrelease(semap, false, 0)
 }
}

func (wg *WaitGroup) Wait() {
 statep, semap := wg.state()
 for {
  state := atomic.LoadUint64(statep)
  v := int32(state >> 32)
  w := uint32(state)
  if v == 0 {
   // Counter is 0, no need to wait.
   return
  }
  // Increment waiters count.
  if atomic.CompareAndSwapUint64(statep, state, state+1) {
   runtime_Semacquire(semap)
   return
 	}
}

type Map struct {
    mu sync.Mutex
    read atomic.Value
    dirty map[interface{}]*entry
    misses int
}

func (m *Map) Load(key any) (value any, ok bool) {
 read, _ := m.read.Load().(readOnly)
 e, ok := read.m[key] // 从只读部分读取数据
 if !ok && read.amended { // 如果没有命中，从 dirty 部分读取数据
  m.mu.Lock()  // 此时读取 dirty 数据需要进行加锁
  // Avoid reporting a spurious miss if m.dirty got promoted while we were
  // blocked on m.mu. (If further loads of the same key will not miss, it's
  // not worth copying the dirty map for this key.)
  read, _ = m.read.Load().(readOnly)
  e, ok = read.m[key]
  // 进行双重检查，可能在加锁之前 dirty 提升为 reed，而被初始化为 nil
  if !ok && read.amended { 
   e, ok = m.dirty[key]
   // Regardless of whether the entry was present, record a miss: this key
   // will take the slow path until the dirty map is promoted to the read
   // map.
   // 检查是否需要进行提升，每次没有在 read 中命中，都会提升 missed 值
    // 当 missed > len(dirty) 时，会发生提升
   m.missLocked() 
  }
  m.mu.Unlock()
 }
 if !ok {
  return nil, false
 }
 return e.load()
}

func (m *Map) Store(key, value any) {
 read, _ := m.read.Load().(readOnly)
 // 如果 read 中存在值，尝试通过 CAS 更新值
 if e, ok := read.m[key]; ok && e.tryStore(&value) {
  return
 }

 m.mu.Lock()
 read, _ = m.read.Load().(readOnly)
 if e, ok := read.m[key]; ok { 
  if e.unexpungeLocked() {
   // The entry was previously expunged, which implies that there is a
   // non-nil dirty map and this entry is not in it.
   m.dirty[key] = e
  }
  e.storeLocked(&value)
  // 插入值并在 read 但在 dirty 中，更新 dirty
 } else if e, ok := m.dirty[key]; ok { 
  e.storeLocked(&value)
 } else { // 插入新值
  if !read.amended {  // 如果 dirty 中没有数据
   // We're adding the first new key to the dirty map.
   // Make sure it is allocated and mark the read-only map as incomplete.
   m.dirtyLocked()
   m.read.Store(readOnly{m: read.m, amended: true})
  }
  m.dirty[key] = newEntry(value)
 }
 m.mu.Unlock()
}

// List represents a doubly linked list.
// The zero value for List is an empty list ready to use.
type List struct {
 root Element // sentinel list element, only &root, root.prev, and root.next are used
 len  int     // current list length excluding (this) sentinel element
}

// Element is an element of a linked list.
type Element struct {
 // Next and previous pointers in the doubly-linked list of elements.
 // To simplify the implementation, internally a list l is implemented
 // as a ring, such that &l.root is both the next element of the last
 // list element (l.Back()) and the previous element of the first list
 // element (l.Front()).
 next, prev *Element

 // The list to which this element belongs.
 list *List

 // The value stored with this element.
 Value any
}

// insert inserts e after at, increments l.len, and returns e.
func (l *List) insert(e, at *Element) *Element {
 e.prev = at
 e.next = at.next
 e.prev.next = e
 e.next.prev = e
 e.list = l
 l.len++
 return e
}

// remove removes e from its list, decrements l.len
func (l *List) remove(e *Element) {
 e.prev.next = e.next
 e.next.prev = e.prev
 e.next = nil // avoid memory leaks
 e.prev = nil // avoid memory leaks
 e.list = nil
 l.len--
}

// move moves e to next to at.
func (l *List) move(e, at *Element) {
 if e == at {
  return
 }
 e.prev.next = e.next
 e.next.prev = e.prev

 e.prev = at
 e.next = at.next
 e.prev.next = e
 e.next.prev = e
}

// A Ring is an element of a circular list, or ring.
// Rings do not have a beginning or end; a pointer to any ring element
// serves as reference to the entire ring. Empty rings are represented
// as nil Ring pointers. The zero value for a Ring is a one-element
// ring with a nil Value.
type Ring struct {
 next, prev *Ring
 Value      any // for use by client; untouched by this library
}

// New creates a ring of n elements.
func New(n int) *Ring {
 if n <= 0 {
  return nil
 }
 r := new(Ring)
 p := r
 for i := 1; i < n; i++ {
  p.next = &Ring{prev: p}
  p = p.next
 }
 p.next = r
 r.prev = p
 return r
}

func (r *Ring) Link(s *Ring) *Ring {
 n := r.Next()
 if s != nil {
  p := s.Prev()
  // Note: Cannot use multiple assignment because
  // evaluation order of LHS is not specified.
  r.next = s
  s.prev = r
  n.prev = p
  p.next = n
 }
 return n
}

// Next returns the next ring element. r must not be empty.
func (r *Ring) Next() *Ring {
 if r.next == nil {
  return r.init()
 }
 return r.next
}

// Prev returns the previous ring element. r must not be empty.
func (r *Ring) Prev() *Ring {
 if r.next == nil {
  return r.init()
 }
 return r.prev
}

// Move moves n % r.Len() elements backward (n < 0) or forward (n >= 0)
// in the ring and returns that ring element. r must not be empty.
func (r *Ring) Move(n int) *Ring {
 if r.next == nil {
  return r.init()
 }
 switch {
 case n < 0:
  for ; n < 0; n++ {
   r = r.prev
  }
 case n > 0:
  for ; n > 0; n-- {
   r = r.next
  }
 }
 return r
}

// Do calls function f on each element of the ring, in forward order.
// The behavior of Do is undefined if f changes *r.
func (r *Ring) Do(f func(any)) {
 if r != nil {
  f(r.Value)
  for p := r.Next(); p != r; p = p.next {
   f(p.Value)
  }
 }
}

type Interface interface {
 sort.Interface
 Push(x any) // add x as element Len()
 Pop() any   // remove and return element Len() - 1.
}

type Interface interface {
	Len() int
	Less(i, j int) bool
	Swap(i, j int)
}

func up(h Interface, j int) {
 for {
  i := (j - 1) / 2 // parent
  if i == j || !h.Less(j, i) {
   break
  }
  h.Swap(i, j)
  j = i
 }
}

func down(h Interface, i0, n int) bool {
 i := i0
 for {
  j1 := 2*i + 1
  if j1 >= n || j1 < 0 { // j1 < 0 after int overflow
   break
  }
  j := j1 // left child
  if j2 := j1 + 1; j2 < n && h.Less(j2, j1) {
   j = j2 // = 2*i + 2  // right child
  }
  if !h.Less(j, i) {
   break
  }
  h.Swap(i, j)
  i = j
 }
 return i > i0
}

func Init(h Interface) {
 // heapify
 n := h.Len()
 for i := n/2 - 1; i >= 0; i-- {
  down(h, i, n)
 }
}

func Push(h Interface, x any) {
	h.Push(x)
	up(h, h.Len()-1)
}

func Pop(h Interface) any {
	n := h.Len() - 1
	h.Swap(0, n)
	down(h, 0, n)
	return h.Pop()
}

func Remove(h Interface, i int) any {
	n := h.Len() - 1
	if n != i {
		h.Swap(i, n)
		if !down(h, i, n) {
			up(h, i)
		}
	}
	return h.Pop()
}

func Fix(h Interface, i int) {
	if !down(h, i, h.Len()) {
		up(h, i)
	}
}

#include <signal.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>

void handler(int sig) {
    printf("hello SIGIO, exit ...");
    exit(0);
} 

int main(int argc, char const *argv[])
{
    signal(SIGIO, handler);
    sleep(20 * 1000);
    return 0;
}