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 }