gui: Allow File|Open to select an encoding for system files.
[pspp] / src / libpspp / deque.c
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
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 *
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 *
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 }