Intermediate changes

3 files changed, 0 insertions, 2118 deletions

diff --git a/contrib/libs/backtrace/macho.c b/contrib/libs/backtrace/macho.c
deleted file mode 100644
index d00aea9bc8a..00000000000
--- a/contrib/libs/backtrace/macho.c
+++ /dev/null
@@ -1,1355 +0,0 @@
-/* elf.c -- Get debug data from a Mach-O file for backtraces.
-   Copyright (C) 2020-2021 Free Software Foundation, Inc.
-   Written by Ian Lance Taylor, Google.
-
-Redistribution and use in source and binary forms, with or without
-modification, are permitted provided that the following conditions are
-met:
-
-    (1) Redistributions of source code must retain the above copyright
-    notice, this list of conditions and the following disclaimer.
-
-    (2) Redistributions in binary form must reproduce the above copyright
-    notice, this list of conditions and the following disclaimer in
-    the documentation and/or other materials provided with the
-    distribution.
-
-    (3) The name of the author may not be used to
-    endorse or promote products derived from this software without
-    specific prior written permission.
-
-THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
-IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
-WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
-DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
-INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
-(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
-SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
-HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
-STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
-IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
-POSSIBILITY OF SUCH DAMAGE.  */
-
-#include "config.h"
-
-#include <sys/types.h>
-#include <dirent.h>
-#include <stdlib.h>
-#include <string.h>
-
-#ifdef HAVE_MACH_O_DYLD_H
-#include <mach-o/dyld.h>
-#endif
-
-#include "backtrace.h"
-#include "internal.h"
-
-/* Mach-O file header for a 32-bit executable.  */
-
-struct macho_header_32
-{
-  uint32_t magic;	/* Magic number (MACH_O_MAGIC_32) */
-  uint32_t cputype;	/* CPU type */
-  uint32_t cpusubtype;	/* CPU subtype */
-  uint32_t filetype;	/* Type of file (object, executable) */
-  uint32_t ncmds;	/* Number of load commands */
-  uint32_t sizeofcmds;	/* Total size of load commands */
-  uint32_t flags;	/* Flags for special features */
-};
-
-/* Mach-O file header for a 64-bit executable.  */
-
-struct macho_header_64
-{
-  uint32_t magic;	/* Magic number (MACH_O_MAGIC_64) */
-  uint32_t cputype;	/* CPU type */
-  uint32_t cpusubtype;	/* CPU subtype */
-  uint32_t filetype;	/* Type of file (object, executable) */
-  uint32_t ncmds;	/* Number of load commands */
-  uint32_t sizeofcmds;	/* Total size of load commands */
-  uint32_t flags;	/* Flags for special features */
-  uint32_t reserved;	/* Reserved */
-};
-
-/* Mach-O file header for a fat executable.  */
-
-struct macho_header_fat
-{
-  uint32_t magic;	/* Magic number (MACH_O_MH_(MAGIC|CIGAM)_FAT(_64)?) */
-  uint32_t nfat_arch;   /* Number of components */
-};
-
-/* Values for the header magic field.  */
-
-#define MACH_O_MH_MAGIC_32	0xfeedface
-#define MACH_O_MH_MAGIC_64	0xfeedfacf
-#define MACH_O_MH_MAGIC_FAT	0xcafebabe
-#define MACH_O_MH_CIGAM_FAT	0xbebafeca
-#define MACH_O_MH_MAGIC_FAT_64	0xcafebabf
-#define MACH_O_MH_CIGAM_FAT_64	0xbfbafeca
-
-/* Value for the header filetype field.  */
-
-#define MACH_O_MH_EXECUTE	0x02
-#define MACH_O_MH_DYLIB		0x06
-#define MACH_O_MH_DSYM		0x0a
-
-/* A component of a fat file.  A fat file starts with a
-   macho_header_fat followed by nfat_arch instances of this
-   struct.  */
-
-struct macho_fat_arch
-{
-  uint32_t cputype;	/* CPU type */
-  uint32_t cpusubtype;	/* CPU subtype */
-  uint32_t offset;	/* File offset of this entry */
-  uint32_t size;	/* Size of this entry */
-  uint32_t align;	/* Alignment of this entry */
-};
-
-/* A component of a 64-bit fat file.  This is used if the magic field
-   is MAGIC_FAT_64.  This is only used when some file size or file
-   offset is too large to represent in the 32-bit format.  */
-
-struct macho_fat_arch_64
-{
-  uint32_t cputype;	/* CPU type */
-  uint32_t cpusubtype;	/* CPU subtype */
-  uint64_t offset;	/* File offset of this entry */
-  uint64_t size;	/* Size of this entry */
-  uint32_t align;	/* Alignment of this entry */
-  uint32_t reserved;	/* Reserved */
-};
-
-/* Values for the fat_arch cputype field (and the header cputype
-   field).  */
-
-#define MACH_O_CPU_ARCH_ABI64 0x01000000
-
-#define MACH_O_CPU_TYPE_X86 7
-#define MACH_O_CPU_TYPE_ARM 12
-#define MACH_O_CPU_TYPE_PPC 18
-
-#define MACH_O_CPU_TYPE_X86_64 (MACH_O_CPU_TYPE_X86 | MACH_O_CPU_ARCH_ABI64)
-#define MACH_O_CPU_TYPE_ARM64  (MACH_O_CPU_TYPE_ARM | MACH_O_CPU_ARCH_ABI64)
-#define MACH_O_CPU_TYPE_PPC64  (MACH_O_CPU_TYPE_PPC | MACH_O_CPU_ARCH_ABI64)
-
-/* The header of a load command.  */
-
-struct macho_load_command
-{
-  uint32_t cmd;		/* The type of load command */
-  uint32_t cmdsize;	/* Size in bytes of the entire command */
-};
-
-/* Values for the load_command cmd field.  */
-
-#define MACH_O_LC_SEGMENT	0x01
-#define MACH_O_LC_SYMTAB	0x02
-#define MACH_O_LC_SEGMENT_64	0x19
-#define MACH_O_LC_UUID		0x1b
-
-/* The length of a section of segment name.  */
-
-#define MACH_O_NAMELEN (16)
-
-/* LC_SEGMENT load command.  */
-
-struct macho_segment_command
-{
-  uint32_t cmd;			/* The type of load command (LC_SEGMENT) */
-  uint32_t cmdsize;		/* Size in bytes of the entire command */
-  char segname[MACH_O_NAMELEN];	/* Segment name */
-  uint32_t vmaddr;		/* Virtual memory address */
-  uint32_t vmsize;		/* Virtual memory size */
-  uint32_t fileoff;		/* Offset of data to be mapped */
-  uint32_t filesize;		/* Size of data in file */
-  uint32_t maxprot;		/* Maximum permitted virtual protection */
-  uint32_t initprot;		/* Initial virtual memory protection */
-  uint32_t nsects;		/* Number of sections in this segment */
-  uint32_t flags;		/* Flags */
-};
-
-/* LC_SEGMENT_64 load command.  */
-
-struct macho_segment_64_command
-{
-  uint32_t cmd;			/* The type of load command (LC_SEGMENT) */
-  uint32_t cmdsize;		/* Size in bytes of the entire command */
-  char segname[MACH_O_NAMELEN];	/* Segment name */
-  uint64_t vmaddr;		/* Virtual memory address */
-  uint64_t vmsize;		/* Virtual memory size */
-  uint64_t fileoff;		/* Offset of data to be mapped */
-  uint64_t filesize;		/* Size of data in file */
-  uint32_t maxprot;		/* Maximum permitted virtual protection */
-  uint32_t initprot;		/* Initial virtual memory protection */
-  uint32_t nsects;		/* Number of sections in this segment */
-  uint32_t flags;		/* Flags */
-};
-
-/* LC_SYMTAB load command.  */
-
-struct macho_symtab_command
-{
-  uint32_t cmd;		/* The type of load command (LC_SEGMENT) */
-  uint32_t cmdsize;	/* Size in bytes of the entire command */
-  uint32_t symoff;	/* File offset of symbol table */
-  uint32_t nsyms;	/* Number of symbols */
-  uint32_t stroff;	/* File offset of string table */
-  uint32_t strsize;	/* String table size */
-};
-
-/* The length of a Mach-O uuid.  */
-
-#define MACH_O_UUID_LEN (16)
-
-/* LC_UUID load command.  */
-
-struct macho_uuid_command
-{
-  uint32_t cmd;				/* Type of load command (LC_UUID) */
-  uint32_t cmdsize;			/* Size in bytes of command */
-  unsigned char uuid[MACH_O_UUID_LEN];	/* UUID */
-};
-
-/* 32-bit section header within a LC_SEGMENT segment.  */
-
-struct macho_section
-{
-  char sectname[MACH_O_NAMELEN];	/* Section name */
-  char segment[MACH_O_NAMELEN];		/* Segment of this section */
-  uint32_t addr;			/* Address in memory */
-  uint32_t size;			/* Section size */
-  uint32_t offset;			/* File offset */
-  uint32_t align;			/* Log2 of section alignment */
-  uint32_t reloff;			/* File offset of relocations */
-  uint32_t nreloc;			/* Number of relocs for this section */
-  uint32_t flags;			/* Flags */
-  uint32_t reserved1;
-  uint32_t reserved2;
-};
-
-/* 64-bit section header within a LC_SEGMENT_64 segment.   */
-
-struct macho_section_64
-{
-  char sectname[MACH_O_NAMELEN];	/* Section name */
-  char segment[MACH_O_NAMELEN];		/* Segment of this section */
-  uint64_t addr;			/* Address in memory */
-  uint64_t size;			/* Section size */
-  uint32_t offset;			/* File offset */
-  uint32_t align;			/* Log2 of section alignment */
-  uint32_t reloff;			/* File offset of section relocations */
-  uint32_t nreloc;			/* Number of relocs for this section */
-  uint32_t flags;			/* Flags */
-  uint32_t reserved1;
-  uint32_t reserved2;
-  uint32_t reserved3;
-};
-
-/* 32-bit symbol data.  */
-
-struct macho_nlist
-{
-  uint32_t n_strx;	/* Index of name in string table */
-  uint8_t n_type;	/* Type flag */
-  uint8_t n_sect;	/* Section number */
-  uint16_t n_desc;	/* Stabs description field */
-  uint32_t n_value;	/* Value */
-};
-
-/* 64-bit symbol data.  */
-
-struct macho_nlist_64
-{
-  uint32_t n_strx;	/* Index of name in string table */
-  uint8_t n_type;	/* Type flag */
-  uint8_t n_sect;	/* Section number */
-  uint16_t n_desc;	/* Stabs description field */
-  uint64_t n_value;	/* Value */
-};
-
-/* Value found in nlist n_type field.  */
-
-#define MACH_O_N_EXT	0x01	/* Extern symbol */
-#define MACH_O_N_ABS	0x02	/* Absolute symbol */
-#define MACH_O_N_SECT	0x0e	/* Defined in section */
-
-#define MACH_O_N_TYPE	0x0e	/* Mask for type bits */
-#define MACH_O_N_STAB	0xe0	/* Stabs debugging symbol */
-
-/* Information we keep for a Mach-O symbol.  */
-
-struct macho_symbol
-{
-  const char *name;	/* Symbol name */
-  uintptr_t address;	/* Symbol address */
-};
-
-/* Information to pass to macho_syminfo.  */
-
-struct macho_syminfo_data
-{
-  struct macho_syminfo_data *next;	/* Next module */
-  struct macho_symbol *symbols;		/* Symbols sorted by address */
-  size_t count;				/* Number of symbols */
-};
-
-/* Names of sections, indexed by enum dwarf_section in internal.h.  */
-
-static const char * const dwarf_section_names[DEBUG_MAX] =
-{
-  "__debug_info",
-  "__debug_line",
-  "__debug_abbrev",
-  "__debug_ranges",
-  "__debug_str",
-  "", /* DEBUG_ADDR */
-  "__debug_str_offs",
-  "", /* DEBUG_LINE_STR */
-  "__debug_rnglists"
-};
-
-/* Forward declaration.  */
-
-static int macho_add (struct backtrace_state *, const char *, int, off_t,
-		      const unsigned char *, uintptr_t, int,
-		      backtrace_error_callback, void *, fileline *, int *);
-
-/* A dummy callback function used when we can't find any debug info.  */
-
-static int
-macho_nodebug (struct backtrace_state *state ATTRIBUTE_UNUSED,
-	       uintptr_t pc ATTRIBUTE_UNUSED,
-	       backtrace_full_callback callback ATTRIBUTE_UNUSED,
-	       backtrace_error_callback error_callback, void *data)
-{
-  error_callback (data, "no debug info in Mach-O executable", -1);
-  return 0;
-}
-
-/* A dummy callback function used when we can't find a symbol
-   table.  */
-
-static void
-macho_nosyms (struct backtrace_state *state ATTRIBUTE_UNUSED,
-	      uintptr_t addr ATTRIBUTE_UNUSED,
-	      backtrace_syminfo_callback callback ATTRIBUTE_UNUSED,
-	      backtrace_error_callback error_callback, void *data)
-{
-  error_callback (data, "no symbol table in Mach-O executable", -1);
-}
-
-/* Add a single DWARF section to DWARF_SECTIONS, if we need the
-   section.  Returns 1 on success, 0 on failure.  */
-
-static int
-macho_add_dwarf_section (struct backtrace_state *state, int descriptor,
-			 const char *sectname, uint32_t offset, uint64_t size,
-			 backtrace_error_callback error_callback, void *data,
-			 struct dwarf_sections *dwarf_sections)
-{
-  int i;
-
-  for (i = 0; i < (int) DEBUG_MAX; ++i)
-    {
-      if (dwarf_section_names[i][0] != '\0'
-	  && strncmp (sectname, dwarf_section_names[i], MACH_O_NAMELEN) == 0)
-	{
-	  struct backtrace_view section_view;
-
-	  /* FIXME: Perhaps it would be better to try to use a single
-	     view to read all the DWARF data, as we try to do for
-	     ELF.  */
-
-	  if (!backtrace_get_view (state, descriptor, offset, size,
-				   error_callback, data, &section_view))
-	    return 0;
-	  dwarf_sections->data[i] = (const unsigned char *) section_view.data;
-	  dwarf_sections->size[i] = size;
-	  break;
-	}
-    }
-  return 1;
-}
-
-/* Collect DWARF sections from a DWARF segment.  Returns 1 on success,
-   0 on failure.  */
-
-static int
-macho_add_dwarf_segment (struct backtrace_state *state, int descriptor,
-			 off_t offset, unsigned int cmd, const char *psecs,
-			 size_t sizesecs, unsigned int nsects,
-			 backtrace_error_callback error_callback, void *data,
-			 struct dwarf_sections *dwarf_sections)
-{
-  size_t sec_header_size;
-  size_t secoffset;
-  unsigned int i;
-
-  switch (cmd)
-    {
-    case MACH_O_LC_SEGMENT:
-      sec_header_size = sizeof (struct macho_section);
-      break;
-    case MACH_O_LC_SEGMENT_64:
-      sec_header_size = sizeof (struct macho_section_64);
-      break;
-    default:
-      abort ();
-    }
-
-  secoffset = 0;
-  for (i = 0; i < nsects; ++i)
-    {
-      if (secoffset + sec_header_size > sizesecs)
-	{
-	  error_callback (data, "section overflow withing segment", 0);
-	  return 0;
-	}
-
-      switch (cmd)
-	{
-	case MACH_O_LC_SEGMENT:
-	  {
-	    struct macho_section section;
-
-	    memcpy (&section, psecs + secoffset, sizeof section);
-	    macho_add_dwarf_section (state, descriptor, section.sectname,
-				     offset + section.offset, section.size,
-				     error_callback, data, dwarf_sections);
-	  }
-	  break;
-
-	case MACH_O_LC_SEGMENT_64:
-	  {
-	    struct macho_section_64 section;
-
-	    memcpy (&section, psecs + secoffset, sizeof section);
-	    macho_add_dwarf_section (state, descriptor, section.sectname,
-				     offset + section.offset, section.size,
-				     error_callback, data, dwarf_sections);
-	  }
-	  break;
-
-	default:
-	  abort ();
-	}
-
-      secoffset += sec_header_size;
-    }
-
-  return 1;
-}
-
-/* Compare struct macho_symbol for qsort.  */
-
-static int
-macho_symbol_compare (const void *v1, const void *v2)
-{
-  const struct macho_symbol *m1 = (const struct macho_symbol *) v1;
-  const struct macho_symbol *m2 = (const struct macho_symbol *) v2;
-
-  if (m1->address < m2->address)
-    return -1;
-  else if (m1->address > m2->address)
-    return 1;
-  else
-    return 0;
-}
-
-/* Compare an address against a macho_symbol for bsearch.  We allocate
-   one extra entry in the array so that this can safely look at the
-   next entry.  */
-
-static int
-macho_symbol_search (const void *vkey, const void *ventry)
-{
-  const uintptr_t *key = (const uintptr_t *) vkey;
-  const struct macho_symbol *entry = (const struct macho_symbol *) ventry;
-  uintptr_t addr;
-
-  addr = *key;
-  if (addr < entry->address)
-    return -1;
-  else if (entry->name[0] == '\0'
-	   && entry->address == ~(uintptr_t) 0)
-    return -1;
-  else if ((entry + 1)->name[0] == '\0'
-	   && (entry + 1)->address == ~(uintptr_t) 0)
-    return -1;
-  else if (addr >= (entry + 1)->address)
-    return 1;
-  else
-    return 0;
-}
-
-/* Return whether the symbol type field indicates a symbol table entry
-   that we care about: a function or data symbol.  */
-
-static int
-macho_defined_symbol (uint8_t type)
-{
-  if ((type & MACH_O_N_STAB) != 0)
-    return 0;
-  if ((type & MACH_O_N_EXT) != 0)
-    return 0;
-  switch (type & MACH_O_N_TYPE)
-    {
-    case MACH_O_N_ABS:
-      return 1;
-    case MACH_O_N_SECT:
-      return 1;
-    default:
-      return 0;
-    }
-}
-
-/* Add symbol table information for a Mach-O file.  */
-
-static int
-macho_add_symtab (struct backtrace_state *state, int descriptor,
-		  uintptr_t base_address, int is_64,
-		  off_t symoff, unsigned int nsyms, off_t stroff,
-		  unsigned int strsize,
-		  backtrace_error_callback error_callback, void *data)
-{
-  size_t symsize;
-  struct backtrace_view sym_view;
-  int sym_view_valid;
-  struct backtrace_view str_view;
-  int str_view_valid;
-  size_t ndefs;
-  size_t symtaboff;
-  unsigned int i;
-  size_t macho_symbol_size;
-  struct macho_symbol *macho_symbols;
-  unsigned int j;
-  struct macho_syminfo_data *sdata;
-
-  sym_view_valid = 0;
-  str_view_valid = 0;
-  macho_symbol_size = 0;
-  macho_symbols = NULL;
-
-  if (is_64)
-    symsize = sizeof (struct macho_nlist_64);
-  else
-    symsize = sizeof (struct macho_nlist);
-
-  if (!backtrace_get_view (state, descriptor, symoff, nsyms * symsize,
-			   error_callback, data, &sym_view))
-    goto fail;
-  sym_view_valid = 1;
-
-  if (!backtrace_get_view (state, descriptor, stroff, strsize,
-			   error_callback, data, &str_view))
-    return 0;
-  str_view_valid = 1;
-
-  ndefs = 0;
-  symtaboff = 0;
-  for (i = 0; i < nsyms; ++i, symtaboff += symsize)
-    {
-      if (is_64)
-	{
-	  struct macho_nlist_64 nlist;
-
-	  memcpy (&nlist, (const char *) sym_view.data + symtaboff,
-		  sizeof nlist);
-	  if (macho_defined_symbol (nlist.n_type))
-	    ++ndefs;
-	}
-      else
-	{
-	  struct macho_nlist nlist;
-
-	  memcpy (&nlist, (const char *) sym_view.data + symtaboff,
-		  sizeof nlist);
-	  if (macho_defined_symbol (nlist.n_type))
-	    ++ndefs;
-	}
-    }
-
-  /* Add 1 to ndefs to make room for a sentinel.  */
-  macho_symbol_size = (ndefs + 1) * sizeof (struct macho_symbol);
-  macho_symbols = ((struct macho_symbol *)
-		   backtrace_alloc (state, macho_symbol_size, error_callback,
-				    data));
-  if (macho_symbols == NULL)
-    goto fail;
-
-  j = 0;
-  symtaboff = 0;
-  for (i = 0; i < nsyms; ++i, symtaboff += symsize)
-    {
-      uint32_t strx;
-      uint64_t value;
-      const char *name;
-
-      strx = 0;
-      value = 0;
-      if (is_64)
-	{
-	  struct macho_nlist_64 nlist;
-
-	  memcpy (&nlist, (const char *) sym_view.data + symtaboff,
-		  sizeof nlist);
-	  if (!macho_defined_symbol (nlist.n_type))
-	    continue;
-
-	  strx = nlist.n_strx;
-	  value = nlist.n_value;
-	}
-      else
-	{
-	  struct macho_nlist nlist;
-
-	  memcpy (&nlist, (const char *) sym_view.data + symtaboff,
-		  sizeof nlist);
-	  if (!macho_defined_symbol (nlist.n_type))
-	    continue;
-
-	  strx = nlist.n_strx;
-	  value = nlist.n_value;
-	}
-
-      if (strx >= strsize)
-	{
-	  error_callback (data, "symbol string index out of range", 0);
-	  goto fail;
-	}
-
-      name = (const char *) str_view.data + strx;
-      if (name[0] == '_')
-	++name;
-      macho_symbols[j].name = name;
-      macho_symbols[j].address = value + base_address;
-      ++j;
-    }
-
-  sdata = ((struct macho_syminfo_data *)
-	   backtrace_alloc (state, sizeof *sdata, error_callback, data));
-  if (sdata == NULL)
-    goto fail;
-
-  /* We need to keep the string table since it holds the names, but we
-     can release the symbol table.  */
-
-  backtrace_release_view (state, &sym_view, error_callback, data);
-  sym_view_valid = 0;
-  str_view_valid = 0;
-
-  /* Add a trailing sentinel symbol.  */
-  macho_symbols[j].name = "";
-  macho_symbols[j].address = ~(uintptr_t) 0;
-
-  backtrace_qsort (macho_symbols, ndefs + 1, sizeof (struct macho_symbol),
-		   macho_symbol_compare);
-
-  sdata->next = NULL;
-  sdata->symbols = macho_symbols;
-  sdata->count = ndefs;
-
-  if (!state->threaded)
-    {
-      struct macho_syminfo_data **pp;
-
-      for (pp = (struct macho_syminfo_data **) (void *) &state->syminfo_data;
-	   *pp != NULL;
-	   pp = &(*pp)->next)
-	;
-      *pp = sdata;
-    }
-  else
-    {
-      while (1)
-	{
-	  struct macho_syminfo_data **pp;
-
-	  pp = (struct macho_syminfo_data **) (void *) &state->syminfo_data;
-
-	  while (1)
-	    {
-	      struct macho_syminfo_data *p;
-
-	      p = backtrace_atomic_load_pointer (pp);
-	      
-	      if (p == NULL)
-		break;
-
-	      pp = &p->next;
-	    }
-
-	  if (__sync_bool_compare_and_swap (pp, NULL, sdata))
-	    break;
-	}
-    }
-
-  return 1;
-
- fail:
-  if (macho_symbols != NULL)
-    backtrace_free (state, macho_symbols, macho_symbol_size,
-		    error_callback, data);
-  if (sym_view_valid)
-    backtrace_release_view (state, &sym_view, error_callback, data);
-  if (str_view_valid)
-    backtrace_release_view (state, &str_view, error_callback, data);
-  return 0;
-}
-
-/* Return the symbol name and value for an ADDR.  */
-
-static void
-macho_syminfo (struct backtrace_state *state, uintptr_t addr,
-	       backtrace_syminfo_callback callback,
-	       backtrace_error_callback error_callback ATTRIBUTE_UNUSED,
-	       void *data)
-{
-  struct macho_syminfo_data *sdata;
-  struct macho_symbol *sym;
-
-  sym = NULL;
-  if (!state->threaded)
-    {
-      for (sdata = (struct macho_syminfo_data *) state->syminfo_data;
-	   sdata != NULL;
-	   sdata = sdata->next)
-	{
-	  sym = ((struct macho_symbol *)
-		 bsearch (&addr, sdata->symbols, sdata->count,
-			  sizeof (struct macho_symbol), macho_symbol_search));
-	  if (sym != NULL)
-	    break;
-	}
-    }
-  else
-    {
-      struct macho_syminfo_data **pp;
-
-      pp = (struct macho_syminfo_data **) (void *) &state->syminfo_data;
-      while (1)
-	{
-	  sdata = backtrace_atomic_load_pointer (pp);
-	  if (sdata == NULL)
-	    break;
-
-	  sym = ((struct macho_symbol *)
-		 bsearch (&addr, sdata->symbols, sdata->count,
-			  sizeof (struct macho_symbol), macho_symbol_search));
-	  if (sym != NULL)
-	    break;
-
-	  pp = &sdata->next;
-	}
-    }
-
-  if (sym == NULL)
-    callback (data, addr, NULL, 0, 0);
-  else
-    callback (data, addr, sym->name, sym->address, 0);
-}
-
-/* Look through a fat file to find the relevant executable.  Returns 1
-   on success, 0 on failure (in both cases descriptor is closed).  */
-
-static int
-macho_add_fat (struct backtrace_state *state, const char *filename,
-	       int descriptor, int swapped, off_t offset,
-	       const unsigned char *match_uuid, uintptr_t base_address,
-	       int skip_symtab, uint32_t nfat_arch, int is_64,
-	       backtrace_error_callback error_callback, void *data,
-	       fileline *fileline_fn, int *found_sym)
-{
-  int arch_view_valid;
-  unsigned int cputype;
-  size_t arch_size;
-  struct backtrace_view arch_view;
-  unsigned int i;
-
-  arch_view_valid = 0;
-
-#if defined (__x86_64__)
-  cputype = MACH_O_CPU_TYPE_X86_64;
-#elif defined (__i386__)
-  cputype = MACH_O_CPU_TYPE_X86;
-#elif defined (__aarch64__)
-  cputype = MACH_O_CPU_TYPE_ARM64;
-#elif defined (__arm__)
-  cputype = MACH_O_CPU_TYPE_ARM;
-#elif defined (__ppc__)
-  cputype = MACH_O_CPU_TYPE_PPC;
-#elif defined (__ppc64__)
-  cputype = MACH_O_CPU_TYPE_PPC64;
-#else
-  error_callback (data, "unknown Mach-O architecture", 0);
-  goto fail;
-#endif
-
-  if (is_64)
-    arch_size = sizeof (struct macho_fat_arch_64);
-  else
-    arch_size = sizeof (struct macho_fat_arch);
-
-  if (!backtrace_get_view (state, descriptor, offset,
-			   nfat_arch * arch_size,
-			   error_callback, data, &arch_view))
-    goto fail;
-
-  for (i = 0; i < nfat_arch; ++i)
-    {
-      uint32_t fcputype;
-      uint64_t foffset;
-
-      if (is_64)
-	{
-	  struct macho_fat_arch_64 fat_arch_64;
-
-	  memcpy (&fat_arch_64,
-		  (const char *) arch_view.data + i * arch_size,
-		  arch_size);
-	  fcputype = fat_arch_64.cputype;
-	  foffset = fat_arch_64.offset;
-	  if (swapped)
-	    {
-	      fcputype = __builtin_bswap32 (fcputype);
-	      foffset = __builtin_bswap64 (foffset);
-	    }
-	}
-      else
-	{
-	  struct macho_fat_arch fat_arch_32;
-
-	  memcpy (&fat_arch_32,
-		  (const char *) arch_view.data + i * arch_size,
-		  arch_size);
-	  fcputype = fat_arch_32.cputype;
-	  foffset = (uint64_t) fat_arch_32.offset;
-	  if (swapped)
-	    {
-	      fcputype = __builtin_bswap32 (fcputype);
-	      foffset = (uint64_t) __builtin_bswap32 ((uint32_t) foffset);
-	    }
-	}
-
-      if (fcputype == cputype)
-	{
-	  /* FIXME: What about cpusubtype?  */
-	  backtrace_release_view (state, &arch_view, error_callback, data);
-	  return macho_add (state, filename, descriptor, foffset, match_uuid,
-			    base_address, skip_symtab, error_callback, data,
-			    fileline_fn, found_sym);
-	}
-    }
-
-  error_callback (data, "could not find executable in fat file", 0);
-
- fail:
-  if (arch_view_valid)
-    backtrace_release_view (state, &arch_view, error_callback, data);
-  if (descriptor != -1)
-    backtrace_close (descriptor, error_callback, data);
-  return 0;
-}
-
-/* Look for the dsym file for FILENAME.  This is called if FILENAME
-   does not have debug info or a symbol table.  Returns 1 on success,
-   0 on failure.  */
-
-static int
-macho_add_dsym (struct backtrace_state *state, const char *filename,
-		uintptr_t base_address, const unsigned char *uuid,
-		backtrace_error_callback error_callback, void *data,
-		fileline* fileline_fn)
-{
-  const char *p;
-  const char *dirname;
-  char *diralc;
-  size_t dirnamelen;
-  const char *basename;
-  size_t basenamelen;
-  const char *dsymsuffixdir;
-  size_t dsymsuffixdirlen;
-  size_t dsymlen;
-  char *dsym;
-  char *ps;
-  int d;
-  int does_not_exist;
-  int dummy_found_sym;
-
-  diralc = NULL;
-  dirnamelen = 0;
-  dsym = NULL;
-  dsymlen = 0;
-
-  p = strrchr (filename, '/');
-  if (p == NULL)
-    {
-      dirname = ".";
-      dirnamelen = 1;
-      basename = filename;
-      basenamelen = strlen (basename);
-      diralc = NULL;
-    }
-  else
-    {
-      dirnamelen = p - filename;
-      diralc = backtrace_alloc (state, dirnamelen + 1, error_callback, data);
-      if (diralc == NULL)
-	goto fail;
-      memcpy (diralc, filename, dirnamelen);
-      diralc[dirnamelen] = '\0';
-      dirname = diralc;
-      basename = p + 1;
-      basenamelen = strlen (basename);
-    }
-
-  dsymsuffixdir = ".dSYM/Contents/Resources/DWARF/";
-  dsymsuffixdirlen = strlen (dsymsuffixdir);
-
-  dsymlen = (dirnamelen
-	     + 1
-	     + basenamelen
-	     + dsymsuffixdirlen
-	     + basenamelen
-	     + 1);
-  dsym = backtrace_alloc (state, dsymlen, error_callback, data);
-  if (dsym == NULL)
-    goto fail;
-
-  ps = dsym;
-  memcpy (ps, dirname, dirnamelen);
-  ps += dirnamelen;
-  *ps++ = '/';
-  memcpy (ps, basename, basenamelen);
-  ps += basenamelen;
-  memcpy (ps, dsymsuffixdir, dsymsuffixdirlen);
-  ps += dsymsuffixdirlen;
-  memcpy (ps, basename, basenamelen);
-  ps += basenamelen;
-  *ps = '\0';
-
-  if (diralc != NULL)
-    {
-      backtrace_free (state, diralc, dirnamelen + 1, error_callback, data);
-      diralc = NULL;
-    }
-
-  d = backtrace_open (dsym, error_callback, data, &does_not_exist);
-  if (d < 0)
-    {
-      /* The file does not exist, so we can't read the debug info.
-	 Just return success.  */
-      backtrace_free (state, dsym, dsymlen, error_callback, data);
-      return 1;
-    }
-
-  if (!macho_add (state, dsym, d, 0, uuid, base_address, 1,
-		  error_callback, data, fileline_fn, &dummy_found_sym))
-    goto fail;
-
-  backtrace_free (state, dsym, dsymlen, error_callback, data);
-
-  return 1;
-
- fail:
-  if (dsym != NULL)
-    backtrace_free (state, dsym, dsymlen, error_callback, data);
-  if (diralc != NULL)
-    backtrace_free (state, diralc, dirnamelen, error_callback, data);
-  return 0;
-}
-
-/* Add the backtrace data for a Macho-O file.  Returns 1 on success, 0
-   on failure (in both cases descriptor is closed).
-
-   FILENAME: the name of the executable.
-   DESCRIPTOR: an open descriptor for the executable, closed here.
-   OFFSET: the offset within the file of this executable, for fat files.
-   MATCH_UUID: if not NULL, UUID that must match.
-   BASE_ADDRESS: the load address of the executable.
-   SKIP_SYMTAB: if non-zero, ignore the symbol table; used for dSYM files.
-   FILELINE_FN: set to the fileline function, by backtrace_dwarf_add.
-   FOUND_SYM: set to non-zero if we found the symbol table.
-*/
-
-static int
-macho_add (struct backtrace_state *state, const char *filename, int descriptor,
-	   off_t offset, const unsigned char *match_uuid,
-	   uintptr_t base_address, int skip_symtab,
-	   backtrace_error_callback error_callback, void *data,
-	   fileline *fileline_fn, int *found_sym)
-{
-  struct backtrace_view header_view;
-  struct macho_header_32 header;
-  off_t hdroffset;
-  int is_64;
-  struct backtrace_view cmds_view;
-  int cmds_view_valid;
-  struct dwarf_sections dwarf_sections;
-  int have_dwarf;
-  unsigned char uuid[MACH_O_UUID_LEN];
-  int have_uuid;
-  size_t cmdoffset;
-  unsigned int i;
-
-  *found_sym = 0;
-
-  cmds_view_valid = 0;
-
-  /* The 32-bit and 64-bit file headers start out the same, so we can
-     just always read the 32-bit version.  A fat header is shorter but
-     it will always be followed by data, so it's OK to read extra.  */
-
-  if (!backtrace_get_view (state, descriptor, offset,
-			   sizeof (struct macho_header_32),
-			   error_callback, data, &header_view))
-    goto fail;
-
-  memcpy (&header, header_view.data, sizeof header);
-
-  backtrace_release_view (state, &header_view, error_callback, data);
-
-  switch (header.magic)
-    {
-    case MACH_O_MH_MAGIC_32:
-      is_64 = 0;
-      hdroffset = offset + sizeof (struct macho_header_32);
-      break;
-    case MACH_O_MH_MAGIC_64:
-      is_64 = 1;
-      hdroffset = offset + sizeof (struct macho_header_64);
-      break;
-    case MACH_O_MH_MAGIC_FAT:
-    case MACH_O_MH_MAGIC_FAT_64:
-      {
-	struct macho_header_fat fat_header;
-
-	hdroffset = offset + sizeof (struct macho_header_fat);
-	memcpy (&fat_header, &header, sizeof fat_header);
-	return macho_add_fat (state, filename, descriptor, 0, hdroffset,
-			      match_uuid, base_address, skip_symtab,
-			      fat_header.nfat_arch,
-			      header.magic == MACH_O_MH_MAGIC_FAT_64,
-			      error_callback, data, fileline_fn, found_sym);
-      }
-    case MACH_O_MH_CIGAM_FAT:
-    case MACH_O_MH_CIGAM_FAT_64:
-      {
-	struct macho_header_fat fat_header;
-	uint32_t nfat_arch;
-
-	hdroffset = offset + sizeof (struct macho_header_fat);
-	memcpy (&fat_header, &header, sizeof fat_header);
-	nfat_arch = __builtin_bswap32 (fat_header.nfat_arch);
-	return macho_add_fat (state, filename, descriptor, 1, hdroffset,
-			      match_uuid, base_address, skip_symtab,
-			      nfat_arch,
-			      header.magic == MACH_O_MH_CIGAM_FAT_64,
-			      error_callback, data, fileline_fn, found_sym);
-      }
-    default:
-      error_callback (data, "executable file is not in Mach-O format", 0);
-      goto fail;
-    }
-
-  switch (header.filetype)
-    {
-    case MACH_O_MH_EXECUTE:
-    case MACH_O_MH_DYLIB:
-    case MACH_O_MH_DSYM:
-      break;
-    default:
-      error_callback (data, "executable file is not an executable", 0);
-      goto fail;
-    }
-
-  if (!backtrace_get_view (state, descriptor, hdroffset, header.sizeofcmds,
-			   error_callback, data, &cmds_view))
-    goto fail;
-  cmds_view_valid = 1;
-
-  memset (&dwarf_sections, 0, sizeof dwarf_sections);
-  have_dwarf = 0;
-  memset (&uuid, 0, sizeof uuid);
-  have_uuid = 0;
-
-  cmdoffset = 0;
-  for (i = 0; i < header.ncmds; ++i)
-    {
-      const char *pcmd;
-      struct macho_load_command load_command;
-
-      if (cmdoffset + sizeof load_command > header.sizeofcmds)
-	break;
-
-      pcmd = (const char *) cmds_view.data + cmdoffset;
-      memcpy (&load_command, pcmd, sizeof load_command);
-
-      switch (load_command.cmd)
-	{
-	case MACH_O_LC_SEGMENT:
-	  {
-	    struct macho_segment_command segcmd;
-
-	    memcpy (&segcmd, pcmd, sizeof segcmd);
-	    if (memcmp (segcmd.segname,
-			"__DWARF\0\0\0\0\0\0\0\0\0",
-			MACH_O_NAMELEN) == 0)
-	      {
-		if (!macho_add_dwarf_segment (state, descriptor, offset,
-					      load_command.cmd,
-					      pcmd + sizeof segcmd,
-					      (load_command.cmdsize
-					       - sizeof segcmd),
-					      segcmd.nsects, error_callback,
-					      data, &dwarf_sections))
-		  goto fail;
-		have_dwarf = 1;
-	      }
-	  }
-	  break;
-
-	case MACH_O_LC_SEGMENT_64:
-	  {
-	    struct macho_segment_64_command segcmd;
-
-	    memcpy (&segcmd, pcmd, sizeof segcmd);
-	    if (memcmp (segcmd.segname,
-			"__DWARF\0\0\0\0\0\0\0\0\0",
-			MACH_O_NAMELEN) == 0)
-	      {
-		if (!macho_add_dwarf_segment (state, descriptor, offset,
-					      load_command.cmd,
-					      pcmd + sizeof segcmd,
-					      (load_command.cmdsize
-					       - sizeof segcmd),
-					      segcmd.nsects, error_callback,
-					      data, &dwarf_sections))
-		  goto fail;
-		have_dwarf = 1;
-	      }
-	  }
-	  break;
-
-	case MACH_O_LC_SYMTAB:
-	  if (!skip_symtab)
-	    {
-	      struct macho_symtab_command symcmd;
-
-	      memcpy (&symcmd, pcmd, sizeof symcmd);
-	      if (!macho_add_symtab (state, descriptor, base_address, is_64,
-				     offset + symcmd.symoff, symcmd.nsyms,
-				     offset + symcmd.stroff, symcmd.strsize,
-				     error_callback, data))
-		goto fail;
-
-	      *found_sym = 1;
-	    }
-	  break;
-
-	case MACH_O_LC_UUID:
-	  {
-	    struct macho_uuid_command uuidcmd;
-
-	    memcpy (&uuidcmd, pcmd, sizeof uuidcmd);
-	    memcpy (&uuid[0], &uuidcmd.uuid[0], MACH_O_UUID_LEN);
-	    have_uuid = 1;
-	  }
-	  break;
-
-	default:
-	  break;
-	}
-
-      cmdoffset += load_command.cmdsize;
-    }
-
-  if (!backtrace_close (descriptor, error_callback, data))
-    goto fail;
-  descriptor = -1;
-
-  backtrace_release_view (state, &cmds_view, error_callback, data);
-  cmds_view_valid = 0;
-
-  if (match_uuid != NULL)
-    {
-      /* If we don't have a UUID, or it doesn't match, just ignore
-	 this file.  */
-      if (!have_uuid
-	  || memcmp (match_uuid, &uuid[0], MACH_O_UUID_LEN) != 0)
-	return 1;
-    }
-
-  if (have_dwarf)
-    {
-      int is_big_endian;
-
-      is_big_endian = 0;
-#if defined(__BYTE_ORDER__) && defined(__ORDER_BIG_ENDIAN__)
-#if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
-      is_big_endian = 1;
-#endif
-#endif
-
-      if (!backtrace_dwarf_add (state, base_address, &dwarf_sections,
-				is_big_endian, NULL, error_callback, data,
-				fileline_fn, NULL))
-	goto fail;
-    }
-
-  if (!have_dwarf && have_uuid)
-    {
-      if (!macho_add_dsym (state, filename, base_address, &uuid[0],
-			   error_callback, data, fileline_fn))
-	goto fail;
-    }
-
-  return 1;
-
- fail:
-  if (cmds_view_valid)
-    backtrace_release_view (state, &cmds_view, error_callback, data);
-  if (descriptor != -1)
-    backtrace_close (descriptor, error_callback, data);
-  return 0;
-}
-
-#ifdef HAVE_MACH_O_DYLD_H
-
-/* Initialize the backtrace data we need from a Mach-O executable
-   using the dyld support functions.  This closes descriptor.  */
-
-int
-backtrace_initialize (struct backtrace_state *state, const char *filename,
-		      int descriptor, backtrace_error_callback error_callback,
-		      void *data, fileline *fileline_fn)
-{
-  uint32_t c;
-  uint32_t i;
-  int closed_descriptor;
-  int found_sym;
-  fileline macho_fileline_fn;
-
-  closed_descriptor = 0;
-  found_sym = 0;
-  macho_fileline_fn = macho_nodebug;
-
-  c = _dyld_image_count ();
-  for (i = 0; i < c; ++i)
-    {
-      uintptr_t base_address;
-      const char *name;
-      int d;
-      fileline mff;
-      int mfs;
-
-      name = _dyld_get_image_name (i);
-      if (name == NULL)
-	continue;
-
-      if (strcmp (name, filename) == 0 && !closed_descriptor)
-	{
-	  d = descriptor;
-	  closed_descriptor = 1;
-	}
-      else
-	{
-	  int does_not_exist;
-
-	  d = backtrace_open (name, error_callback, data, &does_not_exist);
-	  if (d < 0)
-	    continue;
-	}
-
-      base_address = _dyld_get_image_vmaddr_slide (i);
-
-      mff = macho_nodebug;
-      if (!macho_add (state, name, d, 0, NULL, base_address, 0,
-		      error_callback, data, &mff, &mfs))
-	continue;
-
-      if (mff != macho_nodebug)
-	macho_fileline_fn = mff;
-      if (mfs)
-	found_sym = 1;
-    }
-
-  if (!closed_descriptor)
-    backtrace_close (descriptor, error_callback, data);
-
-  if (!state->threaded)
-    {
-      if (found_sym)
-	state->syminfo_fn = macho_syminfo;
-      else if (state->syminfo_fn == NULL)
-	state->syminfo_fn = macho_nosyms;
-    }
-  else
-    {
-      if (found_sym)
-	backtrace_atomic_store_pointer (&state->syminfo_fn, macho_syminfo);
-      else
-	(void) __sync_bool_compare_and_swap (&state->syminfo_fn, NULL,
-					     macho_nosyms);
-    }
-
-  if (!state->threaded)
-    *fileline_fn = state->fileline_fn;
-  else
-    *fileline_fn = backtrace_atomic_load_pointer (&state->fileline_fn);
-
-  if (*fileline_fn == NULL || *fileline_fn == macho_nodebug)
-    *fileline_fn = macho_fileline_fn;
-
-  return 1;
-}
-
-#else /* !defined (HAVE_MACH_O_DYLD_H) */
-
-/* Initialize the backtrace data we need from a Mach-O executable
-   without using the dyld support functions.  This closes
-   descriptor.  */
-
-int
-backtrace_initialize (struct backtrace_state *state, const char *filename,
-		      int descriptor, backtrace_error_callback error_callback,
-		      void *data, fileline *fileline_fn)
-{
-  fileline macho_fileline_fn;
-  int found_sym;
-
-  macho_fileline_fn = macho_nodebug;
-  if (!macho_add (state, filename, descriptor, 0, NULL, 0, 0,
-		  error_callback, data, &macho_fileline_fn, &found_sym))
-    return 0;
-
-  if (!state->threaded)
-    {
-      if (found_sym)
-	state->syminfo_fn = macho_syminfo;
-      else if (state->syminfo_fn == NULL)
-	state->syminfo_fn = macho_nosyms;
-    }
-  else
-    {
-      if (found_sym)
-	backtrace_atomic_store_pointer (&state->syminfo_fn, macho_syminfo);
-      else
-	(void) __sync_bool_compare_and_swap (&state->syminfo_fn, NULL,
-					     macho_nosyms);
-    }
-
-  if (!state->threaded)
-    *fileline_fn = state->fileline_fn;
-  else
-    *fileline_fn = backtrace_atomic_load_pointer (&state->fileline_fn);
-
-  if (*fileline_fn == NULL || *fileline_fn == macho_nodebug)
-    *fileline_fn = macho_fileline_fn;
-
-  return 1;
-}
-
-#endif /* !defined (HAVE_MACH_O_DYLD_H) */
diff --git a/contrib/libs/cxxsupp/libcxx/include/experimental/functional b/contrib/libs/cxxsupp/libcxx/include/experimental/functional
deleted file mode 100644
index 1291894aa08..00000000000
--- a/contrib/libs/cxxsupp/libcxx/include/experimental/functional
+++ /dev/null
@@ -1,425 +0,0 @@
-// -*- C++ -*-
-//===----------------------------------------------------------------------===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef _LIBCPP_EXPERIMENTAL_FUNCTIONAL
-#define _LIBCPP_EXPERIMENTAL_FUNCTIONAL
-
-/*
-   experimental/functional synopsis
-
-#include <algorithm>
-
-namespace std {
-namespace experimental {
-inline namespace fundamentals_v1 {
-    // 4.3, Searchers
-    template<class ForwardIterator, class BinaryPredicate = equal_to<>>
-      class default_searcher;
-
-    template<class RandomAccessIterator,
-             class Hash = hash<typename iterator_traits<RandomAccessIterator>::value_type>,
-             class BinaryPredicate = equal_to<>>
-      class boyer_moore_searcher;
-
-    template<class RandomAccessIterator,
-             class Hash = hash<typename iterator_traits<RandomAccessIterator>::value_type>,
-             class BinaryPredicate = equal_to<>>
-      class boyer_moore_horspool_searcher;
-
-    template<class ForwardIterator, class BinaryPredicate = equal_to<>>
-    default_searcher<ForwardIterator, BinaryPredicate>
-    make_default_searcher(ForwardIterator pat_first, ForwardIterator pat_last,
-                          BinaryPredicate pred = BinaryPredicate());
-
-    template<class RandomAccessIterator,
-             class Hash = hash<typename iterator_traits<RandomAccessIterator>::value_type>,
-             class BinaryPredicate = equal_to<>>
-    boyer_moore_searcher<RandomAccessIterator, Hash, BinaryPredicate>
-    make_boyer_moore_searcher(
-        RandomAccessIterator pat_first, RandomAccessIterator pat_last,
-        Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate());
-
-    template<class RandomAccessIterator,
-             class Hash = hash<typename iterator_traits<RandomAccessIterator>::value_type>,
-             class BinaryPredicate = equal_to<>>
-    boyer_moore_horspool_searcher<RandomAccessIterator, Hash, BinaryPredicate>
-    make_boyer_moore_horspool_searcher(
-        RandomAccessIterator pat_first, RandomAccessIterator pat_last,
-        Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate());
-
-  } // namespace fundamentals_v1
-  } // namespace experimental
-
-} // namespace std
-
-*/
-
-#include <__debug>
-#include <__memory/uses_allocator.h>
-#include <array>
-#include <experimental/__config>
-#include <functional>
-#include <type_traits>
-#include <unordered_map>
-#include <vector>
-
-#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
-#  pragma GCC system_header
-#endif
-
-_LIBCPP_PUSH_MACROS
-#include <__undef_macros>
-
-_LIBCPP_BEGIN_NAMESPACE_LFTS
-
-#if _LIBCPP_STD_VER > 11
-// default searcher
-template<class _ForwardIterator, class _BinaryPredicate = equal_to<>>
-class _LIBCPP_TEMPLATE_VIS default_searcher {
-public:
-    _LIBCPP_INLINE_VISIBILITY
-    default_searcher(_ForwardIterator __f, _ForwardIterator __l,
-                       _BinaryPredicate __p = _BinaryPredicate())
-        : __first_(__f), __last_(__l), __pred_(__p) {}
-
-    template <typename _ForwardIterator2>
-    _LIBCPP_INLINE_VISIBILITY
-    pair<_ForwardIterator2, _ForwardIterator2>
-    operator () (_ForwardIterator2 __f, _ForwardIterator2 __l) const
-    {
-        return _VSTD::__search(__f, __l, __first_, __last_, __pred_,
-            typename iterator_traits<_ForwardIterator>::iterator_category(),
-            typename iterator_traits<_ForwardIterator2>::iterator_category());
-    }
-
-private:
-    _ForwardIterator __first_;
-    _ForwardIterator __last_;
-    _BinaryPredicate __pred_;
-    };
-
-template<class _ForwardIterator, class _BinaryPredicate = equal_to<>>
-_LIBCPP_INLINE_VISIBILITY
-default_searcher<_ForwardIterator, _BinaryPredicate>
-make_default_searcher( _ForwardIterator __f, _ForwardIterator __l, _BinaryPredicate __p = _BinaryPredicate ())
-{
-    return default_searcher<_ForwardIterator, _BinaryPredicate>(__f, __l, __p);
-}
-
-template<class _Key, class _Value, class _Hash, class _BinaryPredicate, bool /*useArray*/> class _BMSkipTable;
-
-//  General case for BM data searching; use a map
-template<class _Key, typename _Value, class _Hash, class _BinaryPredicate>
-class _BMSkipTable<_Key, _Value, _Hash, _BinaryPredicate, false> {
-    typedef _Value value_type;
-    typedef _Key   key_type;
-
-    const _Value __default_value_;
-    std::unordered_map<_Key, _Value, _Hash, _BinaryPredicate> __table;
-
-public:
-    _LIBCPP_INLINE_VISIBILITY
-    _BMSkipTable(size_t __sz, _Value __default, _Hash __hf, _BinaryPredicate __pred)
-        : __default_value_(__default), __table(__sz, __hf, __pred) {}
-
-    _LIBCPP_INLINE_VISIBILITY
-    void insert(const key_type &__key, value_type __val)
-    {
-        __table [__key] = __val;    // Would skip_.insert (val) be better here?
-    }
-
-    _LIBCPP_INLINE_VISIBILITY
-    value_type operator [](const key_type & __key) const
-    {
-        auto __it = __table.find (__key);
-        return __it == __table.end() ? __default_value_ : __it->second;
-    }
-};
-
-
-//  Special case small numeric values; use an array
-template<class _Key, typename _Value, class _Hash, class _BinaryPredicate>
-class _BMSkipTable<_Key, _Value, _Hash, _BinaryPredicate, true> {
-private:
-    typedef _Value value_type;
-    typedef _Key   key_type;
-
-    typedef typename make_unsigned<key_type>::type unsigned_key_type;
-    typedef std::array<value_type, numeric_limits<unsigned_key_type>::max()> skip_map;
-    skip_map __table;
-
-public:
-    _LIBCPP_INLINE_VISIBILITY
-    _BMSkipTable(size_t /*__sz*/, _Value __default, _Hash /*__hf*/, _BinaryPredicate /*__pred*/)
-    {
-        std::fill_n(__table.begin(), __table.size(), __default);
-    }
-
-    _LIBCPP_INLINE_VISIBILITY
-    void insert(key_type __key, value_type __val)
-    {
-        __table[static_cast<unsigned_key_type>(__key)] = __val;
-    }
-
-    _LIBCPP_INLINE_VISIBILITY
-    value_type operator [](key_type __key) const
-    {
-        return __table[static_cast<unsigned_key_type>(__key)];
-    }
-};
-
-
-template <class _RandomAccessIterator1,
-          class _Hash = hash<typename iterator_traits<_RandomAccessIterator1>::value_type>,
-          class _BinaryPredicate = equal_to<>>
-class _LIBCPP_TEMPLATE_VIS boyer_moore_searcher {
-private:
-    typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type difference_type;
-    typedef typename std::iterator_traits<_RandomAccessIterator1>::value_type      value_type;
-    typedef _BMSkipTable<value_type, difference_type, _Hash, _BinaryPredicate,
-                    is_integral<value_type>::value && // what about enums?
-                    sizeof(value_type) == 1 &&
-                    is_same<_Hash, hash<value_type>>::value &&
-                    is_same<_BinaryPredicate, equal_to<>>::value
-            > skip_table_type;
-
-public:
-    boyer_moore_searcher(_RandomAccessIterator1 __f, _RandomAccessIterator1 __l,
-                _Hash __hf = _Hash(), _BinaryPredicate __pred = _BinaryPredicate())
-            : __first_(__f), __last_(__l), __pred_(__pred),
-              __pattern_length_(_VSTD::distance(__first_, __last_)),
-              __skip_{make_shared<skip_table_type>(__pattern_length_, -1, __hf, __pred_)},
-              __suffix_{make_shared<vector<difference_type>>(__pattern_length_ + 1)}
-        {
-    //  build the skip table
-        for ( difference_type __i = 0; __f != __l; ++__f, (void) ++__i )
-            __skip_->insert(*__f, __i);
-
-        this->__build_suffix_table ( __first_, __last_, __pred_ );
-        }
-
-    template <typename _RandomAccessIterator2>
-    pair<_RandomAccessIterator2, _RandomAccessIterator2>
-    operator ()(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const
-    {
-        static_assert(__is_same_uncvref<typename iterator_traits<_RandomAccessIterator1>::value_type,
-                                        typename iterator_traits<_RandomAccessIterator2>::value_type>::value,
-                      "Corpus and Pattern iterators must point to the same type");
-
-        if (__f      == __l )    return make_pair(__l, __l); // empty corpus
-        if (__first_ == __last_) return make_pair(__f, __f); // empty pattern
-
-    //  If the pattern is larger than the corpus, we can't find it!
-        if ( __pattern_length_ > _VSTD::distance(__f, __l))
-            return make_pair(__l, __l);
-
-    //  Do the search
-        return this->__search(__f, __l);
-    }
-
-private:
-    _RandomAccessIterator1               __first_;
-    _RandomAccessIterator1               __last_;
-    _BinaryPredicate                     __pred_;
-    difference_type                      __pattern_length_;
-    shared_ptr<skip_table_type>          __skip_;
-    shared_ptr<vector<difference_type>>  __suffix_;
-
-    template <typename _RandomAccessIterator2>
-    pair<_RandomAccessIterator2, _RandomAccessIterator2>
-    __search(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const
-    {
-        _RandomAccessIterator2 __cur = __f;
-        const _RandomAccessIterator2 __last = __l - __pattern_length_;
-        const skip_table_type &         __skip   = *__skip_.get();
-        const vector<difference_type> & __suffix = *__suffix_.get();
-
-        while (__cur <= __last)
-        {
-
-        //  Do we match right where we are?
-            difference_type __j = __pattern_length_;
-            while (__pred_(__first_ [__j-1], __cur [__j-1])) {
-                __j--;
-            //  We matched - we're done!
-                if ( __j == 0 )
-                    return make_pair(__cur, __cur + __pattern_length_);
-                }
-
-        //  Since we didn't match, figure out how far to skip forward
-            difference_type __k = __skip[__cur [ __j - 1 ]];
-            difference_type __m = __j - __k - 1;
-            if (__k < __j && __m > __suffix[ __j ])
-                __cur += __m;
-            else
-                __cur += __suffix[ __j ];
-        }
-
-        return make_pair(__l, __l);     // We didn't find anything
-    }
-
-
-    template<typename _Iterator, typename _Container>
-    void __compute_bm_prefix ( _Iterator __f, _Iterator __l, _BinaryPredicate __pred, _Container &__prefix )
-    {
-        const size_t __count = _VSTD::distance(__f, __l);
-
-        __prefix[0] = 0;
-        size_t __k = 0;
-        for ( size_t __i = 1; __i < __count; ++__i )
-        {
-            while ( __k > 0 && !__pred ( __f[__k], __f[__i] ))
-                __k = __prefix [ __k - 1 ];
-
-            if ( __pred ( __f[__k], __f[__i] ))
-                __k++;
-            __prefix [ __i ] = __k;
-        }
-    }
-
-    void __build_suffix_table(_RandomAccessIterator1 __f, _RandomAccessIterator1 __l,
-                                                    _BinaryPredicate __pred)
-    {
-        const size_t __count = _VSTD::distance(__f, __l);
-        vector<difference_type> & __suffix = *__suffix_.get();
-        if (__count > 0)
-        {
-            vector<value_type> __scratch(__count);
-
-            __compute_bm_prefix(__f, __l, __pred, __scratch);
-            for ( size_t __i = 0; __i <= __count; __i++ )
-                __suffix[__i] = __count - __scratch[__count-1];
-
-            typedef reverse_iterator<_RandomAccessIterator1> _RevIter;
-            __compute_bm_prefix(_RevIter(__l), _RevIter(__f), __pred, __scratch);
-
-            for ( size_t __i = 0; __i < __count; __i++ )
-            {
-                const size_t     __j = __count - __scratch[__i];
-                const difference_type __k = __i     - __scratch[__i] + 1;
-
-                if (__suffix[__j] > __k)
-                    __suffix[__j] = __k;
-            }
-        }
-    }
-
-};
-
-template<class _RandomAccessIterator,
-         class _Hash = hash<typename iterator_traits<_RandomAccessIterator>::value_type>,
-         class _BinaryPredicate = equal_to<>>
-_LIBCPP_INLINE_VISIBILITY
-boyer_moore_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate>
-make_boyer_moore_searcher( _RandomAccessIterator __f, _RandomAccessIterator __l,
-                    _Hash __hf = _Hash(), _BinaryPredicate __p = _BinaryPredicate ())
-{
-    return boyer_moore_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate>(__f, __l, __hf, __p);
-}
-
-// boyer-moore-horspool
-template <class _RandomAccessIterator1,
-          class _Hash = hash<typename iterator_traits<_RandomAccessIterator1>::value_type>,
-          class _BinaryPredicate = equal_to<>>
-class _LIBCPP_TEMPLATE_VIS boyer_moore_horspool_searcher {
-private:
-    typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type difference_type;
-    typedef typename std::iterator_traits<_RandomAccessIterator1>::value_type      value_type;
-    typedef _BMSkipTable<value_type, difference_type, _Hash, _BinaryPredicate,
-                    is_integral<value_type>::value && // what about enums?
-                    sizeof(value_type) == 1 &&
-                    is_same<_Hash, hash<value_type>>::value &&
-                    is_same<_BinaryPredicate, equal_to<>>::value
-            > skip_table_type;
-
-public:
-    boyer_moore_horspool_searcher(_RandomAccessIterator1 __f, _RandomAccessIterator1 __l,
-                _Hash __hf = _Hash(), _BinaryPredicate __pred = _BinaryPredicate())
-            : __first_(__f), __last_(__l), __pred_(__pred),
-              __pattern_length_(_VSTD::distance(__first_, __last_)),
-              __skip_{_VSTD::make_shared<skip_table_type>(__pattern_length_, __pattern_length_, __hf, __pred_)}
-        {
-    //  build the skip table
-            if ( __f != __l )
-            {
-                __l = __l - 1;
-                for ( difference_type __i = 0; __f != __l; ++__f, (void) ++__i )
-                    __skip_->insert(*__f, __pattern_length_ - 1 - __i);
-            }
-        }
-
-    template <typename _RandomAccessIterator2>
-    pair<_RandomAccessIterator2, _RandomAccessIterator2>
-    operator ()(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const
-    {
-        static_assert(__is_same_uncvref<typename std::iterator_traits<_RandomAccessIterator1>::value_type,
-                                        typename std::iterator_traits<_RandomAccessIterator2>::value_type>::value,
-                      "Corpus and Pattern iterators must point to the same type");
-
-        if (__f      == __l )    return make_pair(__l, __l); // empty corpus
-        if (__first_ == __last_) return make_pair(__f, __f); // empty pattern
-
-    //  If the pattern is larger than the corpus, we can't find it!
-        if ( __pattern_length_ > _VSTD::distance(__f, __l))
-            return make_pair(__l, __l);
-
-    //  Do the search
-        return this->__search(__f, __l);
-    }
-
-private:
-    _RandomAccessIterator1      __first_;
-    _RandomAccessIterator1      __last_;
-    _BinaryPredicate            __pred_;
-    difference_type             __pattern_length_;
-    shared_ptr<skip_table_type> __skip_;
-
-    template <typename _RandomAccessIterator2>
-    pair<_RandomAccessIterator2, _RandomAccessIterator2>
-    __search ( _RandomAccessIterator2 __f, _RandomAccessIterator2 __l ) const {
-        _RandomAccessIterator2 __cur = __f;
-        const _RandomAccessIterator2 __last = __l - __pattern_length_;
-        const skip_table_type & __skip = *__skip_.get();
-
-        while (__cur <= __last)
-        {
-        //  Do we match right where we are?
-            difference_type __j = __pattern_length_;
-            while (__pred_(__first_[__j-1], __cur[__j-1]))
-            {
-                __j--;
-            //  We matched - we're done!
-                if ( __j == 0 )
-                    return make_pair(__cur, __cur + __pattern_length_);
-            }
-            __cur += __skip[__cur[__pattern_length_-1]];
-        }
-
-        return make_pair(__l, __l);
-    }
-};
-
-template<class _RandomAccessIterator,
-         class _Hash = hash<typename iterator_traits<_RandomAccessIterator>::value_type>,
-         class _BinaryPredicate = equal_to<>>
-_LIBCPP_INLINE_VISIBILITY
-boyer_moore_horspool_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate>
-make_boyer_moore_horspool_searcher( _RandomAccessIterator __f, _RandomAccessIterator __l,
-                    _Hash __hf = _Hash(), _BinaryPredicate __p = _BinaryPredicate ())
-{
-    return boyer_moore_horspool_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate>(__f, __l, __hf, __p);
-}
-
-#endif // _LIBCPP_STD_VER > 11
-
-_LIBCPP_END_NAMESPACE_LFTS
-
-_LIBCPP_POP_MACROS
-
-#endif /* _LIBCPP_EXPERIMENTAL_FUNCTIONAL */
diff --git a/contrib/libs/sparsehash/src/sparsehash/dense_hash_set b/contrib/libs/sparsehash/src/sparsehash/dense_hash_set
deleted file mode 100644
index 050b15d1d5d..00000000000
--- a/contrib/libs/sparsehash/src/sparsehash/dense_hash_set
+++ /dev/null
@@ -1,338 +0,0 @@
-// Copyright (c) 2005, Google Inc.
-// All rights reserved.
-//
-// Redistribution and use in source and binary forms, with or without
-// modification, are permitted provided that the following conditions are
-// met:
-//
-//     * Redistributions of source code must retain the above copyright
-// notice, this list of conditions and the following disclaimer.
-//     * Redistributions in binary form must reproduce the above
-// copyright notice, this list of conditions and the following disclaimer
-// in the documentation and/or other materials provided with the
-// distribution.
-//     * Neither the name of Google Inc. nor the names of its
-// contributors may be used to endorse or promote products derived from
-// this software without specific prior written permission.
-//
-// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
-// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
-// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
-// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
-// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
-// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
-// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
-// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
-// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
-// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-
-// ---
-//
-// This is just a very thin wrapper over densehashtable.h, just
-// like sgi stl's stl_hash_set is a very thin wrapper over
-// stl_hashtable.  The major thing we define is operator[], because
-// we have a concept of a data_type which stl_hashtable doesn't
-// (it only has a key and a value).
-//
-// This is more different from dense_hash_map than you might think,
-// because all iterators for sets are const (you obviously can't
-// change the key, and for sets there is no value).
-//
-// NOTE: this is exactly like sparse_hash_set.h, with the word
-// "sparse" replaced by "dense", except for the addition of
-// set_empty_key().
-//
-//   YOU MUST CALL SET_EMPTY_KEY() IMMEDIATELY AFTER CONSTRUCTION.
-//
-// Otherwise your program will die in mysterious ways.  (Note if you
-// use the constructor that takes an InputIterator range, you pass in
-// the empty key in the constructor, rather than after.  As a result,
-// this constructor differs from the standard STL version.)
-//
-// In other respects, we adhere mostly to the STL semantics for
-// hash-map.  One important exception is that insert() may invalidate
-// iterators entirely -- STL semantics are that insert() may reorder
-// iterators, but they all still refer to something valid in the
-// hashtable.  Not so for us.  Likewise, insert() may invalidate
-// pointers into the hashtable.  (Whether insert invalidates iterators
-// and pointers depends on whether it results in a hashtable resize).
-// On the plus side, delete() doesn't invalidate iterators or pointers
-// at all, or even change the ordering of elements.
-//
-// Here are a few "power user" tips:
-//
-//    1) set_deleted_key():
-//         If you want to use erase() you must call set_deleted_key(),
-//         in addition to set_empty_key(), after construction.
-//         The deleted and empty keys must differ.
-//
-//    2) resize(0):
-//         When an item is deleted, its memory isn't freed right
-//         away.  This allows you to iterate over a hashtable,
-//         and call erase(), without invalidating the iterator.
-//         To force the memory to be freed, call resize(0).
-//         For tr1 compatibility, this can also be called as rehash(0).
-//
-//    3) min_load_factor(0.0)
-//         Setting the minimum load factor to 0.0 guarantees that
-//         the hash table will never shrink.
-//
-// Roughly speaking:
-//   (1) dense_hash_set: fastest, uses the most memory unless entries are small
-//   (2) sparse_hash_set: slowest, uses the least memory
-//   (3) hash_set / unordered_set (STL): in the middle
-//
-// Typically I use sparse_hash_set when I care about space and/or when
-// I need to save the hashtable on disk.  I use hash_set otherwise.  I
-// don't personally use dense_hash_set ever; some people use it for
-// small sets with lots of lookups.
-//
-// - dense_hash_set has, typically, about 78% memory overhead (if your
-//   data takes up X bytes, the hash_set uses .78X more bytes in overhead).
-// - sparse_hash_set has about 4 bits overhead per entry.
-// - sparse_hash_set can be 3-7 times slower than the others for lookup and,
-//   especially, inserts.  See time_hash_map.cc for details.
-//
-// See /usr/(local/)?doc/sparsehash-*/dense_hash_set.html
-// for information about how to use this class.
-
-#ifndef _DENSE_HASH_SET_H_
-#define _DENSE_HASH_SET_H_
-
-#include <sparsehash/internal/sparseconfig.h>
-#include <algorithm>                        // needed by stl_alloc
-#include <functional>                       // for equal_to<>, select1st<>, etc
-#include <memory>                           // for alloc
-#include <utility>                          // for pair<>
-#include <sparsehash/internal/densehashtable.h>        // IWYU pragma: export
-#include <sparsehash/internal/libc_allocator_with_realloc.h>
-#include HASH_FUN_H                 // for hash<>
-_START_GOOGLE_NAMESPACE_
-
-template <class Value,
-          class HashFcn = SPARSEHASH_HASH<Value>,   // defined in sparseconfig.h
-          class EqualKey = std::equal_to<Value>,
-          class Alloc = libc_allocator_with_realloc<Value> >
-class dense_hash_set {
- private:
-  // Apparently identity is not stl-standard, so we define our own
-  struct Identity {
-    typedef const Value& result_type;
-    const Value& operator()(const Value& v) const { return v; }
-  };
-  struct SetKey {
-    void operator()(Value* value, const Value& new_key) const {
-      *value = new_key;
-    }
-  };
-
-  // The actual data
-  typedef dense_hashtable<Value, Value, HashFcn, Identity, SetKey,
-                          EqualKey, Alloc> ht;
-  ht rep;
-
- public:
-  typedef typename ht::key_type key_type;
-  typedef typename ht::value_type value_type;
-  typedef typename ht::hasher hasher;
-  typedef typename ht::key_equal key_equal;
-  typedef Alloc allocator_type;
-
-  typedef typename ht::size_type size_type;
-  typedef typename ht::difference_type difference_type;
-  typedef typename ht::const_pointer pointer;
-  typedef typename ht::const_pointer const_pointer;
-  typedef typename ht::const_reference reference;
-  typedef typename ht::const_reference const_reference;
-
-  typedef typename ht::const_iterator iterator;
-  typedef typename ht::const_iterator const_iterator;
-  typedef typename ht::const_local_iterator local_iterator;
-  typedef typename ht::const_local_iterator const_local_iterator;
-
-
-  // Iterator functions -- recall all iterators are const
-  iterator begin() const                  { return rep.begin(); }
-  iterator end() const                    { return rep.end(); }
-
-  // These come from tr1's unordered_set. For us, a bucket has 0 or 1 elements.
-  local_iterator begin(size_type i) const { return rep.begin(i); }
-  local_iterator end(size_type i) const   { return rep.end(i); }
-
-
-  // Accessor functions
-  allocator_type get_allocator() const    { return rep.get_allocator(); }
-  hasher hash_funct() const               { return rep.hash_funct(); }
-  hasher hash_function() const            { return hash_funct(); }  // tr1 name
-  key_equal key_eq() const                { return rep.key_eq(); }
-
-
-  // Constructors
-  explicit dense_hash_set(size_type expected_max_items_in_table = 0,
-                          const hasher& hf = hasher(),
-                          const key_equal& eql = key_equal(),
-                          const allocator_type& alloc = allocator_type())
-      : rep(expected_max_items_in_table, hf, eql, Identity(), SetKey(), alloc) {
-  }
-
-  template <class InputIterator>
-  dense_hash_set(InputIterator f, InputIterator l,
-                 const key_type& empty_key_val,
-                 size_type expected_max_items_in_table = 0,
-                 const hasher& hf = hasher(),
-                 const key_equal& eql = key_equal(),
-                 const allocator_type& alloc = allocator_type())
-      : rep(expected_max_items_in_table, hf, eql, Identity(), SetKey(), alloc) {
-    set_empty_key(empty_key_val);
-    rep.insert(f, l);
-  }
-  // We use the default copy constructor
-  // We use the default operator=()
-  // We use the default destructor
-
-  void clear()                        { rep.clear(); }
-  // This clears the hash set without resizing it down to the minimum
-  // bucket count, but rather keeps the number of buckets constant
-  void clear_no_resize()              { rep.clear_no_resize(); }
-  void swap(dense_hash_set& hs)       { rep.swap(hs.rep); }
-
-
-  // Functions concerning size
-  size_type size() const              { return rep.size(); }
-  size_type max_size() const          { return rep.max_size(); }
-  bool empty() const                  { return rep.empty(); }
-  size_type bucket_count() const      { return rep.bucket_count(); }
-  size_type max_bucket_count() const  { return rep.max_bucket_count(); }
-
-  // These are tr1 methods.  bucket() is the bucket the key is or would be in.
-  size_type bucket_size(size_type i) const    { return rep.bucket_size(i); }
-  size_type bucket(const key_type& key) const { return rep.bucket(key); }
-  float load_factor() const {
-    return size() * 1.0f / bucket_count();
-  }
-  float max_load_factor() const {
-    float shrink, grow;
-    rep.get_resizing_parameters(&shrink, &grow);
-    return grow;
-  }
-  void max_load_factor(float new_grow) {
-    float shrink, grow;
-    rep.get_resizing_parameters(&shrink, &grow);
-    rep.set_resizing_parameters(shrink, new_grow);
-  }
-  // These aren't tr1 methods but perhaps ought to be.
-  float min_load_factor() const {
-    float shrink, grow;
-    rep.get_resizing_parameters(&shrink, &grow);
-    return shrink;
-  }
-  void min_load_factor(float new_shrink) {
-    float shrink, grow;
-    rep.get_resizing_parameters(&shrink, &grow);
-    rep.set_resizing_parameters(new_shrink, grow);
-  }
-  // Deprecated; use min_load_factor() or max_load_factor() instead.
-  void set_resizing_parameters(float shrink, float grow) {
-    rep.set_resizing_parameters(shrink, grow);
-  }
-
-  void resize(size_type hint)         { rep.resize(hint); }
-  void rehash(size_type hint)         { resize(hint); }     // the tr1 name
-
-  // Lookup routines
-  iterator find(const key_type& key) const           { return rep.find(key); }
-
-  size_type count(const key_type& key) const         { return rep.count(key); }
-
-  std::pair<iterator, iterator> equal_range(const key_type& key) const {
-    return rep.equal_range(key);
-  }
-
-
-  // Insertion routines
-  std::pair<iterator, bool> insert(const value_type& obj) {
-    std::pair<typename ht::iterator, bool> p = rep.insert(obj);
-    return std::pair<iterator, bool>(p.first, p.second);   // const to non-const
-  }
-  template <class InputIterator> void insert(InputIterator f, InputIterator l) {
-    rep.insert(f, l);
-  }
-  void insert(const_iterator f, const_iterator l) {
-    rep.insert(f, l);
-  }
-  // Required for std::insert_iterator; the passed-in iterator is ignored.
-  iterator insert(iterator, const value_type& obj)   {
-    return insert(obj).first;
-  }
-
-  // Deletion and empty routines
-  // THESE ARE NON-STANDARD!  I make you specify an "impossible" key
-  // value to identify deleted and empty buckets.  You can change the
-  // deleted key as time goes on, or get rid of it entirely to be insert-only.
-  void set_empty_key(const key_type& key)     { rep.set_empty_key(key); }
-  key_type empty_key() const                  { return rep.empty_key(); }
-
-  void set_deleted_key(const key_type& key)   { rep.set_deleted_key(key); }
-  void clear_deleted_key()                    { rep.clear_deleted_key(); }
-  key_type deleted_key() const                { return rep.deleted_key(); }
-
-  // These are standard
-  size_type erase(const key_type& key)               { return rep.erase(key); }
-  void erase(iterator it)                            { rep.erase(it); }
-  void erase(iterator f, iterator l)                 { rep.erase(f, l); }
-
-
-  // Comparison
-  bool operator==(const dense_hash_set& hs) const    { return rep == hs.rep; }
-  bool operator!=(const dense_hash_set& hs) const    { return rep != hs.rep; }
-
-
-  // I/O -- this is an add-on for writing metainformation to disk
-  //
-  // For maximum flexibility, this does not assume a particular
-  // file type (though it will probably be a FILE *).  We just pass
-  // the fp through to rep.
-
-  // If your keys and values are simple enough, you can pass this
-  // serializer to serialize()/unserialize().  "Simple enough" means
-  // value_type is a POD type that contains no pointers.  Note,
-  // however, we don't try to normalize endianness.
-  typedef typename ht::NopointerSerializer NopointerSerializer;
-
-  // serializer: a class providing operator()(OUTPUT*, const value_type&)
-  //    (writing value_type to OUTPUT).  You can specify a
-  //    NopointerSerializer object if appropriate (see above).
-  // fp: either a FILE*, OR an ostream*/subclass_of_ostream*, OR a
-  //    pointer to a class providing size_t Write(const void*, size_t),
-  //    which writes a buffer into a stream (which fp presumably
-  //    owns) and returns the number of bytes successfully written.
-  //    Note basic_ostream<not_char> is not currently supported.
-  template <typename ValueSerializer, typename OUTPUT>
-  bool serialize(ValueSerializer serializer, OUTPUT* fp) {
-    return rep.serialize(serializer, fp);
-  }
-
-  // serializer: a functor providing operator()(INPUT*, value_type*)
-  //    (reading from INPUT and into value_type).  You can specify a
-  //    NopointerSerializer object if appropriate (see above).
-  // fp: either a FILE*, OR an istream*/subclass_of_istream*, OR a
-  //    pointer to a class providing size_t Read(void*, size_t),
-  //    which reads into a buffer from a stream (which fp presumably
-  //    owns) and returns the number of bytes successfully read.
-  //    Note basic_istream<not_char> is not currently supported.
-  template <typename ValueSerializer, typename INPUT>
-  bool unserialize(ValueSerializer serializer, INPUT* fp) {
-    return rep.unserialize(serializer, fp);
-  }
-};
-
-template <class Val, class HashFcn, class EqualKey, class Alloc>
-inline void swap(dense_hash_set<Val, HashFcn, EqualKey, Alloc>& hs1,
-                 dense_hash_set<Val, HashFcn, EqualKey, Alloc>& hs2) {
-  hs1.swap(hs2);
-}
-
-_END_GOOGLE_NAMESPACE_
-
-#endif /* _DENSE_HASH_SET_H_ */