diff options
| author | thegeorg <[email protected]> | 2024-10-04 11:18:39 +0300 |
|---|---|---|
| committer | thegeorg <[email protected]> | 2024-10-04 11:36:54 +0300 |
| commit | 79b132a5a400c9c8498361c67876aa070640f066 (patch) | |
| tree | c6f17f152f17f5913feb0a319251b371e42b962c | |
| parent | 37112f646e6da1c3eb50de15cbbb8793b383b27e (diff) | |
Remove some of gnulib sources from contrib/tools/m4
commit_hash:48e647f4025141980063113500045d228cbd83ea
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 |
