aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorThomas Schmucker <ts@its1.de>2020-08-15 09:27:30 +0200
committerThomas Schmucker <ts@its1.de>2020-08-15 09:27:30 +0200
commit7028633c6c6211a01bcad0515499a4cb893ea646 (patch)
treed894746fe342cadb01820fa06693d89ab7685bec
parenteceae48ed4ab43cfe013fbe5b674ed9de80f7a3b (diff)
downloaddata-structures-7028633c6c6211a01bcad0515499a4cb893ea646.tar.gz
data-structures-7028633c6c6211a01bcad0515499a4cb893ea646.tar.bz2
data-structures-7028633c6c6211a01bcad0515499a4cb893ea646.zip
code cleanup
-rw-r--r--deque.c45
1 files changed, 28 insertions, 17 deletions
diff --git a/deque.c b/deque.c
index e019adc..3e78410 100644
--- a/deque.c
+++ b/deque.c
@@ -114,8 +114,9 @@ map_prepend_chunk(struct deque *d)
114static void 114static void
115map_remove_front_chunk(struct deque *d) 115map_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)
128static void 129static void
129map_remove_tail_chunk(struct deque *d) 130map_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
142void 144bool
143deque_get_at(struct deque *d, size_t idx, T *data) 145deque_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
152void 160void
153deque_push_back(struct deque *d, T data) 161deque_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)
184bool 193bool
185deque_pop_back(struct deque *d, T *data) 194deque_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)
205bool 215bool
206deque_pop_front(struct deque *d, T *data) 216deque_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
237int 248int