1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2007 Free Software Foundation, Inc.
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.
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.
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/>. */
19 #include <libpspp/deque.h>
25 /* Initializes DEQUE as an empty deque with an initial capacity
28 deque_init_null (struct deque *deque)
35 /* Initializes DEQUE as an empty deque of elements ELEM_SIZE
36 bytes in size, with an initial capacity of at least
37 CAPACITY. Returns the initial deque data array. */
39 deque_init (struct deque *deque, size_t capacity, size_t elem_size)
42 deque_init_null (deque);
46 while (deque->capacity < capacity)
47 deque->capacity <<= 1;
48 data = xnmalloc (deque->capacity, elem_size);
53 /* Increases the capacity of DEQUE and returns a new deque data
54 array that replaces the old data array. */
56 deque_expand (struct deque *deque, void *old_data_, size_t elem_size)
58 size_t old_capacity = deque->capacity;
59 size_t new_capacity = MAX (4, old_capacity * 2);
60 char *old_data = old_data_;
61 char *new_data = xnmalloc (new_capacity, elem_size);
63 for (idx = deque->back; idx != deque->front; idx += copy_cnt)
65 size_t can_copy = old_capacity - (idx & (old_capacity - 1));
66 size_t want_copy = deque->front - idx;
67 copy_cnt = MIN (can_copy, want_copy);
68 memcpy (new_data + (idx & (new_capacity - 1)) * elem_size,
69 old_data + (idx & (old_capacity - 1)) * elem_size,
70 copy_cnt * elem_size);
72 deque->capacity = new_capacity;