| 263 | |
| 264 | template <typename T> |
| 265 | Node * |
| 266 | Tree<T>::add(uint32_t parent_id, uint32_t id, uint32_t weight, bool exclusive, T t, bool shadow) |
| 267 | { |
| 268 | // Can we vivify a shadow node? |
| 269 | Node *node = find_shadow(id); |
| 270 | if (node != nullptr && node->is_shadow()) { |
| 271 | node->t = t; |
| 272 | node->point = id; |
| 273 | node->weight = weight; |
| 274 | node->shadow = false; |
| 275 | // Move the shadow node into the proper position in the tree |
| 276 | node = reprioritize(node, parent_id, exclusive); |
| 277 | return node; |
| 278 | } |
| 279 | |
| 280 | bool is_max_leaf = false; |
| 281 | Node *parent = find_shadow(parent_id, &is_max_leaf); // Look for real and shadow nodes |
| 282 | |
| 283 | if (parent == nullptr) { |
| 284 | if (parent_id < id) { // See if we still have a history of the parent |
| 285 | uint32_t pid = parent_id; |
| 286 | do { |
| 287 | pid = was_ancestor(pid); |
| 288 | if (pid != 0) { |
| 289 | parent = find(pid); |
| 290 | } |
| 291 | } while (pid != 0 && parent == nullptr); |
| 292 | if (parent == nullptr) { |
| 293 | // Found no ancestor, just add to root at default weight |
| 294 | weight = HTTP2_PRIORITY_DEFAULT_WEIGHT; |
| 295 | exclusive = false; |
| 296 | parent = _root; |
| 297 | } |
| 298 | } |
| 299 | if (parent == nullptr || parent == _root) { // Create a shadow node |
| 300 | parent = add(0, parent_id, HTTP2_PRIORITY_DEFAULT_WEIGHT, false, nullptr, true); |
| 301 | exclusive = false; |
| 302 | } |
| 303 | } else if (is_max_leaf) { // Chain too long, just add to root |
| 304 | parent = _root; |
| 305 | exclusive = false; |
| 306 | } |
| 307 | |
| 308 | // Use stream id as initial point |
| 309 | node = new Node(id, weight, id, parent, t); |
| 310 | |
| 311 | if (exclusive) { |
| 312 | while (Node *child = parent->children.pop()) { |
| 313 | if (child->queued) { |
| 314 | parent->queue->erase(child->entry); |
| 315 | node->queue->push(child->entry); |
| 316 | } |
| 317 | node->children.push(child); |
| 318 | child->parent = node; |
| 319 | } |
| 320 | } |
| 321 | |
| 322 | parent->children.push(node); |