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 }