src/libpspp/deque.c

   1 /* PSPP - computes sample statistics.
   2    Copyright (C) 2007 Free Software Foundation, Inc.
   3
   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.
   8
   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.
  13
  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
  17    02110-1301, USA. */
  18
  19 #include <config.h>
  20
  21 #include <libpspp/deque.h>
  22 #include <string.h>
  23
  24 #include "minmax.h"
  25 #include "xalloc.h"
  26
  27 /* Initializes DEQUE as an empty deque with an initial capacity
  28    of zero. */
  29 void
  30 deque_init_null (struct deque *deque)
  31 {
  32   deque->capacity = 0;
  33   deque->front = 0;
  34   deque->back = 0;
  35 }
  36
  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. */
  40 void *
  41 deque_init (struct deque *deque, size_t capacity, size_t elem_size)
  42 {
  43   void *data = NULL;
  44   deque_init_null (deque);
  45   if (capacity > 0)
  46     {
  47       deque->capacity = 1;
  48       while (deque->capacity < capacity)
  49         deque->capacity <<= 1;
  50       data = xnmalloc (deque->capacity, elem_size);
  51     }
  52   return data;
  53 }
  54
  55 /* Increases the capacity of DEQUE and returns a new deque data
  56    array that replaces the old data array. */
  57 void *
  58 deque_expand (struct deque *deque, void *old_data_, size_t elem_size)
  59 {
  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);
  64   size_t idx, copy_cnt;
  65   for (idx = deque->back; idx != deque->front; idx += copy_cnt)
  66     {
  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);
  73     }
  74   deque->capacity = new_capacity;
  75   free (old_data);
  76   return new_data;
  77 }