Lines Matching defs:ksl
52 static void ksl_node_set_key(nghttp3_ksl *ksl, nghttp3_ksl_node *node,
54 memcpy(node->key, key, ksl->keylen);
57 void nghttp3_ksl_init(nghttp3_ksl *ksl, nghttp3_ksl_compar compar,
61 nghttp3_objalloc_init(&ksl->blkalloc,
65 ksl->head = NULL;
66 ksl->front = ksl->back = NULL;
67 ksl->compar = compar;
68 ksl->keylen = keylen;
69 ksl->nodelen = nodelen;
70 ksl->n = 0;
73 static nghttp3_ksl_blk *ksl_blk_objalloc_new(nghttp3_ksl *ksl) {
74 return nghttp3_objalloc_ksl_blk_len_get(&ksl->blkalloc,
75 ksl_blklen(ksl->nodelen));
78 static void ksl_blk_objalloc_del(nghttp3_ksl *ksl, nghttp3_ksl_blk *blk) {
79 nghttp3_objalloc_ksl_blk_release(&ksl->blkalloc, blk);
82 static int ksl_head_init(nghttp3_ksl *ksl) {
83 nghttp3_ksl_blk *head = ksl_blk_objalloc_new(ksl);
92 ksl->head = head;
93 ksl->front = ksl->back = head;
102 static void ksl_free_blk(nghttp3_ksl *ksl, nghttp3_ksl_blk *blk) {
107 ksl_free_blk(ksl, nghttp3_ksl_nth_node(ksl, blk, i)->blk);
111 ksl_blk_objalloc_del(ksl, blk);
115 void nghttp3_ksl_free(nghttp3_ksl *ksl) {
116 if (!ksl || !ksl->head) {
121 ksl_free_blk(ksl, ksl->head);
124 nghttp3_objalloc_free(&ksl->blkalloc);
135 static nghttp3_ksl_blk *ksl_split_blk(nghttp3_ksl *ksl, nghttp3_ksl_blk *blk) {
138 rblk = ksl_blk_objalloc_new(ksl);
147 } else if (ksl->back == blk) {
148 ksl->back = rblk;
155 memcpy(rblk->nodes, blk->nodes + ksl->nodelen * (blk->n - rblk->n),
156 ksl->nodelen * rblk->n);
177 static int ksl_split_node(nghttp3_ksl *ksl, nghttp3_ksl_blk *blk, size_t i) {
179 nghttp3_ksl_blk *lblk = nghttp3_ksl_nth_node(ksl, blk, i)->blk, *rblk;
181 rblk = ksl_split_blk(ksl, lblk);
186 memmove(blk->nodes + (i + 2) * ksl->nodelen,
187 blk->nodes + (i + 1) * ksl->nodelen,
188 ksl->nodelen * (blk->n - (i + 1)));
190 node = nghttp3_ksl_nth_node(ksl, blk, i + 1);
193 ksl_node_set_key(ksl, node,
194 nghttp3_ksl_nth_node(ksl, rblk, rblk->n - 1)->key);
196 node = nghttp3_ksl_nth_node(ksl, blk, i);
197 ksl_node_set_key(ksl, node,
198 nghttp3_ksl_nth_node(ksl, lblk, lblk->n - 1)->key);
213 static int ksl_split_head(nghttp3_ksl *ksl) {
217 rblk = ksl_split_blk(ksl, ksl->head);
222 lblk = ksl->head;
224 nhead = ksl_blk_objalloc_new(ksl);
226 ksl_blk_objalloc_del(ksl, rblk);
233 node = nghttp3_ksl_nth_node(ksl, nhead, 0);
234 ksl_node_set_key(ksl, node,
235 nghttp3_ksl_nth_node(ksl, lblk, lblk->n - 1)->key);
238 node = nghttp3_ksl_nth_node(ksl, nhead, 1);
239 ksl_node_set_key(ksl, node,
240 nghttp3_ksl_nth_node(ksl, rblk, rblk->n - 1)->key);
243 ksl->head = nhead;
254 static void ksl_insert_node(nghttp3_ksl *ksl, nghttp3_ksl_blk *blk, size_t i,
260 memmove(blk->nodes + (i + 1) * ksl->nodelen, blk->nodes + i * ksl->nodelen,
261 ksl->nodelen * (blk->n - i));
263 node = nghttp3_ksl_nth_node(ksl, blk, i);
264 ksl_node_set_key(ksl, node, key);
270 static size_t ksl_bsearch(nghttp3_ksl *ksl, nghttp3_ksl_blk *blk,
278 ++i, node = (nghttp3_ksl_node *)(void *)((uint8_t *)node + ksl->nodelen))
284 int nghttp3_ksl_insert(nghttp3_ksl *ksl, nghttp3_ksl_it *it,
291 if (!ksl->head) {
292 rv = ksl_head_init(ksl);
298 blk = ksl->head;
301 rv = ksl_split_head(ksl);
305 blk = ksl->head;
309 i = ksl_bsearch(ksl, blk, key, ksl->compar);
313 !ksl->compar(key, nghttp3_ksl_nth_node(ksl, blk, i)->key)) {
315 *it = nghttp3_ksl_end(ksl);
319 ksl_insert_node(ksl, blk, i, key, data);
320 ++ksl->n;
322 nghttp3_ksl_it_init(it, ksl, blk, i);
330 node = nghttp3_ksl_nth_node(ksl, blk, blk->n - 1);
332 rv = ksl_split_node(ksl, blk, blk->n - 1);
336 node = nghttp3_ksl_nth_node(ksl, blk, blk->n - 1);
338 ksl_node_set_key(ksl, node, key);
341 ksl_insert_node(ksl, blk, blk->n, key, data);
342 ++ksl->n;
344 nghttp3_ksl_it_init(it, ksl, blk, blk->n - 1);
349 node = nghttp3_ksl_nth_node(ksl, blk, i);
352 rv = ksl_split_node(ksl, blk, i);
356 if (ksl->compar((nghttp3_ksl_key *)node->key, key)) {
357 node = nghttp3_ksl_nth_node(ksl, blk, i + 1);
358 if (ksl->compar((nghttp3_ksl_key *)node->key, key)) {
359 ksl_node_set_key(ksl, node, key);
372 static void ksl_remove_node(nghttp3_ksl *ksl, nghttp3_ksl_blk *blk, size_t i) {
373 memmove(blk->nodes + i * ksl->nodelen, blk->nodes + (i + 1) * ksl->nodelen,
374 ksl->nodelen * (blk->n - (i + 1)));
385 * which decreases the height of |ksl| by 1.
389 static nghttp3_ksl_blk *ksl_merge_node(nghttp3_ksl *ksl, nghttp3_ksl_blk *blk,
395 lblk = nghttp3_ksl_nth_node(ksl, blk, i)->blk;
396 rblk = nghttp3_ksl_nth_node(ksl, blk, i + 1)->blk;
400 memcpy(lblk->nodes + ksl->nodelen * lblk->n, rblk->nodes,
401 ksl->nodelen * rblk->n);
407 } else if (ksl->back == rblk) {
408 ksl->back = lblk;
411 ksl_blk_objalloc_del(ksl, rblk);
413 if (ksl->head == blk && blk->n == 2) {
414 ksl_blk_objalloc_del(ksl, ksl->head);
415 ksl->head = lblk;
417 ksl_remove_node(ksl, blk, i + 1);
418 ksl_node_set_key(ksl, nghttp3_ksl_nth_node(ksl, blk, i),
419 nghttp3_ksl_nth_node(ksl, lblk, lblk->n - 1)->key);
430 static void ksl_shift_left(nghttp3_ksl *ksl, nghttp3_ksl_blk *blk, size_t i) {
436 lnode = nghttp3_ksl_nth_node(ksl, blk, i - 1);
437 rnode = nghttp3_ksl_nth_node(ksl, blk, i);
448 memcpy(lnode->blk->nodes + ksl->nodelen * lnode->blk->n, rnode->blk->nodes,
449 ksl->nodelen * n);
455 ksl, lnode,
456 nghttp3_ksl_nth_node(ksl, lnode->blk, lnode->blk->n - 1)->key);
458 memmove(rnode->blk->nodes, rnode->blk->nodes + ksl->nodelen * n,
459 ksl->nodelen * rnode->blk->n);
467 static void ksl_shift_right(nghttp3_ksl *ksl, nghttp3_ksl_blk *blk, size_t i) {
473 lnode = nghttp3_ksl_nth_node(ksl, blk, i);
474 rnode = nghttp3_ksl_nth_node(ksl, blk, i + 1);
485 memmove(rnode->blk->nodes + ksl->nodelen * n, rnode->blk->nodes,
486 ksl->nodelen * rnode->blk->n);
491 memcpy(rnode->blk->nodes, lnode->blk->nodes + ksl->nodelen * lnode->blk->n,
492 ksl->nodelen * n);
495 ksl, lnode,
496 nghttp3_ksl_nth_node(ksl, lnode->blk, lnode->blk->n - 1)->key);
508 int nghttp3_ksl_remove_hint(nghttp3_ksl *ksl, nghttp3_ksl_it *it,
513 assert(ksl->head);
516 return nghttp3_ksl_remove(ksl, it, key);
519 ksl_remove_node(ksl, blk, hint->i);
521 --ksl->n;
525 nghttp3_ksl_it_init(it, ksl, blk->next, 0);
527 nghttp3_ksl_it_init(it, ksl, blk, hint->i);
534 int nghttp3_ksl_remove(nghttp3_ksl *ksl, nghttp3_ksl_it *it,
536 nghttp3_ksl_blk *blk = ksl->head;
540 if (!ksl->head) {
545 nghttp3_ksl_nth_node(ksl, blk, 0)->blk->n == NGHTTP3_KSL_MIN_NBLK &&
546 nghttp3_ksl_nth_node(ksl, blk, 1)->blk->n == NGHTTP3_KSL_MIN_NBLK) {
547 blk = ksl_merge_node(ksl, ksl->head, 0);
551 i = ksl_bsearch(ksl, blk, key, ksl->compar);
555 *it = nghttp3_ksl_end(ksl);
561 if (ksl->compar(key, nghttp3_ksl_nth_node(ksl, blk, i)->key)) {
563 *it = nghttp3_ksl_end(ksl);
567 ksl_remove_node(ksl, blk, i);
568 --ksl->n;
571 nghttp3_ksl_it_init(it, ksl, blk->next, 0);
573 nghttp3_ksl_it_init(it, ksl, blk, i);
579 node = nghttp3_ksl_nth_node(ksl, blk, i);
589 nghttp3_ksl_nth_node(ksl, blk, i + 1)->blk->n > NGHTTP3_KSL_MIN_NBLK) {
590 ksl_shift_left(ksl, blk, i + 1);
596 nghttp3_ksl_nth_node(ksl, blk, i - 1)->blk->n > NGHTTP3_KSL_MIN_NBLK) {
597 ksl_shift_right(ksl, blk, i - 1);
603 blk = ksl_merge_node(ksl, blk, i);
609 blk = ksl_merge_node(ksl, blk, i - 1);
613 nghttp3_ksl_it nghttp3_ksl_lower_bound(nghttp3_ksl *ksl,
615 nghttp3_ksl_blk *blk = ksl->head;
620 nghttp3_ksl_it_init(&it, ksl, &null_blk, 0);
625 i = ksl_bsearch(ksl, blk, key, ksl->compar);
632 nghttp3_ksl_it_init(&it, ksl, blk, i);
639 for (; !blk->leaf; blk = nghttp3_ksl_nth_node(ksl, blk, blk->n - 1)->blk)
647 nghttp3_ksl_it_init(&it, ksl, blk, i);
650 blk = nghttp3_ksl_nth_node(ksl, blk, i)->blk;
654 nghttp3_ksl_it nghttp3_ksl_lower_bound_compar(nghttp3_ksl *ksl,
657 nghttp3_ksl_blk *blk = ksl->head;
662 nghttp3_ksl_it_init(&it, ksl, &null_blk, 0);
667 i = ksl_bsearch(ksl, blk, key, compar);
674 nghttp3_ksl_it_init(&it, ksl, blk, i);
681 for (; !blk->leaf; blk = nghttp3_ksl_nth_node(ksl, blk, blk->n - 1)->blk)
689 nghttp3_ksl_it_init(&it, ksl, blk, i);
692 blk = nghttp3_ksl_nth_node(ksl, blk, i)->blk;
696 void nghttp3_ksl_update_key(nghttp3_ksl *ksl, const nghttp3_ksl_key *old_key,
698 nghttp3_ksl_blk *blk = ksl->head;
702 assert(ksl->head);
705 i = ksl_bsearch(ksl, blk, old_key, ksl->compar);
708 node = nghttp3_ksl_nth_node(ksl, blk, i);
711 assert(key_equal(ksl->compar, (nghttp3_ksl_key *)node->key, old_key));
712 ksl_node_set_key(ksl, node, new_key);
716 if (key_equal(ksl->compar, (nghttp3_ksl_key *)node->key, old_key) ||
717 ksl->compar((nghttp3_ksl_key *)node->key, new_key)) {
718 ksl_node_set_key(ksl, node, new_key);
725 static void ksl_print(nghttp3_ksl *ksl, nghttp3_ksl_blk *blk, size_t level) {
733 node = nghttp3_ksl_nth_node(ksl, blk, i);
741 ksl_print(ksl, nghttp3_ksl_nth_node(ksl, blk, i)->blk, level + 1);
745 size_t nghttp3_ksl_len(nghttp3_ksl *ksl) { return ksl->n; }
747 void nghttp3_ksl_clear(nghttp3_ksl *ksl) {
748 if (!ksl->head) {
753 ksl_free_blk(ksl, ksl->head);
756 ksl->front = ksl->back = ksl->head = NULL;
757 ksl->n = 0;
759 nghttp3_objalloc_clear(&ksl->blkalloc);
762 void nghttp3_ksl_print(nghttp3_ksl *ksl) {
763 if (!ksl->head) {
767 ksl_print(ksl, ksl->head, 0);
770 nghttp3_ksl_it nghttp3_ksl_begin(const nghttp3_ksl *ksl) {
773 if (ksl->head) {
774 nghttp3_ksl_it_init(&it, ksl, ksl->front, 0);
776 nghttp3_ksl_it_init(&it, ksl, &null_blk, 0);
782 nghttp3_ksl_it nghttp3_ksl_end(const nghttp3_ksl *ksl) {
785 if (ksl->head) {
786 nghttp3_ksl_it_init(&it, ksl, ksl->back, ksl->back->n);
788 nghttp3_ksl_it_init(&it, ksl, &null_blk, 0);
794 void nghttp3_ksl_it_init(nghttp3_ksl_it *it, const nghttp3_ksl *ksl,
796 it->ksl = ksl;