From dbb5ba792719088f99b58a954a53b1cdab213f0c Mon Sep 17 00:00:00 2001 From: Tucker Evans Date: Wed, 27 May 2020 04:41:40 -0400 Subject: Fix resize implementation (double ended queue). Needed to take into account circular buffer i.e. handle a split buffer (base<->end & beg<->limit) along with regular (beg<->end). --- collections/double_ended_queue.c | 35 +++++++++++++++++++++-------------- 1 file changed, 21 insertions(+), 14 deletions(-) (limited to 'collections/double_ended_queue.c') diff --git a/collections/double_ended_queue.c b/collections/double_ended_queue.c index 25f3181..b555e3a 100644 --- a/collections/double_ended_queue.c +++ b/collections/double_ended_queue.c @@ -73,25 +73,32 @@ deq *root; void deq_resize(root) deq *root; { - if (root->beg != root->base) { - memmove(root->base, root->beg, root->end - root->beg); - root->end = root->base + deq_size(root); - root->beg = root->base; - } else { - root->base = malloc(root->limit * 2 * sizeof(void*)); - assert(root->base); + void **tmp; + int size; + tmp = malloc(root->limit * 2 * sizeof(void*)); + assert(root->base); - root->base = memcpy(root->base, root->beg, root->limit * sizeof(void*)); - assert(root->base); + if (root->beg > root->end) { + /*copy beg<->limit*/ + size = (root->base + (root->limit*sizeof(void*)) - root->beg); + tmp = memcpy(tmp, root->beg, size * sizeof(void*); + assert(tmp); + /*copy base<->end*/ + tmp = memcpy(tmp + size, root->beg, + (root->end - root->base)* sizeof(void*)); + assert(tmp); + } else { + size = deq_size(root); + tmp = memcpy(tmp, root->beg, size*sizeof(void*)); + } - root->end = root->base + deq_size(root); - root->limit = root->limit * 2; + root->limit *= 2; - free(root->beg); - root->beg = root->base; - } + free(root->base); + root->base = root->beg = tmp; + root->end = root->base + size; } void* deq_index(root, index) -- cgit v1.1