lib/lbitset.h

   1 /* Functions to support lbitsets.
   2    Copyright (C) 2002 Free Software Foundation, Inc.
   3    Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
   4
   5 This program is free software; you can redistribute it and/or modify
   6 it under the terms of the GNU General Public License as published by
   7 the Free Software Foundation; either version 2 of the License, or
   8 (at your option) any later version.
   9
  10 This program is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 GNU General Public License for more details.
  14
  15 You should have received a copy of the GNU General Public License
  16 along with this program; if not, write to the Free Software
  17 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
  18
  19 #ifndef _LBITSET_H
  20 #define _LBITSET_H
  21
  22 #include "bitset-int.h"
  23
  24 /* Number of words to use for each element.  The larger the value the
  25    greater the size of the cache and the shorter the time to find a given bit
  26    but the more memory wasted for sparse bitsets and the longer the time
  27    to search for set bits.  */
  28 #ifndef LBITSET_ELT_WORDS
  29 #define LBITSET_ELT_WORDS 2
  30 #endif
  31
  32 typedef bitset_word lbitset_word;
  33 #define LBITSET_WORD_BITS BITSET_WORD_BITS
  34
  35 /* Number of bits stored in each element.  */
  36 #define LBITSET_ELT_BITS \
  37   ((unsigned) (LBITSET_ELT_WORDS * LBITSET_WORD_BITS))
  38
  39 /* Lbitset element.   We use an array of bits for each element.
  40    These are linked together in a doubly-linked list.  */
  41 typedef struct lbitset_elt_struct
  42 {
  43   struct lbitset_elt_struct *next; /* Next element.  */
  44   struct lbitset_elt_struct *prev; /* Previous element.  */
  45   bitset_windex index;          /* bitno / BITSET_WORD_BITS.  */
  46   bitset_word words[LBITSET_ELT_WORDS]; /* Bits that are set.  */
  47 } lbitset_elt;
  48
  49
  50 /* Head of lbitset linked list.  */
  51 typedef struct lbitset_struct
  52 {
  53   lbitset_elt *head;            /* First element in linked list.  */
  54   lbitset_elt *tail;            /* Last element in linked list.  */
  55 } *lbitset;
  56
  57
  58 extern int lbitset_bytes PARAMS ((bitset_bindex));
  59
  60 extern void lbitset_release_memory PARAMS ((void));
  61
  62 #endif