kc3-lang/gnulib/lib/bitset/array.c

• Show log

  Commit

• Hash : 32a72f45
  Author :
  Date : 2023-01-01T01:14:21
  

  maint: run 'make update-copyright'
  

Download

• lib/bitset/array.c

• /* Array bitsets.
  
     Copyright (C) 2002-2003, 2006, 2009-2015, 2018-2023 Free Software
     Foundation, Inc.
  
     Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
  
     This program is free software: you can redistribute it and/or modify
     it under the terms of the GNU General Public License as published by
     the Free Software Foundation, either version 3 of the License, or
     (at your option) any later version.
  
     This program is distributed in the hope that it will be useful,
     but WITHOUT ANY WARRANTY; without even the implied warranty of
     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     GNU General Public License for more details.
  
     You should have received a copy of the GNU General Public License
     along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  
  #include <config.h>
  
  #include "bitset/array.h"
  #include <stddef.h>
  #include <stdlib.h>
  #include <string.h>
  
  /* This file implements fixed size bitsets stored as an array
     of words.  Any unused bits in the last word must be zero.  */
  
  #define ABITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS)
  #define ABITSET_WORDS(X) ((X)->a.words)
  
  
  static bitset_bindex
  abitset_resize (bitset src, bitset_bindex size)
  {
    /* These bitsets have a fixed size.  */
    if (BITSET_SIZE_ (src) != size)
      abort ();
  
    return size;
  }
  
  /* Find list of up to NUM bits set in SRC starting from and including
     *NEXT and store in array LIST.  Return with actual number of bits
     found and with *NEXT indicating where search stopped.  */
  static bitset_bindex
  abitset_small_list (bitset src, bitset_bindex *list,
                      bitset_bindex num, bitset_bindex *next)
  {
    bitset_word word = ABITSET_WORDS (src)[0];
  
    /* Short circuit common case.  */
    if (!word)
      return 0;
  
    bitset_windex size = BITSET_SIZE_ (src);
    bitset_bindex bitno = *next;
    if (bitno >= size)
      return 0;
  
    word >>= bitno;
  
    bitset_bindex count = 0;
    /* Is there enough room to avoid checking in each iteration? */
    if (num >= BITSET_WORD_BITS)
      BITSET_FOR_EACH_BIT (pos, word)
        list[count++] = bitno + pos;
    else
      BITSET_FOR_EACH_BIT (pos, word)
        {
          list[count++] = bitno + pos;
          if (count >= num)
            {
              *next = bitno + pos + 1;
              return count;
            }
        }
    *next = bitno + BITSET_WORD_BITS;
    return count;
  }
  
  
  /* Set bit BITNO in bitset DST.  */
  static void
  abitset_set (MAYBE_UNUSED bitset dst, MAYBE_UNUSED bitset_bindex bitno)
  {
    /* This should never occur for abitsets since we should always hit
       the cache.  It is likely someone is trying to access outside the
       bounds of the bitset.  */
    abort ();
  }
  
  
  /* Reset bit BITNO in bitset DST.  */
  static void
  abitset_reset (MAYBE_UNUSED bitset dst,
                 MAYBE_UNUSED bitset_bindex bitno)
  {
    /* This should never occur for abitsets since we should always hit
       the cache.  It is likely someone is trying to access outside the
       bounds of the bitset.  Since the bit is zero anyway, let it pass.  */
  }
  
  
  /* Test bit BITNO in bitset SRC.  */
  static bool
  abitset_test (MAYBE_UNUSED bitset src,
                MAYBE_UNUSED bitset_bindex bitno)
  {
    /* This should never occur for abitsets since we should always
       hit the cache.  */
    return false;
  }
  
  
  /* Find list of up to NUM bits set in SRC in reverse order, starting
     from and including NEXT and store in array LIST.  Return with
     actual number of bits found and with *NEXT indicating where search
     stopped.  */
  static bitset_bindex
  abitset_list_reverse (bitset src, bitset_bindex *list,
                        bitset_bindex num, bitset_bindex *next)
  {
    bitset_bindex rbitno = *next;
    bitset_word *srcp = ABITSET_WORDS (src);
    bitset_bindex n_bits = BITSET_SIZE_ (src);
  
    /* If num is 1, we could speed things up with a binary search
       of the word of interest.  */
  
    if (rbitno >= n_bits)
      return 0;
  
    bitset_bindex count = 0;
  
    bitset_bindex bitno = n_bits - (rbitno + 1);
  
    bitset_windex windex = bitno / BITSET_WORD_BITS;
    unsigned bitcnt = bitno % BITSET_WORD_BITS;
    bitset_bindex bitoff = windex * BITSET_WORD_BITS;
  
    do
      {
        bitset_word word = srcp[windex];
        if (bitcnt + 1 < BITSET_WORD_BITS)
          /* We're starting in the middle of a word: smash bits to ignore.  */
          word &= ((bitset_word) 1 << (bitcnt + 1)) - 1;
        BITSET_FOR_EACH_BIT_REVERSE(pos, word)
          {
            list[count++] = bitoff + pos;
            if (count >= num)
              {
                *next = n_bits - (bitoff + pos);
                return count;
              }
          }
        bitoff -= BITSET_WORD_BITS;
        bitcnt = BITSET_WORD_BITS - 1;
      }
    while (windex--);
  
    *next = n_bits - (bitoff + 1);
    return count;
  }
  
  
  /* Find list of up to NUM bits set in SRC starting from and including
     *NEXT and store in array LIST.  Return with actual number of bits
     found and with *NEXT indicating where search stopped.  */
  static bitset_bindex
  abitset_list (bitset src, bitset_bindex *list,
                bitset_bindex num, bitset_bindex *next)
  {
    bitset_windex windex;
    bitset_bindex bitoff;
    bitset_windex size = src->b.csize;
    bitset_word *srcp = ABITSET_WORDS (src);
  
    bitset_bindex bitno = *next;
  
    bitset_bindex count = 0;
    if (!bitno)
      {
        /* Many bitsets are zero, so make this common case fast.  */
        for (windex = 0; windex < size && !srcp[windex]; windex++)
          continue;
        if (windex >= size)
          return 0;
  
        bitoff = windex * BITSET_WORD_BITS;
      }
    else
      {
        if (bitno >= BITSET_SIZE_ (src))
          return 0;
  
        windex = bitno / BITSET_WORD_BITS;
        bitno = bitno % BITSET_WORD_BITS;
  
        if (bitno)
          {
            /* Handle the case where we start within a word.
               Most often, this is executed with large bitsets
               with many set bits where we filled the array
               on the previous call to this function.  */
  
            bitoff = windex * BITSET_WORD_BITS;
            bitset_word word = srcp[windex] >> bitno;
            bitno = bitoff + bitno;
            BITSET_FOR_EACH_BIT (pos, word)
              {
                list[count++] = bitno + pos;
                if (count >= num)
                  {
                    *next = bitno + pos + 1;
                    return count;
                  }
              }
            windex++;
          }
        bitoff = windex * BITSET_WORD_BITS;
      }
  
    for (; windex < size; windex++, bitoff += BITSET_WORD_BITS)
      {
        bitset_word word = srcp[windex];
        if (!word)
          continue;
  
        /* Is there enough room to avoid checking in each iteration? */
        if ((count + BITSET_WORD_BITS) < num)
          BITSET_FOR_EACH_BIT (pos, word)
            list[count++] = bitoff + pos;
        else
          BITSET_FOR_EACH_BIT (pos, word)
            {
              list[count++] = bitoff + pos;
              if (count >= num)
                {
                  *next = bitoff + pos + 1;
                  return count;
                }
            }
      }
  
    *next = bitoff;
    return count;
  }
  
  
  /* Ensure that any unused bits within the last word are clear.  */
  static inline void
  abitset_unused_clear (bitset dst)
  {
    unsigned last_bit = BITSET_SIZE_ (dst) % BITSET_WORD_BITS;
    if (last_bit)
      ABITSET_WORDS (dst)[dst->b.csize - 1] &=
        ((bitset_word) 1 << last_bit) - 1;
  }
  
  
  static void
  abitset_ones (bitset dst)
  {
    bitset_word *dstp = ABITSET_WORDS (dst);
    size_t bytes = sizeof (bitset_word) * dst->b.csize;
  
    memset (dstp, -1, bytes);
    abitset_unused_clear (dst);
  }
  
  
  static void
  abitset_zero (bitset dst)
  {
    bitset_word *dstp = ABITSET_WORDS (dst);
    size_t bytes = sizeof (bitset_word) * dst->b.csize;
  
    memset (dstp, 0, bytes);
  }
  
  
  static bool
  abitset_empty_p (bitset dst)
  {
    bitset_word *dstp = ABITSET_WORDS (dst);
  
    for (bitset_windex i = 0; i < dst->b.csize; i++)
      if (dstp[i])
        return false;
    return true;
  }
  
  
  static void
  abitset_copy1 (bitset dst, bitset src)
  {
    bitset_word *srcp = ABITSET_WORDS (src);
    bitset_word *dstp = ABITSET_WORDS (dst);
    if (srcp == dstp)
      return;
    bitset_windex size = dst->b.csize;
    memcpy (dstp, srcp, sizeof (bitset_word) * size);
  }
  
  
  static void
  abitset_not (bitset dst, bitset src)
  {
    bitset_word *srcp = ABITSET_WORDS (src);
    bitset_word *dstp = ABITSET_WORDS (dst);
    bitset_windex size = dst->b.csize;
  
    for (bitset_windex i = 0; i < size; i++)
      *dstp++ = ~(*srcp++);
    abitset_unused_clear (dst);
  }
  
  
  static bool
  abitset_equal_p (bitset dst, bitset src)
  {
    bitset_word *srcp = ABITSET_WORDS (src);
    bitset_word *dstp = ABITSET_WORDS (dst);
    bitset_windex size = dst->b.csize;
  
    for (bitset_windex i = 0; i < size; i++)
      if (*srcp++ != *dstp++)
        return false;
    return true;
  }
  
  
  static bool
  abitset_subset_p (bitset dst, bitset src)
  {
    bitset_word *srcp = ABITSET_WORDS (src);
    bitset_word *dstp = ABITSET_WORDS (dst);
    bitset_windex size = dst->b.csize;
  
    for (bitset_windex i = 0; i < size; i++, dstp++, srcp++)
      if (*dstp != (*srcp | *dstp))
        return false;
    return true;
  }
  
  
  static bool
  abitset_disjoint_p (bitset dst, bitset src)
  {
    bitset_word *srcp = ABITSET_WORDS (src);
    bitset_word *dstp = ABITSET_WORDS (dst);
    bitset_windex size = dst->b.csize;
  
    for (bitset_windex i = 0; i < size; i++)
      if (*srcp++ & *dstp++)
        return false;
    return true;
  }
  
  
  static void
  abitset_and (bitset dst, bitset src1, bitset src2)
  {
    bitset_word *src1p = ABITSET_WORDS (src1);
    bitset_word *src2p = ABITSET_WORDS (src2);
    bitset_word *dstp = ABITSET_WORDS (dst);
    bitset_windex size = dst->b.csize;
  
    for (bitset_windex i = 0; i < size; i++)
      *dstp++ = *src1p++ & *src2p++;
  }
  
  
  static bool
  abitset_and_cmp (bitset dst, bitset src1, bitset src2)
  {
    bool changed = false;
    bitset_word *src1p = ABITSET_WORDS (src1);
    bitset_word *src2p = ABITSET_WORDS (src2);
    bitset_word *dstp = ABITSET_WORDS (dst);
    bitset_windex size = dst->b.csize;
  
    for (bitset_windex i = 0; i < size; i++, dstp++)
      {
        bitset_word tmp = *src1p++ & *src2p++;
        if (*dstp != tmp)
          {
            changed = true;
            *dstp = tmp;
          }
      }
    return changed;
  }
  
  
  static void
  abitset_andn (bitset dst, bitset src1, bitset src2)
  {
    bitset_word *src1p = ABITSET_WORDS (src1);
    bitset_word *src2p = ABITSET_WORDS (src2);
    bitset_word *dstp = ABITSET_WORDS (dst);
    bitset_windex size = dst->b.csize;
  
    for (bitset_windex i = 0; i < size; i++)
      *dstp++ = *src1p++ & ~(*src2p++);
  }
  
  
  static bool
  abitset_andn_cmp (bitset dst, bitset src1, bitset src2)
  {
    bool changed = false;
    bitset_word *src1p = ABITSET_WORDS (src1);
    bitset_word *src2p = ABITSET_WORDS (src2);
    bitset_word *dstp = ABITSET_WORDS (dst);
    bitset_windex size = dst->b.csize;
  
    for (bitset_windex i = 0; i < size; i++, dstp++)
      {
        bitset_word tmp = *src1p++ & ~(*src2p++);
        if (*dstp != tmp)
          {
            changed = true;
            *dstp = tmp;
          }
      }
    return changed;
  }
  
  
  static void
  abitset_or (bitset dst, bitset src1, bitset src2)
  {
    bitset_word *src1p = ABITSET_WORDS (src1);
    bitset_word *src2p = ABITSET_WORDS (src2);
    bitset_word *dstp = ABITSET_WORDS (dst);
    bitset_windex size = dst->b.csize;
  
    for (bitset_windex i = 0; i < size; i++)
      *dstp++ = *src1p++ | *src2p++;
  }
  
  
  static bool
  abitset_or_cmp (bitset dst, bitset src1, bitset src2)
  {
    bool changed = false;
    bitset_word *src1p = ABITSET_WORDS (src1);
    bitset_word *src2p = ABITSET_WORDS (src2);
    bitset_word *dstp = ABITSET_WORDS (dst);
    bitset_windex size = dst->b.csize;
  
    for (bitset_windex i = 0; i < size; i++, dstp++)
      {
        bitset_word tmp = *src1p++ | *src2p++;
  
        if (*dstp != tmp)
          {
            changed = true;
            *dstp = tmp;
          }
      }
    return changed;
  }
  
  
  static void
  abitset_xor (bitset dst, bitset src1, bitset src2)
  {
    bitset_word *src1p = ABITSET_WORDS (src1);
    bitset_word *src2p = ABITSET_WORDS (src2);
    bitset_word *dstp = ABITSET_WORDS (dst);
    bitset_windex size = dst->b.csize;
  
    for (bitset_windex i = 0; i < size; i++)
      *dstp++ = *src1p++ ^ *src2p++;
  }
  
  
  static bool
  abitset_xor_cmp (bitset dst, bitset src1, bitset src2)
  {
    bool changed = false;
    bitset_word *src1p = ABITSET_WORDS (src1);
    bitset_word *src2p = ABITSET_WORDS (src2);
    bitset_word *dstp = ABITSET_WORDS (dst);
    bitset_windex size = dst->b.csize;
  
    for (bitset_windex i = 0; i < size; i++, dstp++)
      {
        bitset_word tmp = *src1p++ ^ *src2p++;
  
        if (*dstp != tmp)
          {
            changed = true;
            *dstp = tmp;
          }
      }
    return changed;
  }
  
  
  static void
  abitset_and_or (bitset dst, bitset src1, bitset src2, bitset src3)
  {
    bitset_word *src1p = ABITSET_WORDS (src1);
    bitset_word *src2p = ABITSET_WORDS (src2);
    bitset_word *src3p = ABITSET_WORDS (src3);
    bitset_word *dstp = ABITSET_WORDS (dst);
    bitset_windex size = dst->b.csize;
  
    for (bitset_windex i = 0; i < size; i++)
      *dstp++ = (*src1p++ & *src2p++) | *src3p++;
  }
  
  
  static bool
  abitset_and_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
  {
    bool changed = false;
    bitset_word *src1p = ABITSET_WORDS (src1);
    bitset_word *src2p = ABITSET_WORDS (src2);
    bitset_word *src3p = ABITSET_WORDS (src3);
    bitset_word *dstp = ABITSET_WORDS (dst);
    bitset_windex size = dst->b.csize;
  
    for (bitset_windex i = 0; i < size; i++, dstp++)
      {
        bitset_word tmp = (*src1p++ & *src2p++) | *src3p++;
        if (*dstp != tmp)
          {
            changed = true;
            *dstp = tmp;
          }
      }
    return changed;
  }
  
  
  static void
  abitset_andn_or (bitset dst, bitset src1, bitset src2, bitset src3)
  {
    bitset_word *src1p = ABITSET_WORDS (src1);
    bitset_word *src2p = ABITSET_WORDS (src2);
    bitset_word *src3p = ABITSET_WORDS (src3);
    bitset_word *dstp = ABITSET_WORDS (dst);
    bitset_windex size = dst->b.csize;
  
    for (bitset_windex i = 0; i < size; i++)
      *dstp++ = (*src1p++ & ~(*src2p++)) | *src3p++;
  }
  
  
  static bool
  abitset_andn_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
  {
    bool changed = false;
    bitset_word *src1p = ABITSET_WORDS (src1);
    bitset_word *src2p = ABITSET_WORDS (src2);
    bitset_word *src3p = ABITSET_WORDS (src3);
    bitset_word *dstp = ABITSET_WORDS (dst);
    bitset_windex size = dst->b.csize;
  
    for (bitset_windex i = 0; i < size; i++, dstp++)
      {
        bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++;
        if (*dstp != tmp)
          {
            changed = true;
            *dstp = tmp;
          }
      }
    return changed;
  }
  
  
  static void
  abitset_or_and (bitset dst, bitset src1, bitset src2, bitset src3)
  {
    bitset_word *src1p = ABITSET_WORDS (src1);
    bitset_word *src2p = ABITSET_WORDS (src2);
    bitset_word *src3p = ABITSET_WORDS (src3);
    bitset_word *dstp = ABITSET_WORDS (dst);
    bitset_windex size = dst->b.csize;
  
    for (bitset_windex i = 0; i < size; i++)
      *dstp++ = (*src1p++ | *src2p++) & *src3p++;
  }
  
  
  static bool
  abitset_or_and_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
  {
    bool changed = false;
    bitset_word *src1p = ABITSET_WORDS (src1);
    bitset_word *src2p = ABITSET_WORDS (src2);
    bitset_word *src3p = ABITSET_WORDS (src3);
    bitset_word *dstp = ABITSET_WORDS (dst);
    bitset_windex size = dst->b.csize;
  
    for (bitset_windex i = 0; i < size; i++, dstp++)
      {
        bitset_word tmp = (*src1p++ | *src2p++) & *src3p++;
        if (*dstp != tmp)
          {
            changed = true;
            *dstp = tmp;
          }
      }
    return changed;
  }
  
  
  static void
  abitset_copy (bitset dst, bitset src)
  {
    if (BITSET_COMPATIBLE_ (dst, src))
      abitset_copy1 (dst, src);
    else
      bitset_copy_ (dst, src);
  }
  
  
  /* Vector of operations for single word bitsets.  */
  struct bitset_vtable abitset_small_vtable = {
    abitset_set,
    abitset_reset,
    bitset_toggle_,
    abitset_test,
    abitset_resize,
    bitset_size_,
    bitset_count_,
    abitset_empty_p,
    abitset_ones,
    abitset_zero,
    abitset_copy,
    abitset_disjoint_p,
    abitset_equal_p,
    abitset_not,
    abitset_subset_p,
    abitset_and,
    abitset_and_cmp,
    abitset_andn,
    abitset_andn_cmp,
    abitset_or,
    abitset_or_cmp,
    abitset_xor,
    abitset_xor_cmp,
    abitset_and_or,
    abitset_and_or_cmp,
    abitset_andn_or,
    abitset_andn_or_cmp,
    abitset_or_and,
    abitset_or_and_cmp,
    abitset_small_list,
    abitset_list_reverse,
    NULL,
    BITSET_ARRAY
  };
  
  
  /* Vector of operations for multiple word bitsets.  */
  struct bitset_vtable abitset_vtable = {
    abitset_set,
    abitset_reset,
    bitset_toggle_,
    abitset_test,
    abitset_resize,
    bitset_size_,
    bitset_count_,
    abitset_empty_p,
    abitset_ones,
    abitset_zero,
    abitset_copy,
    abitset_disjoint_p,
    abitset_equal_p,
    abitset_not,
    abitset_subset_p,
    abitset_and,
    abitset_and_cmp,
    abitset_andn,
    abitset_andn_cmp,
    abitset_or,
    abitset_or_cmp,
    abitset_xor,
    abitset_xor_cmp,
    abitset_and_or,
    abitset_and_or_cmp,
    abitset_andn_or,
    abitset_andn_or_cmp,
    abitset_or_and,
    abitset_or_and_cmp,
    abitset_list,
    abitset_list_reverse,
    NULL,
    BITSET_ARRAY
  };
  
  
  size_t
  abitset_bytes (bitset_bindex n_bits)
  {
    size_t header_size = offsetof (union bitset_union, a.words);
    struct bitset_align_struct { char a; union bitset_union b; };
    size_t bitset_alignment = offsetof (struct bitset_align_struct, b);
  
    bitset_windex size = ABITSET_N_WORDS (n_bits);
    size_t bytes = header_size + size * sizeof (bitset_word);
  
    /* Align the size properly for a vector of abitset objects.  */
    if (header_size % bitset_alignment != 0
        || sizeof (bitset_word) % bitset_alignment != 0)
      {
        bytes += bitset_alignment - 1;
        bytes -= bytes % bitset_alignment;
      }
  
    return bytes;
  }
  
  
  bitset
  abitset_init (bitset bset, bitset_bindex n_bits)
  {
    bitset_windex size = ABITSET_N_WORDS (n_bits);
    BITSET_NBITS_ (bset) = n_bits;
  
    /* Use optimized routines if bitset fits within a single word.
       There is probably little merit if using caching since
       the small bitset will always fit in the cache.  */
    bset->b.vtable = size == 1 ? &abitset_small_vtable : &abitset_vtable;
    bset->b.cindex = 0;
    bset->b.csize = size;
    bset->b.cdata = ABITSET_WORDS (bset);
    return bset;
  }
  

Download