summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorthegeorg <[email protected]>2024-10-04 11:18:39 +0300
committerthegeorg <[email protected]>2024-10-04 11:36:54 +0300
commit79b132a5a400c9c8498361c67876aa070640f066 (patch)
treec6f17f152f17f5913feb0a319251b371e42b962c
parent37112f646e6da1c3eb50de15cbbb8793b383b27e (diff)
Remove some of gnulib sources from contrib/tools/m4
commit_hash:48e647f4025141980063113500045d228cbd83ea
-rw-r--r--contrib/tools/m4/lib/abitset.c828
-rw-r--r--contrib/tools/m4/lib/abitset.h29
-rw-r--r--contrib/tools/m4/lib/argmatch.c277
-rw-r--r--contrib/tools/m4/lib/argmatch.h111
-rw-r--r--contrib/tools/m4/lib/bbitset.h304
-rw-r--r--contrib/tools/m4/lib/bison-system.h264
-rw-r--r--contrib/tools/m4/lib/bitset.c505
-rw-r--r--contrib/tools/m4/lib/bitset.h393
-rw-r--r--contrib/tools/m4/lib/bitset_stats.c728
-rw-r--r--contrib/tools/m4/lib/bitset_stats.h33
-rw-r--r--contrib/tools/m4/lib/bitsetv-print.c71
-rw-r--r--contrib/tools/m4/lib/bitsetv-print.h28
-rw-r--r--contrib/tools/m4/lib/bitsetv.c169
-rw-r--r--contrib/tools/m4/lib/bitsetv.h60
-rw-r--r--contrib/tools/m4/lib/concat-filename.c2
-rw-r--r--contrib/tools/m4/lib/ebitset.c1361
-rw-r--r--contrib/tools/m4/lib/ebitset.h31
-rw-r--r--contrib/tools/m4/lib/lbitset.c1401
-rw-r--r--contrib/tools/m4/lib/lbitset.h31
-rw-r--r--contrib/tools/m4/lib/libiberty.h36
-rw-r--r--contrib/tools/m4/lib/str-two-way.h452
-rw-r--r--contrib/tools/m4/lib/strchrnul.c142
-rw-r--r--contrib/tools/m4/lib/string--.h10
-rw-r--r--contrib/tools/m4/lib/strndup.c36
-rw-r--r--contrib/tools/m4/lib/strstr.c82
-rw-r--r--contrib/tools/m4/lib/strverscmp.c131
-rw-r--r--contrib/tools/m4/lib/timevar.c571
-rw-r--r--contrib/tools/m4/lib/timevar.def61
-rw-r--r--contrib/tools/m4/lib/timevar.h92
-rw-r--r--contrib/tools/m4/lib/vbitset.c1140
-rw-r--r--contrib/tools/m4/lib/vbitset.h29
-rw-r--r--contrib/tools/m4/lib/ya.make14
32 files changed, 1 insertions, 9421 deletions
diff --git a/contrib/tools/m4/lib/abitset.c b/contrib/tools/m4/lib/abitset.c
deleted file mode 100644
index f876996bcfd..00000000000
--- a/contrib/tools/m4/lib/abitset.c
+++ /dev/null
@@ -1,828 +0,0 @@
-/* Array bitsets.
-
- Copyright (C) 2002-2003, 2006, 2009-2013 Free Software Foundation,
- Inc.
-
- Contributed by Michael Hayes ([email protected]).
-
- 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 <http://www.gnu.org/licenses/>. */
-
-#include <config.h>
-
-#include "abitset.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 BSET 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_bindex bitno;
- bitset_bindex count;
- bitset_windex size;
- bitset_word word;
-
- word = ABITSET_WORDS (src)[0];
-
- /* Short circuit common case. */
- if (!word)
- return 0;
-
- size = BITSET_SIZE_ (src);
- bitno = *next;
- if (bitno >= size)
- return 0;
-
- word >>= bitno;
-
- /* If num is 1, we could speed things up with a binary search
- of the word of interest. */
-
- if (num >= BITSET_WORD_BITS)
- {
- for (count = 0; word; bitno++)
- {
- if (word & 1)
- list[count++] = bitno;
- word >>= 1;
- }
- }
- else
- {
- for (count = 0; word; bitno++)
- {
- if (word & 1)
- {
- list[count++] = bitno;
- if (count >= num)
- {
- bitno++;
- break;
- }
- }
- word >>= 1;
- }
- }
-
- *next = bitno;
- return count;
-}
-
-
-/* Set bit BITNO in bitset DST. */
-static void
-abitset_set (bitset dst ATTRIBUTE_UNUSED, bitset_bindex bitno ATTRIBUTE_UNUSED)
-{
- /* 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 (bitset dst ATTRIBUTE_UNUSED,
- bitset_bindex bitno ATTRIBUTE_UNUSED)
-{
- /* 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 (bitset src ATTRIBUTE_UNUSED,
- bitset_bindex bitno ATTRIBUTE_UNUSED)
-{
- /* This should never occur for abitsets since we should always
- hit the cache. */
- return false;
-}
-
-
-/* Find list of up to NUM bits set in BSET 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 bitno;
- bitset_bindex rbitno;
- bitset_bindex count;
- bitset_windex windex;
- unsigned int bitcnt;
- bitset_bindex bitoff;
- bitset_word *srcp = ABITSET_WORDS (src);
- bitset_bindex n_bits = BITSET_SIZE_ (src);
-
- rbitno = *next;
-
- /* If num is 1, we could speed things up with a binary search
- of the word of interest. */
-
- if (rbitno >= n_bits)
- return 0;
-
- count = 0;
-
- bitno = n_bits - (rbitno + 1);
-
- windex = bitno / BITSET_WORD_BITS;
- bitcnt = bitno % BITSET_WORD_BITS;
- bitoff = windex * BITSET_WORD_BITS;
-
- do
- {
- bitset_word word;
-
- word = srcp[windex] << (BITSET_WORD_BITS - 1 - bitcnt);
- for (; word; bitcnt--)
- {
- if (word & BITSET_MSB)
- {
- list[count++] = bitoff + bitcnt;
- if (count >= num)
- {
- *next = n_bits - (bitoff + bitcnt);
- return count;
- }
- }
- word <<= 1;
- }
- 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 BSET 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_bindex bitno;
- bitset_bindex count;
- bitset_windex windex;
- bitset_bindex bitoff;
- bitset_windex size = src->b.csize;
- bitset_word *srcp = ABITSET_WORDS (src);
- bitset_word word;
-
- bitno = *next;
-
- 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;
-
- /* If num is 1, we could speed things up with a binary search
- of the current word. */
-
- 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;
- word = srcp[windex] >> bitno;
- for (bitno = bitoff + bitno; word; bitno++)
- {
- if (word & 1)
- {
- list[count++] = bitno;
- if (count >= num)
- {
- *next = bitno + 1;
- return count;
- }
- }
- word >>= 1;
- }
- windex++;
- }
- bitoff = windex * BITSET_WORD_BITS;
- }
-
- for (; windex < size; windex++, bitoff += BITSET_WORD_BITS)
- {
- if (!(word = srcp[windex]))
- continue;
-
- if ((count + BITSET_WORD_BITS) < num)
- {
- for (bitno = bitoff; word; bitno++)
- {
- if (word & 1)
- list[count++] = bitno;
- word >>= 1;
- }
- }
- else
- {
- for (bitno = bitoff; word; bitno++)
- {
- if (word & 1)
- {
- list[count++] = bitno;
- if (count >= num)
- {
- *next = bitno + 1;
- return count;
- }
- }
- word >>= 1;
- }
- }
- }
-
- *next = bitoff;
- return count;
-}
-
-
-/* Ensure that any unused bits within the last word are clear. */
-static inline void
-abitset_unused_clear (bitset dst)
-{
- unsigned int last_bit;
-
- 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;
-
- 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;
-
- bytes = sizeof (bitset_word) * dst->b.csize;
-
- memset (dstp, 0, bytes);
-}
-
-
-static bool
-abitset_empty_p (bitset dst)
-{
- bitset_windex i;
- bitset_word *dstp = ABITSET_WORDS (dst);
-
- for (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);
- bitset_windex size = dst->b.csize;
-
- if (srcp == dstp)
- return;
- memcpy (dstp, srcp, sizeof (bitset_word) * size);
-}
-
-
-static void
-abitset_not (bitset dst, bitset src)
-{
- bitset_windex i;
- bitset_word *srcp = ABITSET_WORDS (src);
- bitset_word *dstp = ABITSET_WORDS (dst);
- bitset_windex size = dst->b.csize;
-
- for (i = 0; i < size; i++)
- *dstp++ = ~(*srcp++);
- abitset_unused_clear (dst);
-}
-
-
-static bool
-abitset_equal_p (bitset dst, bitset src)
-{
- bitset_windex i;
- bitset_word *srcp = ABITSET_WORDS (src);
- bitset_word *dstp = ABITSET_WORDS (dst);
- bitset_windex size = dst->b.csize;
-
- for (i = 0; i < size; i++)
- if (*srcp++ != *dstp++)
- return false;
- return true;
-}
-
-
-static bool
-abitset_subset_p (bitset dst, bitset src)
-{
- bitset_windex i;
- bitset_word *srcp = ABITSET_WORDS (src);
- bitset_word *dstp = ABITSET_WORDS (dst);
- bitset_windex size = dst->b.csize;
-
- for (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_windex i;
- bitset_word *srcp = ABITSET_WORDS (src);
- bitset_word *dstp = ABITSET_WORDS (dst);
- bitset_windex size = dst->b.csize;
-
- for (i = 0; i < size; i++)
- if (*srcp++ & *dstp++)
- return false;
-
- return true;
-}
-
-
-static void
-abitset_and (bitset dst, bitset src1, bitset src2)
-{
- bitset_windex i;
- 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 (i = 0; i < size; i++)
- *dstp++ = *src1p++ & *src2p++;
-}
-
-
-static bool
-abitset_and_cmp (bitset dst, bitset src1, bitset src2)
-{
- bitset_windex i;
- 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 (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_windex i;
- 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 (i = 0; i < size; i++)
- *dstp++ = *src1p++ & ~(*src2p++);
-}
-
-
-static bool
-abitset_andn_cmp (bitset dst, bitset src1, bitset src2)
-{
- bitset_windex i;
- 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 (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_windex i;
- 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 (i = 0; i < size; i++)
- *dstp++ = *src1p++ | *src2p++;
-}
-
-
-static bool
-abitset_or_cmp (bitset dst, bitset src1, bitset src2)
-{
- bitset_windex i;
- 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 (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_windex i;
- 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 (i = 0; i < size; i++)
- *dstp++ = *src1p++ ^ *src2p++;
-}
-
-
-static bool
-abitset_xor_cmp (bitset dst, bitset src1, bitset src2)
-{
- bitset_windex i;
- 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 (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_windex i;
- 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 (i = 0; i < size; i++)
- *dstp++ = (*src1p++ & *src2p++) | *src3p++;
-}
-
-
-static bool
-abitset_and_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
-{
- bitset_windex i;
- 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 (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_windex i;
- 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 (i = 0; i < size; i++)
- *dstp++ = (*src1p++ & ~(*src2p++)) | *src3p++;
-}
-
-
-static bool
-abitset_andn_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
-{
- bitset_windex i;
- 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 (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_windex i;
- 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 (i = 0; i < size; i++)
- *dstp++ = (*src1p++ | *src2p++) & *src3p++;
-}
-
-
-static bool
-abitset_or_and_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
-{
- bitset_windex i;
- 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 (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)
-{
- bitset_windex size;
- size_t bytes;
- 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);
-
- size = ABITSET_N_WORDS (n_bits);
- 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;
-
- 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. */
- if (size == 1)
- bset->b.vtable = &abitset_small_vtable;
- else
- bset->b.vtable = &abitset_vtable;
-
- bset->b.cindex = 0;
- bset->b.csize = size;
- bset->b.cdata = ABITSET_WORDS (bset);
- return bset;
-}
diff --git a/contrib/tools/m4/lib/abitset.h b/contrib/tools/m4/lib/abitset.h
deleted file mode 100644
index f66122894a7..00000000000
--- a/contrib/tools/m4/lib/abitset.h
+++ /dev/null
@@ -1,29 +0,0 @@
-/* Functions to support abitsets.
-
- Copyright (C) 2002, 2004, 2009-2013 Free Software Foundation, Inc.
-
- Contributed by Michael Hayes ([email protected]).
-
- 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 <http://www.gnu.org/licenses/>. */
-
-#ifndef _ABITSET_H
-#define _ABITSET_H
-
-#include "bitset.h"
-
-extern size_t abitset_bytes (bitset_bindex);
-
-extern bitset abitset_init (bitset, bitset_bindex);
-
-#endif
diff --git a/contrib/tools/m4/lib/argmatch.c b/contrib/tools/m4/lib/argmatch.c
deleted file mode 100644
index 9125e2af048..00000000000
--- a/contrib/tools/m4/lib/argmatch.c
+++ /dev/null
@@ -1,277 +0,0 @@
-/* argmatch.c -- find a match for a string in an array
-
- Copyright (C) 1990, 1998-1999, 2001-2007, 2009-2013 Free Software
- Foundation, Inc.
-
- 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 <http://www.gnu.org/licenses/>. */
-
-/* Written by David MacKenzie <[email protected]>
- Modified by Akim Demaille <[email protected]> */
-
-#include <config.h>
-
-/* Specification. */
-#include "argmatch.h"
-
-#include <stdbool.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-#include "gettext.h"
-#define _(msgid) gettext (msgid)
-
-#include "error.h"
-#include "quotearg.h"
-#include "quote.h"
-
-#if USE_UNLOCKED_IO
-# include "unlocked-io.h"
-#endif
-
-/* When reporting an invalid argument, show nonprinting characters
- by using the quoting style ARGMATCH_QUOTING_STYLE. Do not use
- literal_quoting_style. */
-#ifndef ARGMATCH_QUOTING_STYLE
-# define ARGMATCH_QUOTING_STYLE locale_quoting_style
-#endif
-
-/* Non failing version of argmatch call this function after failing. */
-#ifndef ARGMATCH_DIE
-# include "exitfail.h"
-# define ARGMATCH_DIE exit (exit_failure)
-#endif
-
-#ifdef ARGMATCH_DIE_DECL
-ARGMATCH_DIE_DECL;
-#endif
-
-static void
-__argmatch_die (void)
-{
- ARGMATCH_DIE;
-}
-
-/* Used by XARGMATCH and XARGCASEMATCH. See description in argmatch.h.
- Default to __argmatch_die, but allow caller to change this at run-time. */
-argmatch_exit_fn argmatch_die = __argmatch_die;
-
-
-/* If ARG is an unambiguous match for an element of the
- NULL-terminated array ARGLIST, return the index in ARGLIST
- of the matched element, else -1 if it does not match any element
- or -2 if it is ambiguous (is a prefix of more than one element).
-
- If VALLIST is none null, use it to resolve ambiguities limited to
- synonyms, i.e., for
- "yes", "yop" -> 0
- "no", "nope" -> 1
- "y" is a valid argument, for 0, and "n" for 1. */
-
-ptrdiff_t
-argmatch (const char *arg, const char *const *arglist,
- const char *vallist, size_t valsize)
-{
- size_t i; /* Temporary index in ARGLIST. */
- size_t arglen; /* Length of ARG. */
- ptrdiff_t matchind = -1; /* Index of first nonexact match. */
- bool ambiguous = false; /* If true, multiple nonexact match(es). */
-
- arglen = strlen (arg);
-
- /* Test all elements for either exact match or abbreviated matches. */
- for (i = 0; arglist[i]; i++)
- {
- if (!strncmp (arglist[i], arg, arglen))
- {
- if (strlen (arglist[i]) == arglen)
- /* Exact match found. */
- return i;
- else if (matchind == -1)
- /* First nonexact match found. */
- matchind = i;
- else
- {
- /* Second nonexact match found. */
- if (vallist == NULL
- || memcmp (vallist + valsize * matchind,
- vallist + valsize * i, valsize))
- {
- /* There is a real ambiguity, or we could not
- disambiguate. */
- ambiguous = true;
- }
- }
- }
- }
- if (ambiguous)
- return -2;
- else
- return matchind;
-}
-
-/* Error reporting for argmatch.
- CONTEXT is a description of the type of entity that was being matched.
- VALUE is the invalid value that was given.
- PROBLEM is the return value from argmatch. */
-
-void
-argmatch_invalid (const char *context, const char *value, ptrdiff_t problem)
-{
- char const *format = (problem == -1
- ? _("invalid argument %s for %s")
- : _("ambiguous argument %s for %s"));
-
- error (0, 0, format, quotearg_n_style (0, ARGMATCH_QUOTING_STYLE, value),
- quote_n (1, context));
-}
-
-/* List the valid arguments for argmatch.
- ARGLIST is the same as in argmatch.
- VALLIST is a pointer to an array of values.
- VALSIZE is the size of the elements of VALLIST */
-void
-argmatch_valid (const char *const *arglist,
- const char *vallist, size_t valsize)
-{
- size_t i;
- const char *last_val = NULL;
-
- /* We try to put synonyms on the same line. The assumption is that
- synonyms follow each other */
- fputs (_("Valid arguments are:"), stderr);
- for (i = 0; arglist[i]; i++)
- if ((i == 0)
- || memcmp (last_val, vallist + valsize * i, valsize))
- {
- fprintf (stderr, "\n - %s", quote (arglist[i]));
- last_val = vallist + valsize * i;
- }
- else
- {
- fprintf (stderr, ", %s", quote (arglist[i]));
- }
- putc ('\n', stderr);
-}
-
-/* Never failing versions of the previous functions.
-
- CONTEXT is the context for which argmatch is called (e.g.,
- "--version-control", or "$VERSION_CONTROL" etc.). Upon failure,
- calls the (supposed never to return) function EXIT_FN. */
-
-ptrdiff_t
-__xargmatch_internal (const char *context,
- const char *arg, const char *const *arglist,
- const char *vallist, size_t valsize,
- argmatch_exit_fn exit_fn)
-{
- ptrdiff_t res = argmatch (arg, arglist, vallist, valsize);
- if (res >= 0)
- /* Success. */
- return res;
-
- /* We failed. Explain why. */
- argmatch_invalid (context, arg, res);
- argmatch_valid (arglist, vallist, valsize);
- (*exit_fn) ();
-
- return -1; /* To please the compilers. */
-}
-
-/* Look for VALUE in VALLIST, an array of objects of size VALSIZE and
- return the first corresponding argument in ARGLIST */
-const char *
-argmatch_to_argument (const char *value,
- const char *const *arglist,
- const char *vallist, size_t valsize)
-{
- size_t i;
-
- for (i = 0; arglist[i]; i++)
- if (!memcmp (value, vallist + valsize * i, valsize))
- return arglist[i];
- return NULL;
-}
-
-#ifdef TEST
-/*
- * Based on "getversion.c" by David MacKenzie <[email protected]>
- */
-char *program_name;
-
-/* When to make backup files. */
-enum backup_type
-{
- /* Never make backups. */
- no_backups,
-
- /* Make simple backups of every file. */
- simple_backups,
-
- /* Make numbered backups of files that already have numbered backups,
- and simple backups of the others. */
- numbered_existing_backups,
-
- /* Make numbered backups of every file. */
- numbered_backups
-};
-
-/* Two tables describing arguments (keys) and their corresponding
- values */
-static const char *const backup_args[] =
-{
- "no", "none", "off",
- "simple", "never",
- "existing", "nil",
- "numbered", "t",
- 0
-};
-
-static const enum backup_type backup_vals[] =
-{
- no_backups, no_backups, no_backups,
- simple_backups, simple_backups,
- numbered_existing_backups, numbered_existing_backups,
- numbered_backups, numbered_backups
-};
-
-int
-main (int argc, const char *const *argv)
-{
- const char *cp;
- enum backup_type backup_type = no_backups;
-
- program_name = (char *) argv[0];
-
- if (argc > 2)
- {
- fprintf (stderr, "Usage: %s [VERSION_CONTROL]\n", program_name);
- exit (1);
- }
-
- if ((cp = getenv ("VERSION_CONTROL")))
- backup_type = XARGMATCH ("$VERSION_CONTROL", cp,
- backup_args, backup_vals);
-
- if (argc == 2)
- backup_type = XARGMATCH (program_name, argv[1],
- backup_args, backup_vals);
-
- printf ("The version control is '%s'\n",
- ARGMATCH_TO_ARGUMENT (backup_type, backup_args, backup_vals));
-
- return 0;
-}
-#endif
diff --git a/contrib/tools/m4/lib/argmatch.h b/contrib/tools/m4/lib/argmatch.h
deleted file mode 100644
index e4c8027144a..00000000000
--- a/contrib/tools/m4/lib/argmatch.h
+++ /dev/null
@@ -1,111 +0,0 @@
-/* argmatch.h -- definitions and prototypes for argmatch.c
-
- Copyright (C) 1990, 1998-1999, 2001-2002, 2004-2005, 2009-2013 Free Software
- Foundation, Inc.
-
- 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 <http://www.gnu.org/licenses/>. */
-
-/* Written by David MacKenzie <[email protected]>
- Modified by Akim Demaille <[email protected]> */
-
-#ifndef ARGMATCH_H_
-# define ARGMATCH_H_ 1
-
-# include <stddef.h>
-
-# include "verify.h"
-
-#ifdef __cplusplus
-extern "C" {
-#endif
-
-# define ARRAY_CARDINALITY(Array) (sizeof (Array) / sizeof *(Array))
-
-/* Assert there are as many real arguments as there are values
- (argument list ends with a NULL guard). */
-
-# define ARGMATCH_VERIFY(Arglist, Vallist) \
- verify (ARRAY_CARDINALITY (Arglist) == ARRAY_CARDINALITY (Vallist) + 1)
-
-/* Return the index of the element of ARGLIST (NULL terminated) that
- matches with ARG. If VALLIST is not NULL, then use it to resolve
- false ambiguities (i.e., different matches of ARG but corresponding
- to the same values in VALLIST). */
-
-ptrdiff_t argmatch (char const *arg, char const *const *arglist,
- char const *vallist, size_t valsize) _GL_ATTRIBUTE_PURE;
-
-# define ARGMATCH(Arg, Arglist, Vallist) \
- argmatch (Arg, Arglist, (char const *) (Vallist), sizeof *(Vallist))
-
-/* xargmatch calls this function when it fails. This function should not
- return. By default, this is a function that calls ARGMATCH_DIE which
- in turn defaults to 'exit (exit_failure)'. */
-typedef void (*argmatch_exit_fn) (void);
-extern argmatch_exit_fn argmatch_die;
-
-/* Report on stderr why argmatch failed. Report correct values. */
-
-void argmatch_invalid (char const *context, char const *value,
- ptrdiff_t problem);
-
-/* Left for compatibility with the old name invalid_arg */
-
-# define invalid_arg(Context, Value, Problem) \
- argmatch_invalid (Context, Value, Problem)
-
-
-
-/* Report on stderr the list of possible arguments. */
-
-void argmatch_valid (char const *const *arglist,
- char const *vallist, size_t valsize);
-
-# define ARGMATCH_VALID(Arglist, Vallist) \
- argmatch_valid (Arglist, (char const *) (Vallist), sizeof *(Vallist))
-
-
-
-/* Same as argmatch, but upon failure, report an explanation of the
- failure, and exit using the function EXIT_FN. */
-
-ptrdiff_t __xargmatch_internal (char const *context,
- char const *arg, char const *const *arglist,
- char const *vallist, size_t valsize,
- argmatch_exit_fn exit_fn);
-
-/* Programmer friendly interface to __xargmatch_internal. */
-
-# define XARGMATCH(Context, Arg, Arglist, Vallist) \
- ((Vallist) [__xargmatch_internal (Context, Arg, Arglist, \
- (char const *) (Vallist), \
- sizeof *(Vallist), \
- argmatch_die)])
-
-/* Convert a value into a corresponding argument. */
-
-char const *argmatch_to_argument (char const *value,
- char const *const *arglist,
- char const *vallist, size_t valsize)
- _GL_ATTRIBUTE_PURE;
-
-# define ARGMATCH_TO_ARGUMENT(Value, Arglist, Vallist) \
- argmatch_to_argument (Value, Arglist, \
- (char const *) (Vallist), sizeof *(Vallist))
-
-#ifdef __cplusplus
-}
-#endif
-
-#endif /* ARGMATCH_H_ */
diff --git a/contrib/tools/m4/lib/bbitset.h b/contrib/tools/m4/lib/bbitset.h
deleted file mode 100644
index 443d2da2e8e..00000000000
--- a/contrib/tools/m4/lib/bbitset.h
+++ /dev/null
@@ -1,304 +0,0 @@
-/* Base bitset stuff.
-
- Copyright (C) 2002-2004, 2006, 2009-2013 Free Software Foundation,
- Inc.
-
- Contributed by Michael Hayes ([email protected]).
-
- 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 <http://www.gnu.org/licenses/>. */
-
-#ifndef _BBITSET_H
-#define _BBITSET_H
-
-#include "libiberty.h"
-
-#include <stdbool.h>
-#include <limits.h>
-#include <stddef.h>
-
-/* Currently we support five flavours of bitsets:
- BITSET_ARRAY: Array of bits (fixed size, fast for dense bitsets).
- Memory for bit array and bitset structure allocated
- contiguously.
- BITSET_LIST: Linked list of arrays of bits (variable size, least storage
- for large very sparse sets).
- BITSET_TABLE: Expandable table of pointers to arrays of bits
- (variable size, less storage for large sparse sets).
- Faster than BITSET_LIST for random access.
- BITSET_VARRAY: Variable array of bits (variable size, fast for
- dense bitsets).
- BITSET_STATS: Wrapper bitset for internal use only. Used for gathering
- statistics and/or better run-time checking.
-*/
-enum bitset_type {BITSET_ARRAY, BITSET_LIST, BITSET_TABLE, BITSET_VARRAY,
- BITSET_TYPE_NUM, BITSET_STATS};
-#define BITSET_TYPE_NAMES {"abitset", "lbitset", "ebitset", "vbitset"}
-
-extern const char * const bitset_type_names[];
-
-enum bitset_alloc_type {BITSET_MALLOC, BITSET_OBALLOC};
-
-/* Data type used to store a word of bits. */
-typedef unsigned long int bitset_word;
-#define BITSET_WORD_BITS ((unsigned int) (CHAR_BIT * sizeof (bitset_word)))
-
-/* Bit index. In theory we might need a type wider than size_t, but
- in practice we lose at most a factor of CHAR_BIT by going with
- size_t, and that is good enough. If this type is changed to be
- wider than size_t, the code needs to be modified to check for
- overflow when converting bit counts to byte or word counts.
- The bit and word index types must be unsigned. */
-typedef size_t bitset_bindex;
-
-/* Word index. */
-typedef size_t bitset_windex;
-
-/* Maximum values for commonly-used unsigned types. BITSET_SIZE_MAX
- always equals SIZE_MAX, but some older systems lack SIZE_MAX. */
-#define BITSET_BINDEX_MAX ((bitset_bindex) -1)
-
-/* Limit max word index to the maximum value of a signed integer
- to simplify cache disabling. */
-#define BITSET_WINDEX_MAX (((bitset_windex) -1) >> 1)
-#define BITSET_SIZE_MAX ((size_t) -1)
-
-#define BITSET_MSB ((bitset_word) 1 << (BITSET_WORD_BITS - 1))
-
-#define BITSET_LIST_SIZE 1024
-
-enum bitset_ops {BITSET_OP_ZERO, BITSET_OP_ONES,
- BITSET_OP_COPY, BITSET_OP_NOT,
- BITSET_OP_EMPTY_P, BITSET_OP_EQUAL_P,
- BITSET_OP_SUBSET_P, BITSET_OP_DISJOINT_P,
- BITSET_OP_AND, BITSET_OP_OR, BITSET_OP_XOR, BITSET_OP_ANDN,
- BITSET_OP_OR_AND, BITSET_OP_AND_OR, BITSET_OP_ANDN_OR};
-
-struct bbitset_struct
-{
- const struct bitset_vtable *vtable;
- bitset_windex cindex; /* Cache word index. */
- bitset_windex csize; /* Cache size in words. */
- bitset_word *cdata; /* Cache data pointer. */
- bitset_bindex n_bits; /* Number of bits. */
- /* Perhaps we could sacrifice another word to indicate
- that the bitset is known to be zero, that a bit has been set
- in the cache, and that a bit has been cleared in the cache.
- This would speed up some of the searches but slightly slow down
- bit set/reset operations of cached bits. */
-};
-
-
-typedef union bitset_union *bitset;
-
-
-/* Private accessor macros to bitset structure. */
-#define BITSET_VTABLE_(SRC) (SRC)->b.vtable
-#define BITSET_CINDEX_(SRC) (SRC)->b.cindex
-#define BITSET_CDATA_(SRC) (SRC)->b.cdata
-#define BITSET_CSIZE_(SRC) (SRC)->b.csize
-#define BITSET_NBITS_(SRC) (SRC)->b.n_bits
-
-
-/* The contents of this structure should be considered private. */
-struct bitset_vtable
-{
- void (*set) (bitset, bitset_bindex);
- void (*reset) (bitset, bitset_bindex);
- bool (*toggle) (bitset, bitset_bindex);
- bool (*test) (bitset, bitset_bindex);
- bitset_bindex (*resize) (bitset, bitset_bindex);
- bitset_bindex (*size) (bitset);
- bitset_bindex (*count) (bitset);
-
- bool (*empty_p) (bitset);
- void (*ones) (bitset);
- void (*zero) (bitset);
-
- void (*copy) (bitset, bitset);
- bool (*disjoint_p) (bitset, bitset);
- bool (*equal_p) (bitset, bitset);
- void (*not_) (bitset, bitset);
- bool (*subset_p) (bitset, bitset);
-
- void (*and_) (bitset, bitset, bitset);
- bool (*and_cmp) (bitset, bitset, bitset);
- void (*andn) (bitset, bitset, bitset);
- bool (*andn_cmp) (bitset, bitset, bitset);
- void (*or_) (bitset, bitset, bitset);
- bool (*or_cmp) (bitset, bitset, bitset);
- void (*xor_) (bitset, bitset, bitset);
- bool (*xor_cmp) (bitset, bitset, bitset);
-
- void (*and_or) (bitset, bitset, bitset, bitset);
- bool (*and_or_cmp) (bitset, bitset, bitset, bitset);
- void (*andn_or) (bitset, bitset, bitset, bitset);
- bool (*andn_or_cmp) (bitset, bitset, bitset, bitset);
- void (*or_and) (bitset, bitset, bitset, bitset);
- bool (*or_and_cmp) (bitset, bitset, bitset, bitset);
-
- bitset_bindex (*list) (bitset, bitset_bindex *, bitset_bindex,
- bitset_bindex *);
- bitset_bindex (*list_reverse) (bitset, bitset_bindex *, bitset_bindex,
- bitset_bindex *);
- void (*free) (bitset);
- enum bitset_type type;
-};
-
-#define BITSET_COMPATIBLE_(BSET1, BSET2) \
-((BSET1)->b.vtable == (BSET2)->b.vtable)
-
-#define BITSET_CHECK2_(DST, SRC) \
-if (!BITSET_COMPATIBLE_ (DST, SRC)) abort ();
-
-#define BITSET_CHECK3_(DST, SRC1, SRC2) \
-if (!BITSET_COMPATIBLE_ (DST, SRC1) \
- || !BITSET_COMPATIBLE_ (DST, SRC2)) abort ();
-
-#define BITSET_CHECK4_(DST, SRC1, SRC2, SRC3) \
-if (!BITSET_COMPATIBLE_ (DST, SRC1) || !BITSET_COMPATIBLE_ (DST, SRC2) \
- || !BITSET_COMPATIBLE_ (DST, SRC3)) abort ();
-
-
-/* Redefine number of bits in bitset DST. */
-#define BITSET_RESIZE_(DST, SIZE) (DST)->b.vtable->resize (DST, SIZE)
-
-/* Return size in bits of bitset SRC. */
-#define BITSET_SIZE_(SRC) (SRC)->b.vtable->size (SRC)
-
-/* Return number of bits set in bitset SRC. */
-#define BITSET_COUNT_(SRC) (SRC)->b.vtable->count (SRC)
-
-/* Return type of bitset SRC. */
-#define BITSET_TYPE_(DST) (DST)->b.vtable->type
-
-/* Set bit BITNO in bitset DST. */
-#define BITSET_SET_(DST, BITNO) (DST)->b.vtable->set (DST, BITNO)
-
-/* Reset bit BITNO in bitset DST. */
-#define BITSET_RESET_(DST, BITNO) (DST)->b.vtable->reset (DST, BITNO)
-
-/* Toggle bit BITNO in bitset DST. */
-#define BITSET_TOGGLE_(DST, BITNO) (DST)->b.vtable->toggle (DST, BITNO)
-
-/* Return non-zero if bit BITNO in bitset SRC is set. */
-#define BITSET_TEST_(SRC, BITNO) (SRC)->b.vtable->test (SRC, BITNO)
-
-/* Free bitset SRC. */
-#define BITSET_FREE_(SRC)\
- ((SRC)->b.vtable->free ? (SRC)->b.vtable->free (SRC) :(void)0)
-
-
-/* Return SRC == 0. */
-#define BITSET_EMPTY_P_(SRC) (SRC)->b.vtable->empty_p (SRC)
-
-/* DST = ~0. */
-#define BITSET_ONES_(DST) (DST)->b.vtable->ones (DST)
-
-/* DST = 0. */
-#define BITSET_ZERO_(DST) (DST)->b.vtable->zero (DST)
-
-
-
-/* DST = SRC. */
-#define BITSET_COPY_(DST, SRC) (SRC)->b.vtable->copy (DST, SRC)
-
-/* Return DST & SRC == 0. */
-#define BITSET_DISJOINT_P_(DST, SRC) (SRC)->b.vtable->disjoint_p (DST, SRC)
-
-/* Return DST == SRC. */
-#define BITSET_EQUAL_P_(DST, SRC) (SRC)->b.vtable->equal_p (DST, SRC)
-
-/* DST = ~SRC. */
-#define BITSET_NOT_(DST, SRC) (SRC)->b.vtable->not_ (DST, SRC)
-
-/* Return DST == DST | SRC. */
-#define BITSET_SUBSET_P_(DST, SRC) (SRC)->b.vtable->subset_p (DST, SRC)
-
-
-/* DST = SRC1 & SRC2. */
-#define BITSET_AND_(DST, SRC1, SRC2) (SRC1)->b.vtable->and_ (DST, SRC1, SRC2)
-#define BITSET_AND_CMP_(DST, SRC1, SRC2) (SRC1)->b.vtable->and_cmp (DST, SRC1, SRC2)
-
-/* DST = SRC1 & ~SRC2. */
-#define BITSET_ANDN_(DST, SRC1, SRC2) (SRC1)->b.vtable->andn (DST, SRC1, SRC2)
-#define BITSET_ANDN_CMP_(DST, SRC1, SRC2) (SRC1)->b.vtable->andn_cmp (DST, SRC1, SRC2)
-
-/* DST = SRC1 | SRC2. */
-#define BITSET_OR_(DST, SRC1, SRC2) (SRC1)->b.vtable->or_ (DST, SRC1, SRC2)
-#define BITSET_OR_CMP_(DST, SRC1, SRC2) (SRC1)->b.vtable->or_cmp (DST, SRC1, SRC2)
-
-/* DST = SRC1 ^ SRC2. */
-#define BITSET_XOR_(DST, SRC1, SRC2) (SRC1)->b.vtable->xor_ (DST, SRC1, SRC2)
-#define BITSET_XOR_CMP_(DST, SRC1, SRC2) (SRC1)->b.vtable->xor_cmp (DST, SRC1, SRC2)
-
-
-
-/* DST = (SRC1 & SRC2) | SRC3. Return non-zero if
- DST != (SRC1 & SRC2) | SRC3. */
-#define BITSET_AND_OR_(DST, SRC1, SRC2, SRC3) \
- (SRC1)->b.vtable->and_or (DST, SRC1, SRC2, SRC3)
-#define BITSET_AND_OR_CMP_(DST, SRC1, SRC2, SRC3) \
- (SRC1)->b.vtable->and_or_cmp (DST, SRC1, SRC2, SRC3)
-
-/* DST = (SRC1 & ~SRC2) | SRC3. Return non-zero if
- DST != (SRC1 & ~SRC2) | SRC3. */
-#define BITSET_ANDN_OR_(DST, SRC1, SRC2, SRC3) \
- (SRC1)->b.vtable->andn_or (DST, SRC1, SRC2, SRC3)
-#define BITSET_ANDN_OR_CMP_(DST, SRC1, SRC2, SRC3) \
- (SRC1)->b.vtable->andn_or_cmp (DST, SRC1, SRC2, SRC3)
-
-/* DST = (SRC1 | SRC2) & SRC3. Return non-zero if
- DST != (SRC1 | SRC2) & SRC3. */
-#define BITSET_OR_AND_(DST, SRC1, SRC2, SRC3) \
- (SRC1)->b.vtable->or_and (DST, SRC1, SRC2, SRC3)
-#define BITSET_OR_AND_CMP_(DST, SRC1, SRC2, SRC3) \
- (SRC1)->b.vtable->or_and_cmp (DST, SRC1, SRC2, SRC3)
-
-
-/* Find list of up to NUM bits set in BSET starting from and including
- *NEXT. Return with actual number of bits found and with *NEXT
- indicating where search stopped. */
-#define BITSET_LIST_(BSET, LIST, NUM, NEXT) \
- (BSET)->b.vtable->list (BSET, LIST, NUM, NEXT)
-
-/* Find reverse list of up to NUM bits set in BSET starting from and
- including NEXT. Return with actual number of bits found and with
- *NEXT indicating where search stopped. */
-#define BITSET_LIST_REVERSE_(BSET, LIST, NUM, NEXT) \
- (BSET)->b.vtable->list_reverse (BSET, LIST, NUM, NEXT)
-
-
-/* Private functions for bitset implementations. */
-
-extern bool bitset_toggle_ (bitset, bitset_bindex);
-
-extern bitset_bindex bitset_count_ (bitset);
-
-extern bitset_bindex bitset_size_ (bitset);
-
-extern bool bitset_copy_ (bitset, bitset);
-
-extern void bitset_and_or_ (bitset, bitset, bitset, bitset);
-
-extern bool bitset_and_or_cmp_ (bitset, bitset, bitset, bitset);
-
-extern void bitset_andn_or_ (bitset, bitset, bitset, bitset);
-
-extern bool bitset_andn_or_cmp_ (bitset, bitset, bitset, bitset);
-
-extern void bitset_or_and_ (bitset, bitset, bitset, bitset);
-
-extern bool bitset_or_and_cmp_ (bitset, bitset, bitset, bitset);
-
-#endif /* _BBITSET_H */
diff --git a/contrib/tools/m4/lib/bison-system.h b/contrib/tools/m4/lib/bison-system.h
deleted file mode 100644
index 472a1921a7e..00000000000
--- a/contrib/tools/m4/lib/bison-system.h
+++ /dev/null
@@ -1,264 +0,0 @@
-/* System-dependent definitions for Bison.
-
- Copyright (C) 2000-2007, 2009-2013 Free Software Foundation, Inc.
-
- 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 <http://www.gnu.org/licenses/>. */
-
-#ifndef BISON_SYSTEM_H
-# define BISON_SYSTEM_H
-
-/* flex 2.5.31 gratutiously defines macros like INT8_MIN. But this
- runs afoul of pre-C99 compilers that have <inttypes.h> or
- <stdint.h>, which are included below if available. It also runs
- afoul of pre-C99 compilers that define these macros in <limits.h>. */
-# if ! defined __STDC_VERSION__ || __STDC_VERSION__ < 199901
-# undef INT8_MIN
-# undef INT16_MIN
-# undef INT32_MIN
-# undef INT8_MAX
-# undef INT16_MAX
-# undef UINT8_MAX
-# undef INT32_MAX
-# undef UINT16_MAX
-# undef UINT32_MAX
-# endif
-
-# include <limits.h>
-# include <stddef.h>
-# include <stdlib.h>
-# include <string.h>
-
-# define ARRAY_CARDINALITY(Array) (sizeof (Array) / sizeof *(Array))
-# define STREQ(L, R) (strcmp(L, R) == 0)
-# define STRNEQ(L, R) (!STREQ(L, R))
-
-/* Just like strncmp, but the second argument must be a literal string
- and you don't specify the length. */
-# define STRNCMP_LIT(S, Literal) \
- strncmp (S, "" Literal "", sizeof (Literal) - 1)
-
-/* Whether Literal is a prefix of S. */
-# define STRPREFIX_LIT(Literal, S) \
- (STRNCMP_LIT (S, Literal) == 0)
-
-# include <unistd.h>
-#if (defined _MSC_VER) && (_MSC_VER < 1800)
-#else
-# include <inttypes.h>
-#endif
-
-# ifndef UINTPTR_MAX
-/* This isn't perfect, but it's good enough for Bison, which needs
- only to hash pointers. */
-typedef size_t uintptr_t;
-# endif
-
-/* Version mismatch. */
-# define EX_MISMATCH 63
-
-/*---------.
-| Gnulib. |
-`---------*/
-
-# include <unlocked-io.h>
-# include <verify.h>
-# include <xalloc.h>
-
-
-/*-----------------.
-| GCC extensions. |
-`-----------------*/
-
-/* Use PACIFY_CC to indicate that Code is unimportant to the logic of Bison
- but that it is necessary for suppressing compiler warnings. For example,
- Code might be a variable initializer that's always overwritten before the
- variable is used.
-
- PACIFY_CC is intended to be useful only as a comment as it does not alter
- Code. It is tempting to redefine PACIFY_CC so that it will suppress Code
- when configuring without --enable-gcc-warnings. However, that would mean
- that, for maintainers, Bison would compile with potentially less warnings
- and safer logic than it would for users. Due to the overhead of M4,
- suppressing Code is unlikely to offer any significant improvement in
- Bison's performance anyway. */
-# define PACIFY_CC(Code) Code
-
-# ifndef __attribute__
-/* This feature is available in gcc versions 2.5 and later. */
-# if (! defined __GNUC__ || __GNUC__ < 2 \
- || (__GNUC__ == 2 && __GNUC_MINOR__ < 5))
-# define __attribute__(Spec) /* empty */
-# endif
-# endif
-
-/* The __-protected variants of 'format' and 'printf' attributes
- are accepted by gcc versions 2.6.4 (effectively 2.7) and later. */
-# if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 7)
-# define __format__ format
-# define __printf__ printf
-# endif
-
-# ifndef ATTRIBUTE_NORETURN
-# define ATTRIBUTE_NORETURN __attribute__ ((__noreturn__))
-# endif
-
-# ifndef ATTRIBUTE_UNUSED
-# define ATTRIBUTE_UNUSED __attribute__ ((__unused__))
-# endif
-
-
-/*------.
-| NLS. |
-`------*/
-
-# include <locale.h>
-
-# include <gettext.h>
-# define _(Msgid) gettext (Msgid)
-# define N_(Msgid) (Msgid)
-
-
-/*-----------.
-| Booleans. |
-`-----------*/
-
-# include <stdbool.h>
-
-
-
-/*-------------.
-| Assertions. |
-`-------------*/
-
-/* In the past, Bison defined aver to simply invoke abort in the case of
- a failed assertion. The rationale was that <assert.h>'s assertions
- were too heavyweight and could be disabled too easily. See
- discussions at
- <http://lists.gnu.org/archive/html/bison-patches/2006-01/msg00080.html>
- <http://lists.gnu.org/archive/html/bison-patches/2006-09/msg00111.html>.
-
- However, normal assert output can be helpful during development and
- in bug reports from users. Moreover, it's not clear now that
- <assert.h>'s assertions are significantly heavyweight. Finally, if
- users want to experiment with disabling assertions, it's debatable
- whether it's our responsibility to stop them. See discussion
- starting at
- <http://lists.gnu.org/archive/html/bison-patches/2009-09/msg00013.html>.
-
- For now, we use assert but we call it aver throughout Bison in case
- we later wish to try another scheme.
-*/
-# include <assert.h>
-# define aver assert
-
-
-/*-----------.
-| Obstacks. |
-`-----------*/
-
-# define obstack_chunk_alloc xmalloc
-# define obstack_chunk_free free
-# include <obstack.h>
-
-/* String-grow: append Str to Obs. */
-
-# define obstack_sgrow(Obs, Str) \
- obstack_grow (Obs, Str, strlen (Str))
-
-/* Output Str escaped for our postprocessing (i.e., escape M4 special
- characters).
-
- For instance "[foo]" -> "@{foo@}", "$$" -> "$][$][". */
-
-# define obstack_escape(Obs, Str) \
- do { \
- char const *p__; \
- for (p__ = Str; *p__; p__++) \
- switch (*p__) \
- { \
- case '$': obstack_sgrow (Obs, "$]["); break; \
- case '@': obstack_sgrow (Obs, "@@" ); break; \
- case '[': obstack_sgrow (Obs, "@{" ); break; \
- case ']': obstack_sgrow (Obs, "@}" ); break; \
- default: obstack_1grow (Obs, *p__ ); break; \
- } \
- } while (0)
-
-
-/* Output Str both quoted for M4 (i.e., embed in [[...]]), and escaped
- for our postprocessing (i.e., escape M4 special characters). If
- Str is empty (or NULL), output "[]" instead of "[[]]" as it make M4
- programming easier (m4_ifval can be used).
-
- For instance "[foo]" -> "[[@{foo@}]]", "$$" -> "[[$][$][]]". */
-
-# define obstack_quote(Obs, Str) \
- do { \
- char const* obstack_quote_p = Str; \
- if (obstack_quote_p && obstack_quote_p[0]) \
- { \
- obstack_sgrow (Obs, "[["); \
- obstack_escape (Obs, obstack_quote_p); \
- obstack_sgrow (Obs, "]]"); \
- } \
- else \
- obstack_sgrow (Obs, "[]"); \
- } while (0)
-
-
-/* Append the ending 0, finish Obs, and return the string. */
-
-# define obstack_finish0(Obs) \
- (obstack_1grow (Obs, '\0'), (char *) obstack_finish (Obs))
-
-
-/*-----------------------------------------.
-| Extensions to use for the output files. |
-`-----------------------------------------*/
-
-# ifndef OUTPUT_EXT
-# define OUTPUT_EXT ".output"
-# endif
-
-# ifndef TAB_EXT
-# define TAB_EXT ".tab"
-# endif
-
-
-
-/*---------------------.
-| Free a linked list. |
-`---------------------*/
-
-# define LIST_FREE(Type, List) \
- do { \
- Type *_node, *_next; \
- for (_node = List; _node; _node = _next) \
- { \
- _next = _node->next; \
- free (_node); \
- } \
- } while (0)
-
-
-/*---------------------------------------------.
-| Debugging memory allocation (must be last). |
-`---------------------------------------------*/
-
-# if WITH_DMALLOC
-# define DMALLOC_FUNC_CHECK
-# include <dmalloc.h>
-# endif /* WITH_DMALLOC */
-
-#endif /* ! BISON_SYSTEM_H */
diff --git a/contrib/tools/m4/lib/bitset.c b/contrib/tools/m4/lib/bitset.c
deleted file mode 100644
index f7a9996afb4..00000000000
--- a/contrib/tools/m4/lib/bitset.c
+++ /dev/null
@@ -1,505 +0,0 @@
-/* General bitsets.
-
- Copyright (C) 2002-2006, 2009-2013 Free Software Foundation, Inc.
-
- Contributed by Michael Hayes ([email protected]).
-
- 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 <http://www.gnu.org/licenses/>. */
-
-#include <config.h>
-
-#include "bitset.h"
-
-#include <stdlib.h>
-#include <string.h>
-#include "abitset.h"
-#include "lbitset.h"
-#include "ebitset.h"
-#include "vbitset.h"
-#include "bitset_stats.h"
-#include "obstack.h"
-
-const char * const bitset_type_names[] = BITSET_TYPE_NAMES;
-
-
-/* Return number of bytes required to create a N_BIT bitset
- of TYPE. The bitset may grow to require more bytes than this. */
-size_t
-bitset_bytes (enum bitset_type type, bitset_bindex n_bits)
-{
- size_t bytes;
-
- if (bitset_stats_enabled)
- return bitset_stats_bytes ();
-
- switch (type)
- {
- default:
- abort ();
-
- case BITSET_ARRAY:
- bytes = abitset_bytes (n_bits);
- break;
-
- case BITSET_LIST:
- bytes = lbitset_bytes (n_bits);
- break;
-
- case BITSET_TABLE:
- bytes = ebitset_bytes (n_bits);
- break;
-
- case BITSET_VARRAY:
- bytes = vbitset_bytes (n_bits);
- break;
- }
-
- return bytes;
-}
-
-
-/* Initialise bitset BSET of TYPE for N_BITS. */
-bitset
-bitset_init (bitset bset, bitset_bindex n_bits, enum bitset_type type)
-{
- if (bitset_stats_enabled)
- return bitset_stats_init (bset, n_bits, type);
-
- switch (type)
- {
- default:
- abort ();
-
- case BITSET_ARRAY:
- return abitset_init (bset, n_bits);
-
- case BITSET_LIST:
- return lbitset_init (bset, n_bits);
-
- case BITSET_TABLE:
- return ebitset_init (bset, n_bits);
-
- case BITSET_VARRAY:
- return vbitset_init (bset, n_bits);
- }
-}
-
-
-/* Select a bitset type for a set of N_BITS and with attribute hints
- specified by ATTR. For variable size bitsets, N_BITS is only a
- hint and may be zero. */
-enum bitset_type
-bitset_type_choose (bitset_bindex n_bits ATTRIBUTE_UNUSED, unsigned int attr)
-{
- /* Check attributes. */
- if (attr & BITSET_FIXED && attr & BITSET_VARIABLE)
- abort ();
- if (attr & BITSET_SPARSE && attr & BITSET_DENSE)
- abort ();
-
- /* Choose the type of bitset. Note that sometimes we will be asked
- for a zero length fixed size bitset. */
-
-
- /* If no attributes selected, choose a good compromise. */
- if (!attr)
- return BITSET_VARRAY;
-
- if (attr & BITSET_SPARSE)
- return BITSET_LIST;
-
- if (attr & BITSET_FIXED)
- return BITSET_ARRAY;
-
- if (attr & BITSET_GREEDY)
- return BITSET_TABLE;
-
- return BITSET_VARRAY;
-}
-
-
-/* Create a bitset of N_BITS of type TYPE. */
-bitset
-bitset_alloc (bitset_bindex n_bits, enum bitset_type type)
-{
- size_t bytes;
- bitset bset;
-
- bytes = bitset_bytes (type, n_bits);
-
- bset = xcalloc (1, bytes);
-
- /* The cache is disabled until some elements are allocated. If we
- have variable length arrays, then we may need to allocate a dummy
- element. */
-
- return bitset_init (bset, n_bits, type);
-}
-
-
-/* Create a bitset of N_BITS of type TYPE. */
-bitset
-bitset_obstack_alloc (struct obstack *bobstack,
- bitset_bindex n_bits, enum bitset_type type)
-{
- size_t bytes;
- bitset bset;
-
- bytes = bitset_bytes (type, n_bits);
-
- bset = obstack_alloc (bobstack, bytes);
- memset (bset, 0, bytes);
-
- return bitset_init (bset, n_bits, type);
-}
-
-
-/* Create a bitset of N_BITS and with attribute hints specified by
- ATTR. */
-bitset
-bitset_create (bitset_bindex n_bits, unsigned int attr)
-{
- enum bitset_type type;
-
- type = bitset_type_choose (n_bits, attr);
-
- return bitset_alloc (n_bits, type);
-}
-
-
-/* Free bitset BSET. */
-void
-bitset_free (bitset bset)
-{
- BITSET_FREE_ (bset);
- free (bset);
-}
-
-
-/* Free bitset BSET allocated on obstack. */
-void
-bitset_obstack_free (bitset bset)
-{
- BITSET_FREE_ (bset);
-}
-
-
-/* Return bitset type. */
-enum bitset_type
-bitset_type_get (bitset bset)
-{
- enum bitset_type type;
-
- type = BITSET_TYPE_ (bset);
- if (type != BITSET_STATS)
- return type;
-
- return bitset_stats_type_get (bset);
-}
-
-
-/* Return name of bitset type. */
-const char *
-bitset_type_name_get (bitset bset)
-{
- enum bitset_type type;
-
- type = bitset_type_get (bset);
-
- return bitset_type_names[type];
-}
-
-
-/* Find next bit set in SRC starting from and including BITNO.
- Return BITSET_BINDEX_MAX if SRC empty. */
-bitset_bindex
-bitset_next (bitset src, bitset_bindex bitno)
-{
- bitset_bindex val;
- bitset_bindex next = bitno;
-
- if (!bitset_list (src, &val, 1, &next))
- return BITSET_BINDEX_MAX;
- return val;
-}
-
-
-/* Return true if both bitsets are of the same type and size. */
-extern bool
-bitset_compatible_p (bitset bset1, bitset bset2)
-{
- return BITSET_COMPATIBLE_ (bset1, bset2);
-}
-
-
-/* Find previous bit set in SRC starting from and including BITNO.
- Return BITSET_BINDEX_MAX if SRC empty. */
-bitset_bindex
-bitset_prev (bitset src, bitset_bindex bitno)
-{
- bitset_bindex val;
- bitset_bindex next = bitno;
-
- if (!bitset_list_reverse (src, &val, 1, &next))
- return BITSET_BINDEX_MAX;
- return val;
-}
-
-
-/* Find first set bit. */
-bitset_bindex
-bitset_first (bitset src)
-{
- return bitset_next (src, 0);
-}
-
-
-/* Find last set bit. */
-bitset_bindex
-bitset_last (bitset src)
-{
- return bitset_prev (src, 0);
-}
-
-
-/* Is BITNO in SRC the only set bit? */
-bool
-bitset_only_set_p (bitset src, bitset_bindex bitno)
-{
- bitset_bindex val[2];
- bitset_bindex next = 0;
-
- if (bitset_list (src, val, 2, &next) != 1)
- return false;
- return val[0] == bitno;
-}
-
-
-/* Print contents of bitset BSET to FILE. */
-static void
-bitset_print (FILE *file, bitset bset, bool verbose)
-{
- unsigned int pos;
- bitset_bindex i;
- bitset_iterator iter;
-
- if (verbose)
- fprintf (file, "n_bits = %lu, set = {",
- (unsigned long int) bitset_size (bset));
-
- pos = 30;
- BITSET_FOR_EACH (iter, bset, i, 0)
- {
- if (pos > 70)
- {
- fprintf (file, "\n");
- pos = 0;
- }
-
- fprintf (file, "%lu ", (unsigned long int) i);
- pos += 1 + (i >= 10) + (i >= 100);
- };
-
- if (verbose)
- fprintf (file, "}\n");
-}
-
-
-/* Dump bitset BSET to FILE. */
-void
-bitset_dump (FILE *file, bitset bset)
-{
- bitset_print (file, bset, false);
-}
-
-
-/* Release memory associated with bitsets. */
-void
-bitset_release_memory (void)
-{
- lbitset_release_memory ();
- ebitset_release_memory ();
-}
-
-
-/* Toggle bit BITNO in bitset BSET and the new value of the bit. */
-bool
-bitset_toggle_ (bitset bset, bitset_bindex bitno)
-{
- /* This routine is for completeness. It could be optimized if
- required. */
- if (bitset_test (bset, bitno))
- {
- bitset_reset (bset, bitno);
- return false;
- }
- else
- {
- bitset_set (bset, bitno);
- return true;
- }
-}
-
-
-/* Return number of bits in bitset SRC. */
-bitset_bindex
-bitset_size_ (bitset src)
-{
- return BITSET_NBITS_ (src);
-}
-
-
-/* Return number of bits set in bitset SRC. */
-bitset_bindex
-bitset_count_ (bitset src)
-{
- bitset_bindex list[BITSET_LIST_SIZE];
- bitset_bindex next;
- bitset_bindex num;
- bitset_bindex count;
-
- /* This could be greatly sped up by adding a count method for each
- bitset implementation that uses a direct technique (based on
- masks) for counting the number of bits set in a word. */
-
- next = 0;
- for (count = 0; (num = bitset_list (src, list, BITSET_LIST_SIZE, &next));
- count += num)
- continue;
-
- return count;
-}
-
-
-/* DST = SRC. Return true if DST != SRC.
- This is a fallback for the case where SRC and DST are different
- bitset types. */
-bool
-bitset_copy_ (bitset dst, bitset src)
-{
- bitset_bindex i;
- bitset_iterator iter;
-
- /* Convert bitset types. We assume that the DST bitset
- is large enough to hold the SRC bitset. */
- bitset_zero (dst);
- BITSET_FOR_EACH (iter, src, i, 0)
- {
- bitset_set (dst, i);
- };
-
- return true;
-}
-
-
-/* This is a fallback for implementations that do not support
- four operand operations. */
-static inline bool
-bitset_op4_cmp (bitset dst, bitset src1, bitset src2, bitset src3,
- enum bitset_ops op)
-{
- bool changed = false;
- bool stats_enabled_save;
- bitset tmp;
-
- /* Create temporary bitset. */
- stats_enabled_save = bitset_stats_enabled;
- bitset_stats_enabled = false;
- tmp = bitset_alloc (0, bitset_type_get (dst));
- bitset_stats_enabled = stats_enabled_save;
-
- switch (op)
- {
- default:
- abort ();
-
- case BITSET_OP_OR_AND:
- bitset_or (tmp, src1, src2);
- changed = bitset_and_cmp (dst, src3, tmp);
- break;
-
- case BITSET_OP_AND_OR:
- bitset_and (tmp, src1, src2);
- changed = bitset_or_cmp (dst, src3, tmp);
- break;
-
- case BITSET_OP_ANDN_OR:
- bitset_andn (tmp, src1, src2);
- changed = bitset_or_cmp (dst, src3, tmp);
- break;
- }
-
- bitset_free (tmp);
- return changed;
-}
-
-
-/* DST = (SRC1 & SRC2) | SRC3. */
-void
-bitset_and_or_ (bitset dst, bitset src1, bitset src2, bitset src3)
-{
- bitset_and_or_cmp_ (dst, src1, src2, src3);
-}
-
-
-/* DST = (SRC1 & SRC2) | SRC3. Return non-zero if
- DST != (SRC1 & SRC2) | SRC3. */
-bool
-bitset_and_or_cmp_ (bitset dst, bitset src1, bitset src2, bitset src3)
-{
- return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_AND_OR);
-}
-
-
-/* DST = (SRC1 & ~SRC2) | SRC3. */
-void
-bitset_andn_or_ (bitset dst, bitset src1, bitset src2, bitset src3)
-{
- bitset_andn_or_cmp_ (dst, src1, src2, src3);
-}
-
-
-/* DST = (SRC1 & ~SRC2) | SRC3. Return non-zero if
- DST != (SRC1 & ~SRC2) | SRC3. */
-bool
-bitset_andn_or_cmp_ (bitset dst, bitset src1, bitset src2, bitset src3)
-{
- return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_ANDN_OR);
-}
-
-
-/* DST = (SRC1 | SRC2) & SRC3. */
-void
-bitset_or_and_ (bitset dst, bitset src1, bitset src2, bitset src3)
-{
- bitset_or_and_cmp_ (dst, src1, src2, src3);
-}
-
-
-/* DST = (SRC1 | SRC2) & SRC3. Return non-zero if
- DST != (SRC1 | SRC2) & SRC3. */
-bool
-bitset_or_and_cmp_ (bitset dst, bitset src1, bitset src2, bitset src3)
-{
- return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_OR_AND);
-}
-
-
-/* Function to be called from debugger to print bitset. */
-void
-debug_bitset (bitset bset)
-{
- if (bset)
- bitset_print (stderr, bset, true);
-}
diff --git a/contrib/tools/m4/lib/bitset.h b/contrib/tools/m4/lib/bitset.h
deleted file mode 100644
index ef44ea4cf86..00000000000
--- a/contrib/tools/m4/lib/bitset.h
+++ /dev/null
@@ -1,393 +0,0 @@
-/* Generic bitsets.
-
- Copyright (C) 2002-2004, 2009-2013 Free Software Foundation, Inc.
-
- Contributed by Michael Hayes ([email protected]).
-
- 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 <http://www.gnu.org/licenses/>. */
-
-#ifndef _BITSET_H
-#define _BITSET_H
-
-/* This file is the public interface to the bitset abstract data type.
- Only use the functions and macros defined in this file. */
-
-#include "bbitset.h"
-#include "obstack.h"
-#include <stdio.h>
-
-#if USE_UNLOCKED_IO
-# include "unlocked-io.h"
-#endif
-
-/* Attributes used to select a bitset implementation. */
-enum bitset_attr {BITSET_FIXED = 1, /* Bitset size fixed. */
- BITSET_VARIABLE = 2, /* Bitset size variable. */
- BITSET_DENSE = 4, /* Bitset dense. */
- BITSET_SPARSE = 8, /* Bitset sparse. */
- BITSET_FRUGAL = 16, /* Prefer most compact. */
- BITSET_GREEDY = 32}; /* Prefer fastest at memory expense. */
-
-typedef unsigned int bitset_attrs;
-
-/* The contents of the union should be considered to be private.
- While I would like to make this union opaque, it needs to be
- visible for the inline bit set/test functions, and for delegation
- to the proper implementation. */
-union bitset_union
-{
- /* This must be the first member of every other structure that is a
- member of this union. */
- struct bbitset_struct b; /* Base bitset data. */
-
- struct abitset_struct
- {
- struct bbitset_struct b;
- bitset_word words[1]; /* The array of bits. */
- } a;
-
- struct ebitset_struct
- {
- struct bbitset_struct b;
- bitset_windex size; /* Number of elements. */
- struct ebitset_elt_struct **elts; /* Expanding array of ptrs to elts. */
- } e;
-
- struct lbitset_struct
- {
- struct bbitset_struct b;
- struct lbitset_elt_struct *head; /* First element in linked list. */
- struct lbitset_elt_struct *tail; /* Last element in linked list. */
- } l;
-
- struct bitset_stats_struct
- {
- struct bbitset_struct b;
- bitset bset;
- } s;
-
- struct vbitset_struct
- {
- struct bbitset_struct b;
- bitset_windex size; /* Allocated size of array. */
- } v;
-
-};
-
-
-/* The contents of this structure should be considered private.
- It is used for iterating over set bits. */
-typedef struct
-{
- bitset_bindex list[BITSET_LIST_SIZE];
- bitset_bindex next;
- bitset_bindex num;
- bitset_bindex i;
-} bitset_iterator;
-
-
-/* Return bytes required for bitset of desired type and size. */
-extern size_t bitset_bytes (enum bitset_type, bitset_bindex);
-
-/* Initialise a bitset with desired type and size. */
-extern bitset bitset_init (bitset, bitset_bindex, enum bitset_type);
-
-/* Select an implementation type based on the desired bitset size
- and attributes. */
-extern enum bitset_type bitset_type_choose (bitset_bindex, bitset_attrs);
-
-/* Create a bitset of desired type and size. The bitset is zeroed. */
-extern bitset bitset_alloc (bitset_bindex, enum bitset_type);
-
-/* Free bitset. */
-extern void bitset_free (bitset);
-
-/* Create a bitset of desired type and size using an obstack. The
- bitset is zeroed. */
-extern bitset bitset_obstack_alloc (struct obstack *bobstack,
- bitset_bindex, enum bitset_type);
-
-/* Free bitset allocated on obstack. */
-extern void bitset_obstack_free (bitset);
-
-/* Create a bitset of desired size and attributes. The bitset is zeroed. */
-extern bitset bitset_create (bitset_bindex, bitset_attrs);
-
-/* Return bitset type. */
-extern enum bitset_type bitset_type_get (bitset);
-
-/* Return bitset type name. */
-extern const char *bitset_type_name_get (bitset);
-
-
-/* Set bit BITNO in bitset BSET. */
-static inline void
-bitset_set (bitset bset, bitset_bindex bitno)
-{
- bitset_windex windex = bitno / BITSET_WORD_BITS;
- bitset_windex offset = windex - bset->b.cindex;
-
- if (offset < bset->b.csize)
- bset->b.cdata[offset] |= ((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
- else
- BITSET_SET_ (bset, bitno);
-}
-
-
-/* Reset bit BITNO in bitset BSET. */
-static inline void
-bitset_reset (bitset bset, bitset_bindex bitno)
-{
- bitset_windex windex = bitno / BITSET_WORD_BITS;
- bitset_windex offset = windex - bset->b.cindex;
-
- if (offset < bset->b.csize)
- bset->b.cdata[offset] &= ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
- else
- BITSET_RESET_ (bset, bitno);
-}
-
-
-/* Test bit BITNO in bitset BSET. */
-static inline bool
-bitset_test (bitset bset, bitset_bindex bitno)
-{
- bitset_windex windex = bitno / BITSET_WORD_BITS;
- bitset_windex offset = windex - bset->b.cindex;
-
- if (offset < bset->b.csize)
- return (bset->b.cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1;
- else
- return BITSET_TEST_ (bset, bitno);
-}
-
-
-/* Toggle bit BITNO in bitset BSET and return non-zero if now set. */
-#define bitset_toggle(bset, bitno) BITSET_TOGGLE_ (bset, bitno)
-
-/* Return size in bits of bitset SRC. */
-#define bitset_size(SRC) BITSET_SIZE_ (SRC)
-
-/* Change size of bitset. */
-extern void bitset_resize (bitset, bitset_bindex);
-
-/* Return number of bits set in bitset SRC. */
-#define bitset_count(SRC) BITSET_COUNT_ (SRC)
-
-
-/* Return SRC == 0. */
-#define bitset_empty_p(SRC) BITSET_EMPTY_P_ (SRC)
-
-/* DST = ~0. */
-#define bitset_ones(DST) BITSET_ONES_ (DST)
-
-/* DST = 0. */
-#define bitset_zero(DST) BITSET_ZERO_ (DST)
-
-
-
-/* DST = SRC. */
-#define bitset_copy(DST, SRC) BITSET_COPY_ (DST, SRC)
-
-/* Return DST & SRC == 0. */
-#define bitset_disjoint_p(DST, SRC) BITSET_DISJOINT_P_ (DST, SRC)
-
-/* Return DST == SRC. */
-#define bitset_equal_p(DST, SRC) BITSET_EQUAL_P_ (DST, SRC)
-
-/* DST = ~SRC. */
-#define bitset_not(DST, SRC) BITSET_NOT_ (DST, SRC)
-
-/* Return DST == DST | SRC. */
-#define bitset_subset_p(DST, SRC) BITSET_SUBSET_P_ (DST, SRC)
-
-
-
-/* DST = SRC1 & SRC2. */
-#define bitset_and(DST, SRC1, SRC2) BITSET_AND_ (DST, SRC1, SRC2)
-
-/* DST = SRC1 & SRC2. Return non-zero if DST != SRC1 & SRC2. */
-#define bitset_and_cmp(DST, SRC1, SRC2) BITSET_AND_CMP_ (DST, SRC1, SRC2)
-
-/* DST = SRC1 & ~SRC2. */
-#define bitset_andn(DST, SRC1, SRC2) BITSET_ANDN_ (DST, SRC1, SRC2)
-
-/* DST = SRC1 & ~SRC2. Return non-zero if DST != SRC1 & ~SRC2. */
-#define bitset_andn_cmp(DST, SRC1, SRC2) BITSET_ANDN_CMP_ (DST, SRC1, SRC2)
-
-/* DST = SRC1 | SRC2. */
-#define bitset_or(DST, SRC1, SRC2) BITSET_OR_ (DST, SRC1, SRC2)
-
-/* DST = SRC1 | SRC2. Return non-zero if DST != SRC1 | SRC2. */
-#define bitset_or_cmp(DST, SRC1, SRC2) BITSET_OR_CMP_ (DST, SRC1, SRC2)
-
-/* DST = SRC1 ^ SRC2. */
-#define bitset_xor(DST, SRC1, SRC2) BITSET_XOR_ (DST, SRC1, SRC2)
-
-/* DST = SRC1 ^ SRC2. Return non-zero if DST != SRC1 ^ SRC2. */
-#define bitset_xor_cmp(DST, SRC1, SRC2) BITSET_XOR_CMP_ (DST, SRC1, SRC2)
-
-
-
-/* DST = (SRC1 & SRC2) | SRC3. */
-#define bitset_and_or(DST, SRC1, SRC2, SRC3) \
- BITSET_AND_OR_ (DST, SRC1, SRC2, SRC3)
-
-/* DST = (SRC1 & SRC2) | SRC3. Return non-zero if
- DST != (SRC1 & SRC2) | SRC3. */
-#define bitset_and_or_cmp(DST, SRC1, SRC2, SRC3) \
- BITSET_AND_OR_CMP_ (DST, SRC1, SRC2, SRC3)
-
-/* DST = (SRC1 & ~SRC2) | SRC3. */
-#define bitset_andn_or(DST, SRC1, SRC2, SRC3) \
- BITSET_ANDN_OR_ (DST, SRC1, SRC2, SRC3)
-
-/* DST = (SRC1 & ~SRC2) | SRC3. Return non-zero if
- DST != (SRC1 & ~SRC2) | SRC3. */
-#define bitset_andn_or_cmp(DST, SRC1, SRC2, SRC3) \
- BITSET_ANDN_OR_CMP_ (DST, SRC1, SRC2, SRC3)
-
-/* DST = (SRC1 | SRC2) & SRC3. */
-#define bitset_or_and(DST, SRC1, SRC2, SRC3)\
- BITSET_OR_AND_ (DST, SRC1, SRC2, SRC3)
-
-/* DST = (SRC1 | SRC2) & SRC3. Return non-zero if
- DST != (SRC1 | SRC2) & SRC3. */
-#define bitset_or_and_cmp(DST, SRC1, SRC2, SRC3)\
- BITSET_OR_AND_CMP_ (DST, SRC1, SRC2, SRC3)
-
-/* Find list of up to NUM bits set in BSET starting from and including
- *NEXT. Return with actual number of bits found and with *NEXT
- indicating where search stopped. */
-#define bitset_list(BSET, LIST, NUM, NEXT) \
- BITSET_LIST_ (BSET, LIST, NUM, NEXT)
-
-/* Find reverse list of up to NUM bits set in BSET starting from and
- including NEXT. Return with actual number of bits found and with
- *NEXT indicating where search stopped. */
-#define bitset_list_reverse(BSET, LIST, NUM, NEXT) \
- BITSET_LIST_REVERSE_ (BSET, LIST, NUM, NEXT)
-
-/* Return true if both bitsets are of the same type and size. */
-extern bool bitset_compatible_p (bitset bset1, bitset bset2);
-
-/* Find next set bit from the given bit index. */
-extern bitset_bindex bitset_next (bitset, bitset_bindex);
-
-/* Find previous set bit from the given bit index. */
-extern bitset_bindex bitset_prev (bitset, bitset_bindex);
-
-/* Find first set bit. */
-extern bitset_bindex bitset_first (bitset);
-
-/* Find last set bit. */
-extern bitset_bindex bitset_last (bitset);
-
-/* Return nonzero if this is the only set bit. */
-extern bool bitset_only_set_p (bitset, bitset_bindex);
-
-/* Dump bitset. */
-extern void bitset_dump (FILE *, bitset);
-
-/* Loop over all elements of BSET, starting with MIN, setting INDEX
- to the index of each set bit. For example, the following will print
- the bits set in a bitset:
-
- bitset_bindex i;
- bitset_iterator iter;
-
- BITSET_FOR_EACH (iter, src, i, 0)
- {
- printf ("%lu ", (unsigned long int) i);
- };
-*/
-#define BITSET_FOR_EACH(ITER, BSET, INDEX, MIN) \
- for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE; \
- (ITER.num == BITSET_LIST_SIZE) \
- && (ITER.num = bitset_list (BSET, ITER.list, \
- BITSET_LIST_SIZE, &ITER.next));) \
- for (ITER.i = 0; \
- ITER.i < ITER.num && ((INDEX) = ITER.list[ITER.i], 1); \
- ITER.i++)
-
-
-/* Loop over all elements of BSET, in reverse order starting with
- MIN, setting INDEX to the index of each set bit. For example, the
- following will print the bits set in a bitset in reverse order:
-
- bitset_bindex i;
- bitset_iterator iter;
-
- BITSET_FOR_EACH_REVERSE (iter, src, i, 0)
- {
- printf ("%lu ", (unsigned long int) i);
- };
-*/
-#define BITSET_FOR_EACH_REVERSE(ITER, BSET, INDEX, MIN) \
- for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE; \
- (ITER.num == BITSET_LIST_SIZE) \
- && (ITER.num = bitset_list_reverse (BSET, ITER.list, \
- BITSET_LIST_SIZE, &ITER.next));) \
- for (ITER.i = 0; \
- ITER.i < ITER.num && ((INDEX) = ITER.list[ITER.i], 1); \
- ITER.i++)
-
-
-/* Define set operations in terms of logical operations. */
-
-#define bitset_diff(DST, SRC1, SRC2) bitset_andn (DST, SRC1, SRC2)
-#define bitset_diff_cmp(DST, SRC1, SRC2) bitset_andn_cmp (DST, SRC1, SRC2)
-
-#define bitset_intersection(DST, SRC1, SRC2) bitset_and (DST, SRC1, SRC2)
-#define bitset_intersection_cmp(DST, SRC1, SRC2) bitset_and_cmp (DST, SRC1, SRC2)
-
-#define bitset_union(DST, SRC1, SRC2) bitset_or (DST, SRC1, SRC2)
-#define bitset_union_cmp(DST, SRC1, SRC2) bitset_or_cmp (DST, SRC1, SRC2)
-
-/* Symmetrical difference. */
-#define bitset_symdiff(DST, SRC1, SRC2) bitset_xor (DST, SRC1, SRC2)
-#define bitset_symdiff_cmp(DST, SRC1, SRC2) bitset_xor_cmp (DST, SRC1, SRC2)
-
-/* Union of difference. */
-#define bitset_diff_union(DST, SRC1, SRC2, SRC3) \
- bitset_andn_or (DST, SRC1, SRC2, SRC3)
-#define bitset_diff_union_cmp(DST, SRC1, SRC2, SRC3) \
- bitset_andn_or_cmp (DST, SRC1, SRC2, SRC3)
-
-
-/* Release any memory tied up with bitsets. */
-extern void bitset_release_memory (void);
-
-/* Enable bitset stats gathering. */
-extern void bitset_stats_enable (void);
-
-/* Disable bitset stats gathering. */
-extern void bitset_stats_disable (void);
-
-/* Read bitset stats file of accummulated stats. */
-void bitset_stats_read (const char *file_name);
-
-/* Write bitset stats file of accummulated stats. */
-void bitset_stats_write (const char *file_name);
-
-/* Dump bitset stats. */
-extern void bitset_stats_dump (FILE *);
-
-/* Function to debug bitset from debugger. */
-extern void debug_bitset (bitset);
-
-/* Function to debug bitset stats from debugger. */
-extern void debug_bitset_stats (void);
-
-#endif /* _BITSET_H */
diff --git a/contrib/tools/m4/lib/bitset_stats.c b/contrib/tools/m4/lib/bitset_stats.c
deleted file mode 100644
index 83163026165..00000000000
--- a/contrib/tools/m4/lib/bitset_stats.c
+++ /dev/null
@@ -1,728 +0,0 @@
-/* Bitset statistics.
-
- Copyright (C) 2002-2006, 2009-2013 Free Software Foundation, Inc.
-
- Contributed by Michael Hayes ([email protected]).
-
- 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 <http://www.gnu.org/licenses/>. */
-
-/* This file is a wrapper bitset implementation for the other bitset
- implementations. It provides bitset compatibility checking and
- statistics gathering without having to instrument the bitset
- implementations. When statistics gathering is enabled, the bitset
- operations get vectored through here and we then call the appropriate
- routines. */
-
-#include <config.h>
-
-#include "bitset_stats.h"
-
-#include "bbitset.h"
-#include "abitset.h"
-#include "ebitset.h"
-#include "lbitset.h"
-#include "vbitset.h"
-#include <stdlib.h>
-#include <string.h>
-#include <stdio.h>
-
-#include "gettext.h"
-#define _(Msgid) gettext (Msgid)
-
-/* Configuration macros. */
-#define BITSET_STATS_FILE "bitset.dat"
-#define BITSET_LOG_COUNT_BINS 10
-#define BITSET_LOG_SIZE_BINS 16
-#define BITSET_DENSITY_BINS 20
-
-
-/* Accessor macros. */
-#define BITSET_STATS_ALLOCS_INC(TYPE) \
- bitset_stats_info->types[(TYPE)].allocs++
-#define BITSET_STATS_FREES_INC(BSET) \
- bitset_stats_info->types[BITSET_TYPE_ (BSET)].frees++
-#define BITSET_STATS_SETS_INC(BSET) \
- bitset_stats_info->types[BITSET_TYPE_ (BSET)].sets++
-#define BITSET_STATS_CACHE_SETS_INC(BSET) \
- bitset_stats_info->types[BITSET_TYPE_ (BSET)].cache_sets++
-#define BITSET_STATS_RESETS_INC(BSET) \
- bitset_stats_info->types[BITSET_TYPE_ (BSET)].resets++
-#define BITSET_STATS_CACHE_RESETS_INC(BSET) \
- bitset_stats_info->types[BITSET_TYPE_ (BSET)].cache_resets++
-#define BITSET_STATS_TESTS_INC(BSET) \
- bitset_stats_info->types[BITSET_TYPE_ (BSET)].tests++
-#define BITSET_STATS_CACHE_TESTS_INC(BSET) \
- bitset_stats_info->types[BITSET_TYPE_ (BSET)].cache_tests++
-#define BITSET_STATS_LISTS_INC(BSET) \
- bitset_stats_info->types[BITSET_TYPE_ (BSET)].lists++
-#define BITSET_STATS_LIST_COUNTS_INC(BSET, I) \
- bitset_stats_info->types[BITSET_TYPE_ (BSET)].list_counts[(I)]++
-#define BITSET_STATS_LIST_SIZES_INC(BSET, I) \
- bitset_stats_info->types[BITSET_TYPE_ (BSET)].list_sizes[(I)]++
-#define BITSET_STATS_LIST_DENSITY_INC(BSET, I) \
- bitset_stats_info->types[BITSET_TYPE_ (BSET)].list_density[(I)]++
-
-
-struct bitset_type_info_struct
-{
- unsigned int allocs;
- unsigned int frees;
- unsigned int lists;
- unsigned int sets;
- unsigned int cache_sets;
- unsigned int resets;
- unsigned int cache_resets;
- unsigned int tests;
- unsigned int cache_tests;
- unsigned int list_counts[BITSET_LOG_COUNT_BINS];
- unsigned int list_sizes[BITSET_LOG_SIZE_BINS];
- unsigned int list_density[BITSET_DENSITY_BINS];
-};
-
-struct bitset_stats_info_struct
-{
- unsigned int runs;
- struct bitset_type_info_struct types[BITSET_TYPE_NUM];
-};
-
-
-struct bitset_stats_info_struct bitset_stats_info_data;
-struct bitset_stats_info_struct *bitset_stats_info;
-bool bitset_stats_enabled = false;
-
-
-/* Print a percentage histogram with message MSG to FILE. */
-static void
-bitset_percent_histogram_print (FILE *file, const char *name, const char *msg,
- unsigned int n_bins, unsigned int *bins)
-{
- unsigned int i;
- unsigned int total;
-
- total = 0;
- for (i = 0; i < n_bins; i++)
- total += bins[i];
-
- if (!total)
- return;
-
- fprintf (file, "%s %s", name, msg);
- for (i = 0; i < n_bins; i++)
- fprintf (file, "%.0f-%.0f%%\t%8u (%5.1f%%)\n",
- i * 100.0 / n_bins,
- (i + 1) * 100.0 / n_bins, bins[i],
- (100.0 * bins[i]) / total);
-}
-
-
-/* Print a log histogram with message MSG to FILE. */
-static void
-bitset_log_histogram_print (FILE *file, const char *name, const char *msg,
- unsigned int n_bins, unsigned int *bins)
-{
- unsigned int i;
- unsigned int total;
- unsigned int max_width;
-
- total = 0;
- for (i = 0; i < n_bins; i++)
- total += bins[i];
-
- if (!total)
- return;
-
- /* Determine number of useful bins. */
- for (i = n_bins; i > 3 && ! bins[i - 1]; i--)
- continue;
- n_bins = i;
-
- /* 2 * ceil (log10 (2) * (N - 1)) + 1. */
- max_width = 2 * (unsigned int) (0.30103 * (n_bins - 1) + 0.9999) + 1;
-
- fprintf (file, "%s %s", name, msg);
- for (i = 0; i < 2; i++)
- fprintf (file, "%*d\t%8u (%5.1f%%)\n",
- max_width, i, bins[i], 100.0 * bins[i] / total);
-
- for (; i < n_bins; i++)
- fprintf (file, "%*lu-%lu\t%8u (%5.1f%%)\n",
- max_width - ((unsigned int) (0.30103 * (i) + 0.9999) + 1),
- 1UL << (i - 1),
- (1UL << i) - 1,
- bins[i],
- (100.0 * bins[i]) / total);
-}
-
-
-/* Print bitset statistics to FILE. */
-static void
-bitset_stats_print_1 (FILE *file, const char *name,
- struct bitset_type_info_struct *stats)
-{
- if (!stats)
- return;
-
- fprintf (file, "%s:\n", name);
- fprintf (file, _("%u bitset_allocs, %u freed (%.2f%%).\n"),
- stats->allocs, stats->frees,
- stats->allocs ? 100.0 * stats->frees / stats->allocs : 0);
- fprintf (file, _("%u bitset_sets, %u cached (%.2f%%)\n"),
- stats->sets, stats->cache_sets,
- stats->sets ? 100.0 * stats->cache_sets / stats->sets : 0);
- fprintf (file, _("%u bitset_resets, %u cached (%.2f%%)\n"),
- stats->resets, stats->cache_resets,
- stats->resets ? 100.0 * stats->cache_resets / stats->resets : 0);
- fprintf (file, _("%u bitset_tests, %u cached (%.2f%%)\n"),
- stats->tests, stats->cache_tests,
- stats->tests ? 100.0 * stats->cache_tests / stats->tests : 0);
-
- fprintf (file, _("%u bitset_lists\n"), stats->lists);
-
- bitset_log_histogram_print (file, name, _("count log histogram\n"),
- BITSET_LOG_COUNT_BINS, stats->list_counts);
-
- bitset_log_histogram_print (file, name, _("size log histogram\n"),
- BITSET_LOG_SIZE_BINS, stats->list_sizes);
-
- bitset_percent_histogram_print (file, name, _("density histogram\n"),
- BITSET_DENSITY_BINS, stats->list_density);
-}
-
-
-/* Print all bitset statistics to FILE. */
-static void
-bitset_stats_print (FILE *file, bool verbose ATTRIBUTE_UNUSED)
-{
- int i;
-
- if (!bitset_stats_info)
- return;
-
- fprintf (file, _("Bitset statistics:\n\n"));
-
- if (bitset_stats_info->runs > 1)
- fprintf (file, _("Accumulated runs = %u\n"), bitset_stats_info->runs);
-
- for (i = 0; i < BITSET_TYPE_NUM; i++)
- bitset_stats_print_1 (file, bitset_type_names[i],
- &bitset_stats_info->types[i]);
-}
-
-
-/* Initialise bitset statistics logging. */
-void
-bitset_stats_enable (void)
-{
- if (!bitset_stats_info)
- bitset_stats_info = &bitset_stats_info_data;
- bitset_stats_enabled = true;
-}
-
-
-void
-bitset_stats_disable (void)
-{
- bitset_stats_enabled = false;
-}
-
-
-/* Read bitset statistics file. */
-void
-bitset_stats_read (const char *file_name)
-{
- FILE *file;
-
- if (!bitset_stats_info)
- return;
-
- if (!file_name)
- file_name = BITSET_STATS_FILE;
-
- file = fopen (file_name, "r");
- if (file)
- {
- if (fread (&bitset_stats_info_data, sizeof (bitset_stats_info_data),
- 1, file) != 1)
- {
- if (ferror (file))
- perror (_("cannot read stats file"));
- else
- fprintf (stderr, _("bad stats file size\n"));
- }
- if (fclose (file) != 0)
- perror (_("cannot read stats file"));
- }
- bitset_stats_info_data.runs++;
-}
-
-
-/* Write bitset statistics file. */
-void
-bitset_stats_write (const char *file_name)
-{
- FILE *file;
-
- if (!bitset_stats_info)
- return;
-
- if (!file_name)
- file_name = BITSET_STATS_FILE;
-
- file = fopen (file_name, "w");
- if (file)
- {
- if (fwrite (&bitset_stats_info_data, sizeof (bitset_stats_info_data),
- 1, file) != 1)
- perror (_("cannot write stats file"));
- if (fclose (file) != 0)
- perror (_("cannot write stats file"));
- }
- else
- perror (_("cannot open stats file for writing"));
-}
-
-
-/* Dump bitset statistics to FILE. */
-void
-bitset_stats_dump (FILE *file)
-{
- bitset_stats_print (file, false);
-}
-
-
-/* Function to be called from debugger to print bitset stats. */
-void
-debug_bitset_stats (void)
-{
- bitset_stats_print (stderr, true);
-}
-
-
-static void
-bitset_stats_set (bitset dst, bitset_bindex bitno)
-{
- bitset bset = dst->s.bset;
- bitset_windex wordno = bitno / BITSET_WORD_BITS;
- bitset_windex offset = wordno - bset->b.cindex;
-
- BITSET_STATS_SETS_INC (bset);
-
- if (offset < bset->b.csize)
- {
- bset->b.cdata[offset] |= (bitset_word) 1 << (bitno % BITSET_WORD_BITS);
- BITSET_STATS_CACHE_SETS_INC (bset);
- }
- else
- BITSET_SET_ (bset, bitno);
-}
-
-
-static void
-bitset_stats_reset (bitset dst, bitset_bindex bitno)
-{
- bitset bset = dst->s.bset;
- bitset_windex wordno = bitno / BITSET_WORD_BITS;
- bitset_windex offset = wordno - bset->b.cindex;
-
- BITSET_STATS_RESETS_INC (bset);
-
- if (offset < bset->b.csize)
- {
- bset->b.cdata[offset] &=
- ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
- BITSET_STATS_CACHE_RESETS_INC (bset);
- }
- else
- BITSET_RESET_ (bset, bitno);
-}
-
-
-static bool
-bitset_stats_toggle (bitset src, bitset_bindex bitno)
-{
- return BITSET_TOGGLE_ (src->s.bset, bitno);
-}
-
-
-static bool
-bitset_stats_test (bitset src, bitset_bindex bitno)
-{
- bitset bset = src->s.bset;
- bitset_windex wordno = bitno / BITSET_WORD_BITS;
- bitset_windex offset = wordno - bset->b.cindex;
-
- BITSET_STATS_TESTS_INC (bset);
-
- if (offset < bset->b.csize)
- {
- BITSET_STATS_CACHE_TESTS_INC (bset);
- return (bset->b.cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1;
- }
- else
- return BITSET_TEST_ (bset, bitno);
-}
-
-
-static bitset_bindex
-bitset_stats_resize (bitset src, bitset_bindex size)
-{
- return BITSET_RESIZE_ (src->s.bset, size);
-}
-
-
-static bitset_bindex
-bitset_stats_size (bitset src)
-{
- return BITSET_SIZE_ (src->s.bset);
-}
-
-
-static bitset_bindex
-bitset_stats_count (bitset src)
-{
- return BITSET_COUNT_ (src->s.bset);
-}
-
-
-static bool
-bitset_stats_empty_p (bitset dst)
-{
- return BITSET_EMPTY_P_ (dst->s.bset);
-}
-
-
-static void
-bitset_stats_ones (bitset dst)
-{
- BITSET_ONES_ (dst->s.bset);
-}
-
-
-static void
-bitset_stats_zero (bitset dst)
-{
- BITSET_ZERO_ (dst->s.bset);
-}
-
-
-static void
-bitset_stats_copy (bitset dst, bitset src)
-{
- BITSET_CHECK2_ (dst, src);
- BITSET_COPY_ (dst->s.bset, src->s.bset);
-}
-
-
-static bool
-bitset_stats_disjoint_p (bitset dst, bitset src)
-{
- BITSET_CHECK2_ (dst, src);
- return BITSET_DISJOINT_P_ (dst->s.bset, src->s.bset);
-}
-
-
-static bool
-bitset_stats_equal_p (bitset dst, bitset src)
-{
- BITSET_CHECK2_ (dst, src);
- return BITSET_EQUAL_P_ (dst->s.bset, src->s.bset);
-}
-
-
-static void
-bitset_stats_not (bitset dst, bitset src)
-{
- BITSET_CHECK2_ (dst, src);
- BITSET_NOT_ (dst->s.bset, src->s.bset);
-}
-
-
-static bool
-bitset_stats_subset_p (bitset dst, bitset src)
-{
- BITSET_CHECK2_ (dst, src);
- return BITSET_SUBSET_P_ (dst->s.bset, src->s.bset);
-}
-
-
-static void
-bitset_stats_and (bitset dst, bitset src1, bitset src2)
-{
- BITSET_CHECK3_ (dst, src1, src2);
- BITSET_AND_ (dst->s.bset, src1->s.bset, src2->s.bset);
-}
-
-
-static bool
-bitset_stats_and_cmp (bitset dst, bitset src1, bitset src2)
-{
- BITSET_CHECK3_ (dst, src1, src2);
- return BITSET_AND_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset);
-}
-
-
-static void
-bitset_stats_andn (bitset dst, bitset src1, bitset src2)
-{
- BITSET_CHECK3_ (dst, src1, src2);
- BITSET_ANDN_ (dst->s.bset, src1->s.bset, src2->s.bset);
-}
-
-
-static bool
-bitset_stats_andn_cmp (bitset dst, bitset src1, bitset src2)
-{
- BITSET_CHECK3_ (dst, src1, src2);
- return BITSET_ANDN_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset);
-}
-
-
-static void
-bitset_stats_or (bitset dst, bitset src1, bitset src2)
-{
- BITSET_CHECK3_ (dst, src1, src2);
- BITSET_OR_ (dst->s.bset, src1->s.bset, src2->s.bset);
-}
-
-
-static bool
-bitset_stats_or_cmp (bitset dst, bitset src1, bitset src2)
-{
- BITSET_CHECK3_ (dst, src1, src2);
- return BITSET_OR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset);
-}
-
-
-static void
-bitset_stats_xor (bitset dst, bitset src1, bitset src2)
-{
- BITSET_CHECK3_ (dst, src1, src2);
- BITSET_XOR_ (dst->s.bset, src1->s.bset, src2->s.bset);
-}
-
-
-static bool
-bitset_stats_xor_cmp (bitset dst, bitset src1, bitset src2)
-{
- BITSET_CHECK3_ (dst, src1, src2);
- return BITSET_XOR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset);
-}
-
-
-static void
-bitset_stats_and_or (bitset dst, bitset src1, bitset src2, bitset src3)
-{
- BITSET_CHECK4_ (dst, src1, src2, src3);
- BITSET_AND_OR_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
-}
-
-
-static bool
-bitset_stats_and_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
-{
- BITSET_CHECK4_ (dst, src1, src2, src3);
- return BITSET_AND_OR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
-}
-
-
-static void
-bitset_stats_andn_or (bitset dst, bitset src1, bitset src2, bitset src3)
-{
- BITSET_CHECK4_ (dst, src1, src2, src3);
- BITSET_ANDN_OR_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
-}
-
-
-static bool
-bitset_stats_andn_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
-{
- BITSET_CHECK4_ (dst, src1, src2, src3);
- return BITSET_ANDN_OR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
-}
-
-
-static void
-bitset_stats_or_and (bitset dst, bitset src1, bitset src2, bitset src3)
-{
- BITSET_CHECK4_ (dst, src1, src2, src3);
- BITSET_OR_AND_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
-}
-
-
-static bool
-bitset_stats_or_and_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
-{
- BITSET_CHECK4_ (dst, src1, src2, src3);
- return BITSET_OR_AND_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
-}
-
-
-static bitset_bindex
-bitset_stats_list (bitset bset, bitset_bindex *list,
- bitset_bindex num, bitset_bindex *next)
-{
- bitset_bindex count;
- bitset_bindex tmp;
- bitset_bindex size;
- bitset_bindex i;
-
- count = BITSET_LIST_ (bset->s.bset, list, num, next);
-
- BITSET_STATS_LISTS_INC (bset->s.bset);
-
- /* Log histogram of number of set bits. */
- for (i = 0, tmp = count; tmp; tmp >>= 1, i++)
- continue;
- if (i >= BITSET_LOG_COUNT_BINS)
- i = BITSET_LOG_COUNT_BINS - 1;
- BITSET_STATS_LIST_COUNTS_INC (bset->s.bset, i);
-
- /* Log histogram of number of bits in set. */
- size = BITSET_SIZE_ (bset->s.bset);
- for (i = 0, tmp = size; tmp; tmp >>= 1, i++)
- continue;
- if (i >= BITSET_LOG_SIZE_BINS)
- i = BITSET_LOG_SIZE_BINS - 1;
- BITSET_STATS_LIST_SIZES_INC (bset->s.bset, i);
-
- /* Histogram of fraction of bits set. */
- i = size ? (count * BITSET_DENSITY_BINS) / size : 0;
- if (i >= BITSET_DENSITY_BINS)
- i = BITSET_DENSITY_BINS - 1;
- BITSET_STATS_LIST_DENSITY_INC (bset->s.bset, i);
- return count;
-}
-
-
-static bitset_bindex
-bitset_stats_list_reverse (bitset bset, bitset_bindex *list,
- bitset_bindex num, bitset_bindex *next)
-{
- return BITSET_LIST_REVERSE_ (bset->s.bset, list, num, next);
-}
-
-
-static void
-bitset_stats_free (bitset bset)
-{
- BITSET_STATS_FREES_INC (bset->s.bset);
- BITSET_FREE_ (bset->s.bset);
-}
-
-
-struct bitset_vtable bitset_stats_vtable = {
- bitset_stats_set,
- bitset_stats_reset,
- bitset_stats_toggle,
- bitset_stats_test,
- bitset_stats_resize,
- bitset_stats_size,
- bitset_stats_count,
- bitset_stats_empty_p,
- bitset_stats_ones,
- bitset_stats_zero,
- bitset_stats_copy,
- bitset_stats_disjoint_p,
- bitset_stats_equal_p,
- bitset_stats_not,
- bitset_stats_subset_p,
- bitset_stats_and,
- bitset_stats_and_cmp,
- bitset_stats_andn,
- bitset_stats_andn_cmp,
- bitset_stats_or,
- bitset_stats_or_cmp,
- bitset_stats_xor,
- bitset_stats_xor_cmp,
- bitset_stats_and_or,
- bitset_stats_and_or_cmp,
- bitset_stats_andn_or,
- bitset_stats_andn_or_cmp,
- bitset_stats_or_and,
- bitset_stats_or_and_cmp,
- bitset_stats_list,
- bitset_stats_list_reverse,
- bitset_stats_free,
- BITSET_STATS
-};
-
-
-/* Return enclosed bitset type. */
-enum bitset_type
-bitset_stats_type_get (bitset bset)
-{
- return BITSET_TYPE_ (bset->s.bset);
-}
-
-
-size_t
-bitset_stats_bytes (void)
-{
- return sizeof (struct bitset_stats_struct);
-}
-
-
-bitset
-bitset_stats_init (bitset bset, bitset_bindex n_bits, enum bitset_type type)
-{
- size_t bytes;
- bitset sbset;
-
- bset->b.vtable = &bitset_stats_vtable;
-
- /* Disable cache. */
- bset->b.cindex = 0;
- bset->b.csize = 0;
- bset->b.cdata = 0;
-
- BITSET_NBITS_ (bset) = n_bits;
-
- /* Set up the actual bitset implementation that
- we are a wrapper over. */
- switch (type)
- {
- default:
- abort ();
-
- case BITSET_ARRAY:
- bytes = abitset_bytes (n_bits);
- sbset = xcalloc (1, bytes);
- abitset_init (sbset, n_bits);
- break;
-
- case BITSET_LIST:
- bytes = lbitset_bytes (n_bits);
- sbset = xcalloc (1, bytes);
- lbitset_init (sbset, n_bits);
- break;
-
- case BITSET_TABLE:
- bytes = ebitset_bytes (n_bits);
- sbset = xcalloc (1, bytes);
- ebitset_init (sbset, n_bits);
- break;
-
- case BITSET_VARRAY:
- bytes = vbitset_bytes (n_bits);
- sbset = xcalloc (1, bytes);
- vbitset_init (sbset, n_bits);
- break;
- }
-
- bset->s.bset = sbset;
-
- BITSET_STATS_ALLOCS_INC (type);
-
- return bset;
-}
diff --git a/contrib/tools/m4/lib/bitset_stats.h b/contrib/tools/m4/lib/bitset_stats.h
deleted file mode 100644
index d65fcad93cf..00000000000
--- a/contrib/tools/m4/lib/bitset_stats.h
+++ /dev/null
@@ -1,33 +0,0 @@
-/* Functions to support bitset statistics.
-
- Copyright (C) 2002-2004, 2009-2013 Free Software Foundation, Inc.
-
- Contributed by Michael Hayes ([email protected]).
-
- 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 <http://www.gnu.org/licenses/>. */
-
-#ifndef _BITSET_STATS_H
-#define _BITSET_STATS_H
-
-#include "bbitset.h"
-
-extern bool bitset_stats_enabled;
-
-extern enum bitset_type bitset_stats_type_get (bitset);
-
-extern size_t bitset_stats_bytes (void);
-
-extern bitset bitset_stats_init (bitset, bitset_bindex, enum bitset_type);
-
-#endif
diff --git a/contrib/tools/m4/lib/bitsetv-print.c b/contrib/tools/m4/lib/bitsetv-print.c
deleted file mode 100644
index dd544a9c9ea..00000000000
--- a/contrib/tools/m4/lib/bitsetv-print.c
+++ /dev/null
@@ -1,71 +0,0 @@
-/* Bitset vectors.
-
- Copyright (C) 2001-2002, 2004, 2006, 2009-2013 Free Software
- Foundation, Inc.
-
- 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 <http://www.gnu.org/licenses/>. */
-
-#include <config.h>
-
-#include "bitsetv-print.h"
-
-#include <stdlib.h>
-
-/*--------------------------------------------------------.
-| Display the MATRIX array of SIZE bitsets of size SIZE. |
-`--------------------------------------------------------*/
-
-void
-bitsetv_matrix_dump (FILE * out, const char *title, bitsetv bset)
-{
- bitset_bindex i, j;
- bitset_bindex hsize = bitset_size (bset[0]);
-
- /* Title. */
- fprintf (out, "%s BEGIN\n", title);
-
- /* Column numbers. */
- fputs (" ", out);
- for (i = 0; i < hsize; ++i)
- putc (i / 10 ? '0' + i / 10 : ' ', out);
- putc ('\n', out);
- fputs (" ", out);
- for (i = 0; i < hsize; ++i)
- fprintf (out, "%d", (int) (i % 10));
- putc ('\n', out);
-
- /* Bar. */
- fputs (" .", out);
- for (i = 0; i < hsize; ++i)
- putc ('-', out);
- fputs (".\n", out);
-
- /* Contents. */
- for (i = 0; bset[i]; ++i)
- {
- fprintf (out, "%2lu|", (unsigned long int) i);
- for (j = 0; j < hsize; ++j)
- fputs (bitset_test (bset[i], j) ? "1" : " ", out);
- fputs ("|\n", out);
- }
-
- /* Bar. */
- fputs (" `", out);
- for (i = 0; i < hsize; ++i)
- putc ('-', out);
- fputs ("'\n", out);
-
- /* End title. */
- fprintf (out, "%s END\n\n", title);
-}
diff --git a/contrib/tools/m4/lib/bitsetv-print.h b/contrib/tools/m4/lib/bitsetv-print.h
deleted file mode 100644
index a7cc8bc1068..00000000000
--- a/contrib/tools/m4/lib/bitsetv-print.h
+++ /dev/null
@@ -1,28 +0,0 @@
-/* Bitset vectors.
-
- Copyright (C) 2002, 2004, 2009-2013 Free Software Foundation, Inc.
-
- Contributed by Akim Demaille ([email protected]).
-
- 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 <http://www.gnu.org/licenses/>. */
-
-#ifndef _BITSETV_PRINT_H
-#define _BITSETV_PRINT_H
-
-#include "bitsetv.h"
-
-/* Dump vector of bitsets as a matrix. */
-extern void bitsetv_matrix_dump (FILE *, const char *, bitsetv);
-
-#endif /* _BITSETV_H */
diff --git a/contrib/tools/m4/lib/bitsetv.c b/contrib/tools/m4/lib/bitsetv.c
deleted file mode 100644
index 2bdf1bfa1a6..00000000000
--- a/contrib/tools/m4/lib/bitsetv.c
+++ /dev/null
@@ -1,169 +0,0 @@
-/* Bitset vectors.
-
- Copyright (C) 2001-2002, 2004-2006, 2009-2013 Free Software
- Foundation, Inc.
-
- 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 <http://www.gnu.org/licenses/>. */
-
-#include <config.h>
-
-#include "bitsetv.h"
-
-#include <stdlib.h>
-
-
-/* Create a vector of N_VECS bitsets, each of N_BITS, and of
- type TYPE. */
-bitset *
-bitsetv_alloc (bitset_bindex n_vecs, bitset_bindex n_bits,
- enum bitset_type type)
-{
- size_t vector_bytes;
- size_t bytes;
- bitset *bsetv;
- bitset_bindex i;
-
- /* Determine number of bytes for each set. */
- bytes = bitset_bytes (type, n_bits);
-
- /* If size calculation overflows, memory is exhausted. */
- if (BITSET_SIZE_MAX / (sizeof (bitset) + bytes) <= n_vecs)
- xalloc_die ();
-
- /* Allocate vector table at head of bitset array. */
- vector_bytes = (n_vecs + 1) * sizeof (bitset) + bytes - 1;
- vector_bytes -= vector_bytes % bytes;
- bsetv = xcalloc (1, vector_bytes + bytes * n_vecs);
-
- for (i = 0; i < n_vecs; i++)
- {
- bsetv[i] = (bitset) (void *) ((char *) bsetv + vector_bytes + i * bytes);
-
- bitset_init (bsetv[i], n_bits, type);
- }
-
- /* Null terminate table. */
- bsetv[i] = 0;
- return bsetv;
-}
-
-
-/* Create a vector of N_VECS bitsets, each of N_BITS, and with
- attribute hints specified by ATTR. */
-bitset *
-bitsetv_create (bitset_bindex n_vecs, bitset_bindex n_bits, unsigned int attr)
-{
- enum bitset_type type;
-
- type = bitset_type_choose (n_bits, attr);
- return bitsetv_alloc (n_vecs, n_bits, type);
-}
-
-
-/* Free bitset vector BSETV. */
-void
-bitsetv_free (bitsetv bsetv)
-{
- bitset_bindex i;
-
- for (i = 0; bsetv[i]; i++)
- BITSET_FREE_ (bsetv[i]);
- free (bsetv);
-}
-
-
-/* Zero a vector of bitsets. */
-void
-bitsetv_zero (bitsetv bsetv)
-{
- bitset_bindex i;
-
- for (i = 0; bsetv[i]; i++)
- bitset_zero (bsetv[i]);
-}
-
-
-/* Set a vector of bitsets to ones. */
-void
-bitsetv_ones (bitsetv bsetv)
-{
- bitset_bindex i;
-
- for (i = 0; bsetv[i]; i++)
- bitset_ones (bsetv[i]);
-}
-
-
-/* Given a vector BSETV of N bitsets of size N, modify its contents to
- be the transitive closure of what was given. */
-void
-bitsetv_transitive_closure (bitsetv bsetv)
-{
- bitset_bindex i;
- bitset_bindex j;
-
- for (i = 0; bsetv[i]; i++)
- for (j = 0; bsetv[j]; j++)
- if (bitset_test (bsetv[j], i))
- bitset_or (bsetv[j], bsetv[j], bsetv[i]);
-}
-
-
-/* Given a vector BSETV of N bitsets of size N, modify its contents to
- be the reflexive transitive closure of what was given. This is
- the same as transitive closure but with all bits on the diagonal
- of the bit matrix set. */
-void
-bitsetv_reflexive_transitive_closure (bitsetv bsetv)
-{
- bitset_bindex i;
-
- bitsetv_transitive_closure (bsetv);
- for (i = 0; bsetv[i]; i++)
- bitset_set (bsetv[i], i);
-}
-
-
-/* Dump the contents of a bitset vector BSETV with N_VECS elements to
- FILE. */
-void
-bitsetv_dump (FILE *file, char const *title, char const *subtitle,
- bitsetv bsetv)
-{
- bitset_windex i;
-
- fprintf (file, "%s\n", title);
- for (i = 0; bsetv[i]; i++)
- {
- fprintf (file, "%s %lu\n", subtitle, (unsigned long int) i);
- bitset_dump (file, bsetv[i]);
- }
-
- fprintf (file, "\n");
-}
-
-
-void
-debug_bitsetv (bitsetv bsetv)
-{
- bitset_windex i;
-
- for (i = 0; bsetv[i]; i++)
- {
- fprintf (stderr, "%lu: ", (unsigned long int) i);
- debug_bitset (bsetv[i]);
- }
-
- fprintf (stderr, "\n");
-}
diff --git a/contrib/tools/m4/lib/bitsetv.h b/contrib/tools/m4/lib/bitsetv.h
deleted file mode 100644
index 2472a82a5cf..00000000000
--- a/contrib/tools/m4/lib/bitsetv.h
+++ /dev/null
@@ -1,60 +0,0 @@
-/* Bitset vectors.
-
- Copyright (C) 2002, 2004, 2009-2013 Free Software Foundation, Inc.
-
- Contributed by Michael Hayes ([email protected]).
-
- 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 <http://www.gnu.org/licenses/>. */
-
-#ifndef _BITSETV_H
-#define _BITSETV_H
-
-#include "bitset.h"
-
-typedef bitset * bitsetv;
-
-/* Create a vector of N_VECS bitsets, each of N_BITS, and of
- type TYPE. */
-extern bitsetv bitsetv_alloc (bitset_bindex, bitset_bindex, enum bitset_type);
-
-/* Create a vector of N_VECS bitsets, each of N_BITS, and with
- attribute hints specified by ATTR. */
-extern bitsetv bitsetv_create (bitset_bindex, bitset_bindex, unsigned int);
-
-/* Free vector of bitsets. */
-extern void bitsetv_free (bitsetv);
-
-/* Zero vector of bitsets. */
-extern void bitsetv_zero (bitsetv);
-
-/* Set vector of bitsets. */
-extern void bitsetv_ones (bitsetv);
-
-/* Given a vector BSETV of N bitsets of size N, modify its contents to
- be the transitive closure of what was given. */
-extern void bitsetv_transitive_closure (bitsetv);
-
-/* Given a vector BSETV of N bitsets of size N, modify its contents to
- be the reflexive transitive closure of what was given. This is
- the same as transitive closure but with all bits on the diagonal
- of the bit matrix set. */
-extern void bitsetv_reflexive_transitive_closure (bitsetv);
-
-/* Dump vector of bitsets. */
-extern void bitsetv_dump (FILE *, const char *, const char *, bitsetv);
-
-/* Function to debug vector of bitsets from debugger. */
-extern void debug_bitsetv (bitsetv);
-
-#endif /* _BITSETV_H */
diff --git a/contrib/tools/m4/lib/concat-filename.c b/contrib/tools/m4/lib/concat-filename.c
index b749d6838b2..68168dcd53e 100644
--- a/contrib/tools/m4/lib/concat-filename.c
+++ b/contrib/tools/m4/lib/concat-filename.c
@@ -23,7 +23,7 @@
#include <errno.h>
#include <stdlib.h>
-#include "string--.h"
+#include <string.h>
#include "filename.h"
diff --git a/contrib/tools/m4/lib/ebitset.c b/contrib/tools/m4/lib/ebitset.c
deleted file mode 100644
index e5d6c9239b7..00000000000
--- a/contrib/tools/m4/lib/ebitset.c
+++ /dev/null
@@ -1,1361 +0,0 @@
-/* Functions to support expandable bitsets.
-
- Copyright (C) 2002-2006, 2009-2013 Free Software Foundation, Inc.
-
- Contributed by Michael Hayes ([email protected]).
-
- 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 <http://www.gnu.org/licenses/>. */
-
-#include <config.h>
-
-#include "ebitset.h"
-
-#include "obstack.h"
-#include <stdlib.h>
-#include <string.h>
-
-/* This file implements expandable bitsets. These bitsets can be of
- arbitrary length and are more efficient than arrays of bits for
- large sparse sets.
-
- Empty elements are represented by a NULL pointer in the table of
- element pointers. An alternative is to point to a special zero
- element. Similarly, we could represent an all 1's element with
- another special ones element pointer.
-
- Bitsets are commonly empty so we need to ensure that this special
- case is fast. A zero bitset is indicated when cdata is 0. This is
- conservative since cdata may be non zero and the bitset may still
- be zero.
-
- The bitset cache can be disabled either by setting cindex to
- BITSET_WINDEX_MAX or by setting csize to 0. Here
- we use the former approach since cindex needs to be updated whenever
- cdata is changed.
-*/
-
-
-/* Number of words to use for each element. */
-#define EBITSET_ELT_WORDS 2
-
-/* Number of bits stored in each element. */
-#define EBITSET_ELT_BITS \
- ((unsigned int) (EBITSET_ELT_WORDS * BITSET_WORD_BITS))
-
-/* Ebitset element. We use an array of bits. */
-typedef struct ebitset_elt_struct
-{
- union
- {
- bitset_word words[EBITSET_ELT_WORDS]; /* Bits that are set. */
- struct ebitset_elt_struct *next;
- }
- u;
-}
-ebitset_elt;
-
-
-typedef ebitset_elt *ebitset_elts;
-
-
-/* Number of elements to initially allocate. */
-
-#ifndef EBITSET_INITIAL_SIZE
-#define EBITSET_INITIAL_SIZE 2
-#endif
-
-
-enum ebitset_find_mode
- { EBITSET_FIND, EBITSET_CREATE, EBITSET_SUBST };
-
-static ebitset_elt ebitset_zero_elts[1]; /* Elements of all zero bits. */
-
-/* Obstack to allocate bitset elements from. */
-static struct obstack ebitset_obstack;
-static bool ebitset_obstack_init = false;
-static ebitset_elt *ebitset_free_list; /* Free list of bitset elements. */
-
-#define EBITSET_N_ELTS(N) (((N) + EBITSET_ELT_BITS - 1) / EBITSET_ELT_BITS)
-#define EBITSET_ELTS(BSET) ((BSET)->e.elts)
-#define EBITSET_SIZE(BSET) EBITSET_N_ELTS (BITSET_NBITS_ (BSET))
-#define EBITSET_ASIZE(BSET) ((BSET)->e.size)
-
-#define EBITSET_NEXT(ELT) ((ELT)->u.next)
-#define EBITSET_WORDS(ELT) ((ELT)->u.words)
-
-/* Disable bitset cache and mark BSET as being zero. */
-#define EBITSET_ZERO_SET(BSET) ((BSET)->b.cindex = BITSET_WINDEX_MAX, \
- (BSET)->b.cdata = 0)
-
-#define EBITSET_CACHE_DISABLE(BSET) ((BSET)->b.cindex = BITSET_WINDEX_MAX)
-
-/* Disable bitset cache and mark BSET as being possibly non-zero. */
-#define EBITSET_NONZERO_SET(BSET) \
- (EBITSET_CACHE_DISABLE (BSET), (BSET)->b.cdata = (bitset_word *)~0)
-
-/* A conservative estimate of whether the bitset is zero.
- This is non-zero only if we know for sure that the bitset is zero. */
-#define EBITSET_ZERO_P(BSET) ((BSET)->b.cdata == 0)
-
-/* Enable cache to point to element with table index EINDEX.
- The element must exist. */
-#define EBITSET_CACHE_SET(BSET, EINDEX) \
- ((BSET)->b.cindex = (EINDEX) * EBITSET_ELT_WORDS, \
- (BSET)->b.cdata = EBITSET_WORDS (EBITSET_ELTS (BSET) [EINDEX]))
-
-#undef min
-#undef max
-#define min(a, b) ((a) > (b) ? (b) : (a))
-#define max(a, b) ((a) > (b) ? (a) : (b))
-
-static bitset_bindex
-ebitset_resize (bitset src, bitset_bindex n_bits)
-{
- bitset_windex oldsize;
- bitset_windex newsize;
-
- if (n_bits == BITSET_NBITS_ (src))
- return n_bits;
-
- oldsize = EBITSET_SIZE (src);
- newsize = EBITSET_N_ELTS (n_bits);
-
- if (oldsize < newsize)
- {
- bitset_windex size;
-
- /* The bitset needs to grow. If we already have enough memory
- allocated, then just zero what we need. */
- if (newsize > EBITSET_ASIZE (src))
- {
- /* We need to allocate more memory. When oldsize is
- non-zero this means that we are changing the size, so
- grow the bitset 25% larger than requested to reduce
- number of reallocations. */
-
- if (oldsize == 0)
- size = newsize;
- else
- size = newsize + newsize / 4;
-
- EBITSET_ELTS (src)
- = realloc (EBITSET_ELTS (src), size * sizeof (ebitset_elt *));
- EBITSET_ASIZE (src) = size;
- }
-
- memset (EBITSET_ELTS (src) + oldsize, 0,
- (newsize - oldsize) * sizeof (ebitset_elt *));
- }
- else
- {
- /* The bitset needs to shrink. There's no point deallocating
- the memory unless it is shrinking by a reasonable amount. */
- if ((oldsize - newsize) >= oldsize / 2)
- {
- EBITSET_ELTS (src)
- = realloc (EBITSET_ELTS (src), newsize * sizeof (ebitset_elt *));
- EBITSET_ASIZE (src) = newsize;
- }
-
- /* Need to prune any excess bits. FIXME. */
- }
-
- BITSET_NBITS_ (src) = n_bits;
- return n_bits;
-}
-
-
-/* Allocate a ebitset element. The bits are not cleared. */
-static inline ebitset_elt *
-ebitset_elt_alloc (void)
-{
- ebitset_elt *elt;
-
- if (ebitset_free_list != 0)
- {
- elt = ebitset_free_list;
- ebitset_free_list = EBITSET_NEXT (elt);
- }
- else
- {
- if (!ebitset_obstack_init)
- {
- ebitset_obstack_init = true;
-
- /* Let particular systems override the size of a chunk. */
-
-#ifndef OBSTACK_CHUNK_SIZE
-#define OBSTACK_CHUNK_SIZE 0
-#endif
-
- /* Let them override the alloc and free routines too. */
-
-#ifndef OBSTACK_CHUNK_ALLOC
-#define OBSTACK_CHUNK_ALLOC xmalloc
-#endif
-
-#ifndef OBSTACK_CHUNK_FREE
-#define OBSTACK_CHUNK_FREE free
-#endif
-
-#if ! defined __GNUC__ || __GNUC__ < 2
-#define __alignof__(type) 0
-#endif
-
- obstack_specify_allocation (&ebitset_obstack, OBSTACK_CHUNK_SIZE,
- __alignof__ (ebitset_elt),
- OBSTACK_CHUNK_ALLOC,
- OBSTACK_CHUNK_FREE);
- }
-
- /* Perhaps we should add a number of new elements to the free
- list. */
- elt = (ebitset_elt *) obstack_alloc (&ebitset_obstack,
- sizeof (ebitset_elt));
- }
-
- return elt;
-}
-
-
-/* Allocate a ebitset element. The bits are cleared. */
-static inline ebitset_elt *
-ebitset_elt_calloc (void)
-{
- ebitset_elt *elt;
-
- elt = ebitset_elt_alloc ();
- memset (EBITSET_WORDS (elt), 0, sizeof (EBITSET_WORDS (elt)));
- return elt;
-}
-
-
-static inline void
-ebitset_elt_free (ebitset_elt *elt)
-{
- EBITSET_NEXT (elt) = ebitset_free_list;
- ebitset_free_list = elt;
-}
-
-
-/* Remove element with index EINDEX from bitset BSET. */
-static inline void
-ebitset_elt_remove (bitset bset, bitset_windex eindex)
-{
- ebitset_elts *elts;
- ebitset_elt *elt;
-
- elts = EBITSET_ELTS (bset);
-
- elt = elts[eindex];
-
- elts[eindex] = 0;
- ebitset_elt_free (elt);
-}
-
-
-/* Add ELT into elts at index EINDEX of bitset BSET. */
-static inline void
-ebitset_elt_add (bitset bset, ebitset_elt *elt, bitset_windex eindex)
-{
- ebitset_elts *elts;
-
- elts = EBITSET_ELTS (bset);
- /* Assume that the elts entry not allocated. */
- elts[eindex] = elt;
-}
-
-
-/* Are all bits in an element zero? */
-static inline bool
-ebitset_elt_zero_p (ebitset_elt *elt)
-{
- int i;
-
- for (i = 0; i < EBITSET_ELT_WORDS; i++)
- if (EBITSET_WORDS (elt)[i])
- return false;
-
- return true;
-}
-
-
-static ebitset_elt *
-ebitset_elt_find (bitset bset, bitset_bindex bindex,
- enum ebitset_find_mode mode)
-{
- ebitset_elt *elt;
- bitset_windex size;
- bitset_windex eindex;
- ebitset_elts *elts;
-
- eindex = bindex / EBITSET_ELT_BITS;
-
- elts = EBITSET_ELTS (bset);
- size = EBITSET_SIZE (bset);
-
- if (eindex < size)
- {
- if ((elt = elts[eindex]))
- {
- if (EBITSET_WORDS (elt) == bset->b.cdata)
- return elt;
-
- EBITSET_CACHE_SET (bset, eindex);
- return elt;
- }
- }
-
- /* The element could not be found. */
-
- switch (mode)
- {
- default:
- abort ();
-
- case EBITSET_FIND:
- return 0;
-
- case EBITSET_CREATE:
- if (eindex >= size)
- ebitset_resize (bset, bindex);
-
- /* Create a new element. */
- elt = ebitset_elt_calloc ();
- ebitset_elt_add (bset, elt, eindex);
- EBITSET_CACHE_SET (bset, eindex);
- return elt;
-
- case EBITSET_SUBST:
- return &ebitset_zero_elts[0];
- }
-}
-
-
-/* Weed out the zero elements from the elts. */
-static inline bitset_windex
-ebitset_weed (bitset bset)
-{
- ebitset_elts *elts;
- bitset_windex j;
- bitset_windex count;
-
- if (EBITSET_ZERO_P (bset))
- return 0;
-
- elts = EBITSET_ELTS (bset);
- count = 0;
- for (j = 0; j < EBITSET_SIZE (bset); j++)
- {
- ebitset_elt *elt = elts[j];
-
- if (elt)
- {
- if (ebitset_elt_zero_p (elt))
- {
- ebitset_elt_remove (bset, j);
- count++;
- }
- }
- else
- count++;
- }
-
- count = j - count;
- if (!count)
- {
- /* All the bits are zero. We could shrink the elts.
- For now just mark BSET as known to be zero. */
- EBITSET_ZERO_SET (bset);
- }
- else
- EBITSET_NONZERO_SET (bset);
-
- return count;
-}
-
-
-/* Set all bits in the bitset to zero. */
-static inline void
-ebitset_zero (bitset bset)
-{
- ebitset_elts *elts;
- bitset_windex j;
-
- if (EBITSET_ZERO_P (bset))
- return;
-
- elts = EBITSET_ELTS (bset);
- for (j = 0; j < EBITSET_SIZE (bset); j++)
- {
- ebitset_elt *elt = elts[j];
-
- if (elt)
- ebitset_elt_remove (bset, j);
- }
-
- /* All the bits are zero. We could shrink the elts.
- For now just mark BSET as known to be zero. */
- EBITSET_ZERO_SET (bset);
-}
-
-
-static inline bool
-ebitset_equal_p (bitset dst, bitset src)
-{
- ebitset_elts *selts;
- ebitset_elts *delts;
- bitset_windex j;
-
- if (src == dst)
- return true;
-
- ebitset_weed (dst);
- ebitset_weed (src);
-
- if (EBITSET_SIZE (src) != EBITSET_SIZE (dst))
- return false;
-
- selts = EBITSET_ELTS (src);
- delts = EBITSET_ELTS (dst);
-
- for (j = 0; j < EBITSET_SIZE (src); j++)
- {
- unsigned int i;
- ebitset_elt *selt = selts[j];
- ebitset_elt *delt = delts[j];
-
- if (!selt && !delt)
- continue;
- if ((selt && !delt) || (!selt && delt))
- return false;
-
- for (i = 0; i < EBITSET_ELT_WORDS; i++)
- if (EBITSET_WORDS (selt)[i] != EBITSET_WORDS (delt)[i])
- return false;
- }
- return true;
-}
-
-
-/* Copy bits from bitset SRC to bitset DST. */
-static inline void
-ebitset_copy_ (bitset dst, bitset src)
-{
- ebitset_elts *selts;
- ebitset_elts *delts;
- bitset_windex j;
-
- if (src == dst)
- return;
-
- ebitset_zero (dst);
-
- if (BITSET_NBITS_ (dst) != BITSET_NBITS_ (src))
- ebitset_resize (dst, BITSET_NBITS_ (src));
-
- selts = EBITSET_ELTS (src);
- delts = EBITSET_ELTS (dst);
- for (j = 0; j < EBITSET_SIZE (src); j++)
- {
- ebitset_elt *selt = selts[j];
-
- if (selt)
- {
- ebitset_elt *tmp;
-
- tmp = ebitset_elt_alloc ();
- delts[j] = tmp;
- memcpy (EBITSET_WORDS (tmp), EBITSET_WORDS (selt),
- sizeof (EBITSET_WORDS (selt)));
- }
- }
- EBITSET_NONZERO_SET (dst);
-}
-
-
-/* Copy bits from bitset SRC to bitset DST. Return true if
- bitsets different. */
-static inline bool
-ebitset_copy_cmp (bitset dst, bitset src)
-{
- if (src == dst)
- return false;
-
- if (EBITSET_ZERO_P (dst))
- {
- ebitset_copy_ (dst, src);
- return !EBITSET_ZERO_P (src);
- }
-
- if (ebitset_equal_p (dst, src))
- return false;
-
- ebitset_copy_ (dst, src);
- return true;
-}
-
-
-/* Set bit BITNO in bitset DST. */
-static void
-ebitset_set (bitset dst, bitset_bindex bitno)
-{
- bitset_windex windex = bitno / BITSET_WORD_BITS;
-
- ebitset_elt_find (dst, bitno, EBITSET_CREATE);
-
- dst->b.cdata[windex - dst->b.cindex] |=
- (bitset_word) 1 << (bitno % BITSET_WORD_BITS);
-}
-
-
-/* Reset bit BITNO in bitset DST. */
-static void
-ebitset_reset (bitset dst, bitset_bindex bitno)
-{
- bitset_windex windex = bitno / BITSET_WORD_BITS;
-
- if (!ebitset_elt_find (dst, bitno, EBITSET_FIND))
- return;
-
- dst->b.cdata[windex - dst->b.cindex] &=
- ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
-
- /* If all the data is zero, perhaps we should remove it now...
- However, there is a good chance that the element will be needed
- again soon. */
-}
-
-
-/* Test bit BITNO in bitset SRC. */
-static bool
-ebitset_test (bitset src, bitset_bindex bitno)
-{
- bitset_windex windex = bitno / BITSET_WORD_BITS;
-
- return (ebitset_elt_find (src, bitno, EBITSET_FIND)
- && ((src->b.cdata[windex - src->b.cindex]
- >> (bitno % BITSET_WORD_BITS))
- & 1));
-}
-
-
-static void
-ebitset_free (bitset bset)
-{
- ebitset_zero (bset);
- free (EBITSET_ELTS (bset));
-}
-
-
-/* Find list of up to NUM bits set in BSET 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
-ebitset_list_reverse (bitset bset, bitset_bindex *list,
- bitset_bindex num, bitset_bindex *next)
-{
- bitset_bindex n_bits;
- bitset_bindex bitno;
- bitset_bindex rbitno;
- unsigned int bcount;
- bitset_bindex boffset;
- bitset_windex windex;
- bitset_windex eindex;
- bitset_windex woffset;
- bitset_bindex count;
- bitset_windex size;
- ebitset_elts *elts;
-
- if (EBITSET_ZERO_P (bset))
- return 0;
-
- size = EBITSET_SIZE (bset);
- n_bits = size * EBITSET_ELT_BITS;
- rbitno = *next;
-
- if (rbitno >= n_bits)
- return 0;
-
- elts = EBITSET_ELTS (bset);
-
- bitno = n_bits - (rbitno + 1);
-
- windex = bitno / BITSET_WORD_BITS;
- eindex = bitno / EBITSET_ELT_BITS;
- woffset = windex - eindex * EBITSET_ELT_WORDS;
-
- /* If num is 1, we could speed things up with a binary search
- of the word of interest. */
-
- count = 0;
- bcount = bitno % BITSET_WORD_BITS;
- boffset = windex * BITSET_WORD_BITS;
-
- do
- {
- ebitset_elt *elt;
- bitset_word *srcp;
-
- elt = elts[eindex];
- if (elt)
- {
- srcp = EBITSET_WORDS (elt);
-
- do
- {
- bitset_word word;
-
- word = srcp[woffset] << (BITSET_WORD_BITS - 1 - bcount);
-
- for (; word; bcount--)
- {
- if (word & BITSET_MSB)
- {
- list[count++] = boffset + bcount;
- if (count >= num)
- {
- *next = n_bits - (boffset + bcount);
- return count;
- }
- }
- word <<= 1;
- }
- boffset -= BITSET_WORD_BITS;
- bcount = BITSET_WORD_BITS - 1;
- }
- while (woffset--);
- }
-
- woffset = EBITSET_ELT_WORDS - 1;
- boffset = eindex * EBITSET_ELT_BITS - BITSET_WORD_BITS;
- }
- while (eindex--);
-
- *next = n_bits - (boffset + 1);
- return count;
-}
-
-
-/* Find list of up to NUM bits set in BSET 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
-ebitset_list (bitset bset, bitset_bindex *list,
- bitset_bindex num, bitset_bindex *next)
-{
- bitset_bindex bitno;
- bitset_windex windex;
- bitset_windex eindex;
- bitset_bindex count;
- bitset_windex size;
- ebitset_elt *elt;
- bitset_word word;
- ebitset_elts *elts;
-
- if (EBITSET_ZERO_P (bset))
- return 0;
-
- bitno = *next;
- count = 0;
-
- elts = EBITSET_ELTS (bset);
- size = EBITSET_SIZE (bset);
- eindex = bitno / EBITSET_ELT_BITS;
-
- if (bitno % EBITSET_ELT_BITS)
- {
- /* We need to start within an element. This is not very common. */
-
- elt = elts[eindex];
- if (elt)
- {
- bitset_windex woffset;
- bitset_word *srcp = EBITSET_WORDS (elt);
-
- windex = bitno / BITSET_WORD_BITS;
- woffset = eindex * EBITSET_ELT_WORDS;
-
- for (; (windex - woffset) < EBITSET_ELT_WORDS; windex++)
- {
- word = srcp[windex - woffset] >> (bitno % BITSET_WORD_BITS);
-
- for (; word; bitno++)
- {
- if (word & 1)
- {
- list[count++] = bitno;
- if (count >= num)
- {
- *next = bitno + 1;
- return count;
- }
- }
- word >>= 1;
- }
- bitno = (windex + 1) * BITSET_WORD_BITS;
- }
- }
-
- /* Skip to next element. */
- eindex++;
- }
-
- /* If num is 1, we could speed things up with a binary search
- of the word of interest. */
-
- for (; eindex < size; eindex++)
- {
- int i;
- bitset_word *srcp;
-
- elt = elts[eindex];
- if (!elt)
- continue;
-
- srcp = EBITSET_WORDS (elt);
- windex = eindex * EBITSET_ELT_WORDS;
-
- if ((count + EBITSET_ELT_BITS) < num)
- {
- /* The coast is clear, plant boot! */
-
-#if EBITSET_ELT_WORDS == 2
- word = srcp[0];
- if (word)
- {
- if (!(word & 0xffff))
- {
- word >>= 16;
- bitno += 16;
- }
- if (!(word & 0xff))
- {
- word >>= 8;
- bitno += 8;
- }
- for (; word; bitno++)
- {
- if (word & 1)
- list[count++] = bitno;
- word >>= 1;
- }
- }
- windex++;
- bitno = windex * BITSET_WORD_BITS;
-
- word = srcp[1];
- if (word)
- {
- if (!(word & 0xffff))
- {
- word >>= 16;
- bitno += 16;
- }
- for (; word; bitno++)
- {
- if (word & 1)
- list[count++] = bitno;
- word >>= 1;
- }
- }
- windex++;
- bitno = windex * BITSET_WORD_BITS;
-#else
- for (i = 0; i < EBITSET_ELT_WORDS; i++, windex++)
- {
- bitno = windex * BITSET_WORD_BITS;
-
- word = srcp[i];
- if (word)
- {
- if (!(word & 0xffff))
- {
- word >>= 16;
- bitno += 16;
- }
- if (!(word & 0xff))
- {
- word >>= 8;
- bitno += 8;
- }
- for (; word; bitno++)
- {
- if (word & 1)
- list[count++] = bitno;
- word >>= 1;
- }
- }
- }
-#endif
- }
- else
- {
- /* Tread more carefully since we need to check
- if array overflows. */
-
- for (i = 0; i < EBITSET_ELT_WORDS; i++, windex++)
- {
- bitno = windex * BITSET_WORD_BITS;
-
- for (word = srcp[i]; word; bitno++)
- {
- if (word & 1)
- {
- list[count++] = bitno;
- if (count >= num)
- {
- *next = bitno + 1;
- return count;
- }
- }
- word >>= 1;
- }
- }
- }
- }
-
- *next = bitno;
- return count;
-}
-
-
-/* Ensure that any unused bits within the last element are clear. */
-static inline void
-ebitset_unused_clear (bitset dst)
-{
- unsigned int last_bit;
- bitset_bindex n_bits;
-
- n_bits = BITSET_NBITS_ (dst);
- last_bit = n_bits % EBITSET_ELT_BITS;
-
- if (last_bit)
- {
- bitset_windex eindex;
- ebitset_elts *elts;
- ebitset_elt *elt;
-
- elts = EBITSET_ELTS (dst);
-
- eindex = n_bits / EBITSET_ELT_BITS;
-
- elt = elts[eindex];
- if (elt)
- {
- bitset_windex windex;
- bitset_windex woffset;
- bitset_word *srcp = EBITSET_WORDS (elt);
-
- windex = n_bits / BITSET_WORD_BITS;
- woffset = eindex * EBITSET_ELT_WORDS;
-
- srcp[windex - woffset] &= ((bitset_word) 1 << last_bit) - 1;
- windex++;
- for (; (windex - woffset) < EBITSET_ELT_WORDS; windex++)
- srcp[windex - woffset] = 0;
- }
- }
-}
-
-
-static void
-ebitset_ones (bitset dst)
-{
- bitset_windex j;
- ebitset_elt *elt;
-
- for (j = 0; j < EBITSET_SIZE (dst); j++)
- {
- /* Create new elements if they cannot be found. Perhaps
- we should just add pointers to a ones element? */
- elt =
- ebitset_elt_find (dst, j * EBITSET_ELT_BITS, EBITSET_CREATE);
- memset (EBITSET_WORDS (elt), -1, sizeof (EBITSET_WORDS (elt)));
- }
- EBITSET_NONZERO_SET (dst);
- ebitset_unused_clear (dst);
-}
-
-
-static bool
-ebitset_empty_p (bitset dst)
-{
- ebitset_elts *elts;
- bitset_windex j;
-
- if (EBITSET_ZERO_P (dst))
- return 1;
-
- elts = EBITSET_ELTS (dst);
- for (j = 0; j < EBITSET_SIZE (dst); j++)
- {
- ebitset_elt *elt = elts[j];
-
- if (elt)
- {
- if (!ebitset_elt_zero_p (elt))
- return 0;
- /* Do some weeding as we go. */
- ebitset_elt_remove (dst, j);
- }
- }
-
- /* All the bits are zero. We could shrink the elts.
- For now just mark DST as known to be zero. */
- EBITSET_ZERO_SET (dst);
- return 1;
-}
-
-
-static void
-ebitset_not (bitset dst, bitset src)
-{
- unsigned int i;
- ebitset_elt *selt;
- ebitset_elt *delt;
- bitset_windex j;
-
- ebitset_resize (dst, BITSET_NBITS_ (src));
-
- for (j = 0; j < EBITSET_SIZE (src); j++)
- {
- /* Create new elements for dst if they cannot be found
- or substitute zero elements if src elements not found. */
- selt =
- ebitset_elt_find (dst, j * EBITSET_ELT_BITS, EBITSET_SUBST);
- delt =
- ebitset_elt_find (dst, j * EBITSET_ELT_BITS, EBITSET_CREATE);
-
- for (i = 0; i < EBITSET_ELT_WORDS; i++)
- EBITSET_WORDS (delt)[i] = ~EBITSET_WORDS (selt)[i];
- }
- EBITSET_NONZERO_SET (dst);
- ebitset_unused_clear (dst);
-}
-
-
-/* Is DST == DST | SRC? */
-static bool
-ebitset_subset_p (bitset dst, bitset src)
-{
- bitset_windex j;
- ebitset_elts *selts;
- ebitset_elts *delts;
- bitset_windex ssize;
- bitset_windex dsize;
-
- selts = EBITSET_ELTS (src);
- delts = EBITSET_ELTS (dst);
-
- ssize = EBITSET_SIZE (src);
- dsize = EBITSET_SIZE (dst);
-
- for (j = 0; j < ssize; j++)
- {
- unsigned int i;
- ebitset_elt *selt;
- ebitset_elt *delt;
-
- selt = j < ssize ? selts[j] : 0;
- delt = j < dsize ? delts[j] : 0;
-
- if (!selt && !delt)
- continue;
-
- if (!selt)
- selt = &ebitset_zero_elts[0];
- if (!delt)
- delt = &ebitset_zero_elts[0];
-
- for (i = 0; i < EBITSET_ELT_WORDS; i++)
- if (EBITSET_WORDS (delt)[i]
- != (EBITSET_WORDS (selt)[i] | EBITSET_WORDS (delt)[i]))
- return false;
- }
- return true;
-}
-
-
-/* Is DST & SRC == 0? */
-static bool
-ebitset_disjoint_p (bitset dst, bitset src)
-{
- bitset_windex j;
- ebitset_elts *selts;
- ebitset_elts *delts;
- bitset_windex ssize;
- bitset_windex dsize;
-
- selts = EBITSET_ELTS (src);
- delts = EBITSET_ELTS (dst);
-
- ssize = EBITSET_SIZE (src);
- dsize = EBITSET_SIZE (dst);
-
- for (j = 0; j < ssize; j++)
- {
- unsigned int i;
- ebitset_elt *selt;
- ebitset_elt *delt;
-
- selt = j < ssize ? selts[j] : 0;
- delt = j < dsize ? delts[j] : 0;
-
- if (!selt || !delt)
- continue;
-
- for (i = 0; i < EBITSET_ELT_WORDS; i++)
- if ((EBITSET_WORDS (selt)[i] & EBITSET_WORDS (delt)[i]))
- return false;
- }
- return true;
-}
-
-
-
-static bool
-ebitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op)
-{
- bitset_windex ssize1;
- bitset_windex ssize2;
- bitset_windex dsize;
- bitset_windex size;
- ebitset_elts *selts1;
- ebitset_elts *selts2;
- ebitset_elts *delts;
- bitset_word *srcp1;
- bitset_word *srcp2;
- bitset_word *dstp;
- bool changed = false;
- unsigned int i;
- bitset_windex j;
-
- ebitset_resize (dst, max (BITSET_NBITS_ (src1), BITSET_NBITS_ (src2)));
-
- ssize1 = EBITSET_SIZE (src1);
- ssize2 = EBITSET_SIZE (src2);
- dsize = EBITSET_SIZE (dst);
- size = ssize1;
- if (size < ssize2)
- size = ssize2;
-
- selts1 = EBITSET_ELTS (src1);
- selts2 = EBITSET_ELTS (src2);
- delts = EBITSET_ELTS (dst);
-
- for (j = 0; j < size; j++)
- {
- ebitset_elt *selt1;
- ebitset_elt *selt2;
- ebitset_elt *delt;
-
- selt1 = j < ssize1 ? selts1[j] : 0;
- selt2 = j < ssize2 ? selts2[j] : 0;
- delt = j < dsize ? delts[j] : 0;
-
- if (!selt1 && !selt2)
- {
- if (delt)
- {
- changed = true;
- ebitset_elt_remove (dst, j);
- }
- continue;
- }
-
- if (!selt1)
- selt1 = &ebitset_zero_elts[0];
- if (!selt2)
- selt2 = &ebitset_zero_elts[0];
- if (!delt)
- delt = ebitset_elt_calloc ();
- else
- delts[j] = 0;
-
- srcp1 = EBITSET_WORDS (selt1);
- srcp2 = EBITSET_WORDS (selt2);
- dstp = EBITSET_WORDS (delt);
- switch (op)
- {
- default:
- abort ();
-
- case BITSET_OP_OR:
- for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
- {
- bitset_word tmp = *srcp1++ | *srcp2++;
-
- if (*dstp != tmp)
- {
- changed = true;
- *dstp = tmp;
- }
- }
- break;
-
- case BITSET_OP_AND:
- for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
- {
- bitset_word tmp = *srcp1++ & *srcp2++;
-
- if (*dstp != tmp)
- {
- changed = true;
- *dstp = tmp;
- }
- }
- break;
-
- case BITSET_OP_XOR:
- for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
- {
- bitset_word tmp = *srcp1++ ^ *srcp2++;
-
- if (*dstp != tmp)
- {
- changed = true;
- *dstp = tmp;
- }
- }
- break;
-
- case BITSET_OP_ANDN:
- for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
- {
- bitset_word tmp = *srcp1++ & ~(*srcp2++);
-
- if (*dstp != tmp)
- {
- changed = true;
- *dstp = tmp;
- }
- }
- break;
- }
-
- if (!ebitset_elt_zero_p (delt))
- {
- ebitset_elt_add (dst, delt, j);
- }
- else
- {
- ebitset_elt_free (delt);
- }
- }
-
- /* If we have elements of DST left over, free them all. */
- for (; j < dsize; j++)
- {
- ebitset_elt *delt;
-
- changed = true;
-
- delt = delts[j];
-
- if (delt)
- ebitset_elt_remove (dst, j);
- }
-
- EBITSET_NONZERO_SET (dst);
- return changed;
-}
-
-
-static bool
-ebitset_and_cmp (bitset dst, bitset src1, bitset src2)
-{
- bool changed;
-
- if (EBITSET_ZERO_P (src2))
- {
- ebitset_weed (dst);
- changed = EBITSET_ZERO_P (dst);
- ebitset_zero (dst);
- return changed;
- }
- else if (EBITSET_ZERO_P (src1))
- {
- ebitset_weed (dst);
- changed = EBITSET_ZERO_P (dst);
- ebitset_zero (dst);
- return changed;
- }
- return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_AND);
-}
-
-
-static void
-ebitset_and (bitset dst, bitset src1, bitset src2)
-{
- ebitset_and_cmp (dst, src1, src2);
-}
-
-
-static bool
-ebitset_andn_cmp (bitset dst, bitset src1, bitset src2)
-{
- bool changed;
-
- if (EBITSET_ZERO_P (src2))
- {
- return ebitset_copy_cmp (dst, src1);
- }
- else if (EBITSET_ZERO_P (src1))
- {
- ebitset_weed (dst);
- changed = EBITSET_ZERO_P (dst);
- ebitset_zero (dst);
- return changed;
- }
- return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_ANDN);
-}
-
-
-static void
-ebitset_andn (bitset dst, bitset src1, bitset src2)
-{
- ebitset_andn_cmp (dst, src1, src2);
-}
-
-
-static bool
-ebitset_or_cmp (bitset dst, bitset src1, bitset src2)
-{
- if (EBITSET_ZERO_P (src2))
- {
- return ebitset_copy_cmp (dst, src1);
- }
- else if (EBITSET_ZERO_P (src1))
- {
- return ebitset_copy_cmp (dst, src2);
- }
- return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_OR);
-}
-
-
-static void
-ebitset_or (bitset dst, bitset src1, bitset src2)
-{
- ebitset_or_cmp (dst, src1, src2);
-}
-
-
-static bool
-ebitset_xor_cmp (bitset dst, bitset src1, bitset src2)
-{
- if (EBITSET_ZERO_P (src2))
- {
- return ebitset_copy_cmp (dst, src1);
- }
- else if (EBITSET_ZERO_P (src1))
- {
- return ebitset_copy_cmp (dst, src2);
- }
- return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_XOR);
-}
-
-
-static void
-ebitset_xor (bitset dst, bitset src1, bitset src2)
-{
- ebitset_xor_cmp (dst, src1, src2);
-}
-
-
-static void
-ebitset_copy (bitset dst, bitset src)
-{
- if (BITSET_COMPATIBLE_ (dst, src))
- ebitset_copy_ (dst, src);
- else
- bitset_copy_ (dst, src);
-}
-
-
-/* Vector of operations for linked-list bitsets. */
-struct bitset_vtable ebitset_vtable = {
- ebitset_set,
- ebitset_reset,
- bitset_toggle_,
- ebitset_test,
- ebitset_resize,
- bitset_size_,
- bitset_count_,
- ebitset_empty_p,
- ebitset_ones,
- ebitset_zero,
- ebitset_copy,
- ebitset_disjoint_p,
- ebitset_equal_p,
- ebitset_not,
- ebitset_subset_p,
- ebitset_and,
- ebitset_and_cmp,
- ebitset_andn,
- ebitset_andn_cmp,
- ebitset_or,
- ebitset_or_cmp,
- ebitset_xor,
- ebitset_xor_cmp,
- bitset_and_or_,
- bitset_and_or_cmp_,
- bitset_andn_or_,
- bitset_andn_or_cmp_,
- bitset_or_and_,
- bitset_or_and_cmp_,
- ebitset_list,
- ebitset_list_reverse,
- ebitset_free,
- BITSET_TABLE
-};
-
-
-/* Return size of initial structure. */
-size_t
-ebitset_bytes (bitset_bindex n_bits ATTRIBUTE_UNUSED)
-{
- return sizeof (struct ebitset_struct);
-}
-
-
-/* Initialize a bitset. */
-
-bitset
-ebitset_init (bitset bset, bitset_bindex n_bits)
-{
- bset->b.vtable = &ebitset_vtable;
-
- bset->b.csize = EBITSET_ELT_WORDS;
-
- EBITSET_ZERO_SET (bset);
-
- EBITSET_ASIZE (bset) = 0;
- EBITSET_ELTS (bset) = 0;
- ebitset_resize (bset, n_bits);
-
- return bset;
-}
-
-
-void
-ebitset_release_memory (void)
-{
- ebitset_free_list = 0;
- if (ebitset_obstack_init)
- {
- ebitset_obstack_init = false;
- obstack_free (&ebitset_obstack, NULL);
- }
-}
diff --git a/contrib/tools/m4/lib/ebitset.h b/contrib/tools/m4/lib/ebitset.h
deleted file mode 100644
index d31bda7d507..00000000000
--- a/contrib/tools/m4/lib/ebitset.h
+++ /dev/null
@@ -1,31 +0,0 @@
-/* Functions to support ebitsets.
-
- Copyright (C) 2002, 2004, 2009-2013 Free Software Foundation, Inc.
-
- Contributed by Michael Hayes ([email protected]).
-
- 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 <http://www.gnu.org/licenses/>. */
-
-#ifndef _EBITSET_H
-#define _EBITSET_H
-
-#include "bitset.h"
-
-extern size_t ebitset_bytes (bitset_bindex);
-
-extern bitset ebitset_init (bitset, bitset_bindex);
-
-extern void ebitset_release_memory (void);
-
-#endif
diff --git a/contrib/tools/m4/lib/lbitset.c b/contrib/tools/m4/lib/lbitset.c
deleted file mode 100644
index 7a638c6f9b1..00000000000
--- a/contrib/tools/m4/lib/lbitset.c
+++ /dev/null
@@ -1,1401 +0,0 @@
-/* Functions to support link list bitsets.
-
- Copyright (C) 2002-2004, 2006, 2009-2013 Free Software Foundation,
- Inc.
-
- Contributed by Michael Hayes ([email protected]).
-
- 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 <http://www.gnu.org/licenses/>. */
-
-#include <config.h>
-
-#include "lbitset.h"
-
-#include "obstack.h"
-#include <stddef.h>
-#include <stdlib.h>
-#include <stdio.h>
-#include <string.h>
-
-/* This file implements linked-list bitsets. These bitsets can be of
- arbitrary length and are more efficient than arrays of bits for
- large sparse sets.
-
- Usually if all the bits in an element are zero we remove the element
- from the list. However, a side effect of the bit caching is that we
- do not always notice when an element becomes zero. Hence the
- lbitset_weed function which removes zero elements. */
-
-
-/* Number of words to use for each element. The larger the value the
- greater the size of the cache and the shorter the time to find a given bit
- but the more memory wasted for sparse bitsets and the longer the time
- to search for set bits.
-
- The routines that dominate timing profiles are lbitset_elt_find
- and lbitset_elt_link, especially when accessing the bits randomly. */
-
-#define LBITSET_ELT_WORDS 2
-
-typedef bitset_word lbitset_word;
-
-#define LBITSET_WORD_BITS BITSET_WORD_BITS
-
-/* Number of bits stored in each element. */
-#define LBITSET_ELT_BITS \
- ((unsigned int) (LBITSET_ELT_WORDS * LBITSET_WORD_BITS))
-
-/* Lbitset element. We use an array of bits for each element.
- These are linked together in a doubly-linked list. */
-typedef struct lbitset_elt_struct
-{
- struct lbitset_elt_struct *next; /* Next element. */
- struct lbitset_elt_struct *prev; /* Previous element. */
- bitset_windex index; /* bitno / BITSET_WORD_BITS. */
- bitset_word words[LBITSET_ELT_WORDS]; /* Bits that are set. */
-}
-lbitset_elt;
-
-
-enum lbitset_find_mode
- { LBITSET_FIND, LBITSET_CREATE, LBITSET_SUBST };
-
-static lbitset_elt lbitset_zero_elts[3]; /* Elements of all zero bits. */
-
-/* Obstack to allocate bitset elements from. */
-static struct obstack lbitset_obstack;
-static bool lbitset_obstack_init = false;
-static lbitset_elt *lbitset_free_list; /* Free list of bitset elements. */
-
-extern void debug_lbitset (bitset);
-
-#define LBITSET_CURRENT1(X) \
- ((lbitset_elt *) (void *) ((char *) (X) - offsetof (lbitset_elt, words)))
-
-#define LBITSET_CURRENT(X) LBITSET_CURRENT1((X)->b.cdata)
-
-#define LBITSET_HEAD(X) ((X)->l.head)
-#define LBITSET_TAIL(X) ((X)->l.tail)
-
-/* Allocate a lbitset element. The bits are not cleared. */
-static inline lbitset_elt *
-lbitset_elt_alloc (void)
-{
- lbitset_elt *elt;
-
- if (lbitset_free_list != 0)
- {
- elt = lbitset_free_list;
- lbitset_free_list = elt->next;
- }
- else
- {
- if (!lbitset_obstack_init)
- {
- lbitset_obstack_init = true;
-
- /* Let particular systems override the size of a chunk. */
-
-#ifndef OBSTACK_CHUNK_SIZE
-#define OBSTACK_CHUNK_SIZE 0
-#endif
-
- /* Let them override the alloc and free routines too. */
-
-#ifndef OBSTACK_CHUNK_ALLOC
-#define OBSTACK_CHUNK_ALLOC xmalloc
-#endif
-
-#ifndef OBSTACK_CHUNK_FREE
-#define OBSTACK_CHUNK_FREE free
-#endif
-
-#if ! defined __GNUC__ || __GNUC__ < 2
-#define __alignof__(type) 0
-#endif
-
- obstack_specify_allocation (&lbitset_obstack, OBSTACK_CHUNK_SIZE,
- __alignof__ (lbitset_elt),
- OBSTACK_CHUNK_ALLOC,
- OBSTACK_CHUNK_FREE);
- }
-
- /* Perhaps we should add a number of new elements to the free
- list. */
- elt = (lbitset_elt *) obstack_alloc (&lbitset_obstack,
- sizeof (lbitset_elt));
- }
-
- return elt;
-}
-
-
-/* Allocate a lbitset element. The bits are cleared. */
-static inline lbitset_elt *
-lbitset_elt_calloc (void)
-{
- lbitset_elt *elt;
-
- elt = lbitset_elt_alloc ();
- memset (elt->words, 0, sizeof (elt->words));
- return elt;
-}
-
-
-static inline void
-lbitset_elt_free (lbitset_elt *elt)
-{
- elt->next = lbitset_free_list;
- lbitset_free_list = elt;
-}
-
-
-/* Unlink element ELT from bitset BSET. */
-static inline void
-lbitset_elt_unlink (bitset bset, lbitset_elt *elt)
-{
- lbitset_elt *next = elt->next;
- lbitset_elt *prev = elt->prev;
-
- if (prev)
- prev->next = next;
-
- if (next)
- next->prev = prev;
-
- if (LBITSET_HEAD (bset) == elt)
- LBITSET_HEAD (bset) = next;
- if (LBITSET_TAIL (bset) == elt)
- LBITSET_TAIL (bset) = prev;
-
- /* Update cache pointer. Since the first thing we try is to insert
- before current, make current the next entry in preference to the
- previous. */
- if (LBITSET_CURRENT (bset) == elt)
- {
- if (next)
- {
- bset->b.cdata = next->words;
- bset->b.cindex = next->index;
- }
- else if (prev)
- {
- bset->b.cdata = prev->words;
- bset->b.cindex = prev->index;
- }
- else
- {
- bset->b.csize = 0;
- bset->b.cdata = 0;
- }
- }
-
- lbitset_elt_free (elt);
-}
-
-
-/* Cut the chain of bitset BSET before element ELT and free the
- elements. */
-static inline void
-lbitset_prune (bitset bset, lbitset_elt *elt)
-{
- lbitset_elt *next;
-
- if (!elt)
- return;
-
- if (elt->prev)
- {
- LBITSET_TAIL (bset) = elt->prev;
- bset->b.cdata = elt->prev->words;
- bset->b.cindex = elt->prev->index;
- elt->prev->next = 0;
- }
- else
- {
- LBITSET_HEAD (bset) = 0;
- LBITSET_TAIL (bset) = 0;
- bset->b.cdata = 0;
- bset->b.csize = 0;
- }
-
- for (; elt; elt = next)
- {
- next = elt->next;
- lbitset_elt_free (elt);
- }
-}
-
-
-/* Are all bits in an element zero? */
-static inline bool
-lbitset_elt_zero_p (lbitset_elt *elt)
-{
- int i;
-
- for (i = 0; i < LBITSET_ELT_WORDS; i++)
- if (elt->words[i])
- return false;
-
- return true;
-}
-
-
-/* Link the bitset element into the current bitset linked list. */
-static inline void
-lbitset_elt_link (bitset bset, lbitset_elt *elt)
-{
- bitset_windex windex = elt->index;
- lbitset_elt *ptr;
- lbitset_elt *current;
-
- if (bset->b.csize)
- current = LBITSET_CURRENT (bset);
- else
- current = LBITSET_HEAD (bset);
-
- /* If this is the first and only element, add it in. */
- if (LBITSET_HEAD (bset) == 0)
- {
- elt->next = elt->prev = 0;
- LBITSET_HEAD (bset) = elt;
- LBITSET_TAIL (bset) = elt;
- }
-
- /* If this index is less than that of the current element, it goes
- somewhere before the current element. */
- else if (windex < bset->b.cindex)
- {
- for (ptr = current;
- ptr->prev && ptr->prev->index > windex; ptr = ptr->prev)
- continue;
-
- if (ptr->prev)
- ptr->prev->next = elt;
- else
- LBITSET_HEAD (bset) = elt;
-
- elt->prev = ptr->prev;
- elt->next = ptr;
- ptr->prev = elt;
- }
-
- /* Otherwise, it must go somewhere after the current element. */
- else
- {
- for (ptr = current;
- ptr->next && ptr->next->index < windex; ptr = ptr->next)
- continue;
-
- if (ptr->next)
- ptr->next->prev = elt;
- else
- LBITSET_TAIL (bset) = elt;
-
- elt->next = ptr->next;
- elt->prev = ptr;
- ptr->next = elt;
- }
-
- /* Set up so this is the first element searched. */
- bset->b.cindex = windex;
- bset->b.csize = LBITSET_ELT_WORDS;
- bset->b.cdata = elt->words;
-}
-
-
-static lbitset_elt *
-lbitset_elt_find (bitset bset, bitset_windex windex,
- enum lbitset_find_mode mode)
-{
- lbitset_elt *elt;
- lbitset_elt *current;
-
- if (bset->b.csize)
- {
- current = LBITSET_CURRENT (bset);
- /* Check if element is the cached element. */
- if ((windex - bset->b.cindex) < bset->b.csize)
- return current;
- }
- else
- {
- current = LBITSET_HEAD (bset);
- }
-
- if (current)
- {
- if (windex < bset->b.cindex)
- {
- for (elt = current;
- elt->prev && elt->index > windex; elt = elt->prev)
- continue;
- }
- else
- {
- for (elt = current;
- elt->next && (elt->index + LBITSET_ELT_WORDS - 1) < windex;
- elt = elt->next)
- continue;
- }
-
- /* ELT is the nearest to the one we want. If it's not the one
- we want, the one we want does not exist. */
- if (windex - elt->index < LBITSET_ELT_WORDS)
- {
- bset->b.cindex = elt->index;
- bset->b.csize = LBITSET_ELT_WORDS;
- bset->b.cdata = elt->words;
- return elt;
- }
- }
-
- switch (mode)
- {
- default:
- abort ();
-
- case LBITSET_FIND:
- return 0;
-
- case LBITSET_CREATE:
- windex -= windex % LBITSET_ELT_WORDS;
-
- elt = lbitset_elt_calloc ();
- elt->index = windex;
- lbitset_elt_link (bset, elt);
- return elt;
-
- case LBITSET_SUBST:
- return &lbitset_zero_elts[0];
- }
-}
-
-
-/* Weed out the zero elements from the list. */
-static inline void
-lbitset_weed (bitset bset)
-{
- lbitset_elt *elt;
- lbitset_elt *next;
-
- for (elt = LBITSET_HEAD (bset); elt; elt = next)
- {
- next = elt->next;
- if (lbitset_elt_zero_p (elt))
- lbitset_elt_unlink (bset, elt);
- }
-}
-
-
-/* Set all bits in the bitset to zero. */
-static void
-lbitset_zero (bitset bset)
-{
- lbitset_elt *head;
-
- head = LBITSET_HEAD (bset);
- if (!head)
- return;
-
- /* Clear a bitset by freeing the linked list at the head element. */
- lbitset_prune (bset, head);
-}
-
-
-/* Is DST == SRC? */
-static inline bool
-lbitset_equal_p (bitset dst, bitset src)
-{
- lbitset_elt *selt;
- lbitset_elt *delt;
- int j;
-
- if (src == dst)
- return true;
-
- lbitset_weed (src);
- lbitset_weed (dst);
- for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst);
- selt && delt; selt = selt->next, delt = delt->next)
- {
- if (selt->index != delt->index)
- return false;
-
- for (j = 0; j < LBITSET_ELT_WORDS; j++)
- if (delt->words[j] != selt->words[j])
- return false;
- }
- return !selt && !delt;
-}
-
-
-/* Copy bits from bitset SRC to bitset DST. */
-static inline void
-lbitset_copy (bitset dst, bitset src)
-{
- lbitset_elt *elt;
- lbitset_elt *head;
- lbitset_elt *prev;
- lbitset_elt *tmp;
-
- if (src == dst)
- return;
-
- lbitset_zero (dst);
-
- head = LBITSET_HEAD (src);
- if (!head)
- return;
-
- prev = 0;
- for (elt = head; elt; elt = elt->next)
- {
- tmp = lbitset_elt_alloc ();
- tmp->index = elt->index;
- tmp->prev = prev;
- tmp->next = 0;
- if (prev)
- prev->next = tmp;
- else
- LBITSET_HEAD (dst) = tmp;
- prev = tmp;
-
- memcpy (tmp->words, elt->words, sizeof (elt->words));
- }
- LBITSET_TAIL (dst) = tmp;
-
- dst->b.csize = LBITSET_ELT_WORDS;
- dst->b.cdata = LBITSET_HEAD (dst)->words;
- dst->b.cindex = LBITSET_HEAD (dst)->index;
-}
-
-
-/* Copy bits from bitset SRC to bitset DST. Return true if
- bitsets different. */
-static inline bool
-lbitset_copy_cmp (bitset dst, bitset src)
-{
- if (src == dst)
- return false;
-
- if (!LBITSET_HEAD (dst))
- {
- lbitset_copy (dst, src);
- return LBITSET_HEAD (src) != 0;
- }
-
- if (lbitset_equal_p (dst, src))
- return false;
-
- lbitset_copy (dst, src);
- return true;
-}
-
-
-static bitset_bindex
-lbitset_resize (bitset src, bitset_bindex size)
-{
- BITSET_NBITS_ (src) = size;
-
- /* Need to prune any excess bits. FIXME. */
- return size;
-}
-
-/* Set bit BITNO in bitset DST. */
-static void
-lbitset_set (bitset dst, bitset_bindex bitno)
-{
- bitset_windex windex = bitno / BITSET_WORD_BITS;
-
- lbitset_elt_find (dst, windex, LBITSET_CREATE);
-
- dst->b.cdata[windex - dst->b.cindex] |=
- (bitset_word) 1 << (bitno % BITSET_WORD_BITS);
-}
-
-
-/* Reset bit BITNO in bitset DST. */
-static void
-lbitset_reset (bitset dst, bitset_bindex bitno)
-{
- bitset_windex windex = bitno / BITSET_WORD_BITS;
-
- if (!lbitset_elt_find (dst, windex, LBITSET_FIND))
- return;
-
- dst->b.cdata[windex - dst->b.cindex] &=
- ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
-
- /* If all the data is zero, perhaps we should unlink it now... */
-}
-
-
-/* Test bit BITNO in bitset SRC. */
-static bool
-lbitset_test (bitset src, bitset_bindex bitno)
-{
- bitset_windex windex = bitno / BITSET_WORD_BITS;
-
- return (lbitset_elt_find (src, windex, LBITSET_FIND)
- && ((src->b.cdata[windex - src->b.cindex]
- >> (bitno % BITSET_WORD_BITS))
- & 1));
-}
-
-
-static void
-lbitset_free (bitset bset)
-{
- lbitset_zero (bset);
-}
-
-
-/* Find list of up to NUM bits set in BSET 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
-lbitset_list_reverse (bitset bset, bitset_bindex *list,
- bitset_bindex num, bitset_bindex *next)
-{
- bitset_bindex rbitno;
- bitset_bindex bitno;
- unsigned int bcount;
- bitset_bindex boffset;
- bitset_windex windex;
- bitset_bindex count;
- lbitset_elt *elt;
- bitset_word word;
- bitset_bindex n_bits;
-
- elt = LBITSET_TAIL (bset);
- if (!elt)
- return 0;
-
- n_bits = (elt->index + LBITSET_ELT_WORDS) * BITSET_WORD_BITS;
- rbitno = *next;
-
- if (rbitno >= n_bits)
- return 0;
-
- bitno = n_bits - (rbitno + 1);
-
- windex = bitno / BITSET_WORD_BITS;
-
- /* Skip back to starting element. */
- for (; elt && elt->index > windex; elt = elt->prev)
- continue;
-
- if (!elt)
- return 0;
-
- if (windex >= elt->index + LBITSET_ELT_WORDS)
- {
- /* We are trying to start in no-mans land so start
- at end of current elt. */
- bcount = BITSET_WORD_BITS - 1;
- windex = elt->index + LBITSET_ELT_WORDS - 1;
- }
- else
- {
- bcount = bitno % BITSET_WORD_BITS;
- }
-
- count = 0;
- boffset = windex * BITSET_WORD_BITS;
-
- /* If num is 1, we could speed things up with a binary search
- of the word of interest. */
-
- while (elt)
- {
- bitset_word *srcp = elt->words;
-
- for (; (windex - elt->index) < LBITSET_ELT_WORDS;
- windex--, boffset -= BITSET_WORD_BITS,
- bcount = BITSET_WORD_BITS - 1)
- {
- word =
- srcp[windex - elt->index] << (BITSET_WORD_BITS - 1 - bcount);
-
- for (; word; bcount--)
- {
- if (word & BITSET_MSB)
- {
- list[count++] = boffset + bcount;
- if (count >= num)
- {
- *next = n_bits - (boffset + bcount);
- return count;
- }
- }
- word <<= 1;
- }
- }
-
- elt = elt->prev;
- if (elt)
- {
- windex = elt->index + LBITSET_ELT_WORDS - 1;
- boffset = windex * BITSET_WORD_BITS;
- }
- }
-
- *next = n_bits - (boffset + 1);
- return count;
-}
-
-
-/* Find list of up to NUM bits set in BSET 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
-lbitset_list (bitset bset, bitset_bindex *list,
- bitset_bindex num, bitset_bindex *next)
-{
- bitset_bindex bitno;
- bitset_windex windex;
- bitset_bindex count;
- lbitset_elt *elt;
- lbitset_elt *head;
- bitset_word word;
-
- head = LBITSET_HEAD (bset);
- if (!head)
- return 0;
-
- bitno = *next;
- count = 0;
-
- if (!bitno)
- {
- /* This is the most common case. */
-
- /* Start with the first element. */
- elt = head;
- windex = elt->index;
- bitno = windex * BITSET_WORD_BITS;
- }
- else
- {
- windex = bitno / BITSET_WORD_BITS;
-
- /* Skip to starting element. */
- for (elt = head;
- elt && (elt->index + LBITSET_ELT_WORDS - 1) < windex;
- elt = elt->next)
- continue;
-
- if (!elt)
- return 0;
-
- if (windex < elt->index)
- {
- windex = elt->index;
- bitno = windex * BITSET_WORD_BITS;
- }
- else
- {
- bitset_word *srcp = elt->words;
-
- /* We are starting within an element. */
-
- for (; (windex - elt->index) < LBITSET_ELT_WORDS; windex++)
- {
- word = srcp[windex - elt->index] >> (bitno % BITSET_WORD_BITS);
-
- for (; word; bitno++)
- {
- if (word & 1)
- {
- list[count++] = bitno;
- if (count >= num)
- {
- *next = bitno + 1;
- return count;
- }
- }
- word >>= 1;
- }
- bitno = (windex + 1) * BITSET_WORD_BITS;
- }
-
- elt = elt->next;
- if (elt)
- {
- windex = elt->index;
- bitno = windex * BITSET_WORD_BITS;
- }
- }
- }
-
-
- /* If num is 1, we could speed things up with a binary search
- of the word of interest. */
-
- while (elt)
- {
- int i;
- bitset_word *srcp = elt->words;
-
- if ((count + LBITSET_ELT_BITS) < num)
- {
- /* The coast is clear, plant boot! */
-
-#if LBITSET_ELT_WORDS == 2
- word = srcp[0];
- if (word)
- {
- if (!(word & 0xffff))
- {
- word >>= 16;
- bitno += 16;
- }
- if (!(word & 0xff))
- {
- word >>= 8;
- bitno += 8;
- }
- for (; word; bitno++)
- {
- if (word & 1)
- list[count++] = bitno;
- word >>= 1;
- }
- }
- windex++;
- bitno = windex * BITSET_WORD_BITS;
-
- word = srcp[1];
- if (word)
- {
- if (!(word & 0xffff))
- {
- word >>= 16;
- bitno += 16;
- }
- for (; word; bitno++)
- {
- if (word & 1)
- list[count++] = bitno;
- word >>= 1;
- }
- }
- windex++;
- bitno = windex * BITSET_WORD_BITS;
-#else
- for (i = 0; i < LBITSET_ELT_WORDS; i++)
- {
- word = srcp[i];
- if (word)
- {
- if (!(word & 0xffff))
- {
- word >>= 16;
- bitno += 16;
- }
- if (!(word & 0xff))
- {
- word >>= 8;
- bitno += 8;
- }
- for (; word; bitno++)
- {
- if (word & 1)
- list[count++] = bitno;
- word >>= 1;
- }
- }
- windex++;
- bitno = windex * BITSET_WORD_BITS;
- }
-#endif
- }
- else
- {
- /* Tread more carefully since we need to check
- if array overflows. */
-
- for (i = 0; i < LBITSET_ELT_WORDS; i++)
- {
- for (word = srcp[i]; word; bitno++)
- {
- if (word & 1)
- {
- list[count++] = bitno;
- if (count >= num)
- {
- *next = bitno + 1;
- return count;
- }
- }
- word >>= 1;
- }
- windex++;
- bitno = windex * BITSET_WORD_BITS;
- }
- }
-
- elt = elt->next;
- if (elt)
- {
- windex = elt->index;
- bitno = windex * BITSET_WORD_BITS;
- }
- }
-
- *next = bitno;
- return count;
-}
-
-
-static bool
-lbitset_empty_p (bitset dst)
-{
- lbitset_elt *elt;
- lbitset_elt *next;
-
- for (elt = LBITSET_HEAD (dst); elt; elt = next)
- {
- next = elt->next;
- if (!lbitset_elt_zero_p (elt))
- return 0;
- /* Weed as we go. */
- lbitset_elt_unlink (dst, elt);
- }
-
- return 1;
-}
-
-
-/* Ensure that any unused bits within the last element are clear. */
-static inline void
-lbitset_unused_clear (bitset dst)
-{
- unsigned int last_bit;
- bitset_bindex n_bits;
-
- n_bits = BITSET_SIZE_ (dst);
- last_bit = n_bits % LBITSET_ELT_BITS;
-
- if (last_bit)
- {
- lbitset_elt *elt;
- bitset_windex windex;
- bitset_word *srcp;
-
- elt = LBITSET_TAIL (dst);
- srcp = elt->words;
- windex = n_bits / BITSET_WORD_BITS;
-
- srcp[windex - elt->index] &= ((bitset_word) 1 << last_bit) - 1;
- windex++;
-
- for (; (windex - elt->index) < LBITSET_ELT_WORDS; windex++)
- srcp[windex - elt->index] = 0;
- }
-}
-
-
-static void
-lbitset_ones (bitset dst)
-{
- bitset_windex i;
- bitset_windex windex;
- lbitset_elt *elt;
-
- /* This is a decidedly unfriendly operation for a linked list
- bitset! It makes a sparse bitset become dense. An alternative
- is to have a flag that indicates that the bitset stores the
- complement of what it indicates. */
-
- windex = (BITSET_SIZE_ (dst) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS;
-
- for (i = 0; i < windex; i += LBITSET_ELT_WORDS)
- {
- /* Create new elements if they cannot be found. */
- elt = lbitset_elt_find (dst, i, LBITSET_CREATE);
- memset (elt->words, -1, sizeof (elt->words));
- }
-
- lbitset_unused_clear (dst);
-}
-
-
-static void
-lbitset_not (bitset dst, bitset src)
-{
- lbitset_elt *selt;
- lbitset_elt *delt;
- bitset_windex i;
- unsigned int j;
- bitset_windex windex;
-
- windex = (BITSET_SIZE_ (dst) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS;
-
- for (i = 0; i < windex; i += LBITSET_ELT_WORDS)
- {
- /* Create new elements for dst if they cannot be found
- or substitute zero elements if src elements not found. */
- selt = lbitset_elt_find (src, i, LBITSET_SUBST);
- delt = lbitset_elt_find (dst, i, LBITSET_CREATE);
-
- for (j = 0; j < LBITSET_ELT_WORDS; j++)
- delt->words[j] = ~selt->words[j];
- }
- lbitset_unused_clear (dst);
- lbitset_weed (dst);
- return;
-}
-
-
-/* Is DST == DST | SRC? */
-static bool
-lbitset_subset_p (bitset dst, bitset src)
-{
- lbitset_elt *selt;
- lbitset_elt *delt;
- unsigned int j;
-
- for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst);
- selt || delt; selt = selt->next, delt = delt->next)
- {
- if (!selt)
- selt = &lbitset_zero_elts[0];
- else if (!delt)
- delt = &lbitset_zero_elts[0];
- else if (selt->index != delt->index)
- {
- if (selt->index < delt->index)
- {
- lbitset_zero_elts[2].next = delt;
- delt = &lbitset_zero_elts[2];
- }
- else
- {
- lbitset_zero_elts[1].next = selt;
- selt = &lbitset_zero_elts[1];
- }
- }
-
- for (j = 0; j < LBITSET_ELT_WORDS; j++)
- if (delt->words[j] != (selt->words[j] | delt->words[j]))
- return false;
- }
- return true;
-}
-
-
-/* Is DST & SRC == 0? */
-static bool
-lbitset_disjoint_p (bitset dst, bitset src)
-{
- lbitset_elt *selt;
- lbitset_elt *delt;
- unsigned int j;
-
- for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst);
- selt && delt; selt = selt->next, delt = delt->next)
- {
- if (selt->index != delt->index)
- {
- if (selt->index < delt->index)
- {
- lbitset_zero_elts[2].next = delt;
- delt = &lbitset_zero_elts[2];
- }
- else
- {
- lbitset_zero_elts[1].next = selt;
- selt = &lbitset_zero_elts[1];
- }
- /* Since the elements are different, there is no
- intersection of these elements. */
- continue;
- }
-
- for (j = 0; j < LBITSET_ELT_WORDS; j++)
- if (selt->words[j] & delt->words[j])
- return false;
- }
- return true;
-}
-
-
-static bool
-lbitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op)
-{
- lbitset_elt *selt1 = LBITSET_HEAD (src1);
- lbitset_elt *selt2 = LBITSET_HEAD (src2);
- lbitset_elt *delt = LBITSET_HEAD (dst);
- bitset_windex windex1;
- bitset_windex windex2;
- bitset_windex windex;
- lbitset_elt *stmp1;
- lbitset_elt *stmp2;
- lbitset_elt *dtmp;
- bitset_word *srcp1;
- bitset_word *srcp2;
- bitset_word *dstp;
- bool changed = false;
- unsigned int i;
-
- LBITSET_HEAD (dst) = 0;
- dst->b.csize = 0;
-
- windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX;
- windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX;
-
- while (selt1 || selt2)
- {
- /* Figure out whether we need to substitute zero elements for
- missing links. */
- if (windex1 == windex2)
- {
- windex = windex1;
- stmp1 = selt1;
- stmp2 = selt2;
- selt1 = selt1->next;
- windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX;
- selt2 = selt2->next;
- windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX;
- }
- else if (windex1 < windex2)
- {
- windex = windex1;
- stmp1 = selt1;
- stmp2 = &lbitset_zero_elts[0];
- selt1 = selt1->next;
- windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX;
- }
- else
- {
- windex = windex2;
- stmp1 = &lbitset_zero_elts[0];
- stmp2 = selt2;
- selt2 = selt2->next;
- windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX;
- }
-
- /* Find the appropriate element from DST. Begin by discarding
- elements that we've skipped. */
- while (delt && delt->index < windex)
- {
- changed = true;
- dtmp = delt;
- delt = delt->next;
- lbitset_elt_free (dtmp);
- }
- if (delt && delt->index == windex)
- {
- dtmp = delt;
- delt = delt->next;
- }
- else
- dtmp = lbitset_elt_calloc ();
-
- /* Do the operation, and if any bits are set, link it into the
- linked list. */
- srcp1 = stmp1->words;
- srcp2 = stmp2->words;
- dstp = dtmp->words;
- switch (op)
- {
- default:
- abort ();
-
- case BITSET_OP_OR:
- for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
- {
- bitset_word tmp = *srcp1++ | *srcp2++;
-
- if (*dstp != tmp)
- {
- changed = true;
- *dstp = tmp;
- }
- }
- break;
-
- case BITSET_OP_AND:
- for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
- {
- bitset_word tmp = *srcp1++ & *srcp2++;
-
- if (*dstp != tmp)
- {
- changed = true;
- *dstp = tmp;
- }
- }
- break;
-
- case BITSET_OP_XOR:
- for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
- {
- bitset_word tmp = *srcp1++ ^ *srcp2++;
-
- if (*dstp != tmp)
- {
- changed = true;
- *dstp = tmp;
- }
- }
- break;
-
- case BITSET_OP_ANDN:
- for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
- {
- bitset_word tmp = *srcp1++ & ~(*srcp2++);
-
- if (*dstp != tmp)
- {
- changed = true;
- *dstp = tmp;
- }
- }
- break;
- }
-
- if (!lbitset_elt_zero_p (dtmp))
- {
- dtmp->index = windex;
- /* Perhaps this could be optimised... */
- lbitset_elt_link (dst, dtmp);
- }
- else
- {
- lbitset_elt_free (dtmp);
- }
- }
-
- /* If we have elements of DST left over, free them all. */
- if (delt)
- {
- changed = true;
- lbitset_prune (dst, delt);
- }
-
- return changed;
-}
-
-
-static bool
-lbitset_and_cmp (bitset dst, bitset src1, bitset src2)
-{
- lbitset_elt *selt1 = LBITSET_HEAD (src1);
- lbitset_elt *selt2 = LBITSET_HEAD (src2);
- bool changed;
-
- if (!selt2)
- {
- lbitset_weed (dst);
- changed = !LBITSET_HEAD (dst);
- lbitset_zero (dst);
- return changed;
- }
- else if (!selt1)
- {
- lbitset_weed (dst);
- changed = !LBITSET_HEAD (dst);
- lbitset_zero (dst);
- return changed;
- }
- return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_AND);
-}
-
-
-static void
-lbitset_and (bitset dst, bitset src1, bitset src2)
-{
- lbitset_and_cmp (dst, src1, src2);
-}
-
-
-static bool
-lbitset_andn_cmp (bitset dst, bitset src1, bitset src2)
-{
- lbitset_elt *selt1 = LBITSET_HEAD (src1);
- lbitset_elt *selt2 = LBITSET_HEAD (src2);
- bool changed;
-
- if (!selt2)
- {
- return lbitset_copy_cmp (dst, src1);
- }
- else if (!selt1)
- {
- lbitset_weed (dst);
- changed = !LBITSET_HEAD (dst);
- lbitset_zero (dst);
- return changed;
- }
- return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_ANDN);
-}
-
-
-static void
-lbitset_andn (bitset dst, bitset src1, bitset src2)
-{
- lbitset_andn_cmp (dst, src1, src2);
-}
-
-
-static bool
-lbitset_or_cmp (bitset dst, bitset src1, bitset src2)
-{
- lbitset_elt *selt1 = LBITSET_HEAD (src1);
- lbitset_elt *selt2 = LBITSET_HEAD (src2);
-
- if (!selt2)
- {
- return lbitset_copy_cmp (dst, src1);
- }
- else if (!selt1)
- {
- return lbitset_copy_cmp (dst, src2);
- }
- return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_OR);
-}
-
-
-static void
-lbitset_or (bitset dst, bitset src1, bitset src2)
-{
- lbitset_or_cmp (dst, src1, src2);
-}
-
-
-static bool
-lbitset_xor_cmp (bitset dst, bitset src1, bitset src2)
-{
- lbitset_elt *selt1 = LBITSET_HEAD (src1);
- lbitset_elt *selt2 = LBITSET_HEAD (src2);
-
- if (!selt2)
- {
- return lbitset_copy_cmp (dst, src1);
- }
- else if (!selt1)
- {
- return lbitset_copy_cmp (dst, src2);
- }
- return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_XOR);
-}
-
-
-static void
-lbitset_xor (bitset dst, bitset src1, bitset src2)
-{
- lbitset_xor_cmp (dst, src1, src2);
-}
-
-
-
-/* Vector of operations for linked-list bitsets. */
-struct bitset_vtable lbitset_vtable = {
- lbitset_set,
- lbitset_reset,
- bitset_toggle_,
- lbitset_test,
- lbitset_resize,
- bitset_size_,
- bitset_count_,
- lbitset_empty_p,
- lbitset_ones,
- lbitset_zero,
- lbitset_copy,
- lbitset_disjoint_p,
- lbitset_equal_p,
- lbitset_not,
- lbitset_subset_p,
- lbitset_and,
- lbitset_and_cmp,
- lbitset_andn,
- lbitset_andn_cmp,
- lbitset_or,
- lbitset_or_cmp,
- lbitset_xor,
- lbitset_xor_cmp,
- bitset_and_or_,
- bitset_and_or_cmp_,
- bitset_andn_or_,
- bitset_andn_or_cmp_,
- bitset_or_and_,
- bitset_or_and_cmp_,
- lbitset_list,
- lbitset_list_reverse,
- lbitset_free,
- BITSET_LIST
-};
-
-
-/* Return size of initial structure. */
-size_t
-lbitset_bytes (bitset_bindex n_bits ATTRIBUTE_UNUSED)
-{
- return sizeof (struct lbitset_struct);
-}
-
-
-/* Initialize a bitset. */
-bitset
-lbitset_init (bitset bset, bitset_bindex n_bits ATTRIBUTE_UNUSED)
-{
- BITSET_NBITS_ (bset) = n_bits;
- bset->b.vtable = &lbitset_vtable;
- return bset;
-}
-
-
-void
-lbitset_release_memory (void)
-{
- lbitset_free_list = 0;
- if (lbitset_obstack_init)
- {
- lbitset_obstack_init = false;
- obstack_free (&lbitset_obstack, NULL);
- }
-}
-
-
-/* Function to be called from debugger to debug lbitset. */
-void
-debug_lbitset (bitset bset)
-{
- lbitset_elt *elt;
- unsigned int i;
-
- if (!bset)
- return;
-
- for (elt = LBITSET_HEAD (bset); elt; elt = elt->next)
- {
- fprintf (stderr, "Elt %lu\n", (unsigned long int) elt->index);
- for (i = 0; i < LBITSET_ELT_WORDS; i++)
- {
- unsigned int j;
- bitset_word word;
-
- word = elt->words[i];
-
- fprintf (stderr, " Word %u:", i);
- for (j = 0; j < LBITSET_WORD_BITS; j++)
- if ((word & ((bitset_word) 1 << j)))
- fprintf (stderr, " %u", j);
- fprintf (stderr, "\n");
- }
- }
-}
diff --git a/contrib/tools/m4/lib/lbitset.h b/contrib/tools/m4/lib/lbitset.h
deleted file mode 100644
index 8ccaca74dab..00000000000
--- a/contrib/tools/m4/lib/lbitset.h
+++ /dev/null
@@ -1,31 +0,0 @@
-/* Functions to support lbitsets.
-
- Copyright (C) 2002, 2004, 2009-2013 Free Software Foundation, Inc.
-
- Contributed by Michael Hayes ([email protected]).
-
- 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 <http://www.gnu.org/licenses/>. */
-
-#ifndef _LBITSET_H
-#define _LBITSET_H
-
-#include "bitset.h"
-
-extern size_t lbitset_bytes (bitset_bindex);
-
-extern bitset lbitset_init (bitset, bitset_bindex);
-
-extern void lbitset_release_memory (void);
-
-#endif
diff --git a/contrib/tools/m4/lib/libiberty.h b/contrib/tools/m4/lib/libiberty.h
deleted file mode 100644
index ec1467c59b6..00000000000
--- a/contrib/tools/m4/lib/libiberty.h
+++ /dev/null
@@ -1,36 +0,0 @@
-/* Fake libiberty.h for Bison.
-
- Copyright (C) 2002-2004, 2009-2013 Free Software Foundation, Inc.
-
- 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 <http://www.gnu.org/licenses/>. */
-
-
-/* Bison depends on libiberty's implementation of bitsets, which
- requires a 'libiberty.h' file. This file provides the minimum
- services. */
-
-#ifndef BISON_LIBIBERTY_H_
-# define BISON_LIBIBERTY_H_ 1
-
-# ifndef __attribute__
-# if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8)
-# define __attribute__(x)
-# endif
-# endif
-
-# define ATTRIBUTE_UNUSED __attribute__ ((__unused__))
-
-# include "xalloc.h"
-
-#endif /* ! BISON_LIBIBERTY_H_ */
diff --git a/contrib/tools/m4/lib/str-two-way.h b/contrib/tools/m4/lib/str-two-way.h
deleted file mode 100644
index 707145dbdd2..00000000000
--- a/contrib/tools/m4/lib/str-two-way.h
+++ /dev/null
@@ -1,452 +0,0 @@
-/* Byte-wise substring search, using the Two-Way algorithm.
- Copyright (C) 2008-2013 Free Software Foundation, Inc.
- This file is part of the GNU C Library.
- Written by Eric Blake <[email protected]>, 2008.
-
- 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, 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 <http://www.gnu.org/licenses/>. */
-
-/* Before including this file, you need to include <config.h> and
- <string.h>, and define:
- RESULT_TYPE A macro that expands to the return type.
- AVAILABLE(h, h_l, j, n_l)
- A macro that returns nonzero if there are
- at least N_L bytes left starting at H[J].
- H is 'unsigned char *', H_L, J, and N_L
- are 'size_t'; H_L is an lvalue. For
- NUL-terminated searches, H_L can be
- modified each iteration to avoid having
- to compute the end of H up front.
-
- For case-insensitivity, you may optionally define:
- CMP_FUNC(p1, p2, l) A macro that returns 0 iff the first L
- characters of P1 and P2 are equal.
- CANON_ELEMENT(c) A macro that canonicalizes an element right after
- it has been fetched from one of the two strings.
- The argument is an 'unsigned char'; the result
- must be an 'unsigned char' as well.
-
- This file undefines the macros documented above, and defines
- LONG_NEEDLE_THRESHOLD.
-*/
-
-#include <limits.h>
-#include <stdint.h>
-
-/* We use the Two-Way string matching algorithm (also known as
- Chrochemore-Perrin), which guarantees linear complexity with
- constant space. Additionally, for long needles, we also use a bad
- character shift table similar to the Boyer-Moore algorithm to
- achieve improved (potentially sub-linear) performance.
-
- See http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260,
- http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm,
- http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.34.6641&rep=rep1&type=pdf
-*/
-
-/* Point at which computing a bad-byte shift table is likely to be
- worthwhile. Small needles should not compute a table, since it
- adds (1 << CHAR_BIT) + NEEDLE_LEN computations of preparation for a
- speedup no greater than a factor of NEEDLE_LEN. The larger the
- needle, the better the potential performance gain. On the other
- hand, on non-POSIX systems with CHAR_BIT larger than eight, the
- memory required for the table is prohibitive. */
-#if CHAR_BIT < 10
-# define LONG_NEEDLE_THRESHOLD 32U
-#else
-# define LONG_NEEDLE_THRESHOLD SIZE_MAX
-#endif
-
-#ifndef MAX
-# define MAX(a, b) ((a < b) ? (b) : (a))
-#endif
-
-#ifndef CANON_ELEMENT
-# define CANON_ELEMENT(c) c
-#endif
-#ifndef CMP_FUNC
-# define CMP_FUNC memcmp
-#endif
-
-/* Perform a critical factorization of NEEDLE, of length NEEDLE_LEN.
- Return the index of the first byte in the right half, and set
- *PERIOD to the global period of the right half.
-
- The global period of a string is the smallest index (possibly its
- length) at which all remaining bytes in the string are repetitions
- of the prefix (the last repetition may be a subset of the prefix).
-
- When NEEDLE is factored into two halves, a local period is the
- length of the smallest word that shares a suffix with the left half
- and shares a prefix with the right half. All factorizations of a
- non-empty NEEDLE have a local period of at least 1 and no greater
- than NEEDLE_LEN.
-
- A critical factorization has the property that the local period
- equals the global period. All strings have at least one critical
- factorization with the left half smaller than the global period.
- And while some strings have more than one critical factorization,
- it is provable that with an ordered alphabet, at least one of the
- critical factorizations corresponds to a maximal suffix.
-
- Given an ordered alphabet, a critical factorization can be computed
- in linear time, with 2 * NEEDLE_LEN comparisons, by computing the
- shorter of two ordered maximal suffixes. The ordered maximal
- suffixes are determined by lexicographic comparison while tracking
- periodicity. */
-static size_t
-critical_factorization (const unsigned char *needle, size_t needle_len,
- size_t *period)
-{
- /* Index of last byte of left half, or SIZE_MAX. */
- size_t max_suffix, max_suffix_rev;
- size_t j; /* Index into NEEDLE for current candidate suffix. */
- size_t k; /* Offset into current period. */
- size_t p; /* Intermediate period. */
- unsigned char a, b; /* Current comparison bytes. */
-
- /* Special case NEEDLE_LEN of 1 or 2 (all callers already filtered
- out 0-length needles. */
- if (needle_len < 3)
- {
- *period = 1;
- return needle_len - 1;
- }
-
- /* Invariants:
- 0 <= j < NEEDLE_LEN - 1
- -1 <= max_suffix{,_rev} < j (treating SIZE_MAX as if it were signed)
- min(max_suffix, max_suffix_rev) < global period of NEEDLE
- 1 <= p <= global period of NEEDLE
- p == global period of the substring NEEDLE[max_suffix{,_rev}+1...j]
- 1 <= k <= p
- */
-
- /* Perform lexicographic search. */
- max_suffix = SIZE_MAX;
- j = 0;
- k = p = 1;
- while (j + k < needle_len)
- {
- a = CANON_ELEMENT (needle[j + k]);
- b = CANON_ELEMENT (needle[max_suffix + k]);
- if (a < b)
- {
- /* Suffix is smaller, period is entire prefix so far. */
- j += k;
- k = 1;
- p = j - max_suffix;
- }
- else if (a == b)
- {
- /* Advance through repetition of the current period. */
- if (k != p)
- ++k;
- else
- {
- j += p;
- k = 1;
- }
- }
- else /* b < a */
- {
- /* Suffix is larger, start over from current location. */
- max_suffix = j++;
- k = p = 1;
- }
- }
- *period = p;
-
- /* Perform reverse lexicographic search. */
- max_suffix_rev = SIZE_MAX;
- j = 0;
- k = p = 1;
- while (j + k < needle_len)
- {
- a = CANON_ELEMENT (needle[j + k]);
- b = CANON_ELEMENT (needle[max_suffix_rev + k]);
- if (b < a)
- {
- /* Suffix is smaller, period is entire prefix so far. */
- j += k;
- k = 1;
- p = j - max_suffix_rev;
- }
- else if (a == b)
- {
- /* Advance through repetition of the current period. */
- if (k != p)
- ++k;
- else
- {
- j += p;
- k = 1;
- }
- }
- else /* a < b */
- {
- /* Suffix is larger, start over from current location. */
- max_suffix_rev = j++;
- k = p = 1;
- }
- }
-
- /* Choose the shorter suffix. Return the index of the first byte of
- the right half, rather than the last byte of the left half.
-
- For some examples, 'banana' has two critical factorizations, both
- exposed by the two lexicographic extreme suffixes of 'anana' and
- 'nana', where both suffixes have a period of 2. On the other
- hand, with 'aab' and 'bba', both strings have a single critical
- factorization of the last byte, with the suffix having a period
- of 1. While the maximal lexicographic suffix of 'aab' is 'b',
- the maximal lexicographic suffix of 'bba' is 'ba', which is not a
- critical factorization. Conversely, the maximal reverse
- lexicographic suffix of 'a' works for 'bba', but not 'ab' for
- 'aab'. The shorter suffix of the two will always be a critical
- factorization. */
- if (max_suffix_rev + 1 < max_suffix + 1)
- return max_suffix + 1;
- *period = p;
- return max_suffix_rev + 1;
-}
-
-/* Return the first location of non-empty NEEDLE within HAYSTACK, or
- NULL. HAYSTACK_LEN is the minimum known length of HAYSTACK. This
- method is optimized for NEEDLE_LEN < LONG_NEEDLE_THRESHOLD.
- Performance is guaranteed to be linear, with an initialization cost
- of 2 * NEEDLE_LEN comparisons.
-
- If AVAILABLE does not modify HAYSTACK_LEN (as in memmem), then at
- most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching.
- If AVAILABLE modifies HAYSTACK_LEN (as in strstr), then at most 3 *
- HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching. */
-static RETURN_TYPE
-two_way_short_needle (const unsigned char *haystack, size_t haystack_len,
- const unsigned char *needle, size_t needle_len)
-{
- size_t i; /* Index into current byte of NEEDLE. */
- size_t j; /* Index into current window of HAYSTACK. */
- size_t period; /* The period of the right half of needle. */
- size_t suffix; /* The index of the right half of needle. */
-
- /* Factor the needle into two halves, such that the left half is
- smaller than the global period, and the right half is
- periodic (with a period as large as NEEDLE_LEN - suffix). */
- suffix = critical_factorization (needle, needle_len, &period);
-
- /* Perform the search. Each iteration compares the right half
- first. */
- if (CMP_FUNC (needle, needle + period, suffix) == 0)
- {
- /* Entire needle is periodic; a mismatch in the left half can
- only advance by the period, so use memory to avoid rescanning
- known occurrences of the period in the right half. */
- size_t memory = 0;
- j = 0;
- while (AVAILABLE (haystack, haystack_len, j, needle_len))
- {
- /* Scan for matches in right half. */
- i = MAX (suffix, memory);
- while (i < needle_len && (CANON_ELEMENT (needle[i])
- == CANON_ELEMENT (haystack[i + j])))
- ++i;
- if (needle_len <= i)
- {
- /* Scan for matches in left half. */
- i = suffix - 1;
- while (memory < i + 1 && (CANON_ELEMENT (needle[i])
- == CANON_ELEMENT (haystack[i + j])))
- --i;
- if (i + 1 < memory + 1)
- return (RETURN_TYPE) (haystack + j);
- /* No match, so remember how many repetitions of period
- on the right half were scanned. */
- j += period;
- memory = needle_len - period;
- }
- else
- {
- j += i - suffix + 1;
- memory = 0;
- }
- }
- }
- else
- {
- /* The two halves of needle are distinct; no extra memory is
- required, and any mismatch results in a maximal shift. */
- period = MAX (suffix, needle_len - suffix) + 1;
- j = 0;
- while (AVAILABLE (haystack, haystack_len, j, needle_len))
- {
- /* Scan for matches in right half. */
- i = suffix;
- while (i < needle_len && (CANON_ELEMENT (needle[i])
- == CANON_ELEMENT (haystack[i + j])))
- ++i;
- if (needle_len <= i)
- {
- /* Scan for matches in left half. */
- i = suffix - 1;
- while (i != SIZE_MAX && (CANON_ELEMENT (needle[i])
- == CANON_ELEMENT (haystack[i + j])))
- --i;
- if (i == SIZE_MAX)
- return (RETURN_TYPE) (haystack + j);
- j += period;
- }
- else
- j += i - suffix + 1;
- }
- }
- return NULL;
-}
-
-/* Return the first location of non-empty NEEDLE within HAYSTACK, or
- NULL. HAYSTACK_LEN is the minimum known length of HAYSTACK. This
- method is optimized for LONG_NEEDLE_THRESHOLD <= NEEDLE_LEN.
- Performance is guaranteed to be linear, with an initialization cost
- of 3 * NEEDLE_LEN + (1 << CHAR_BIT) operations.
-
- If AVAILABLE does not modify HAYSTACK_LEN (as in memmem), then at
- most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching,
- and sublinear performance O(HAYSTACK_LEN / NEEDLE_LEN) is possible.
- If AVAILABLE modifies HAYSTACK_LEN (as in strstr), then at most 3 *
- HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching, and
- sublinear performance is not possible. */
-static RETURN_TYPE
-two_way_long_needle (const unsigned char *haystack, size_t haystack_len,
- const unsigned char *needle, size_t needle_len)
-{
- size_t i; /* Index into current byte of NEEDLE. */
- size_t j; /* Index into current window of HAYSTACK. */
- size_t period; /* The period of the right half of needle. */
- size_t suffix; /* The index of the right half of needle. */
- size_t shift_table[1U << CHAR_BIT]; /* See below. */
-
- /* Factor the needle into two halves, such that the left half is
- smaller than the global period, and the right half is
- periodic (with a period as large as NEEDLE_LEN - suffix). */
- suffix = critical_factorization (needle, needle_len, &period);
-
- /* Populate shift_table. For each possible byte value c,
- shift_table[c] is the distance from the last occurrence of c to
- the end of NEEDLE, or NEEDLE_LEN if c is absent from the NEEDLE.
- shift_table[NEEDLE[NEEDLE_LEN - 1]] contains the only 0. */
- for (i = 0; i < 1U << CHAR_BIT; i++)
- shift_table[i] = needle_len;
- for (i = 0; i < needle_len; i++)
- shift_table[CANON_ELEMENT (needle[i])] = needle_len - i - 1;
-
- /* Perform the search. Each iteration compares the right half
- first. */
- if (CMP_FUNC (needle, needle + period, suffix) == 0)
- {
- /* Entire needle is periodic; a mismatch in the left half can
- only advance by the period, so use memory to avoid rescanning
- known occurrences of the period in the right half. */
- size_t memory = 0;
- size_t shift;
- j = 0;
- while (AVAILABLE (haystack, haystack_len, j, needle_len))
- {
- /* Check the last byte first; if it does not match, then
- shift to the next possible match location. */
- shift = shift_table[CANON_ELEMENT (haystack[j + needle_len - 1])];
- if (0 < shift)
- {
- if (memory && shift < period)
- {
- /* Since needle is periodic, but the last period has
- a byte out of place, there can be no match until
- after the mismatch. */
- shift = needle_len - period;
- }
- memory = 0;
- j += shift;
- continue;
- }
- /* Scan for matches in right half. The last byte has
- already been matched, by virtue of the shift table. */
- i = MAX (suffix, memory);
- while (i < needle_len - 1 && (CANON_ELEMENT (needle[i])
- == CANON_ELEMENT (haystack[i + j])))
- ++i;
- if (needle_len - 1 <= i)
- {
- /* Scan for matches in left half. */
- i = suffix - 1;
- while (memory < i + 1 && (CANON_ELEMENT (needle[i])
- == CANON_ELEMENT (haystack[i + j])))
- --i;
- if (i + 1 < memory + 1)
- return (RETURN_TYPE) (haystack + j);
- /* No match, so remember how many repetitions of period
- on the right half were scanned. */
- j += period;
- memory = needle_len - period;
- }
- else
- {
- j += i - suffix + 1;
- memory = 0;
- }
- }
- }
- else
- {
- /* The two halves of needle are distinct; no extra memory is
- required, and any mismatch results in a maximal shift. */
- size_t shift;
- period = MAX (suffix, needle_len - suffix) + 1;
- j = 0;
- while (AVAILABLE (haystack, haystack_len, j, needle_len))
- {
- /* Check the last byte first; if it does not match, then
- shift to the next possible match location. */
- shift = shift_table[CANON_ELEMENT (haystack[j + needle_len - 1])];
- if (0 < shift)
- {
- j += shift;
- continue;
- }
- /* Scan for matches in right half. The last byte has
- already been matched, by virtue of the shift table. */
- i = suffix;
- while (i < needle_len - 1 && (CANON_ELEMENT (needle[i])
- == CANON_ELEMENT (haystack[i + j])))
- ++i;
- if (needle_len - 1 <= i)
- {
- /* Scan for matches in left half. */
- i = suffix - 1;
- while (i != SIZE_MAX && (CANON_ELEMENT (needle[i])
- == CANON_ELEMENT (haystack[i + j])))
- --i;
- if (i == SIZE_MAX)
- return (RETURN_TYPE) (haystack + j);
- j += period;
- }
- else
- j += i - suffix + 1;
- }
- }
- return NULL;
-}
-
-#undef AVAILABLE
-#undef CANON_ELEMENT
-#undef CMP_FUNC
-#undef MAX
-#undef RETURN_TYPE
diff --git a/contrib/tools/m4/lib/strchrnul.c b/contrib/tools/m4/lib/strchrnul.c
deleted file mode 100644
index 43088899507..00000000000
--- a/contrib/tools/m4/lib/strchrnul.c
+++ /dev/null
@@ -1,142 +0,0 @@
-/* Searching in a string.
- Copyright (C) 2003, 2007-2013 Free Software Foundation, Inc.
-
- 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 <http://www.gnu.org/licenses/>. */
-
-#include <config.h>
-
-/* Specification. */
-#include "string--.h"
-
-/* Find the first occurrence of C in S or the final NUL byte. */
-char *
-strchrnul (const char *s, int c_in)
-{
- /* On 32-bit hardware, choosing longword to be a 32-bit unsigned
- long instead of a 64-bit uintmax_t tends to give better
- performance. On 64-bit hardware, unsigned long is generally 64
- bits already. Change this typedef to experiment with
- performance. */
- typedef unsigned long int longword;
-
- const unsigned char *char_ptr;
- const longword *longword_ptr;
- longword repeated_one;
- longword repeated_c;
- unsigned char c;
-
- c = (unsigned char) c_in;
- if (!c)
- return rawmemchr (s, 0);
-
- /* Handle the first few bytes by reading one byte at a time.
- Do this until CHAR_PTR is aligned on a longword boundary. */
- for (char_ptr = (const unsigned char *) s;
- (size_t) char_ptr % sizeof (longword) != 0;
- ++char_ptr)
- if (!*char_ptr || *char_ptr == c)
- return (char *) char_ptr;
-
- longword_ptr = (const longword *) char_ptr;
-
- /* All these elucidatory comments refer to 4-byte longwords,
- but the theory applies equally well to any size longwords. */
-
- /* Compute auxiliary longword values:
- repeated_one is a value which has a 1 in every byte.
- repeated_c has c in every byte. */
- repeated_one = 0x01010101;
- repeated_c = c | (c << 8);
- repeated_c |= repeated_c << 16;
- if (0xffffffffU < (longword) -1)
- {
- repeated_one |= repeated_one << 31 << 1;
- repeated_c |= repeated_c << 31 << 1;
- if (8 < sizeof (longword))
- {
- size_t i;
-
- for (i = 64; i < sizeof (longword) * 8; i *= 2)
- {
- repeated_one |= repeated_one << i;
- repeated_c |= repeated_c << i;
- }
- }
- }
-
- /* Instead of the traditional loop which tests each byte, we will
- test a longword at a time. The tricky part is testing if *any of
- the four* bytes in the longword in question are equal to NUL or
- c. We first use an xor with repeated_c. This reduces the task
- to testing whether *any of the four* bytes in longword1 or
- longword2 is zero.
-
- Let's consider longword1. We compute tmp =
- ((longword1 - repeated_one) & ~longword1) & (repeated_one << 7).
- That is, we perform the following operations:
- 1. Subtract repeated_one.
- 2. & ~longword1.
- 3. & a mask consisting of 0x80 in every byte.
- Consider what happens in each byte:
- - If a byte of longword1 is zero, step 1 and 2 transform it into 0xff,
- and step 3 transforms it into 0x80. A carry can also be propagated
- to more significant bytes.
- - If a byte of longword1 is nonzero, let its lowest 1 bit be at
- position k (0 <= k <= 7); so the lowest k bits are 0. After step 1,
- the byte ends in a single bit of value 0 and k bits of value 1.
- After step 2, the result is just k bits of value 1: 2^k - 1. After
- step 3, the result is 0. And no carry is produced.
- So, if longword1 has only non-zero bytes, tmp is zero.
- Whereas if longword1 has a zero byte, call j the position of the least
- significant zero byte. Then the result has a zero at positions 0, ...,
- j-1 and a 0x80 at position j. We cannot predict the result at the more
- significant bytes (positions j+1..3), but it does not matter since we
- already have a non-zero bit at position 8*j+7.
-
- The test whether any byte in longword1 or longword2 is zero is equivalent
- to testing whether tmp1 is nonzero or tmp2 is nonzero. We can combine
- this into a single test, whether (tmp1 | tmp2) is nonzero.
-
- This test can read more than one byte beyond the end of a string,
- depending on where the terminating NUL is encountered. However,
- this is considered safe since the initialization phase ensured
- that the read will be aligned, therefore, the read will not cross
- page boundaries and will not cause a fault. */
-
- while (1)
- {
- longword longword1 = *longword_ptr ^ repeated_c;
- longword longword2 = *longword_ptr;
-
- if (((((longword1 - repeated_one) & ~longword1)
- | ((longword2 - repeated_one) & ~longword2))
- & (repeated_one << 7)) != 0)
- break;
- longword_ptr++;
- }
-
- char_ptr = (const unsigned char *) longword_ptr;
-
- /* At this point, we know that one of the sizeof (longword) bytes
- starting at char_ptr is == 0 or == c. On little-endian machines,
- we could determine the first such byte without any further memory
- accesses, just by looking at the tmp result from the last loop
- iteration. But this does not work on big-endian machines.
- Choose code that works in both cases. */
-
- char_ptr = (unsigned char *) longword_ptr;
- while (*char_ptr && (*char_ptr != c))
- char_ptr++;
- return (char *) char_ptr;
-}
diff --git a/contrib/tools/m4/lib/string--.h b/contrib/tools/m4/lib/string--.h
deleted file mode 100644
index 24a1932992a..00000000000
--- a/contrib/tools/m4/lib/string--.h
+++ /dev/null
@@ -1,10 +0,0 @@
-#pragma once
-
-#include <string.h>
-
-#if defined(_WIN32)
-void *rawmemchr(const void *s, int c);
-char *stpcpy(char *dest, const char *src);
-#endif
-
-int strverscmp(const char *s1, const char *s2);
diff --git a/contrib/tools/m4/lib/strndup.c b/contrib/tools/m4/lib/strndup.c
deleted file mode 100644
index e60268b86ed..00000000000
--- a/contrib/tools/m4/lib/strndup.c
+++ /dev/null
@@ -1,36 +0,0 @@
-/* A replacement function, for systems that lack strndup.
-
- Copyright (C) 1996-1998, 2001-2003, 2005-2007, 2009-2013 Free Software
- Foundation, Inc.
-
- 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, 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 <http://www.gnu.org/licenses/>. */
-
-#include <config.h>
-
-#include <string.h>
-
-#include <stdlib.h>
-
-char *
-strndup (char const *s, size_t n)
-{
- size_t len = strnlen (s, n);
- char *new = malloc (len + 1);
-
- if (new == NULL)
- return NULL;
-
- new[len] = '\0';
- return memcpy (new, s, len);
-}
diff --git a/contrib/tools/m4/lib/strstr.c b/contrib/tools/m4/lib/strstr.c
deleted file mode 100644
index b91acec7c83..00000000000
--- a/contrib/tools/m4/lib/strstr.c
+++ /dev/null
@@ -1,82 +0,0 @@
-/* Copyright (C) 1991-1994, 1996-1998, 2000, 2004, 2007-2013 Free Software
- Foundation, Inc.
- This file is part of the GNU C Library.
-
- 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, 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 <http://www.gnu.org/licenses/>. */
-
-/* This particular implementation was written by Eric Blake, 2008. */
-
-#ifndef _LIBC
-# include <config.h>
-#endif
-
-/* Specification of strstr. */
-#include <string.h>
-
-#include <stdbool.h>
-
-#ifndef _LIBC
-# define __builtin_expect(expr, val) (expr)
-#endif
-
-#define RETURN_TYPE char *
-#define AVAILABLE(h, h_l, j, n_l) \
- (!memchr ((h) + (h_l), '\0', (j) + (n_l) - (h_l)) \
- && ((h_l) = (j) + (n_l)))
-#include "str-two-way.h"
-
-/* Return the first occurrence of NEEDLE in HAYSTACK. Return HAYSTACK
- if NEEDLE is empty, otherwise NULL if NEEDLE is not found in
- HAYSTACK. */
-char *
-strstr (const char *haystack_start, const char *needle_start)
-{
- const char *haystack = haystack_start;
- const char *needle = needle_start;
- size_t needle_len; /* Length of NEEDLE. */
- size_t haystack_len; /* Known minimum length of HAYSTACK. */
- bool ok = true; /* True if NEEDLE is prefix of HAYSTACK. */
-
- /* Determine length of NEEDLE, and in the process, make sure
- HAYSTACK is at least as long (no point processing all of a long
- NEEDLE if HAYSTACK is too short). */
- while (*haystack && *needle)
- ok &= *haystack++ == *needle++;
- if (*needle)
- return NULL;
- if (ok)
- return (char *) haystack_start;
-
- /* Reduce the size of haystack using strchr, since it has a smaller
- linear coefficient than the Two-Way algorithm. */
- needle_len = needle - needle_start;
- haystack = strchr (haystack_start + 1, *needle_start);
- if (!haystack || __builtin_expect (needle_len == 1, 0))
- return (char *) haystack;
- needle -= needle_len;
- haystack_len = (haystack > haystack_start + needle_len ? 1
- : needle_len + haystack_start - haystack);
-
- /* Perform the search. Abstract memory is considered to be an array
- of 'unsigned char' values, not an array of 'char' values. See
- ISO C 99 section 6.2.6.1. */
- if (needle_len < LONG_NEEDLE_THRESHOLD)
- return two_way_short_needle ((const unsigned char *) haystack,
- haystack_len,
- (const unsigned char *) needle, needle_len);
- return two_way_long_needle ((const unsigned char *) haystack, haystack_len,
- (const unsigned char *) needle, needle_len);
-}
-
-#undef LONG_NEEDLE_THRESHOLD
diff --git a/contrib/tools/m4/lib/strverscmp.c b/contrib/tools/m4/lib/strverscmp.c
deleted file mode 100644
index db4f1edc705..00000000000
--- a/contrib/tools/m4/lib/strverscmp.c
+++ /dev/null
@@ -1,131 +0,0 @@
-/* Compare strings while treating digits characters numerically.
- Copyright (C) 1997, 2000, 2002, 2004, 2006, 2009-2013 Free Software
- Foundation, Inc.
- This file is part of the GNU C Library.
- Contributed by Jean-François Bignolles <[email protected]>, 1997.
-
- 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, 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 <http://www.gnu.org/licenses/>. */
-
-#if !_LIBC
-# include <config.h>
-#endif
-
-#include <string.h>
-#include <ctype.h>
-
-/* states: S_N: normal, S_I: comparing integral part, S_F: comparing
- fractional parts, S_Z: idem but with leading Zeroes only */
-#define S_N 0x0
-#define S_I 0x4
-#define S_F 0x8
-#define S_Z 0xC
-
-/* result_type: CMP: return diff; LEN: compare using len_diff/diff */
-#define CMP 2
-#define LEN 3
-
-
-/* ISDIGIT differs from isdigit, as follows:
- - Its arg may be any int or unsigned int; it need not be an unsigned char
- or EOF.
- - It's typically faster.
- POSIX says that only '0' through '9' are digits. Prefer ISDIGIT to
- isdigit unless it's important to use the locale's definition
- of "digit" even when the host does not conform to POSIX. */
-#define ISDIGIT(c) ((unsigned int) (c) - '0' <= 9)
-
-#undef __strverscmp
-#undef strverscmp
-
-#ifndef weak_alias
-# define __strverscmp strverscmp
-#endif
-
-/* Compare S1 and S2 as strings holding indices/version numbers,
- returning less than, equal to or greater than zero if S1 is less than,
- equal to or greater than S2 (for more info, see the texinfo doc).
-*/
-
-int
-__strverscmp (const char *s1, const char *s2)
-{
- const unsigned char *p1 = (const unsigned char *) s1;
- const unsigned char *p2 = (const unsigned char *) s2;
- unsigned char c1, c2;
- int state;
- int diff;
-
- /* Symbol(s) 0 [1-9] others (padding)
- Transition (10) 0 (01) d (00) x (11) - */
- static const unsigned int next_state[] =
- {
- /* state x d 0 - */
- /* S_N */ S_N, S_I, S_Z, S_N,
- /* S_I */ S_N, S_I, S_I, S_I,
- /* S_F */ S_N, S_F, S_F, S_F,
- /* S_Z */ S_N, S_F, S_Z, S_Z
- };
-
- static const int result_type[] =
- {
- /* state x/x x/d x/0 x/- d/x d/d d/0 d/-
- 0/x 0/d 0/0 0/- -/x -/d -/0 -/- */
-
- /* S_N */ CMP, CMP, CMP, CMP, CMP, LEN, CMP, CMP,
- CMP, CMP, CMP, CMP, CMP, CMP, CMP, CMP,
- /* S_I */ CMP, -1, -1, CMP, 1, LEN, LEN, CMP,
- 1, LEN, LEN, CMP, CMP, CMP, CMP, CMP,
- /* S_F */ CMP, CMP, CMP, CMP, CMP, LEN, CMP, CMP,
- CMP, CMP, CMP, CMP, CMP, CMP, CMP, CMP,
- /* S_Z */ CMP, 1, 1, CMP, -1, CMP, CMP, CMP,
- -1, CMP, CMP, CMP
- };
-
- if (p1 == p2)
- return 0;
-
- c1 = *p1++;
- c2 = *p2++;
- /* Hint: '0' is a digit too. */
- state = S_N | ((c1 == '0') + (ISDIGIT (c1) != 0));
-
- while ((diff = c1 - c2) == 0 && c1 != '\0')
- {
- state = next_state[state];
- c1 = *p1++;
- c2 = *p2++;
- state |= (c1 == '0') + (ISDIGIT (c1) != 0);
- }
-
- state = result_type[state << 2 | ((c2 == '0') + (ISDIGIT (c2) != 0))];
-
- switch (state)
- {
- case CMP:
- return diff;
-
- case LEN:
- while (ISDIGIT (*p1++))
- if (!ISDIGIT (*p2++))
- return 1;
-
- return ISDIGIT (*p2) ? -1 : diff;
-
- default:
- return state;
- }
-}
-#ifdef weak_alias
-weak_alias (__strverscmp, strverscmp)
-#endif
diff --git a/contrib/tools/m4/lib/timevar.c b/contrib/tools/m4/lib/timevar.c
deleted file mode 100644
index a9dbdbdee5e..00000000000
--- a/contrib/tools/m4/lib/timevar.c
+++ /dev/null
@@ -1,571 +0,0 @@
-/* Timing variables for measuring compiler performance.
-
- Copyright (C) 2000, 2002, 2004, 2006, 2009-2013 Free Software
- Foundation, Inc.
-
- Contributed by Alex Samuel <[email protected]>
-
- 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 <http://www.gnu.org/licenses/>. */
-
-#include <config.h>
-
-#if IN_GCC
-
-#include "system.h"
-#include "intl.h"
-#include "rtl.h"
-
-#else
-
-#if defined(_musl_)
- #define HAVE_SYS_TIMES_H 1
- #define HAVE_STRUCT_TMS 1
- #define HAVE_CLOCK_T 1
-#endif
-
-/* This source file is taken from the GCC source code, with slight
- modifications that are under control of the IN_GCC preprocessor
- variable. The !IN_GCC part of this file is specific to Bison. */
-
-# include "bison-system.h"
-# if HAVE_SYS_TIME_H
-# include <sys/time.h>
-# endif
-int timevar_report = 0;
-
-#endif
-
-
-#ifdef HAVE_SYS_TIMES_H
-# include <sys/times.h>
-#endif
-#ifdef HAVE_SYS_RESOURCE_H
-#include <sys/resource.h>
-#endif
-
-#ifndef HAVE_CLOCK_T
-typedef int clock_t;
-#endif
-
-#ifndef HAVE_STRUCT_TMS
-struct tms
-{
- clock_t tms_utime;
- clock_t tms_stime;
- clock_t tms_cutime;
- clock_t tms_cstime;
-};
-#endif
-
-#if defined HAVE_DECL_GETRUSAGE && !HAVE_DECL_GETRUSAGE
-extern int getrusage (int, struct rusage *);
-#endif
-#if defined HAVE_DECL_TIMES && !HAVE_DECL_TIMES
-extern clock_t times (struct tms *);
-#endif
-#if defined HAVE_DECL_CLOCK && !HAVE_DECL_CLOCK
-extern clock_t clock (void);
-#endif
-
-#ifndef RUSAGE_SELF
-# define RUSAGE_SELF 0
-#endif
-
-/* Calculation of scale factor to convert ticks to microseconds.
- We mustn't use CLOCKS_PER_SEC except with clock(). */
-#if HAVE_SYSCONF && defined _SC_CLK_TCK
-# define TICKS_PER_SECOND sysconf (_SC_CLK_TCK) /* POSIX 1003.1-1996 */
-#else
-# ifdef CLK_TCK
-# define TICKS_PER_SECOND CLK_TCK /* POSIX 1003.1-1988; obsolescent */
-# else
-# ifdef HZ
-# define TICKS_PER_SECOND HZ /* traditional UNIX */
-# else
-# define TICKS_PER_SECOND 100 /* often the correct value */
-# endif
-# endif
-#endif
-
-/* Prefer times to getrusage to clock (each gives successively less
- information). */
-#ifdef HAVE_TIMES
-# define USE_TIMES
-# define HAVE_USER_TIME
-# define HAVE_SYS_TIME
-# define HAVE_WALL_TIME
-#else
-#ifdef HAVE_GETRUSAGE
-# define USE_GETRUSAGE
-# define HAVE_USER_TIME
-# define HAVE_SYS_TIME
-#else
-#ifdef HAVE_CLOCK
-# define USE_CLOCK
-# define HAVE_USER_TIME
-#endif
-#endif
-#endif
-
-/* libc is very likely to have snuck a call to sysconf() into one of
- the underlying constants, and that can be very slow, so we have to
- precompute them. Whose wonderful idea was it to make all those
- _constants_ variable at run time, anyway? */
-#ifdef USE_TIMES
-static float ticks_to_msec;
-#define TICKS_TO_MSEC (1.0 / TICKS_PER_SECOND)
-#endif
-
-#ifdef USE_CLOCK
-static float clocks_to_msec;
-#define CLOCKS_TO_MSEC (1.0 / CLOCKS_PER_SEC)
-#endif
-
-#if IN_GCC
-#include "flags.h"
-#endif
-#include "timevar.h"
-
-/* See timevar.h for an explanation of timing variables. */
-
-/* This macro evaluates to nonzero if timing variables are enabled. */
-#define TIMEVAR_ENABLE (timevar_report)
-
-/* A timing variable. */
-
-struct timevar_def
-{
- /* Elapsed time for this variable. */
- struct timevar_time_def elapsed;
-
- /* If this variable is timed independently of the timing stack,
- using timevar_start, this contains the start time. */
- struct timevar_time_def start_time;
-
- /* The name of this timing variable. */
- const char *name;
-
- /* Non-zero if this timing variable is running as a standalone
- timer. */
- unsigned standalone : 1;
-
- /* Non-zero if this timing variable was ever started or pushed onto
- the timing stack. */
- unsigned used : 1;
-};
-
-/* An element on the timing stack. Elapsed time is attributed to the
- topmost timing variable on the stack. */
-
-struct timevar_stack_def
-{
- /* The timing variable at this stack level. */
- struct timevar_def *timevar;
-
- /* The next lower timing variable context in the stack. */
- struct timevar_stack_def *next;
-};
-
-/* Declared timing variables. Constructed from the contents of
- timevar.def. */
-static struct timevar_def timevars[TIMEVAR_LAST];
-
-/* The top of the timing stack. */
-static struct timevar_stack_def *stack;
-
-/* A list of unused (i.e. allocated and subsequently popped)
- timevar_stack_def instances. */
-static struct timevar_stack_def *unused_stack_instances;
-
-/* The time at which the topmost element on the timing stack was
- pushed. Time elapsed since then is attributed to the topmost
- element. */
-static struct timevar_time_def start_time;
-
-static void get_time (struct timevar_time_def *);
-static void timevar_accumulate (struct timevar_time_def *,
- struct timevar_time_def *,
- struct timevar_time_def *);
-
-/* Fill the current times into TIME. The definition of this function
- also defines any or all of the HAVE_USER_TIME, HAVE_SYS_TIME, and
- HAVE_WALL_TIME macros. */
-
-static void
-get_time (now)
- struct timevar_time_def *now;
-{
- now->user = 0;
- now->sys = 0;
- now->wall = 0;
-
- if (!TIMEVAR_ENABLE)
- return;
-
- {
-#ifdef USE_TIMES
- struct tms tms;
- now->wall = times (&tms) * ticks_to_msec;
-#if IN_GCC
- now->user = tms.tms_utime * ticks_to_msec;
- now->sys = tms.tms_stime * ticks_to_msec;
-#else
- now->user = (tms.tms_utime + tms.tms_cutime) * ticks_to_msec;
- now->sys = (tms.tms_stime + tms.tms_cstime) * ticks_to_msec;
-#endif
-#endif
-#ifdef USE_GETRUSAGE
- struct rusage rusage;
-#if IN_GCC
- getrusage (RUSAGE_SELF, &rusage);
-#else
- getrusage (RUSAGE_CHILDREN, &rusage);
-#endif
- now->user = rusage.ru_utime.tv_sec + rusage.ru_utime.tv_usec * 1e-6;
- now->sys = rusage.ru_stime.tv_sec + rusage.ru_stime.tv_usec * 1e-6;
-#endif
-#ifdef USE_CLOCK
- now->user = clock () * clocks_to_msec;
-#endif
- }
-}
-
-/* Add the difference between STOP and START to TIMER. */
-
-static void
-timevar_accumulate (timer, start, stop)
- struct timevar_time_def *timer;
- struct timevar_time_def *start;
- struct timevar_time_def *stop;
-{
- timer->user += stop->user - start->user;
- timer->sys += stop->sys - start->sys;
- timer->wall += stop->wall - start->wall;
-}
-
-/* Initialize timing variables. */
-
-void
-init_timevar ()
-{
- if (!TIMEVAR_ENABLE)
- return;
-
- /* Zero all elapsed times. */
- memset ((void *) timevars, 0, sizeof (timevars));
-
- /* Initialize the names of timing variables. */
-#define DEFTIMEVAR(identifier__, name__) \
- timevars[identifier__].name = name__;
-#include "timevar.def"
-#undef DEFTIMEVAR
-
-#ifdef USE_TIMES
- ticks_to_msec = TICKS_TO_MSEC;
-#endif
-#ifdef USE_CLOCK
- clocks_to_msec = CLOCKS_TO_MSEC;
-#endif
-}
-
-/* Push TIMEVAR onto the timing stack. No further elapsed time is
- attributed to the previous topmost timing variable on the stack;
- subsequent elapsed time is attributed to TIMEVAR, until it is
- popped or another element is pushed on top.
-
- TIMEVAR cannot be running as a standalone timer. */
-
-void
-timevar_push (timevar)
- timevar_id_t timevar;
-{
- struct timevar_def *tv = &timevars[timevar];
- struct timevar_stack_def *context;
- struct timevar_time_def now;
-
- if (!TIMEVAR_ENABLE)
- return;
-
- /* Mark this timing variable as used. */
- tv->used = 1;
-
- /* Can't push a standalone timer. */
- if (tv->standalone)
- abort ();
-
- /* What time is it? */
- get_time (&now);
-
- /* If the stack isn't empty, attribute the current elapsed time to
- the old topmost element. */
- if (stack)
- timevar_accumulate (&stack->timevar->elapsed, &start_time, &now);
-
- /* Reset the start time; from now on, time is attributed to
- TIMEVAR. */
- start_time = now;
-
- /* See if we have a previously-allocated stack instance. If so,
- take it off the list. If not, malloc a new one. */
- if (unused_stack_instances != NULL)
- {
- context = unused_stack_instances;
- unused_stack_instances = unused_stack_instances->next;
- }
- else
- context = (struct timevar_stack_def *)
- xmalloc (sizeof (struct timevar_stack_def));
-
- /* Fill it in and put it on the stack. */
- context->timevar = tv;
- context->next = stack;
- stack = context;
-}
-
-/* Pop the topmost timing variable element off the timing stack. The
- popped variable must be TIMEVAR. Elapsed time since the that
- element was pushed on, or since it was last exposed on top of the
- stack when the element above it was popped off, is credited to that
- timing variable. */
-
-void
-timevar_pop (timevar)
- timevar_id_t timevar;
-{
- struct timevar_time_def now;
- struct timevar_stack_def *popped = stack;
-
- if (!TIMEVAR_ENABLE)
- return;
-
- if (&timevars[timevar] != stack->timevar)
- abort ();
-
- /* What time is it? */
- get_time (&now);
-
- /* Attribute the elapsed time to the element we're popping. */
- timevar_accumulate (&popped->timevar->elapsed, &start_time, &now);
-
- /* Reset the start time; from now on, time is attributed to the
- element just exposed on the stack. */
- start_time = now;
-
- /* Take the item off the stack. */
- stack = stack->next;
-
- /* Don't delete the stack element; instead, add it to the list of
- unused elements for later use. */
- popped->next = unused_stack_instances;
- unused_stack_instances = popped;
-}
-
-/* Start timing TIMEVAR independently of the timing stack. Elapsed
- time until timevar_stop is called for the same timing variable is
- attributed to TIMEVAR. */
-
-void
-timevar_start (timevar)
- timevar_id_t timevar;
-{
- struct timevar_def *tv = &timevars[timevar];
-
- if (!TIMEVAR_ENABLE)
- return;
-
- /* Mark this timing variable as used. */
- tv->used = 1;
-
- /* Don't allow the same timing variable to be started more than
- once. */
- if (tv->standalone)
- abort ();
- tv->standalone = 1;
-
- get_time (&tv->start_time);
-}
-
-/* Stop timing TIMEVAR. Time elapsed since timevar_start was called
- is attributed to it. */
-
-void
-timevar_stop (timevar)
- timevar_id_t timevar;
-{
- struct timevar_def *tv = &timevars[timevar];
- struct timevar_time_def now;
-
- if (!TIMEVAR_ENABLE)
- return;
-
- /* TIMEVAR must have been started via timevar_start. */
- if (!tv->standalone)
- abort ();
-
- get_time (&now);
- timevar_accumulate (&tv->elapsed, &tv->start_time, &now);
-}
-
-/* Fill the elapsed time for TIMEVAR into ELAPSED. Returns
- update-to-date information even if TIMEVAR is currently running. */
-
-void
-timevar_get (timevar, elapsed)
- timevar_id_t timevar;
- struct timevar_time_def *elapsed;
-{
- struct timevar_def *tv = &timevars[timevar];
- struct timevar_time_def now;
-
- *elapsed = tv->elapsed;
-
- /* Is TIMEVAR currently running as a standalone timer? */
- if (tv->standalone)
- {
- get_time (&now);
- timevar_accumulate (elapsed, &tv->start_time, &now);
- }
- /* Or is TIMEVAR at the top of the timer stack? */
- else if (stack->timevar == tv)
- {
- get_time (&now);
- timevar_accumulate (elapsed, &start_time, &now);
- }
-}
-
-/* Summarize timing variables to FP. The timing variable TV_TOTAL has
- a special meaning -- it's considered to be the total elapsed time,
- for normalizing the others, and is displayed last. */
-
-void
-timevar_print (fp)
- FILE *fp;
-{
- /* Only print stuff if we have some sort of time information. */
-#if defined HAVE_USER_TIME || defined HAVE_SYS_TIME || defined HAVE_WALL_TIME
- unsigned int /* timevar_id_t */ id;
- struct timevar_time_def *total = &timevars[TV_TOTAL].elapsed;
- struct timevar_time_def now;
-
- if (!TIMEVAR_ENABLE)
- return;
-
- /* Update timing information in case we're calling this from GDB. */
-
- if (fp == 0)
- fp = stderr;
-
- /* What time is it? */
- get_time (&now);
-
- /* If the stack isn't empty, attribute the current elapsed time to
- the old topmost element. */
- if (stack)
- timevar_accumulate (&stack->timevar->elapsed, &start_time, &now);
-
- /* Reset the start time; from now on, time is attributed to
- TIMEVAR. */
- start_time = now;
-
- fputs (_("\nExecution times (seconds)\n"), fp);
- for (id = 0; id < (unsigned int) TIMEVAR_LAST; ++id)
- {
- struct timevar_def *tv = &timevars[(timevar_id_t) id];
- const float tiny = 5e-3;
-
- /* Don't print the total execution time here; that goes at the
- end. */
- if ((timevar_id_t) id == TV_TOTAL)
- continue;
-
- /* Don't print timing variables that were never used. */
- if (!tv->used)
- continue;
-
- /* Don't print timing variables if we're going to get a row of
- zeroes. */
- if (tv->elapsed.user < tiny
- && tv->elapsed.sys < tiny
- && tv->elapsed.wall < tiny)
- continue;
-
- /* The timing variable name. */
- fprintf (fp, " %-22s:", tv->name);
-
-#ifdef HAVE_USER_TIME
- /* Print user-mode time for this process. */
- fprintf (fp, "%7.2f (%2.0f%%) usr",
- tv->elapsed.user,
- (total->user == 0 ? 0 : tv->elapsed.user / total->user) * 100);
-#endif /* HAVE_USER_TIME */
-
-#ifdef HAVE_SYS_TIME
- /* Print system-mode time for this process. */
- fprintf (fp, "%7.2f (%2.0f%%) sys",
- tv->elapsed.sys,
- (total->sys == 0 ? 0 : tv->elapsed.sys / total->sys) * 100);
-#endif /* HAVE_SYS_TIME */
-
-#ifdef HAVE_WALL_TIME
- /* Print wall clock time elapsed. */
- fprintf (fp, "%7.2f (%2.0f%%) wall",
- tv->elapsed.wall,
- (total->wall == 0 ? 0 : tv->elapsed.wall / total->wall) * 100);
-#endif /* HAVE_WALL_TIME */
-
- putc ('\n', fp);
- }
-
- /* Print total time. */
- fputs (_(" TOTAL :"), fp);
-#ifdef HAVE_USER_TIME
- fprintf (fp, "%7.2f ", total->user);
-#endif
-#ifdef HAVE_SYS_TIME
- fprintf (fp, "%7.2f ", total->sys);
-#endif
-#ifdef HAVE_WALL_TIME
- fprintf (fp, "%7.2f\n", total->wall);
-#endif
-
-#endif /* defined (HAVE_USER_TIME) || defined (HAVE_SYS_TIME)
- || defined (HAVE_WALL_TIME) */
-}
-
-/* Returns time (user + system) used so far by the compiler process,
- in microseconds. */
-
-long
-get_run_time ()
-{
- struct timevar_time_def total_elapsed;
- timevar_get (TV_TOTAL, &total_elapsed);
- return total_elapsed.user + total_elapsed.sys;
-}
-
-/* Prints a message to stderr stating that time elapsed in STR is
- TOTAL (given in microseconds). */
-
-void
-print_time (str, total)
- const char *str;
- long total;
-{
- long all_time = get_run_time ();
- fprintf (stderr,
- _("time in %s: %ld.%06ld (%ld%%)\n"),
- str, total / 1000000, total % 1000000,
- all_time == 0 ? 0
- : (long) (((100.0 * (double) total) / (double) all_time) + .5));
-}
diff --git a/contrib/tools/m4/lib/timevar.def b/contrib/tools/m4/lib/timevar.def
deleted file mode 100644
index 484fe35f7b8..00000000000
--- a/contrib/tools/m4/lib/timevar.def
+++ /dev/null
@@ -1,61 +0,0 @@
-/* This file contains the definitions for timing variables used to -*- C -*-
- measure run-time performance of the compiler.
-
- Copyright (C) 2002, 2007, 2009-2013 Free Software Foundation, Inc.
-
- Contributed by Akim Demaille <[email protected]>.
-
- This file is part of Bison, the GNU Compiler Compiler.
-
- 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 <http://www.gnu.org/licenses/>. */
-
-/* This file contains timing variable definitions, used by timevar.h
- and timevar.c.
-
- Syntax:
-
- DEFTIMEVAR (id, name)
-
- where ID is the enumeral value used to identify the timing
- variable, and NAME is a character string describing its purpose. */
-
-/* The total execution time. */
-DEFTIMEVAR (TV_TOTAL , "total time")
-
-/* Time spent in the reader. */
-DEFTIMEVAR (TV_READER , "reader")
-DEFTIMEVAR (TV_SCANNING , "scanner")
-DEFTIMEVAR (TV_PARSING , "parser")
-
-/* Time spent handling the grammar. */
-DEFTIMEVAR (TV_REDUCE , "reducing the grammar")
-DEFTIMEVAR (TV_SETS , "computing the sets")
-DEFTIMEVAR (TV_LR0 , "LR(0)")
-DEFTIMEVAR (TV_LALR , "LALR(1)")
-DEFTIMEVAR (TV_IELR_PHASE1 , "IELR(1) Phase 1")
-DEFTIMEVAR (TV_IELR_PHASE2 , "IELR(1) Phase 2")
-DEFTIMEVAR (TV_IELR_PHASE3 , "IELR(1) Phase 3")
-DEFTIMEVAR (TV_IELR_PHASE4 , "IELR(1) Phase 4")
-DEFTIMEVAR (TV_CONFLICTS , "conflicts")
-
-/* Time spent outputing results. */
-DEFTIMEVAR (TV_REPORT , "outputing report")
-DEFTIMEVAR (TV_GRAPH , "outputing graph")
-DEFTIMEVAR (TV_XML , "outputing xml")
-DEFTIMEVAR (TV_ACTIONS , "parser action tables")
-DEFTIMEVAR (TV_PARSER , "outputing parser")
-DEFTIMEVAR (TV_M4 , "running m4")
-
-/* Time spent by freeing the memory :). */
-DEFTIMEVAR (TV_FREE , "freeing")
diff --git a/contrib/tools/m4/lib/timevar.h b/contrib/tools/m4/lib/timevar.h
deleted file mode 100644
index d397bd7ff07..00000000000
--- a/contrib/tools/m4/lib/timevar.h
+++ /dev/null
@@ -1,92 +0,0 @@
-/* Timing variables for measuring compiler performance.
-
- Copyright (C) 2000, 2002, 2004, 2009-2013 Free Software Foundation,
- Inc.
-
- Contributed by Alex Samuel <[email protected]>
-
- 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 <http://www.gnu.org/licenses/>. */
-
-#ifndef GCC_TIMEVAR_H
-#define GCC_TIMEVAR_H
-
-/* Timing variables are used to measure elapsed time in various
- portions of the compiler. Each measures elapsed user, system, and
- wall-clock time, as appropriate to and supported by the host
- system.
-
- Timing variables are defined using the DEFTIMEVAR macro in
- timevar.def. Each has an enumeral identifier, used when referring
- to the timing variable in code, and a character string name.
-
- Timing variables can be used in two ways:
-
- - On the timing stack, using timevar_push and timevar_pop.
- Timing variables may be pushed onto the stack; elapsed time is
- attributed to the topmost timing variable on the stack. When
- another variable is pushed on, the previous topmost variable is
- 'paused' until the pushed variable is popped back off.
-
- - As a standalone timer, using timevar_start and timevar_stop.
- All time elapsed between the two calls is attributed to the
- variable.
-*/
-
-/* This structure stores the various varieties of time that can be
- measured. Times are stored in seconds. The time may be an
- absolute time or a time difference; in the former case, the time
- base is undefined, except that the difference between two times
- produces a valid time difference. */
-
-struct timevar_time_def
-{
- /* User time in this process. */
- float user;
-
- /* System time (if applicable for this host platform) in this
- process. */
- float sys;
-
- /* Wall clock time. */
- float wall;
-};
-
-/* An enumeration of timing variable identifiers. Constructed from
- the contents of timevar.def. */
-
-#define DEFTIMEVAR(identifier__, name__) \
- identifier__,
-typedef enum
-{
-#include "timevar.def"
- TIMEVAR_LAST
-}
-timevar_id_t;
-#undef DEFTIMEVAR
-
-extern void init_timevar (void);
-extern void timevar_push (timevar_id_t);
-extern void timevar_pop (timevar_id_t);
-extern void timevar_start (timevar_id_t);
-extern void timevar_stop (timevar_id_t);
-extern void timevar_get (timevar_id_t, struct timevar_time_def *);
-extern void timevar_print (FILE *);
-
-/* Provided for backward compatibility. */
-extern long get_run_time (void);
-extern void print_time (const char *, long);
-
-extern int timevar_report;
-
-#endif /* ! GCC_TIMEVAR_H */
diff --git a/contrib/tools/m4/lib/vbitset.c b/contrib/tools/m4/lib/vbitset.c
deleted file mode 100644
index e7200cdaa5d..00000000000
--- a/contrib/tools/m4/lib/vbitset.c
+++ /dev/null
@@ -1,1140 +0,0 @@
-/* Variable array bitsets.
-
- Copyright (C) 2002-2006, 2009-2013 Free Software Foundation, Inc.
-
- Contributed by Michael Hayes ([email protected]).
-
- 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 <http://www.gnu.org/licenses/>. */
-
-#include <config.h>
-
-#include "vbitset.h"
-
-#include <stdlib.h>
-#include <string.h>
-
-/* This file implements variable size bitsets stored as a variable
- length array of words. Any unused bits in the last word must be
- zero.
-
- Note that binary or ternary operations assume that each bitset operand
- has the same size.
-*/
-
-static void vbitset_unused_clear (bitset);
-
-static void vbitset_set (bitset, bitset_bindex);
-static void vbitset_reset (bitset, bitset_bindex);
-static bool vbitset_test (bitset, bitset_bindex);
-static bitset_bindex vbitset_list (bitset, bitset_bindex *,
- bitset_bindex, bitset_bindex *);
-static bitset_bindex vbitset_list_reverse (bitset, bitset_bindex *,
- bitset_bindex, bitset_bindex *);
-
-#define VBITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS)
-#define VBITSET_WORDS(X) ((X)->b.cdata)
-#define VBITSET_SIZE(X) ((X)->b.csize)
-#define VBITSET_ASIZE(X) ((X)->v.size)
-
-#undef min
-#undef max
-#define min(a, b) ((a) > (b) ? (b) : (a))
-#define max(a, b) ((a) > (b) ? (a) : (b))
-
-static bitset_bindex
-vbitset_resize (bitset src, bitset_bindex n_bits)
-{
- bitset_windex oldsize;
- bitset_windex newsize;
-
- if (n_bits == BITSET_NBITS_ (src))
- return n_bits;
-
- oldsize = VBITSET_SIZE (src);
- newsize = VBITSET_N_WORDS (n_bits);
-
- if (oldsize < newsize)
- {
- bitset_windex size;
-
- /* The bitset needs to grow. If we already have enough memory
- allocated, then just zero what we need. */
- if (newsize > VBITSET_ASIZE (src))
- {
- /* We need to allocate more memory. When oldsize is
- non-zero this means that we are changing the size, so
- grow the bitset 25% larger than requested to reduce
- number of reallocations. */
-
- if (oldsize == 0)
- size = newsize;
- else
- size = newsize + newsize / 4;
-
- VBITSET_WORDS (src)
- = realloc (VBITSET_WORDS (src), size * sizeof (bitset_word));
- VBITSET_ASIZE (src) = size;
- }
-
- memset (VBITSET_WORDS (src) + oldsize, 0,
- (newsize - oldsize) * sizeof (bitset_word));
- VBITSET_SIZE (src) = newsize;
- }
- else
- {
- /* The bitset needs to shrink. There's no point deallocating
- the memory unless it is shrinking by a reasonable amount. */
- if ((oldsize - newsize) >= oldsize / 2)
- {
- VBITSET_WORDS (src)
- = realloc (VBITSET_WORDS (src), newsize * sizeof (bitset_word));
- VBITSET_ASIZE (src) = newsize;
- }
-
- /* Need to prune any excess bits. FIXME. */
-
- VBITSET_SIZE (src) = newsize;
- }
-
- BITSET_NBITS_ (src) = n_bits;
- return n_bits;
-}
-
-
-/* Set bit BITNO in bitset DST. */
-static void
-vbitset_set (dst, bitno)
- bitset dst;
- bitset_bindex bitno;
-{
- bitset_windex windex = bitno / BITSET_WORD_BITS;
-
- /* Perhaps we should abort. The user should explicitly call
- bitset_resize since this will not catch the case when we set a
- bit larger than the current size but smaller than the allocated
- size. */
- vbitset_resize (dst, bitno);
-
- dst->b.cdata[windex - dst->b.cindex] |=
- (bitset_word) 1 << (bitno % BITSET_WORD_BITS);
-}
-
-
-/* Reset bit BITNO in bitset DST. */
-static void
-vbitset_reset (dst, bitno)
- bitset dst ATTRIBUTE_UNUSED;
- bitset_bindex bitno ATTRIBUTE_UNUSED;
-{
- /* We must be accessing outside the cache so the bit is
- zero anyway. */
-}
-
-
-/* Test bit BITNO in bitset SRC. */
-static bool
-vbitset_test (src, bitno)
- bitset src ATTRIBUTE_UNUSED;
- bitset_bindex bitno ATTRIBUTE_UNUSED;
-{
- /* We must be accessing outside the cache so the bit is
- zero anyway. */
- return 0;
-}
-
-
-/* Find list of up to NUM bits set in BSET 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
-vbitset_list_reverse (src, list, num, next)
- bitset src;
- bitset_bindex *list;
- bitset_bindex num;
- bitset_bindex *next;
-{
- bitset_bindex bitno;
- bitset_bindex rbitno;
- bitset_bindex count;
- bitset_windex windex;
- unsigned int bitcnt;
- bitset_bindex bitoff;
- bitset_word *srcp = VBITSET_WORDS (src);
- bitset_bindex n_bits = BITSET_SIZE_ (src);
-
- rbitno = *next;
-
- /* If num is 1, we could speed things up with a binary search
- of the word of interest. */
-
- if (rbitno >= n_bits)
- return 0;
-
- count = 0;
-
- bitno = n_bits - (rbitno + 1);
-
- windex = bitno / BITSET_WORD_BITS;
- bitcnt = bitno % BITSET_WORD_BITS;
- bitoff = windex * BITSET_WORD_BITS;
-
- do
- {
- bitset_word word;
-
- word = srcp[windex] << (BITSET_WORD_BITS - 1 - bitcnt);
- for (; word; bitcnt--)
- {
- if (word & BITSET_MSB)
- {
- list[count++] = bitoff + bitcnt;
- if (count >= num)
- {
- *next = n_bits - (bitoff + bitcnt);
- return count;
- }
- }
- word <<= 1;
- }
- 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 BSET 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
-vbitset_list (src, list, num, next)
- bitset src;
- bitset_bindex *list;
- bitset_bindex num;
- bitset_bindex *next;
-{
- bitset_bindex bitno;
- bitset_bindex count;
- bitset_windex windex;
- bitset_bindex bitoff;
- bitset_windex size = VBITSET_SIZE (src);
- bitset_word *srcp = VBITSET_WORDS (src);
- bitset_word word;
-
- bitno = *next;
-
- 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;
-
- /* If num is 1, we could speed things up with a binary search
- of the current word. */
-
- 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;
- word = srcp[windex] >> bitno;
- for (bitno = bitoff + bitno; word; bitno++)
- {
- if (word & 1)
- {
- list[count++] = bitno;
- if (count >= num)
- {
- *next = bitno + 1;
- return count;
- }
- }
- word >>= 1;
- }
- windex++;
- }
- bitoff = windex * BITSET_WORD_BITS;
- }
-
- for (; windex < size; windex++, bitoff += BITSET_WORD_BITS)
- {
- if (!(word = srcp[windex]))
- continue;
-
- if ((count + BITSET_WORD_BITS) < num)
- {
- for (bitno = bitoff; word; bitno++)
- {
- if (word & 1)
- list[count++] = bitno;
- word >>= 1;
- }
- }
- else
- {
- for (bitno = bitoff; word; bitno++)
- {
- if (word & 1)
- {
- list[count++] = bitno;
- if (count >= num)
- {
- *next = bitno + 1;
- return count;
- }
- }
- word >>= 1;
- }
- }
- }
-
- *next = bitoff;
- return count;
-}
-
-
-/* Ensure that any unused bits within the last word are clear. */
-static inline void
-vbitset_unused_clear (dst)
- bitset dst;
-{
- unsigned int last_bit;
-
- last_bit = BITSET_SIZE_ (dst) % BITSET_WORD_BITS;
- if (last_bit)
- VBITSET_WORDS (dst)[VBITSET_SIZE (dst) - 1] &=
- ((bitset_word) 1 << last_bit) - 1;
-}
-
-
-static void
-vbitset_ones (bitset dst)
-{
- bitset_word *dstp = VBITSET_WORDS (dst);
- unsigned int bytes;
-
- bytes = sizeof (bitset_word) * VBITSET_SIZE (dst);
-
- memset (dstp, -1, bytes);
- vbitset_unused_clear (dst);
-}
-
-
-static void
-vbitset_zero (bitset dst)
-{
- bitset_word *dstp = VBITSET_WORDS (dst);
- unsigned int bytes;
-
- bytes = sizeof (bitset_word) * VBITSET_SIZE (dst);
-
- memset (dstp, 0, bytes);
-}
-
-
-static bool
-vbitset_empty_p (bitset dst)
-{
- unsigned int i;
- bitset_word *dstp = VBITSET_WORDS (dst);
-
- for (i = 0; i < VBITSET_SIZE (dst); i++)
- if (dstp[i])
- return 0;
-
- return 1;
-}
-
-
-static void
-vbitset_copy1 (bitset dst, bitset src)
-{
- bitset_word *srcp;
- bitset_word *dstp;
- bitset_windex ssize;
- bitset_windex dsize;
-
- if (src == dst)
- return;
-
- vbitset_resize (dst, BITSET_SIZE_ (src));
-
- srcp = VBITSET_WORDS (src);
- dstp = VBITSET_WORDS (dst);
- ssize = VBITSET_SIZE (src);
- dsize = VBITSET_SIZE (dst);
-
- memcpy (dstp, srcp, sizeof (bitset_word) * ssize);
-
- memset (dstp + sizeof (bitset_word) * ssize, 0,
- sizeof (bitset_word) * (dsize - ssize));
-}
-
-
-static void
-vbitset_not (bitset dst, bitset src)
-{
- unsigned int i;
- bitset_word *srcp;
- bitset_word *dstp;
- bitset_windex ssize;
- bitset_windex dsize;
-
- vbitset_resize (dst, BITSET_SIZE_ (src));
-
- srcp = VBITSET_WORDS (src);
- dstp = VBITSET_WORDS (dst);
- ssize = VBITSET_SIZE (src);
- dsize = VBITSET_SIZE (dst);
-
- for (i = 0; i < ssize; i++)
- *dstp++ = ~(*srcp++);
-
- vbitset_unused_clear (dst);
- memset (dstp + sizeof (bitset_word) * ssize, 0,
- sizeof (bitset_word) * (dsize - ssize));
-}
-
-
-static bool
-vbitset_equal_p (bitset dst, bitset src)
-{
- unsigned int i;
- bitset_word *srcp = VBITSET_WORDS (src);
- bitset_word *dstp = VBITSET_WORDS (dst);
- bitset_windex ssize = VBITSET_SIZE (src);
- bitset_windex dsize = VBITSET_SIZE (dst);
-
- for (i = 0; i < min (ssize, dsize); i++)
- if (*srcp++ != *dstp++)
- return 0;
-
- if (ssize > dsize)
- {
- for (; i < ssize; i++)
- if (*srcp++)
- return 0;
- }
- else
- {
- for (; i < dsize; i++)
- if (*dstp++)
- return 0;
- }
-
- return 1;
-}
-
-
-static bool
-vbitset_subset_p (bitset dst, bitset src)
-{
- unsigned int i;
- bitset_word *srcp = VBITSET_WORDS (src);
- bitset_word *dstp = VBITSET_WORDS (dst);
- bitset_windex ssize = VBITSET_SIZE (src);
- bitset_windex dsize = VBITSET_SIZE (dst);
-
- for (i = 0; i < min (ssize, dsize); i++, dstp++, srcp++)
- if (*dstp != (*srcp | *dstp))
- return 0;
-
- if (ssize > dsize)
- {
- for (; i < ssize; i++)
- if (*srcp++)
- return 0;
- }
-
- return 1;
-}
-
-
-static bool
-vbitset_disjoint_p (bitset dst, bitset src)
-{
- unsigned int i;
- bitset_word *srcp = VBITSET_WORDS (src);
- bitset_word *dstp = VBITSET_WORDS (dst);
- bitset_windex ssize = VBITSET_SIZE (src);
- bitset_windex dsize = VBITSET_SIZE (dst);
-
- for (i = 0; i < min (ssize, dsize); i++)
- if (*srcp++ & *dstp++)
- return 0;
-
- return 1;
-}
-
-
-static void
-vbitset_and (bitset dst, bitset src1, bitset src2)
-{
- unsigned int i;
- bitset_word *src1p;
- bitset_word *src2p;
- bitset_word *dstp;
- bitset_windex ssize1;
- bitset_windex ssize2;
- bitset_windex dsize;
-
- vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
-
- dsize = VBITSET_SIZE (dst);
- ssize1 = VBITSET_SIZE (src1);
- ssize2 = VBITSET_SIZE (src2);
- dstp = VBITSET_WORDS (dst);
- src1p = VBITSET_WORDS (src1);
- src2p = VBITSET_WORDS (src2);
-
- for (i = 0; i < min (ssize1, ssize2); i++)
- *dstp++ = *src1p++ & *src2p++;
-
- memset (dstp, 0, sizeof (bitset_word) * (dsize - min (ssize1, ssize2)));
-}
-
-
-static bool
-vbitset_and_cmp (bitset dst, bitset src1, bitset src2)
-{
- unsigned int i;
- int changed = 0;
- bitset_word *src1p;
- bitset_word *src2p;
- bitset_word *dstp;
- bitset_windex ssize1;
- bitset_windex ssize2;
- bitset_windex dsize;
-
- vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
-
- dsize = VBITSET_SIZE (dst);
- ssize1 = VBITSET_SIZE (src1);
- ssize2 = VBITSET_SIZE (src2);
- dstp = VBITSET_WORDS (dst);
- src1p = VBITSET_WORDS (src1);
- src2p = VBITSET_WORDS (src2);
-
- for (i = 0; i < min (ssize1, ssize2); i++, dstp++)
- {
- bitset_word tmp = *src1p++ & *src2p++;
-
- if (*dstp != tmp)
- {
- changed = 1;
- *dstp = tmp;
- }
- }
-
- if (ssize2 > ssize1)
- {
- src1p = src2p;
- ssize1 = ssize2;
- }
-
- for (; i < ssize1; i++, dstp++)
- {
- if (*dstp != 0)
- {
- changed = 1;
- *dstp = 0;
- }
- }
-
- memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
-
- return changed;
-}
-
-
-static void
-vbitset_andn (bitset dst, bitset src1, bitset src2)
-{
- unsigned int i;
- bitset_word *src1p;
- bitset_word *src2p;
- bitset_word *dstp;
- bitset_windex ssize1;
- bitset_windex ssize2;
- bitset_windex dsize;
-
- vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
-
- dsize = VBITSET_SIZE (dst);
- ssize1 = VBITSET_SIZE (src1);
- ssize2 = VBITSET_SIZE (src2);
- dstp = VBITSET_WORDS (dst);
- src1p = VBITSET_WORDS (src1);
- src2p = VBITSET_WORDS (src2);
-
- for (i = 0; i < min (ssize1, ssize2); i++)
- *dstp++ = *src1p++ & ~(*src2p++);
-
- if (ssize2 > ssize1)
- {
- for (; i < ssize2; i++)
- *dstp++ = 0;
-
- memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize2));
- }
- else
- {
- for (; i < ssize1; i++)
- *dstp++ = *src1p++;
-
- memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
- }
-}
-
-
-static bool
-vbitset_andn_cmp (bitset dst, bitset src1, bitset src2)
-{
- unsigned int i;
- int changed = 0;
- bitset_word *src1p;
- bitset_word *src2p;
- bitset_word *dstp;
- bitset_windex ssize1;
- bitset_windex ssize2;
- bitset_windex dsize;
-
- vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
-
- dsize = VBITSET_SIZE (dst);
- ssize1 = VBITSET_SIZE (src1);
- ssize2 = VBITSET_SIZE (src2);
- dstp = VBITSET_WORDS (dst);
- src1p = VBITSET_WORDS (src1);
- src2p = VBITSET_WORDS (src2);
-
- for (i = 0; i < min (ssize1, ssize2); i++, dstp++)
- {
- bitset_word tmp = *src1p++ & ~(*src2p++);
-
- if (*dstp != tmp)
- {
- changed = 1;
- *dstp = tmp;
- }
- }
-
- if (ssize2 > ssize1)
- {
- for (; i < ssize2; i++, dstp++)
- {
- if (*dstp != 0)
- {
- changed = 1;
- *dstp = 0;
- }
- }
-
- memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize2));
- }
- else
- {
- for (; i < ssize1; i++, dstp++)
- {
- bitset_word tmp = *src1p++;
-
- if (*dstp != tmp)
- {
- changed = 1;
- *dstp = tmp;
- }
- }
-
- memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
- }
-
- return changed;
-}
-
-
-static void
-vbitset_or (bitset dst, bitset src1, bitset src2)
-{
- unsigned int i;
- bitset_word *src1p;
- bitset_word *src2p;
- bitset_word *dstp;
- bitset_windex ssize1;
- bitset_windex ssize2;
- bitset_windex dsize;
-
- vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
-
- dsize = VBITSET_SIZE (dst);
- ssize1 = VBITSET_SIZE (src1);
- ssize2 = VBITSET_SIZE (src2);
- dstp = VBITSET_WORDS (dst);
- src1p = VBITSET_WORDS (src1);
- src2p = VBITSET_WORDS (src2);
-
- for (i = 0; i < min (ssize1, ssize2); i++)
- *dstp++ = *src1p++ | *src2p++;
-
- if (ssize2 > ssize1)
- {
- src1p = src2p;
- ssize1 = ssize2;
- }
-
- for (; i < ssize1; i++)
- *dstp++ = *src1p++;
-
- memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
-}
-
-
-static bool
-vbitset_or_cmp (bitset dst, bitset src1, bitset src2)
-{
- unsigned int i;
- int changed = 0;
- bitset_word *src1p;
- bitset_word *src2p;
- bitset_word *dstp;
- bitset_windex ssize1;
- bitset_windex ssize2;
- bitset_windex dsize;
-
- vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
-
- dsize = VBITSET_SIZE (dst);
- ssize1 = VBITSET_SIZE (src1);
- ssize2 = VBITSET_SIZE (src2);
- dstp = VBITSET_WORDS (dst);
- src1p = VBITSET_WORDS (src1);
- src2p = VBITSET_WORDS (src2);
-
- for (i = 0; i < min (ssize1, ssize2); i++, dstp++)
- {
- bitset_word tmp = *src1p++ | *src2p++;
-
- if (*dstp != tmp)
- {
- changed = 1;
- *dstp = tmp;
- }
- }
-
- if (ssize2 > ssize1)
- {
- src1p = src2p;
- ssize1 = ssize2;
- }
-
- for (; i < ssize1; i++, dstp++)
- {
- bitset_word tmp = *src1p++;
-
- if (*dstp != tmp)
- {
- changed = 1;
- *dstp = tmp;
- }
- }
-
- memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
-
- return changed;
-}
-
-
-static void
-vbitset_xor (bitset dst, bitset src1, bitset src2)
-{
- unsigned int i;
- bitset_word *src1p;
- bitset_word *src2p;
- bitset_word *dstp;
- bitset_windex ssize1;
- bitset_windex ssize2;
- bitset_windex dsize;
-
- vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
-
- dsize = VBITSET_SIZE (dst);
- ssize1 = VBITSET_SIZE (src1);
- ssize2 = VBITSET_SIZE (src2);
- dstp = VBITSET_WORDS (dst);
- src1p = VBITSET_WORDS (src1);
- src2p = VBITSET_WORDS (src2);
-
- for (i = 0; i < min (ssize1, ssize2); i++)
- *dstp++ = *src1p++ ^ *src2p++;
-
- if (ssize2 > ssize1)
- {
- src1p = src2p;
- ssize1 = ssize2;
- }
-
- for (; i < ssize1; i++)
- *dstp++ = *src1p++;
-
- memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
-}
-
-
-static bool
-vbitset_xor_cmp (bitset dst, bitset src1, bitset src2)
-{
- unsigned int i;
- int changed = 0;
- bitset_word *src1p;
- bitset_word *src2p;
- bitset_word *dstp;
- bitset_windex ssize1;
- bitset_windex ssize2;
- bitset_windex dsize;
-
- vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
-
- dsize = VBITSET_SIZE (dst);
- ssize1 = VBITSET_SIZE (src1);
- ssize2 = VBITSET_SIZE (src2);
- dstp = VBITSET_WORDS (dst);
- src1p = VBITSET_WORDS (src1);
- src2p = VBITSET_WORDS (src2);
-
- for (i = 0; i < min (ssize1, ssize2); i++, dstp++)
- {
- bitset_word tmp = *src1p++ ^ *src2p++;
-
- if (*dstp != tmp)
- {
- changed = 1;
- *dstp = tmp;
- }
- }
-
- if (ssize2 > ssize1)
- {
- src1p = src2p;
- ssize1 = ssize2;
- }
-
- for (; i < ssize1; i++, dstp++)
- {
- bitset_word tmp = *src1p++;
-
- if (*dstp != tmp)
- {
- changed = 1;
- *dstp = tmp;
- }
- }
-
- memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
-
- return changed;
-}
-
-
-/* FIXME, these operations need fixing for different size
- bitsets. */
-
-static void
-vbitset_and_or (bitset dst, bitset src1, bitset src2, bitset src3)
-{
- unsigned int i;
- bitset_word *src1p;
- bitset_word *src2p;
- bitset_word *src3p;
- bitset_word *dstp;
- bitset_windex size;
-
- if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
- || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
- {
- bitset_and_or_ (dst, src1, src2, src3);
- return;
- }
-
- vbitset_resize (dst, BITSET_NBITS_ (src1));
-
- src1p = VBITSET_WORDS (src1);
- src2p = VBITSET_WORDS (src2);
- src3p = VBITSET_WORDS (src3);
- dstp = VBITSET_WORDS (dst);
- size = VBITSET_SIZE (dst);
-
- for (i = 0; i < size; i++)
- *dstp++ = (*src1p++ & *src2p++) | *src3p++;
-}
-
-
-static bool
-vbitset_and_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
-{
- unsigned int i;
- int changed = 0;
- bitset_word *src1p;
- bitset_word *src2p;
- bitset_word *src3p;
- bitset_word *dstp;
- bitset_windex size;
-
- if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
- || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
- return bitset_and_or_cmp_ (dst, src1, src2, src3);
-
- vbitset_resize (dst, BITSET_NBITS_ (src1));
-
- src1p = VBITSET_WORDS (src1);
- src2p = VBITSET_WORDS (src2);
- src3p = VBITSET_WORDS (src3);
- dstp = VBITSET_WORDS (dst);
- size = VBITSET_SIZE (dst);
-
- for (i = 0; i < size; i++, dstp++)
- {
- bitset_word tmp = (*src1p++ & *src2p++) | *src3p++;
-
- if (*dstp != tmp)
- {
- changed = 1;
- *dstp = tmp;
- }
- }
- return changed;
-}
-
-
-static void
-vbitset_andn_or (bitset dst, bitset src1, bitset src2, bitset src3)
-{
- unsigned int i;
- bitset_word *src1p;
- bitset_word *src2p;
- bitset_word *src3p;
- bitset_word *dstp;
- bitset_windex size;
-
- if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
- || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
- {
- bitset_andn_or_ (dst, src1, src2, src3);
- return;
- }
-
- vbitset_resize (dst, BITSET_NBITS_ (src1));
-
- src1p = VBITSET_WORDS (src1);
- src2p = VBITSET_WORDS (src2);
- src3p = VBITSET_WORDS (src3);
- dstp = VBITSET_WORDS (dst);
- size = VBITSET_SIZE (dst);
-
- for (i = 0; i < size; i++)
- *dstp++ = (*src1p++ & ~(*src2p++)) | *src3p++;
-}
-
-
-static bool
-vbitset_andn_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
-{
- unsigned int i;
- int changed = 0;
- bitset_word *src1p;
- bitset_word *src2p;
- bitset_word *src3p;
- bitset_word *dstp;
- bitset_windex size;
-
- if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
- || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
- return bitset_andn_or_cmp_ (dst, src1, src2, src3);
-
- vbitset_resize (dst, BITSET_NBITS_ (src1));
-
- src1p = VBITSET_WORDS (src1);
- src2p = VBITSET_WORDS (src2);
- src3p = VBITSET_WORDS (src3);
- dstp = VBITSET_WORDS (dst);
- size = VBITSET_SIZE (dst);
-
- for (i = 0; i < size; i++, dstp++)
- {
- bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++;
-
- if (*dstp != tmp)
- {
- changed = 1;
- *dstp = tmp;
- }
- }
- return changed;
-}
-
-
-static void
-vbitset_or_and (bitset dst, bitset src1, bitset src2, bitset src3)
-{
- unsigned int i;
- bitset_word *src1p;
- bitset_word *src2p;
- bitset_word *src3p;
- bitset_word *dstp;
- bitset_windex size;
-
- if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
- || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
- {
- bitset_or_and_ (dst, src1, src2, src3);
- return;
- }
-
- vbitset_resize (dst, BITSET_NBITS_ (src1));
-
- src1p = VBITSET_WORDS (src1);
- src2p = VBITSET_WORDS (src2);
- src3p = VBITSET_WORDS (src3);
- dstp = VBITSET_WORDS (dst);
- size = VBITSET_SIZE (dst);
-
- for (i = 0; i < size; i++)
- *dstp++ = (*src1p++ | *src2p++) & *src3p++;
-}
-
-
-static bool
-vbitset_or_and_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
-{
- unsigned int i;
- int changed = 0;
- bitset_word *src1p;
- bitset_word *src2p;
- bitset_word *src3p;
- bitset_word *dstp;
- bitset_windex size;
-
- if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
- || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
- return bitset_or_and_cmp_ (dst, src1, src2, src3);
-
- vbitset_resize (dst, BITSET_NBITS_ (src1));
-
- src1p = VBITSET_WORDS (src1);
- src2p = VBITSET_WORDS (src2);
- src3p = VBITSET_WORDS (src3);
- dstp = VBITSET_WORDS (dst);
- size = VBITSET_SIZE (dst);
-
- for (i = 0; i < size; i++, dstp++)
- {
- bitset_word tmp = (*src1p++ | *src2p++) & *src3p++;
-
- if (*dstp != tmp)
- {
- changed = 1;
- *dstp = tmp;
- }
- }
- return changed;
-}
-
-
-static void
-vbitset_copy (bitset dst, bitset src)
-{
- if (BITSET_COMPATIBLE_ (dst, src))
- vbitset_copy1 (dst, src);
- else
- bitset_copy_ (dst, src);
-}
-
-
-/* Vector of operations for multiple word bitsets. */
-struct bitset_vtable vbitset_vtable = {
- vbitset_set,
- vbitset_reset,
- bitset_toggle_,
- vbitset_test,
- vbitset_resize,
- bitset_size_,
- bitset_count_,
- vbitset_empty_p,
- vbitset_ones,
- vbitset_zero,
- vbitset_copy,
- vbitset_disjoint_p,
- vbitset_equal_p,
- vbitset_not,
- vbitset_subset_p,
- vbitset_and,
- vbitset_and_cmp,
- vbitset_andn,
- vbitset_andn_cmp,
- vbitset_or,
- vbitset_or_cmp,
- vbitset_xor,
- vbitset_xor_cmp,
- vbitset_and_or,
- vbitset_and_or_cmp,
- vbitset_andn_or,
- vbitset_andn_or_cmp,
- vbitset_or_and,
- vbitset_or_and_cmp,
- vbitset_list,
- vbitset_list_reverse,
- NULL,
- BITSET_VARRAY
-};
-
-
-size_t
-vbitset_bytes (n_bits)
- bitset_bindex n_bits ATTRIBUTE_UNUSED;
-{
- return sizeof (struct vbitset_struct);
-}
-
-
-bitset
-vbitset_init (bset, n_bits)
- bitset bset;
- bitset_bindex n_bits;
-{
- bset->b.vtable = &vbitset_vtable;
-
- bset->b.cindex = 0;
-
- VBITSET_SIZE (bset) = 0;
- vbitset_resize (bset, n_bits);
- return bset;
-}
diff --git a/contrib/tools/m4/lib/vbitset.h b/contrib/tools/m4/lib/vbitset.h
deleted file mode 100644
index b91019bcb1b..00000000000
--- a/contrib/tools/m4/lib/vbitset.h
+++ /dev/null
@@ -1,29 +0,0 @@
-/* Functions to support vbitsets.
-
- Copyright (C) 2002, 2004, 2009-2013 Free Software Foundation, Inc.
-
- Contributed by Michael Hayes ([email protected]).
-
- 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 <http://www.gnu.org/licenses/>. */
-
-#ifndef _VBITSET_H
-#define _VBITSET_H
-
-#include "bitset.h"
-
-extern size_t vbitset_bytes (bitset_bindex);
-
-extern bitset vbitset_init (bitset, bitset_bindex);
-
-#endif
diff --git a/contrib/tools/m4/lib/ya.make b/contrib/tools/m4/lib/ya.make
index ad85a9e2cf3..21b3b59c560 100644
--- a/contrib/tools/m4/lib/ya.make
+++ b/contrib/tools/m4/lib/ya.make
@@ -46,17 +46,11 @@ IF (NOT OS_WINDOWS)
ENDIF()
SRCS(
- abitset.c
- argmatch.c
asnprintf.c
basename-lgpl.c
basename.c
binary-io.c
bitrotate.c
- bitset.c
- bitset_stats.c
- bitsetv-print.c
- bitsetv.c
c-ctype.c
c-stack.c
c-strcasecmp.c
@@ -74,7 +68,6 @@ SRCS(
dup-safer-flag.c
dup-safer.c
dup2.c
- ebitset.c
error.c
execute.c
exitfail.c
@@ -107,7 +100,6 @@ SRCS(
isnanf.c
isnanl.c
itold.c
- lbitset.c
localcharset.c
lseek.c
lstat.c
@@ -141,16 +133,13 @@ SRCS(
spawn-pipe.c
stat.c
stpcpy.c
- strchrnul.c
strdup.c
stripslash.c
tempname.c
- timevar.c
tmpdir.c
unistd.c
unsetenv.c
vasnprintf.c
- vbitset.c
verror.c
version-etc-fsf.c
version-etc.c
@@ -179,7 +168,6 @@ ENDIF()
IF (NOT OS_LINUX)
SRCS(
pipe2.c
- strverscmp.c
)
ENDIF()
@@ -194,7 +182,6 @@ IF (OS_WINDOWS)
frexp.c
wcrtomb.c
perror.c
- strstr.c
mkstemp.c
vasprintf.c
strsignal.c
@@ -221,7 +208,6 @@ IF (OS_WINDOWS)
spawnattr_setsigmask.c
spawni.c
spawnp.c
- strndup.c
waitpid.c
wcwidth.c
uniwidth/width.c