1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2007, 2011 Free Software Foundation, Inc.
3
4 This program is free software: you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation, either version 3 of the License, or
7 (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see <http://www.gnu.org/licenses/>. */
16
17 #include <config.h>
18
19 #include "libpspp/deque.h"
20
21 #include <string.h>
22
23 #include "gl/minmax.h"
24 #include "gl/xalloc.h"
25
26 /* Initializes DEQUE as an empty deque with an initial capacity
27 of zero. */
28 void
deque_init_null(struct deque * deque)29 deque_init_null (struct deque *deque)
30 {
31 deque->capacity = 0;
32 deque->front = 0;
33 deque->back = 0;
34 }
35
36 /* Initializes DEQUE as an empty deque of elements ELEM_SIZE
37 bytes in size, with an initial capacity of at least
38 CAPACITY. Returns the initial deque data array. */
39 void *
deque_init(struct deque * deque,size_t capacity,size_t elem_size)40 deque_init (struct deque *deque, size_t capacity, size_t elem_size)
41 {
42 void *data = NULL;
43 deque_init_null (deque);
44 if (capacity > 0)
45 {
46 deque->capacity = 1;
47 while (deque->capacity < capacity)
48 deque->capacity <<= 1;
49 data = xnmalloc (deque->capacity, elem_size);
50 }
51 return data;
52 }
53
54 /* Increases the capacity of DEQUE and returns a new deque data
55 array that replaces the old data array. */
56 void *
deque_expand(struct deque * deque,void * old_data_,size_t elem_size)57 deque_expand (struct deque *deque, void *old_data_, size_t elem_size)
58 {
59 size_t old_capacity = deque->capacity;
60 size_t new_capacity = MAX (4, old_capacity * 2);
61 char *old_data = old_data_;
62 char *new_data = xnmalloc (new_capacity, elem_size);
63 size_t idx, copy_cnt;
64 for (idx = deque->back; idx != deque->front; idx += copy_cnt)
65 {
66 size_t can_copy = old_capacity - (idx & (old_capacity - 1));
67 size_t want_copy = deque->front - idx;
68 copy_cnt = MIN (can_copy, want_copy);
69 memcpy (new_data + (idx & (new_capacity - 1)) * elem_size,
70 old_data + (idx & (old_capacity - 1)) * elem_size,
71 copy_cnt * elem_size);
72 }
73 deque->capacity = new_capacity;
74 free (old_data);
75 return new_data;
76 }
77