Change license from GPLv2+ to GPLv3+.
[pspp-builds.git] / src / libpspp / deque.c
1 /* PSPP - a program for statistical analysis.
2    Copyright (C) 2007 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 #include <string.h>
21
22 #include "minmax.h"
23 #include "xalloc.h"
24
25 /* Initializes DEQUE as an empty deque with an initial capacity
26    of zero. */
27 void
28 deque_init_null (struct deque *deque)
29 {
30   deque->capacity = 0;
31   deque->front = 0;
32   deque->back = 0;
33 }
34
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. */
38 void *
39 deque_init (struct deque *deque, size_t capacity, size_t elem_size)
40 {
41   void *data = NULL;
42   deque_init_null (deque);
43   if (capacity > 0)
44     {
45       deque->capacity = 1;
46       while (deque->capacity < capacity)
47         deque->capacity <<= 1;
48       data = xnmalloc (deque->capacity, elem_size);
49     }
50   return data;
51 }
52
53 /* Increases the capacity of DEQUE and returns a new deque data
54    array that replaces the old data array. */
55 void *
56 deque_expand (struct deque *deque, void *old_data_, size_t elem_size)
57 {
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);
62   size_t idx, copy_cnt;
63   for (idx = deque->back; idx != deque->front; idx += copy_cnt)
64     {
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);
71     }
72   deque->capacity = new_capacity;
73   free (old_data);
74   return new_data;
75 }