codekingpro/portable-devtools

1'use strict'
2
3const {
4  wellknownHeaderNames,
5  headerNameLowerCasedRecord
6} = require('./constants')
7
8class TstNode {
9  /** @type {any} */
10  value = null
11  /** @type {null | TstNode} */
12  left = null
13  /** @type {null | TstNode} */
14  middle = null
15  /** @type {null | TstNode} */
16  right = null
17  /** @type {number} */
18  code
19  /**
20   * @param {string} key
21   * @param {any} value
22   * @param {number} index
23   */
24  constructor (key, value, index) {
25    if (index === undefined || index >= key.length) {
26      throw new TypeError('Unreachable')
27    }
28    const code = this.code = key.charCodeAt(index)
29    // check code is ascii string
30    if (code > 0x7F) {
31      throw new TypeError('key must be ascii string')
32    }
33    if (key.length !== ++index) {
34      this.middle = new TstNode(key, value, index)
35    } else {
36      this.value = value
37    }
38  }
39
40  /**
41   * @param {string} key
42   * @param {any} value
43   */
44  add (key, value) {
45    const length = key.length
46    if (length === 0) {
47      throw new TypeError('Unreachable')
48    }
49    let index = 0
50    let node = this
51    while (true) {
52      const code = key.charCodeAt(index)
53      // check code is ascii string
54      if (code > 0x7F) {
55        throw new TypeError('key must be ascii string')
56      }
57      if (node.code === code) {
58        if (length === ++index) {
59          node.value = value
60          break
61        } else if (node.middle !== null) {
62          node = node.middle
63        } else {
64          node.middle = new TstNode(key, value, index)
65          break
66        }
67      } else if (node.code < code) {
68        if (node.left !== null) {
69          node = node.left
70        } else {
71          node.left = new TstNode(key, value, index)
72          break
73        }
74      } else if (node.right !== null) {
75        node = node.right
76      } else {
77        node.right = new TstNode(key, value, index)
78        break
79      }
80    }
81  }
82
83  /**
84   * @param {Uint8Array} key
85   * @return {TstNode | null}
86   */
87  search (key) {
88    const keylength = key.length
89    let index = 0
90    let node = this
91    while (node !== null && index < keylength) {
92      let code = key[index]
93      // A-Z
94      // First check if it is bigger than 0x5a.
95      // Lowercase letters have higher char codes than uppercase ones.
96      // Also we assume that headers will mostly contain lowercase characters.
97      if (code <= 0x5a && code >= 0x41) {
98        // Lowercase for uppercase.
99        code |= 32
100      }
101      while (node !== null) {
102        if (code === node.code) {
103          if (keylength === ++index) {
104            // Returns Node since it is the last key.
105            return node
106          }
107          node = node.middle
108          break
109        }
110        node = node.code < code ? node.left : node.right
111      }
112    }
113    return null
114  }
115}
116
117class TernarySearchTree {
118  /** @type {TstNode | null} */
119  node = null
120
121  /**
122   * @param {string} key
123   * @param {any} value
124   * */
125  insert (key, value) {
126    if (this.node === null) {
127      this.node = new TstNode(key, value, 0)
128    } else {
129      this.node.add(key, value)
130    }
131  }
132
133  /**
134   * @param {Uint8Array} key
135   * @return {any}
136   */
137  lookup (key) {
138    return this.node?.search(key)?.value ?? null
139  }
140}
141
142const tree = new TernarySearchTree()
143
144for (let i = 0; i < wellknownHeaderNames.length; ++i) {
145  const key = headerNameLowerCasedRecord[wellknownHeaderNames[i]]
146  tree.insert(key, key)
147}
148
149module.exports = {
150  TernarySearchTree,
151  tree
152}
153