| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #include <stdlib.h> | ||
| 2 | #include <string.h> | ||
| 3 | #include <stdio.h> | ||
| 4 | #include "reversed_ordered_set.h" | ||
| 5 | |||
| 6 | #include "../shared-storage/bayrepomalloc.h" | ||
| 7 | |||
| 8 | #include "unit_test_common.h" | ||
| 9 | |||
| 10 | 1597 | static inline int i360_default_rev_compare_keys(char *one, char *two_end, unsigned two_len) { | |
| 11 |
4/4✓ Branch 0 taken 2097 times.
✓ Branch 1 taken 66 times.
✓ Branch 2 taken 2089 times.
✓ Branch 3 taken 8 times.
|
2163 | while (*one && two_len) { |
| 12 |
2/2✓ Branch 0 taken 798 times.
✓ Branch 1 taken 1291 times.
|
2089 | if (*one < *two_end) |
| 13 | 798 | return -1; | |
| 14 |
2/2✓ Branch 0 taken 725 times.
✓ Branch 1 taken 566 times.
|
1291 | else if (*one > *two_end) |
| 15 | 725 | return 1; | |
| 16 | |||
| 17 | 566 | ++one; | |
| 18 | 566 | --two_end; | |
| 19 | 566 | --two_len; | |
| 20 | } | ||
| 21 | |||
| 22 |
2/2✓ Branch 0 taken 8 times.
✓ Branch 1 taken 66 times.
|
74 | if (0 != *one) |
| 23 | 8 | return 1; | |
| 24 |
2/2✓ Branch 0 taken 64 times.
✓ Branch 1 taken 2 times.
|
66 | else if (0 != two_len) |
| 25 | 64 | return -1; | |
| 26 | |||
| 27 | 2 | return 0; | |
| 28 | } | ||
| 29 | |||
| 30 | 159 | static inline int i360_partial_rev_compare_keys(char *one, char *two_end, unsigned two_len) { | |
| 31 |
4/4✓ Branch 0 taken 506 times.
✓ Branch 1 taken 6 times.
✓ Branch 2 taken 500 times.
✓ Branch 3 taken 6 times.
|
512 | while (*one && two_len) { |
| 32 |
2/2✓ Branch 0 taken 68 times.
✓ Branch 1 taken 432 times.
|
500 | if (*one < *two_end) |
| 33 | 68 | return -1; | |
| 34 |
2/2✓ Branch 0 taken 79 times.
✓ Branch 1 taken 353 times.
|
432 | else if (*one > *two_end) |
| 35 | 79 | return 1; | |
| 36 | |||
| 37 | 353 | ++one; | |
| 38 | 353 | --two_end; | |
| 39 | 353 | --two_len; | |
| 40 | } | ||
| 41 | |||
| 42 |
2/2✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
|
12 | if (0 != *one) |
| 43 | 6 | return 1; | |
| 44 | |||
| 45 | 6 | return 0; | |
| 46 | } | ||
| 47 | |||
| 48 | 4 | void i360_initialize_rev_ordered_set(struct reversed_ordered_set_t *set, unsigned num, void *storage) { | |
| 49 | 4 | const unsigned size = sizeof(char *) * num; | |
| 50 | |||
| 51 |
1/2✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
|
4 | set->keys = storage ? (char **)brp_malloc(storage, size) : malloc(size); |
| 52 | 4 | memset(set->keys, 0, size); | |
| 53 | 4 | set->num = 0; | |
| 54 | 4 | set->max = num; | |
| 55 | 4 | set->storage = storage; | |
| 56 | 4 | } | |
| 57 | |||
| 58 | 4 | void i360_deallocated_rev_ordered_set(struct reversed_ordered_set_t *set) { | |
| 59 |
2/2✓ Branch 0 taken 300 times.
✓ Branch 1 taken 4 times.
|
304 | while (set->num) { |
| 60 |
1/2✓ Branch 0 taken 300 times.
✗ Branch 1 not taken.
|
300 | if (set->storage) |
| 61 | 300 | brp_free(set->storage, set->keys[set->num - 1]); | |
| 62 | else | ||
| 63 | ✗ | free(set->keys[set->num - 1]); | |
| 64 | 300 | --set->num; | |
| 65 | } | ||
| 66 | |||
| 67 |
1/2✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
|
4 | if (set->storage) |
| 68 | 4 | brp_free(set->storage, set->keys); | |
| 69 | else | ||
| 70 | ✗ | free(set->keys); | |
| 71 | 4 | } | |
| 72 | |||
| 73 | 305 | static inline unsigned i360_rev_ordered_sub_find(struct reversed_ordered_set_t *set, char *key_end, unsigned len, | |
| 74 | unsigned *last_cmp) { | ||
| 75 | 305 | unsigned left = 0, right = set->num, middle = 0; | |
| 76 | int cmp; | ||
| 77 | char *middle_key; | ||
| 78 | |||
| 79 |
2/2✓ Branch 0 taken 1597 times.
✓ Branch 1 taken 303 times.
|
1900 | while (left < right) { |
| 80 | 1597 | middle = (left + right) >> 1; | |
| 81 | 1597 | middle_key = set->keys[middle]; | |
| 82 | |||
| 83 | 1597 | cmp = i360_default_rev_compare_keys(middle_key, key_end, len); | |
| 84 | |||
| 85 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 1595 times.
|
1597 | if (0 == cmp) { |
| 86 | 2 | *last_cmp = cmp; | |
| 87 | 2 | return middle; | |
| 88 | } | ||
| 89 | |||
| 90 |
2/2✓ Branch 0 taken 862 times.
✓ Branch 1 taken 733 times.
|
1595 | if (0 > cmp) |
| 91 | 862 | left = middle + 1; | |
| 92 | else | ||
| 93 | 733 | right = middle; | |
| 94 | } | ||
| 95 | |||
| 96 | 303 | *last_cmp = 1; | |
| 97 | 303 | return left; | |
| 98 | } | ||
| 99 | |||
| 100 | 3 | int i360_rev_ordered_find(struct reversed_ordered_set_t *set, char *key, unsigned len) { | |
| 101 | unsigned cmp; | ||
| 102 | 3 | char *key_end = key + len - 1; | |
| 103 | 3 | const unsigned index = i360_rev_ordered_sub_find(set, key_end, len, &cmp); | |
| 104 | |||
| 105 |
2/2✓ Branch 0 taken 1 time.
✓ Branch 1 taken 2 times.
|
3 | if (0 == cmp) |
| 106 | 1 | return index; | |
| 107 | |||
| 108 | 3 | return -1; | |
| 109 | } | ||
| 110 | |||
| 111 | 302 | int i360_rev_ordered_set_insert(struct reversed_ordered_set_t *set, char *key, unsigned key_len) { | |
| 112 | unsigned cmp; | ||
| 113 | 302 | char *key_end = key + key_len - 1; | |
| 114 | 302 | const unsigned index = i360_rev_ordered_sub_find(set, key_end, key_len, &cmp); | |
| 115 | |||
| 116 |
2/2✓ Branch 0 taken 1 time.
✓ Branch 1 taken 301 times.
|
302 | if (0 == cmp) |
| 117 | /* for the moment being caller just ignores the result */ | ||
| 118 | 1 | return index; | |
| 119 | |||
| 120 |
2/2✓ Branch 0 taken 1 time.
✓ Branch 1 taken 300 times.
|
301 | if (set->num == set->max) |
| 121 | 1 | return -1; | |
| 122 | |||
| 123 | // shift | ||
| 124 | 300 | memmove(&(set->keys[index + 1]), &(set->keys[index]), (set->num - index) * sizeof(char *)); | |
| 125 |
1/2✓ Branch 0 taken 300 times.
✗ Branch 1 not taken.
|
300 | set->keys[index] = set->storage ? (char *)brp_malloc(set->storage, key_len + 1) : (char *)malloc(key_len + 1); |
| 126 | 300 | ++set->num; | |
| 127 | |||
| 128 | // assign new key and reverse | ||
| 129 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 300 times.
|
300 | if (!key_len) { |
| 130 | ✗ | (*set->keys[index]) = 0; | |
| 131 | } | ||
| 132 | else { | ||
| 133 | 300 | char *new_key = set->keys[index]; | |
| 134 | |||
| 135 |
2/2✓ Branch 0 taken 576 times.
✓ Branch 1 taken 300 times.
|
876 | while (key_len) { |
| 136 | 576 | *new_key = *key_end; | |
| 137 | 576 | ++new_key; | |
| 138 | 576 | --key_end; | |
| 139 | 576 | --key_len; | |
| 140 | } | ||
| 141 | |||
| 142 | 300 | *new_key = 0; | |
| 143 | } | ||
| 144 | |||
| 145 | 302 | return index; | |
| 146 | } | ||
| 147 | |||
| 148 | 23 | static inline unsigned i360_rev_ordered_sub_find_partial(struct reversed_ordered_set_t *set, char *key_end, | |
| 149 | unsigned len, unsigned *last_cmp) { | ||
| 150 | 23 | unsigned left = 0, right = set->num, middle = 0; | |
| 151 | int cmp; | ||
| 152 | char *middle_key; | ||
| 153 | |||
| 154 |
2/2✓ Branch 0 taken 159 times.
✓ Branch 1 taken 17 times.
|
176 | while (left < right) { |
| 155 | 159 | middle = (left + right) >> 1; | |
| 156 | 159 | middle_key = set->keys[middle]; | |
| 157 | |||
| 158 | 159 | cmp = i360_partial_rev_compare_keys(middle_key, key_end, len); | |
| 159 | |||
| 160 |
2/2✓ Branch 0 taken 6 times.
✓ Branch 1 taken 153 times.
|
159 | if (0 == cmp) { |
| 161 | 6 | *last_cmp = cmp; | |
| 162 | 6 | return middle; | |
| 163 | } | ||
| 164 | |||
| 165 |
2/2✓ Branch 0 taken 68 times.
✓ Branch 1 taken 85 times.
|
153 | if (0 > cmp) |
| 166 | 68 | left = middle + 1; | |
| 167 | else | ||
| 168 | 85 | right = middle; | |
| 169 | } | ||
| 170 | |||
| 171 | 17 | *last_cmp = 1; | |
| 172 | 17 | return left; | |
| 173 | } | ||
| 174 | |||
| 175 | 23 | int i360_rev_ordered_find_partial(struct reversed_ordered_set_t *set, char *key, unsigned len) { | |
| 176 | unsigned cmp; | ||
| 177 | 23 | char *key_end = key + len - 1; | |
| 178 | 23 | const unsigned index = i360_rev_ordered_sub_find_partial(set, key_end, len, &cmp); | |
| 179 | |||
| 180 |
2/2✓ Branch 0 taken 6 times.
✓ Branch 1 taken 17 times.
|
23 | if (0 == cmp) |
| 181 | 6 | return index; | |
| 182 | |||
| 183 | 23 | return -1; | |
| 184 | } | ||
| 185 |