diff options
| author | Thomas Schmucker <ts@its1.de> | 2020-08-15 09:27:30 +0200 |
|---|---|---|
| committer | Thomas Schmucker <ts@its1.de> | 2020-08-15 09:27:30 +0200 |
| commit | 7028633c6c6211a01bcad0515499a4cb893ea646 (patch) | |
| tree | d894746fe342cadb01820fa06693d89ab7685bec /deque.c | |
| parent | eceae48ed4ab43cfe013fbe5b674ed9de80f7a3b (diff) | |
| download | data-structures-7028633c6c6211a01bcad0515499a4cb893ea646.tar.gz data-structures-7028633c6c6211a01bcad0515499a4cb893ea646.tar.bz2 data-structures-7028633c6c6211a01bcad0515499a4cb893ea646.zip | |
code cleanup
Diffstat (limited to 'deque.c')
| -rw-r--r-- | deque.c | 45 |
1 files changed, 28 insertions, 17 deletions
| @@ -114,8 +114,9 @@ map_prepend_chunk(struct deque *d) | |||
| 114 | static void | 114 | static void |
| 115 | map_remove_front_chunk(struct deque *d) | 115 | map_remove_front_chunk(struct deque *d) |
| 116 | { | 116 | { |
| 117 | if ( d->map_begin == d->map_end ) | 117 | if ( d->map_begin == d->map_end ) { |
| 118 | return; | 118 | return; |
| 119 | } | ||
| 119 | 120 | ||
| 120 | const size_t next = (d->map_begin + 1) % d->map_capacity; | 121 | const size_t next = (d->map_begin + 1) % d->map_capacity; |
| 121 | 122 | ||
| @@ -128,8 +129,9 @@ map_remove_front_chunk(struct deque *d) | |||
| 128 | static void | 129 | static void |
| 129 | map_remove_tail_chunk(struct deque *d) | 130 | map_remove_tail_chunk(struct deque *d) |
| 130 | { | 131 | { |
| 131 | if ( d->map_begin == d->map_end ) | 132 | if ( d->map_begin == d->map_end ) { |
| 132 | return; | 133 | return; |
| 134 | } | ||
| 133 | 135 | ||
| 134 | const size_t prev = (d->map_end + d->map_capacity - 1) % d->map_capacity; | 136 | const size_t prev = (d->map_end + d->map_capacity - 1) % d->map_capacity; |
| 135 | 137 | ||
| @@ -139,29 +141,36 @@ map_remove_tail_chunk(struct deque *d) | |||
| 139 | d->map_end = prev; | 141 | d->map_end = prev; |
| 140 | } | 142 | } |
| 141 | 143 | ||
| 142 | void | 144 | bool |
| 143 | deque_get_at(struct deque *d, size_t idx, T *data) | 145 | deque_get_at(struct deque *d, size_t idx, T *data) |
| 144 | { | 146 | { |
| 145 | const size_t offset = d->offset + idx; | 147 | if ( idx >= d->size ) { |
| 146 | const size_t chunk_off = offset % CHUNK_CAPACITY; | 148 | return false; |
| 147 | const size_t chunk_num = (offset / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; | 149 | } |
| 150 | |||
| 151 | const size_t pos = d->offset + idx; | ||
| 152 | const size_t chunk_off = pos % CHUNK_CAPACITY; | ||
| 153 | const size_t chunk_num = (pos / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; | ||
| 148 | 154 | ||
| 149 | *data = d->map[chunk_num][chunk_off]; | 155 | *data = d->map[chunk_num][chunk_off]; |
| 156 | |||
| 157 | return true; | ||
| 150 | } | 158 | } |
| 151 | 159 | ||
| 152 | void | 160 | void |
| 153 | deque_push_back(struct deque *d, T data) | 161 | deque_push_back(struct deque *d, T data) |
| 154 | { | 162 | { |
| 155 | const size_t offset = d->offset + d->size; | 163 | const size_t pos = d->offset + d->size; |
| 156 | const size_t chunk_off = offset % CHUNK_CAPACITY; | 164 | const size_t chunk_off = pos % CHUNK_CAPACITY; |
| 157 | size_t chunk_num = (offset / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; | 165 | size_t chunk_num = (pos / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; |
| 158 | 166 | ||
| 159 | if ( chunk_num == d->map_end ) { | 167 | if ( chunk_num == d->map_end ) { |
| 160 | map_append_chunk(d); | 168 | map_append_chunk(d); |
| 161 | chunk_num = (offset / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; | 169 | chunk_num = (pos / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; |
| 162 | } | 170 | } |
| 163 | 171 | ||
| 164 | d->map[chunk_num][chunk_off] = data; | 172 | d->map[chunk_num][chunk_off] = data; |
| 173 | |||
| 165 | ++d->size; | 174 | ++d->size; |
| 166 | } | 175 | } |
| 167 | 176 | ||
| @@ -176,7 +185,7 @@ deque_push_front(struct deque *d, T data) | |||
| 176 | ++d->size; | 185 | ++d->size; |
| 177 | --d->offset; | 186 | --d->offset; |
| 178 | 187 | ||
| 179 | size_t chunk_num = (d->offset / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; | 188 | const size_t chunk_num = (d->offset / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; |
| 180 | 189 | ||
| 181 | d->map[chunk_num][d->offset] = data; | 190 | d->map[chunk_num][d->offset] = data; |
| 182 | } | 191 | } |
| @@ -184,14 +193,15 @@ deque_push_front(struct deque *d, T data) | |||
| 184 | bool | 193 | bool |
| 185 | deque_pop_back(struct deque *d, T *data) | 194 | deque_pop_back(struct deque *d, T *data) |
| 186 | { | 195 | { |
| 187 | if ( d->size == 0 ) | 196 | if ( d->size == 0 ) { |
| 188 | return false; | 197 | return false; |
| 198 | } | ||
| 189 | 199 | ||
| 190 | --d->size; | 200 | --d->size; |
| 191 | 201 | ||
| 192 | const size_t offset = d->offset + d->size; | 202 | const size_t pos = d->offset + d->size; |
| 193 | const size_t chunk_off = offset % CHUNK_CAPACITY; | 203 | const size_t chunk_off = pos % CHUNK_CAPACITY; |
| 194 | const size_t chunk_num = (offset / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; | 204 | const size_t chunk_num = (pos / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; |
| 195 | 205 | ||
| 196 | *data = d->map[chunk_num][chunk_off]; | 206 | *data = d->map[chunk_num][chunk_off]; |
| 197 | 207 | ||
| @@ -205,8 +215,9 @@ deque_pop_back(struct deque *d, T *data) | |||
| 205 | bool | 215 | bool |
| 206 | deque_pop_front(struct deque *d, T *data) | 216 | deque_pop_front(struct deque *d, T *data) |
| 207 | { | 217 | { |
| 208 | if ( d->size == 0 ) | 218 | if ( d->size == 0 ) { |
| 209 | return false; | 219 | return false; |
| 220 | } | ||
| 210 | 221 | ||
| 211 | const size_t chunk_num = (d->offset / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; | 222 | const size_t chunk_num = (d->offset / CHUNK_CAPACITY + d->map_begin) % d->map_capacity; |
| 212 | 223 | ||
| @@ -231,7 +242,7 @@ deque_show(struct deque *d) | |||
| 231 | for ( size_t i = 0; i != d->map_capacity; ++i ) { | 242 | for ( size_t i = 0; i != d->map_capacity; ++i ) { |
| 232 | printf("%zu(%p) ", i, (void *) d->map[i]); | 243 | printf("%zu(%p) ", i, (void *) d->map[i]); |
| 233 | } | 244 | } |
| 234 | puts(""); | 245 | putchar('\n'); |
| 235 | } | 246 | } |
| 236 | 247 | ||
| 237 | int | 248 | int |
