* Inserts the key-value pair into the trie. * Panics if the key already exists. */
| 344 | * Panics if the key already exists. |
| 345 | */ |
| 346 | int |
| 347 | pctrie_insert(struct pctrie *ptree, uint64_t *val, pctrie_alloc_t allocfn) |
| 348 | { |
| 349 | uint64_t index, newind; |
| 350 | struct pctrie_node *node, *tmp; |
| 351 | smr_pctnode_t *parentp; |
| 352 | uint64_t *m; |
| 353 | int slot; |
| 354 | uint16_t clev; |
| 355 | |
| 356 | index = *val; |
| 357 | |
| 358 | /* |
| 359 | * The owner of record for root is not really important because it |
| 360 | * will never be used. |
| 361 | */ |
| 362 | node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); |
| 363 | if (node == NULL) { |
| 364 | ptree->pt_root = (uintptr_t)val | PCTRIE_ISLEAF; |
| 365 | return (0); |
| 366 | } |
| 367 | parentp = (smr_pctnode_t *)&ptree->pt_root; |
| 368 | for (;;) { |
| 369 | if (pctrie_isleaf(node)) { |
| 370 | m = pctrie_toval(node); |
| 371 | if (*m == index) |
| 372 | panic("%s: key %jx is already present", |
| 373 | __func__, (uintmax_t)index); |
| 374 | clev = pctrie_keydiff(*m, index); |
| 375 | tmp = pctrie_node_get(ptree, allocfn, |
| 376 | pctrie_trimkey(index, clev + 1), 2, clev); |
| 377 | if (tmp == NULL) |
| 378 | return (ENOMEM); |
| 379 | /* These writes are not yet visible due to ordering. */ |
| 380 | pctrie_addval(tmp, index, clev, val, |
| 381 | PCTRIE_UNSERIALIZED); |
| 382 | pctrie_addval(tmp, *m, clev, m, PCTRIE_UNSERIALIZED); |
| 383 | /* Synchronize to make leaf visible. */ |
| 384 | pctrie_node_store(parentp, tmp, PCTRIE_LOCKED); |
| 385 | return (0); |
| 386 | } else if (pctrie_keybarr(node, index)) |
| 387 | break; |
| 388 | slot = pctrie_slot(index, node->pn_clev); |
| 389 | parentp = &node->pn_child[slot]; |
| 390 | tmp = pctrie_node_load(parentp, NULL, PCTRIE_LOCKED); |
| 391 | if (tmp == NULL) { |
| 392 | node->pn_count++; |
| 393 | pctrie_addval(node, index, node->pn_clev, val, |
| 394 | PCTRIE_LOCKED); |
| 395 | return (0); |
| 396 | } |
| 397 | node = tmp; |
| 398 | } |
| 399 | |
| 400 | /* |
| 401 | * A new node is needed because the right insertion level is reached. |
| 402 | * Setup the new intermediate node and add the 2 children: the |
| 403 | * new object and the older edge. |
no test coverage detected