| 1 |
|
| |
| 2 |
|
| // read "rinq" as "ring-queue" |
| 3 |
|
| |
| 4 |
|
| #define RINQ_FREELIST_MAX 64 |
| 5 |
|
| static struct rinq *rinq_freelist = NULL; |
| 6 |
|
| static int rinq_freelist_count = 0; |
| 7 |
|
| |
| 8 |
|
| #define RINQ_IS_DETACHED(x_) ((x_)->next == (x_)) |
| 9 |
|
| |
| 10 |
|
| #define RINQ_NEW(x_,ref_) do { \ |
| 11 |
|
| if (rinq_freelist != NULL) { \ |
| 12 |
|
| x_ = rinq_freelist; \ |
| 13 |
|
| rinq_freelist = rinq_freelist->next; \ |
| 14 |
|
| rinq_freelist_count--; \ |
| 15 |
|
| } else { \ |
| 16 |
|
| x_ = (struct rinq *)malloc(sizeof(struct rinq)); \ |
| 17 |
|
| if (unlikely(!x_)) croak("Out of memory in rinq"); \ |
| 18 |
|
| } \ |
| 19 |
|
| x_->next = x_->prev = x_; \ |
| 20 |
|
| x_->ref = ref_; \ |
| 21 |
|
| } while(0) |
| 22 |
|
| |
| 23 |
|
| #define RINQ_FREE(x_) do { \ |
| 24 |
|
| if (rinq_freelist_count < RINQ_FREELIST_MAX) { \ |
| 25 |
|
| (x_)->next = rinq_freelist; \ |
| 26 |
|
| rinq_freelist = (x_); \ |
| 27 |
|
| rinq_freelist_count++; \ |
| 28 |
|
| } else { \ |
| 29 |
|
| free(x_); \ |
| 30 |
|
| } \ |
| 31 |
|
| } while(0) |
| 32 |
|
| |
| 33 |
|
| #define RINQ_DETACH(x_) do { \ |
| 34 |
|
| (x_)->next->prev = (x_)->prev; \ |
| 35 |
|
| (x_)->prev->next = (x_)->next; \ |
| 36 |
|
| (x_)->next = (x_)->prev = (x_); \ |
| 37 |
|
| } while(0) |
| 38 |
|
| |
| 39 |
|
| INLINE_UNLESS_DEBUG |
| 40 |
|
| static struct rinq * |
| 41 |
4720 |
| rinq_push (struct rinq **head, void *ref) |
| 42 |
|
| { |
| 43 |
|
| struct rinq *x; |
| 44 |
4720 |
▶ | RINQ_NEW(x,ref); |
Branch: 2 branches
| Branch | True | False | Total |
| RINQ_NEW(x,ref); |
4248 |
472 |
4720 |
| RINQ_NEW(x,ref); |
0 |
472 |
472 |
|
| 45 |
|
| |
| 46 |
4720 |
▶ | if ((*head) == NULL) { |
Branch: 1 branch
| Branch | True | False | Total |
| if ((*head) == NULL) { |
4415 |
305 |
4720 |
|
| 47 |
4415 |
| (*head) = x; |
| 48 |
|
| } |
| 49 |
|
| else { |
| 50 |
305 |
| x->next = (*head); |
| 51 |
305 |
| x->prev = (*head)->prev; |
| 52 |
305 |
| x->next->prev = x->prev->next = x; |
| 53 |
|
| } |
| 54 |
4720 |
| return x; |
| 55 |
|
| } |
| 56 |
|
| |
| 57 |
|
| INLINE_UNLESS_DEBUG |
| 58 |
|
| static void * |
| 59 |
4067 |
| rinq_shift (struct rinq **head) { |
| 60 |
|
| void *ref; |
| 61 |
|
| struct rinq *x; |
| 62 |
|
| |
| 63 |
4067 |
▶ | if ((*head) == NULL) return NULL; |
Branch: 1 branch
| Branch | True | False | Total |
| if ((*head) == NULL) return NULL; |
401 |
3666 |
4067 |
|
| 64 |
|
| |
| 65 |
3666 |
▶ | if (RINQ_IS_DETACHED((*head))) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (RINQ_IS_DETACHED((*head))) { |
3606 |
60 |
3666 |
|
| 66 |
3606 |
| x = (*head); |
| 67 |
3606 |
| (*head) = NULL; |
| 68 |
|
| } |
| 69 |
|
| else { |
| 70 |
60 |
| x = (*head); |
| 71 |
60 |
| (*head) = (*head)->next; |
| 72 |
60 |
| RINQ_DETACH(x); |
| 73 |
|
| } |
| 74 |
|
| |
| 75 |
3666 |
| ref = x->ref; |
| 76 |
3666 |
▶ | RINQ_FREE(x); |
Branch: 1 branch
| Branch | True | False | Total |
| RINQ_FREE(x); |
3666 |
0 |
3666 |
|
| 77 |
3666 |
| return ref; |
| 78 |
|
| } |
| 79 |
|
| |
| 80 |
|
| INLINE_UNLESS_DEBUG |
| 81 |
|
| static void |
| 82 |
764 |
| rinq_remove (struct rinq **head, struct rinq *node) |
| 83 |
|
| { |
| 84 |
764 |
▶ | if (*head == node) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (*head == node) { |
745 |
19 |
764 |
|
| 85 |
745 |
▶ | if (node->next == node) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (node->next == node) { |
729 |
16 |
745 |
|
| 86 |
729 |
| *head = NULL; |
| 87 |
|
| } else { |
| 88 |
16 |
| *head = node->next; |
| 89 |
|
| } |
| 90 |
|
| } |
| 91 |
764 |
| RINQ_DETACH(node); |
| 92 |
764 |
▶ | RINQ_FREE(node); |
Branch: 1 branch
| Branch | True | False | Total |
| RINQ_FREE(node); |
764 |
0 |
764 |
|
| 93 |
764 |
| } |