1 /* PSPP - computes sample statistics.
2 Copyright (C) 2007 Free Software Foundation, Inc.
4 This program is free software; you can redistribute it and/or
5 modify it under the terms of the GNU General Public License as
6 published by the Free Software Foundation; either version 2 of the
7 License, or (at your option) any later version.
9 This program is distributed in the hope that it will be useful, but
10 WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 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, write to the Free Software
16 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
21 #include <libpspp/deque.h>
27 /* Initializes DEQUE as an empty deque with an initial capacity
30 deque_init_null (struct deque *deque)
37 /* Initializes DEQUE as an empty deque of elements ELEM_SIZE
38 bytes in size, with an initial capacity of at least
39 CAPACITY. Returns the initial deque data array. */
41 deque_init (struct deque *deque, size_t capacity, size_t elem_size)
44 deque_init_null (deque);
48 while (deque->capacity < capacity)
49 deque->capacity <<= 1;
50 data = xnmalloc (deque->capacity, elem_size);
55 /* Increases the capacity of DEQUE and returns a new deque data
56 array that replaces the old data array. */
58 deque_expand (struct deque *deque, void *old_data_, size_t elem_size)
60 size_t old_capacity = deque->capacity;
61 size_t new_capacity = MAX (4, old_capacity * 2);
62 char *old_data = old_data_;
63 char *new_data = xnmalloc (new_capacity, elem_size);
65 for (idx = deque->back; idx != deque->front; idx += copy_cnt)
67 size_t can_copy = old_capacity - (idx & (old_capacity - 1));
68 size_t want_copy = deque->front - idx;
69 copy_cnt = MIN (can_copy, want_copy);
70 memcpy (new_data + (idx & (new_capacity - 1)) * elem_size,
71 old_data + (idx & (old_capacity - 1)) * elem_size,
72 copy_cnt * elem_size);
74 deque->capacity = new_capacity;