* Inserts the key-value pair into the trie. * Panics if the key already exists. */
| 383 | * Panics if the key already exists. |
| 384 | */ |
| 385 | int |
| 386 | vm_radix_insert(struct vm_radix *rtree, vm_page_t page) |
| 387 | { |
| 388 | vm_pindex_t index, newind; |
| 389 | struct vm_radix_node *rnode, *tmp; |
| 390 | smrnode_t *parentp; |
| 391 | vm_page_t m; |
| 392 | int slot; |
| 393 | uint16_t clev; |
| 394 | |
| 395 | index = page->pindex; |
| 396 | |
| 397 | /* |
| 398 | * The owner of record for root is not really important because it |
| 399 | * will never be used. |
| 400 | */ |
| 401 | rnode = vm_radix_root_load(rtree, LOCKED); |
| 402 | if (rnode == NULL) { |
| 403 | rtree->rt_root = (uintptr_t)page | VM_RADIX_ISLEAF; |
| 404 | return (0); |
| 405 | } |
| 406 | parentp = (smrnode_t *)&rtree->rt_root; |
| 407 | for (;;) { |
| 408 | if (vm_radix_isleaf(rnode)) { |
| 409 | m = vm_radix_topage(rnode); |
| 410 | if (m->pindex == index) |
| 411 | panic("%s: key %jx is already present", |
| 412 | __func__, (uintmax_t)index); |
| 413 | clev = vm_radix_keydiff(m->pindex, index); |
| 414 | tmp = vm_radix_node_get(vm_radix_trimkey(index, |
| 415 | clev + 1), 2, clev); |
| 416 | if (tmp == NULL) |
| 417 | return (ENOMEM); |
| 418 | /* These writes are not yet visible due to ordering. */ |
| 419 | vm_radix_addpage(tmp, index, clev, page, UNSERIALIZED); |
| 420 | vm_radix_addpage(tmp, m->pindex, clev, m, UNSERIALIZED); |
| 421 | /* Synchronize to make leaf visible. */ |
| 422 | vm_radix_node_store(parentp, tmp, LOCKED); |
| 423 | return (0); |
| 424 | } else if (vm_radix_keybarr(rnode, index)) |
| 425 | break; |
| 426 | slot = vm_radix_slot(index, rnode->rn_clev); |
| 427 | parentp = &rnode->rn_child[slot]; |
| 428 | tmp = vm_radix_node_load(parentp, LOCKED); |
| 429 | if (tmp == NULL) { |
| 430 | rnode->rn_count++; |
| 431 | vm_radix_addpage(rnode, index, rnode->rn_clev, page, |
| 432 | LOCKED); |
| 433 | return (0); |
| 434 | } |
| 435 | rnode = tmp; |
| 436 | } |
| 437 | |
| 438 | /* |
| 439 | * A new node is needed because the right insertion level is reached. |
| 440 | * Setup the new intermediate node and add the 2 children: the |
| 441 | * new object and the older edge. |
| 442 | */ |
no test coverage detected