pintos-os.org Git - pspp/blob - src/libpspp/sparse-array.h

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2007, 2009 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 /* Sparse array data structure.
  18
  19    Implements a dictionary that associates a "unsigned long int"
  20    key with fixed-size values (elements).
  21
  22    The implementation allocates elements in groups of moderate
  23    size, so it achieves maximum space efficiency when elements
  24    are clustered into groups of consecutive keys.  For the same
  25    reason, elements should be kept relatively small, perhaps a
  26    few pointer elements in size.
  27
  28    The implementation is slightly more efficient both in time and
  29    space when indexes are kept small.  Thus, for example, if the
  30    indexes in use start from some fixed base value, consider
  31    using the offset from that base as the index value. */
  32
  33 #ifndef LIBPSPP_SPARSE_ARRAY_H
  34 #define LIBPSPP_SPARSE_ARRAY_H 1
  35
  36 #include <stddef.h>
  37 #include <stdbool.h>
  38
  39 struct pool;
  40
  41 struct sparse_array *sparse_array_create (size_t elem_size);
  42 struct sparse_array *sparse_array_create_pool (struct pool *,
  43                                                size_t elem_size);
  44 void sparse_array_destroy (struct sparse_array *);
  45
  46 unsigned long int sparse_array_count (const struct sparse_array *);
  47
  48 void *sparse_array_insert (struct sparse_array *, unsigned long int key);
  49 void *sparse_array_get (const struct sparse_array *, unsigned long int key);
  50 bool sparse_array_remove (struct sparse_array *, unsigned long int key);
  51
  52 void *sparse_array_first (const struct sparse_array *,
  53                           unsigned long int *idxp);
  54 void *sparse_array_next (const struct sparse_array *,
  55                          unsigned long int skip, unsigned long int *idxp);
  56 void *sparse_array_last (const struct sparse_array *,
  57                           unsigned long int *idxp);
  58 void *sparse_array_prev (const struct sparse_array *,
  59                          unsigned long int skip, unsigned long int *idxp);
  60
  61 #endif /* libpspp/sparse-array.h */