lib/bitset-int.h

   1 /* Internal bitset definitions.
   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 _BITSET_INT_H
  20 #define _BITSET_INT_H
  21
  22 #ifdef HAVE_LIMITS_H
  23 #include <limits.h>
  24 #endif
  25
  26 /* Currently we support three flavours of bitsets:
  27    BITSET_ARRAY:  Array of bits (fixed size, faster).
  28    BITSET_LIST:   Linked list of array of bits (variable size, least storage
  29    for large very sparse sets).
  30    BITSET_TABLE:  Expandable table of pointers to array of bits
  31    (variable size, less storage for large sparse sets).
  32 */
  33 enum bitset_type {BITSET_ARRAY, BITSET_LIST, BITSET_TABLE, BITSET_TYPE_NUM};
  34 #define BITSET__TYPE_NAMES {"sbitset", "lbitset", "ebitset"}
  35
  36 /* Non-zero to enable bitset caching.  */
  37 #define BITSET_CACHE 1
  38
  39 /* Non-zero to use inline functions instead of macros.  */
  40 #define BITSET_INLINE 0
  41
  42 /* Non-zero to enable bitset statistics gathering.  */
  43 #define BITSET_STATS 1
  44
  45 /* Non-zero to enable bitset type checking.  */
  46 #define BITSET_CHECK 0
  47
  48 typedef unsigned long bitset_word;
  49 #define BITSET_WORD_BITS ((unsigned) CHAR_BIT * sizeof (bitset_word))
  50
  51 /* Bit index.  */
  52 typedef unsigned long bitset_bindex;
  53
  54 /* Word index.  */
  55 typedef unsigned long bitset_windex;
  56
  57 #define BITSET_INDEX_MAX ((1U << (BITSET_WORD_BITS - 1)))
  58
  59 #define BITSET_MSB (1U << (BITSET_WORD_BITS - 1))
  60
  61 #define BITSET_LIST_SIZE 1024
  62
  63 enum bitset_ops {BITSET_ZERO, BITSET_ONES, BITSET_EMPTY_P,
  64                  BITSET_COPY, BITSET_EQUAL_P, BITSET_SUBSET_P, BITSET_NOT,
  65                  BITSET_AND, BITSET_OR, BITSET_XOR, BITSET_ANDN, BITSET_ORN,
  66                  BITSET_OR_AND, BITSET_AND_OR, BITSET_ANDN_OR};
  67
  68 /* Return size in bits of bitset SRC.  */
  69 #define BITSET__SIZE(SRC) (SRC)->ops->size (SRC)
  70
  71 /* Set bit BITNO in bitset DST.  */
  72 #define BITSET__SET(DST, BITNO) (DST)->ops->set (DST, BITNO)
  73
  74 /* Reset bit BITNO in bitset DST.  */
  75 #define BITSET__RESET(DST, BITNO) (DST)->ops->reset (DST, BITNO)
  76
  77 /* Return non-zero if bit BITNO in bitset SRC is set.  */
  78 #define BITSET__TEST(SRC, BITNO) (SRC)->ops->test (SRC, BITNO)
  79
  80 /* Free bitset SRC.  */
  81 #define BITSET__FREE(SRC) ((SRC)->ops->free) (SRC)
  82
  83 /* Perform operation OP on DST.  */
  84 #define BITSET__OP1(DST, OP) (DST)->ops->op1 (DST, OP)
  85
  86 /* Perform operation OP on SRC and store in DST.  */
  87 #define BITSET__OP2(DST, SRC, OP) (DST)->ops->op2 (DST, SRC, OP)
  88
  89 /* DST = SRC1 OP SRC2.  */
  90 #define BITSET__OP3(DST, SRC1, SRC2, OP) \
  91 (DST)->ops->op3 (DST, SRC1, SRC2, OP)
  92
  93 /* DST = (SRC1 OP1 SRC2) OP2 SRC3.  */
  94 #define BITSET__OP4(DST, SRC1, SRC2, SRC3, OP) \
  95 (DST)->ops->op4 (DST, SRC1, SRC2, SRC3, OP)
  96
  97 /* DST = SRC.  */
  98 #define BITSET__COPY(DST, SRC) BITSET__OP2 (DST, SRC, BITSET_COPY)
  99
 100 /* Find list of up to NUM bits set in BSET starting from and including
 101    *NEXT.  Return with actual number of bits found and with *NEXT
 102    indicating where search stopped.  */
 103 #define BITSET__LIST(BSET, LIST, NUM, NEXT) \
 104 (BSET)->ops->list (BSET, LIST, NUM, NEXT)
 105
 106 /* Find reverse list of up to NUM bits set in BSET starting from and
 107    including NEXT.  Return with actual number of bits found and with
 108    *NEXT indicating where search stopped.  */
 109 #define BITSET__REVERSE_LIST(BSET, LIST, NUM, NEXT) \
 110 (BSET)->ops->reverse_list (BSET, LIST, NUM, NEXT)
 111
 112 #endif /* _BITSET_INT_H  */