(t kind, path string, method string, ri routeMethod)
| 546 | } |
| 547 | |
| 548 | func (r *DefaultRouter) insert(t kind, path string, method string, ri routeMethod) { |
| 549 | if len(ri.Parameters) > r.maxPathParamsLength { |
| 550 | r.maxPathParamsLength = len(ri.Parameters) |
| 551 | } |
| 552 | currentNode := r.tree // Current node as root |
| 553 | search := path |
| 554 | |
| 555 | for { |
| 556 | searchLen := len(search) |
| 557 | prefixLen := len(currentNode.prefix) |
| 558 | lcpLen := 0 |
| 559 | |
| 560 | // LCP - Longest Common Prefix (https://en.wikipedia.org/wiki/LCP_array) |
| 561 | maxL := min(searchLen, prefixLen) |
| 562 | for ; lcpLen < maxL && search[lcpLen] == currentNode.prefix[lcpLen]; lcpLen++ { |
| 563 | } |
| 564 | |
| 565 | if lcpLen == 0 { |
| 566 | // At root node |
| 567 | currentNode.label = search[0] |
| 568 | currentNode.prefix = search |
| 569 | if ri.handler != nil { |
| 570 | currentNode.kind = t |
| 571 | currentNode.setHandler(method, &ri) |
| 572 | currentNode.paramsCount = len(ri.Parameters) |
| 573 | currentNode.originalPath = ri.Path |
| 574 | } |
| 575 | currentNode.isLeaf = currentNode.staticChildren == nil && currentNode.paramChild == nil && currentNode.anyChild == nil |
| 576 | } else if lcpLen < prefixLen { |
| 577 | // Split node into two before we insert new node. |
| 578 | // This happens when we are inserting path that is submatch of any existing inserted paths. |
| 579 | // For example, we have node `/test` and now are about to insert `/te/*`. In that case |
| 580 | // 1. overlapping part is `/te` that is used as parent node |
| 581 | // 2. `st` is part from existing node that is not matching - it gets its own node (child to `/te`) |
| 582 | // 3. `/*` is the new part we are about to insert (child to `/te`) |
| 583 | n := newNode( |
| 584 | currentNode.kind, |
| 585 | currentNode.prefix[lcpLen:], |
| 586 | currentNode, |
| 587 | currentNode.staticChildren, |
| 588 | currentNode.methods, |
| 589 | currentNode.paramsCount, |
| 590 | currentNode.originalPath, |
| 591 | currentNode.paramChild, |
| 592 | currentNode.anyChild, |
| 593 | ) |
| 594 | // Update parent path for all children to new node |
| 595 | for _, child := range currentNode.staticChildren { |
| 596 | child.parent = n |
| 597 | } |
| 598 | if currentNode.paramChild != nil { |
| 599 | currentNode.paramChild.parent = n |
| 600 | } |
| 601 | if currentNode.anyChild != nil { |
| 602 | currentNode.anyChild.parent = n |
| 603 | } |
| 604 | |
| 605 | // Reset parent node |
no test coverage detected