Merge tree-ssa-20020619-branch into mainline.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@81764 138bc75d-0d04-0410-961f-82ee72b054a4

10 files changed, 2429 insertions, 0 deletions

diff --git a/libbanshee/libcompat/Makefile.am b/libbanshee/libcompat/Makefile.am
new file mode 100644
index 00000000000..dae6ac0052f
--- /dev/null
+++ b/libbanshee/libcompat/Makefile.am
@@ -0,0 +1,4 @@
+AM_CFLAGS = -I$(srcdir)/../engine -I$(srcdir)/../include -I. -Ddeletes= -Dtraditional= -Dsameregion= -Dparentptr= @ac_libbanshee_warn_cflags@
+noinst_LIBRARIES = libbansheecompat.a
+libbansheecompat_a_SOURCES = regions.c radix-tree.c
+
diff --git a/libbanshee/libcompat/Makefile.in b/libbanshee/libcompat/Makefile.in
new file mode 100644
index 00000000000..48e4249ee3d
--- /dev/null
+++ b/libbanshee/libcompat/Makefile.in
@@ -0,0 +1,365 @@
+# Makefile.in generated by automake 1.7.6 from Makefile.am.
+# @configure_input@
+
+# Copyright 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003
+# Free Software Foundation, Inc.
+# This Makefile.in is free software; the Free Software Foundation
+# gives unlimited permission to copy and/or distribute it,
+# with or without modifications, as long as this notice is preserved.
+
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY, to the extent permitted by law; without
+# even the implied warranty of MERCHANTABILITY or FITNESS FOR A
+# PARTICULAR PURPOSE.
+
+@SET_MAKE@
+
+srcdir = @srcdir@
+top_srcdir = @top_srcdir@
+VPATH = @srcdir@
+pkgdatadir = $(datadir)/@PACKAGE@
+pkglibdir = $(libdir)/@PACKAGE@
+pkgincludedir = $(includedir)/@PACKAGE@
+top_builddir = ..
+
+am__cd = CDPATH="$${ZSH_VERSION+.}$(PATH_SEPARATOR)" && cd
+INSTALL = @INSTALL@
+install_sh_DATA = $(install_sh) -c -m 644
+install_sh_PROGRAM = $(install_sh) -c
+install_sh_SCRIPT = $(install_sh) -c
+INSTALL_HEADER = $(INSTALL_DATA)
+transform = $(program_transform_name)
+NORMAL_INSTALL = :
+PRE_INSTALL = :
+POST_INSTALL = :
+NORMAL_UNINSTALL = :
+PRE_UNINSTALL = :
+POST_UNINSTALL = :
+ACLOCAL = @ACLOCAL@
+AMDEP_FALSE = @AMDEP_FALSE@
+AMDEP_TRUE = @AMDEP_TRUE@
+AMTAR = @AMTAR@
+AUTOCONF = @AUTOCONF@
+AUTOHEADER = @AUTOHEADER@
+AUTOMAKE = @AUTOMAKE@
+AWK = @AWK@
+CC = @CC@
+CCDEPMODE = @CCDEPMODE@
+CFLAGS = @CFLAGS@
+CPP = @CPP@
+CPPFLAGS = @CPPFLAGS@
+CYGPATH_W = @CYGPATH_W@
+DEFS = @DEFS@
+DEPDIR = @DEPDIR@
+ECHO_C = @ECHO_C@
+ECHO_N = @ECHO_N@
+ECHO_T = @ECHO_T@
+EGREP = @EGREP@
+EXEEXT = @EXEEXT@
+INSTALL_DATA = @INSTALL_DATA@
+INSTALL_PROGRAM = @INSTALL_PROGRAM@
+INSTALL_SCRIPT = @INSTALL_SCRIPT@
+INSTALL_STRIP_PROGRAM = @INSTALL_STRIP_PROGRAM@
+LDFLAGS = @LDFLAGS@
+LIBOBJS = @LIBOBJS@
+LIBS = @LIBS@
+LTLIBOBJS = @LTLIBOBJS@
+MAINT = @MAINT@
+MAINTAINER_MODE_FALSE = @MAINTAINER_MODE_FALSE@
+MAINTAINER_MODE_TRUE = @MAINTAINER_MODE_TRUE@
+MAKEINFO = @MAKEINFO@
+OBJEXT = @OBJEXT@
+PACKAGE = @PACKAGE@
+PACKAGE_BUGREPORT = @PACKAGE_BUGREPORT@
+PACKAGE_NAME = @PACKAGE_NAME@
+PACKAGE_STRING = @PACKAGE_STRING@
+PACKAGE_TARNAME = @PACKAGE_TARNAME@
+PACKAGE_VERSION = @PACKAGE_VERSION@
+PATH_SEPARATOR = @PATH_SEPARATOR@
+RANLIB = @RANLIB@
+SET_MAKE = @SET_MAKE@
+SHELL = @SHELL@
+STRIP = @STRIP@
+VERSION = @VERSION@
+ac_ct_CC = @ac_ct_CC@
+ac_ct_RANLIB = @ac_ct_RANLIB@
+ac_ct_STRIP = @ac_ct_STRIP@
+ac_libbanshee_warn_cflags = @ac_libbanshee_warn_cflags@
+am__fastdepCC_FALSE = @am__fastdepCC_FALSE@
+am__fastdepCC_TRUE = @am__fastdepCC_TRUE@
+am__include = @am__include@
+am__leading_dot = @am__leading_dot@
+am__quote = @am__quote@
+bindir = @bindir@
+build_alias = @build_alias@
+datadir = @datadir@
+exec_prefix = @exec_prefix@
+host_alias = @host_alias@
+includedir = @includedir@
+infodir = @infodir@
+install_sh = @install_sh@
+libdir = @libdir@
+libexecdir = @libexecdir@
+localstatedir = @localstatedir@
+mandir = @mandir@
+oldincludedir = @oldincludedir@
+prefix = @prefix@
+program_transform_name = @program_transform_name@
+sbindir = @sbindir@
+sharedstatedir = @sharedstatedir@
+sysconfdir = @sysconfdir@
+target_alias = @target_alias@
+AM_CFLAGS = -I$(srcdir)/../engine -I$(srcdir)/../include -I. -Ddeletes= -Dtraditional= -Dsameregion= -Dparentptr= @ac_libbanshee_warn_cflags@
+noinst_LIBRARIES = libbansheecompat.a
+libbansheecompat_a_SOURCES = regions.c radix-tree.c
+subdir = libcompat
+ACLOCAL_M4 = $(top_srcdir)/aclocal.m4
+mkinstalldirs = $(SHELL) $(top_srcdir)/../mkinstalldirs
+CONFIG_HEADER = $(top_builddir)/config.h
+CONFIG_CLEAN_FILES =
+LIBRARIES = $(noinst_LIBRARIES)
+
+libbansheecompat_a_AR = $(AR) cru
+libbansheecompat_a_LIBADD =
+am_libbansheecompat_a_OBJECTS = regions.$(OBJEXT) radix-tree.$(OBJEXT)
+libbansheecompat_a_OBJECTS = $(am_libbansheecompat_a_OBJECTS)
+
+DEFAULT_INCLUDES =  -I. -I$(srcdir) -I$(top_builddir)
+depcomp = $(SHELL) $(top_srcdir)/../depcomp
+am__depfiles_maybe = depfiles
+@AMDEP_TRUE@DEP_FILES = ./$(DEPDIR)/radix-tree.Po ./$(DEPDIR)/regions.Po
+COMPILE = $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) \
+	$(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS)
+CCLD = $(CC)
+LINK = $(CCLD) $(AM_CFLAGS) $(CFLAGS) $(AM_LDFLAGS) $(LDFLAGS) -o $@
+DIST_SOURCES = $(libbansheecompat_a_SOURCES)
+DIST_COMMON = Makefile.am Makefile.in
+SOURCES = $(libbansheecompat_a_SOURCES)
+
+all: all-am
+
+.SUFFIXES:
+.SUFFIXES: .c .o .obj
+$(srcdir)/Makefile.in: @MAINTAINER_MODE_TRUE@ Makefile.am  $(top_srcdir)/configure.in $(ACLOCAL_M4)
+	cd $(top_srcdir) && \
+	  $(AUTOMAKE) --gnu  libcompat/Makefile
+Makefile: @MAINTAINER_MODE_TRUE@ $(srcdir)/Makefile.in  $(top_builddir)/config.status
+	cd $(top_builddir) && $(SHELL) ./config.status $(subdir)/$@ $(am__depfiles_maybe)
+
+AR = ar
+
+clean-noinstLIBRARIES:
+	-test -z "$(noinst_LIBRARIES)" || rm -f $(noinst_LIBRARIES)
+libbansheecompat.a: $(libbansheecompat_a_OBJECTS) $(libbansheecompat_a_DEPENDENCIES) 
+	-rm -f libbansheecompat.a
+	$(libbansheecompat_a_AR) libbansheecompat.a $(libbansheecompat_a_OBJECTS) $(libbansheecompat_a_LIBADD)
+	$(RANLIB) libbansheecompat.a
+
+mostlyclean-compile:
+	-rm -f *.$(OBJEXT) core *.core
+
+distclean-compile:
+	-rm -f *.tab.c
+
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/radix-tree.Po@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/regions.Po@am__quote@
+
+distclean-depend:
+	-rm -rf ./$(DEPDIR)
+
+.c.o:
+@am__fastdepCC_TRUE@	if $(COMPILE) -MT $@ -MD -MP -MF "$(DEPDIR)/$*.Tpo" \
+@am__fastdepCC_TRUE@	  -c -o $@ `test -f '$<' || echo '$(srcdir)/'`$<; \
+@am__fastdepCC_TRUE@	then mv -f "$(DEPDIR)/$*.Tpo" "$(DEPDIR)/$*.Po"; \
+@am__fastdepCC_TRUE@	else rm -f "$(DEPDIR)/$*.Tpo"; exit 1; \
+@am__fastdepCC_TRUE@	fi
+@AMDEP_TRUE@@am__fastdepCC_FALSE@	source='$<' object='$@' libtool=no @AMDEPBACKSLASH@
+@AMDEP_TRUE@@am__fastdepCC_FALSE@	depfile='$(DEPDIR)/$*.Po' tmpdepfile='$(DEPDIR)/$*.TPo' @AMDEPBACKSLASH@
+@AMDEP_TRUE@@am__fastdepCC_FALSE@	$(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@
+@am__fastdepCC_FALSE@	$(COMPILE) -c `test -f '$<' || echo '$(srcdir)/'`$<
+
+.c.obj:
+@am__fastdepCC_TRUE@	if $(COMPILE) -MT $@ -MD -MP -MF "$(DEPDIR)/$*.Tpo" \
+@am__fastdepCC_TRUE@	  -c -o $@ `if test -f '$<'; then $(CYGPATH_W) '$<'; else $(CYGPATH_W) '$(srcdir)/$<'; fi`; \
+@am__fastdepCC_TRUE@	then mv -f "$(DEPDIR)/$*.Tpo" "$(DEPDIR)/$*.Po"; \
+@am__fastdepCC_TRUE@	else rm -f "$(DEPDIR)/$*.Tpo"; exit 1; \
+@am__fastdepCC_TRUE@	fi
+@AMDEP_TRUE@@am__fastdepCC_FALSE@	source='$<' object='$@' libtool=no @AMDEPBACKSLASH@
+@AMDEP_TRUE@@am__fastdepCC_FALSE@	depfile='$(DEPDIR)/$*.Po' tmpdepfile='$(DEPDIR)/$*.TPo' @AMDEPBACKSLASH@
+@AMDEP_TRUE@@am__fastdepCC_FALSE@	$(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@
+@am__fastdepCC_FALSE@	$(COMPILE) -c `if test -f '$<'; then $(CYGPATH_W) '$<'; else $(CYGPATH_W) '$(srcdir)/$<'; fi`
+uninstall-info-am:
+
+ETAGS = etags
+ETAGSFLAGS =
+
+CTAGS = ctags
+CTAGSFLAGS =
+
+tags: TAGS
+
+ID: $(HEADERS) $(SOURCES) $(LISP) $(TAGS_FILES)
+	list='$(SOURCES) $(HEADERS) $(LISP) $(TAGS_FILES)'; \
+	unique=`for i in $$list; do \
+	    if test -f "$$i"; then echo $$i; else echo $(srcdir)/$$i; fi; \
+	  done | \
+	  $(AWK) '    { files[$$0] = 1; } \
+	       END { for (i in files) print i; }'`; \
+	mkid -fID $$unique
+
+TAGS:  $(HEADERS) $(SOURCES)  $(TAGS_DEPENDENCIES) \
+		$(TAGS_FILES) $(LISP)
+	tags=; \
+	here=`pwd`; \
+	list='$(SOURCES) $(HEADERS)  $(LISP) $(TAGS_FILES)'; \
+	unique=`for i in $$list; do \
+	    if test -f "$$i"; then echo $$i; else echo $(srcdir)/$$i; fi; \
+	  done | \
+	  $(AWK) '    { files[$$0] = 1; } \
+	       END { for (i in files) print i; }'`; \
+	test -z "$(ETAGS_ARGS)$$tags$$unique" \
+	  || $(ETAGS) $(ETAGSFLAGS) $(AM_ETAGSFLAGS) $(ETAGS_ARGS) \
+	     $$tags $$unique
+
+ctags: CTAGS
+CTAGS:  $(HEADERS) $(SOURCES)  $(TAGS_DEPENDENCIES) \
+		$(TAGS_FILES) $(LISP)
+	tags=; \
+	here=`pwd`; \
+	list='$(SOURCES) $(HEADERS)  $(LISP) $(TAGS_FILES)'; \
+	unique=`for i in $$list; do \
+	    if test -f "$$i"; then echo $$i; else echo $(srcdir)/$$i; fi; \
+	  done | \
+	  $(AWK) '    { files[$$0] = 1; } \
+	       END { for (i in files) print i; }'`; \
+	test -z "$(CTAGS_ARGS)$$tags$$unique" \
+	  || $(CTAGS) $(CTAGSFLAGS) $(AM_CTAGSFLAGS) $(CTAGS_ARGS) \
+	     $$tags $$unique
+
+GTAGS:
+	here=`$(am__cd) $(top_builddir) && pwd` \
+	  && cd $(top_srcdir) \
+	  && gtags -i $(GTAGS_ARGS) $$here
+
+distclean-tags:
+	-rm -f TAGS ID GTAGS GRTAGS GSYMS GPATH tags
+DISTFILES = $(DIST_COMMON) $(DIST_SOURCES) $(TEXINFOS) $(EXTRA_DIST)
+
+top_distdir = ..
+distdir = $(top_distdir)/$(PACKAGE)-$(VERSION)
+
+distdir: $(DISTFILES)
+	@srcdirstrip=`echo "$(srcdir)" | sed 's|.|.|g'`; \
+	topsrcdirstrip=`echo "$(top_srcdir)" | sed 's|.|.|g'`; \
+	list='$(DISTFILES)'; for file in $$list; do \
+	  case $$file in \
+	    $(srcdir)/*) file=`echo "$$file" | sed "s|^$$srcdirstrip/||"`;; \
+	    $(top_srcdir)/*) file=`echo "$$file" | sed "s|^$$topsrcdirstrip/|$(top_builddir)/|"`;; \
+	  esac; \
+	  if test -f $$file || test -d $$file; then d=.; else d=$(srcdir); fi; \
+	  dir=`echo "$$file" | sed -e 's,/[^/]*$$,,'`; \
+	  if test "$$dir" != "$$file" && test "$$dir" != "."; then \
+	    dir="/$$dir"; \
+	    $(mkinstalldirs) "$(distdir)$$dir"; \
+	  else \
+	    dir=''; \
+	  fi; \
+	  if test -d $$d/$$file; then \
+	    if test -d $(srcdir)/$$file && test $$d != $(srcdir); then \
+	      cp -pR $(srcdir)/$$file $(distdir)$$dir || exit 1; \
+	    fi; \
+	    cp -pR $$d/$$file $(distdir)$$dir || exit 1; \
+	  else \
+	    test -f $(distdir)/$$file \
+	    || cp -p $$d/$$file $(distdir)/$$file \
+	    || exit 1; \
+	  fi; \
+	done
+check-am: all-am
+check: check-am
+all-am: Makefile $(LIBRARIES)
+
+installdirs:
+install: install-am
+install-exec: install-exec-am
+install-data: install-data-am
+uninstall: uninstall-am
+
+install-am: all-am
+	@$(MAKE) $(AM_MAKEFLAGS) install-exec-am install-data-am
+
+installcheck: installcheck-am
+install-strip:
+	$(MAKE) $(AM_MAKEFLAGS) INSTALL_PROGRAM="$(INSTALL_STRIP_PROGRAM)" \
+	  INSTALL_STRIP_FLAG=-s \
+	  `test -z '$(STRIP)' || \
+	    echo "INSTALL_PROGRAM_ENV=STRIPPROG='$(STRIP)'"` install
+mostlyclean-generic:
+
+clean-generic:
+
+distclean-generic:
+	-rm -f Makefile $(CONFIG_CLEAN_FILES)
+
+maintainer-clean-generic:
+	@echo "This command is intended for maintainers to use"
+	@echo "it deletes files that may require special tools to rebuild."
+clean: clean-am
+
+clean-am: clean-generic clean-noinstLIBRARIES mostlyclean-am
+
+distclean: distclean-am
+
+distclean-am: clean-am distclean-compile distclean-depend \
+	distclean-generic distclean-tags
+
+dvi: dvi-am
+
+dvi-am:
+
+info: info-am
+
+info-am:
+
+install-data-am:
+
+install-exec-am:
+
+install-info: install-info-am
+
+install-man:
+
+installcheck-am:
+
+maintainer-clean: maintainer-clean-am
+
+maintainer-clean-am: distclean-am maintainer-clean-generic
+
+mostlyclean: mostlyclean-am
+
+mostlyclean-am: mostlyclean-compile mostlyclean-generic
+
+pdf: pdf-am
+
+pdf-am:
+
+ps: ps-am
+
+ps-am:
+
+uninstall-am: uninstall-info-am
+
+.PHONY: CTAGS GTAGS all all-am check check-am clean clean-generic \
+	clean-noinstLIBRARIES ctags distclean distclean-compile \
+	distclean-depend distclean-generic distclean-tags distdir dvi \
+	dvi-am info info-am install install-am install-data \
+	install-data-am install-exec install-exec-am install-info \
+	install-info-am install-man install-strip installcheck \
+	installcheck-am installdirs maintainer-clean \
+	maintainer-clean-generic mostlyclean mostlyclean-compile \
+	mostlyclean-generic pdf pdf-am ps ps-am tags uninstall \
+	uninstall-am uninstall-info-am
+
+# Tell versions [3.59,3.63) of GNU make to not export all variables.
+# Otherwise a system limit (for SysV at least) may be exceeded.
+.NOEXPORT:
diff --git a/libbanshee/libcompat/alloc.c b/libbanshee/libcompat/alloc.c
new file mode 100644
index 00000000000..7f2cfd369b2
--- /dev/null
+++ b/libbanshee/libcompat/alloc.c
@@ -0,0 +1,133 @@
+/*
+ * Copyright (c) 1999-2001
+ *      The Regents of the University of California.  All rights reserved.
+ *
+ * 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. Neither the name of the University 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 REGENTS 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 REGENTS 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.
+ *
+ */
+/* TBD: recover unusued portions of pages for use as individual pages */
+
+#include <stddef.h>
+#include "regions.h"
+
+static void alloc_block(region r, struct allocator *a, struct ablock *blk,
+		 void **p1, int s1, int a1, void **p2, int s2, int a2,
+		 size_t blksize, int needsclear)
+{
+  struct page *newp;
+  char *mem1, *mem2;
+  
+  mem1 = PALIGN(blk->allocfrom, a1);
+  mem2 = PALIGN(mem1 + s1, a2);
+
+  /* Can't use last byte of page (pointers to the byte after an object are
+     valid) */
+  if (mem2 + s2 >= blk->base + blksize)
+    {
+      if (blksize == RPAGESIZE)
+	{
+	  newp = alloc_single_page(a->pages);
+	  a->pages = newp;
+	  blk->allocfrom = (char *)newp + offsetof(struct page, previous);
+	  set_region(newp, 1, r);
+	}
+      else
+	{
+	  newp = alloc_pages(blksize >> RPAGELOG, a->bigpages);
+	  a->bigpages = newp;
+	  blk->allocfrom = (char *)newp + offsetof(struct page, previous);
+	  set_region(newp, blksize >> RPAGELOG, r);
+	}
+      blk->base = (char *)newp;
+
+      if (needsclear)
+	preclear(blk->allocfrom, blksize - (blk->allocfrom - (char *)newp));
+      mem1 = PALIGN(blk->allocfrom, a1);
+      mem2 = PALIGN(mem1 + s1, a2);
+    }
+
+  ASSERT_INUSE(blk->base, r);
+  blk->allocfrom = mem2 + s2;
+
+  *p1 = mem1;
+  *p2 = mem2;
+}
+
+void qalloc(region r, struct allocator *a, void **p1, int s1, int a1,
+	    void **p2, int s2, int a2, int needsclear)
+{
+  struct page *p;
+  char *mem;
+  int npages;
+  int n = ALIGN(s1, a2) + s2; /* Yes, this is correct (see alloc_block) */
+
+  if (n <= RPAGESIZE / K)
+    {
+      alloc_block(r, a, &a->page, p1, s1, a1, p2, s2, a2, RPAGESIZE,
+		  needsclear);
+      return;
+    }
+  if (n <= RPAGESIZE)
+    {
+      alloc_block(r, a, &a->superpage, p1, s1, a1, p2, s2, a2,
+		  K * RPAGESIZE, needsclear);
+      return;
+    }
+  if (n <= RPAGESIZE * K)
+    {
+      alloc_block(r, a, &a->hyperpage, p1, s1, a1, p2, s2, a2,
+		  K * K * RPAGESIZE, needsclear);
+      return;
+    }
+
+  npages = (n + ALIGN(offsetof(struct page, previous), a1) + RPAGESIZE - 1)
+    >> RPAGELOG;
+  p = alloc_pages(npages, a->bigpages);
+  a->bigpages = p;
+  set_region(p, npages, r);
+
+  mem = (char *)p + offsetof(struct page, previous);
+  *p1 = PALIGN(mem, a1);
+  *p2 = PALIGN((char *) *p1 + s1, a2);
+  if (needsclear)
+    preclear(*p2, s2);
+}
+
+void free_all_pages(region r, struct allocator *a)
+/* Assumes freepages_lock held */
+{
+  struct page *p, *next;
+
+  for (p = a->pages; p; p = next)
+    {
+      next = p->next;
+      free_single_page(r, p);
+    }
+  for (p = a->bigpages; p; p = next)
+    {
+      next = p->next;
+      free_pages(r, p);
+    }
+}
diff --git a/libbanshee/libcompat/pages.c b/libbanshee/libcompat/pages.c
new file mode 100644
index 00000000000..9e85e9baef0
--- /dev/null
+++ b/libbanshee/libcompat/pages.c
@@ -0,0 +1,459 @@
+/*
+ * Copyright (c) 1999-2001
+ *      The Regents of the University of California.  All rights reserved.
+ *
+ * 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. Neither the name of the University 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 REGENTS 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 REGENTS 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.
+ *
+ */
+#include <limits.h>
+
+typedef __rcintptr pageid;
+
+#if 0
+#define FREEPAGE ((region)-1) /* Id of a free page */
+#else
+#define FREEPAGE (&zeroregion)
+#endif
+#ifdef NMEMDEBUG
+#define ASSERT_FREE(p) 
+#define ASSERT_INUSE(p, r) 
+#else
+#define ASSERT_FREE(p) assert(regionof(p) == FREEPAGE)
+#ifdef DUPLICATES
+#define ASSERT_INUSE(p, r) assert(regionof(p) == r->base)
+#else
+#define ASSERT_INUSE(p, r) assert(regionof(p) == r)
+#endif
+#endif
+
+/* Page allocator for region-based memory management */
+/* TBD: special free list for size == K ?? */
+
+#define PAGECOUNTBITS (CHAR_BIT * sizeof(pageid) - 1)
+
+struct page
+{
+  /* Next page in region or in free list */
+  struct page *next;
+
+  /* Doubly linked list of pages sorted by address */
+  struct page *next_address, *prev_address;
+
+  /* number of pages in this allocation unit. Negative for free pages. */
+  pageid pagecount : PAGECOUNTBITS;
+
+  unsigned int free : 1;
+
+  /* Only in free pages not in the single_pages list */
+  struct page *previous;
+};
+
+/* The pages are kept in a single list sorted by address via the
+   next_address and prev_address fields. The first page's prev_address and
+   the last page's next_address fields points to pages_byaddress.
+   page_byaddress.next_address is the first page
+   page_byaddress.prev_address is the last page
+
+   This list is used for coalescing operations.
+*/
+static struct page pages_byaddress;
+
+struct page *alloc_single_page(struct page *next);
+void free_single_page(region r, struct page *p);
+
+struct page *alloc_pages(int n, struct page *next);
+void free_pages(region r, struct page *p);
+
+
+/* a list of free individual pages */
+struct page *single_pages;
+
+/* free pages (not including those in single_pages) */
+struct page *unused_pages;
+
+static void init_pages(void)
+{
+  pages_byaddress.next_address = &pages_byaddress;
+  pages_byaddress.prev_address = &pages_byaddress;
+}
+
+static void insertbefore_address(struct page *p, struct page *before)
+{
+  p->prev_address = before->prev_address;
+  p->next_address = before;
+  before->prev_address = p;
+  p->prev_address->next_address = p;
+}
+
+static void unlink_address(struct page *p)
+{
+  p->prev_address->next_address = p->next_address;
+  p->next_address->prev_address = p->prev_address;
+}
+
+static void addbyaddress(struct page *p)
+{
+  struct page *address_scan;
+
+  /* Warning: this is slow. Calls to it should not be frequent (once app
+     reaches a steady state of memory usage). */
+
+  for (address_scan = pages_byaddress.next_address; ;
+       address_scan = address_scan->next_address)
+    if (p < address_scan || address_scan == &pages_byaddress)
+      {
+	insertbefore_address(p, address_scan);
+	return;
+      }
+}
+
+/* Doubly linked page list management */
+void addfront(struct page **list, struct page *p)
+/* Effects: Adds p to the front of doubly-linked list list */
+{
+  p->previous = NULL;
+  p->next = *list;
+  if (*list) (*list)->previous = p;
+  *list = p;
+}
+
+void unlink_page(struct page **list, struct page *p)
+/* Effects: Remove p from its doubly linked list */
+{
+  if (p->previous)
+    p->previous->next = p->next;
+  else
+    *list = p->next;
+  if (p->next)
+    p->next->previous = p->previous;
+}
+
+void *region_get_mem(size_t s)
+{
+  void *mem = malloc(s + RPAGESIZE - 1);
+
+  return (void *)ALIGN((__rcintptr)mem, RPAGESIZE);
+}
+
+/* Page to region map management */
+/* ----------------------------- */
+
+RADIX_TREE(__rcregionmap);
+
+static void set_page_region(pageid pagenb, region r)
+{
+  radix_tree_delete (&__rcregionmap, pagenb);
+  radix_tree_insert (&__rcregionmap, pagenb, r);
+}
+
+#define page_region(pagenb) (radix_tree_lookup (&__rcregionmap, (pagenb)))
+
+void set_region(struct page *p, int npages, region r)
+{
+  pageid pnb = PAGENB(p);
+
+  while (npages-- > 0) 
+    set_page_region(pnb++, r);
+}
+
+/* Mark the memory range from 'from' (inclusive) to 'to' (exclusive)
+   as belonging to region with id 'rid' */
+void set_region_range(void *from, void *to, region r)
+{
+  pageid first = PAGENB(from), last = PAGENB((pageid)to - 1);
+
+  while (first <= last)
+    set_page_region(first++, r);
+}
+
+/* Multi-page allocation management */
+/* -------------------------------- */
+
+struct page *alloc_new(int n, struct page *next)
+/* Assumes freepages_lock held */
+{
+  struct page *newp = region_get_mem(n << RPAGELOG);
+
+  if (!newp)
+    {
+      if (nomem_h)
+	nomem_h();
+      abort();
+    }
+  assert(!((long)newp & (RPAGESIZE - 1)));
+
+  newp->next = next;
+  newp->pagecount = n;
+  newp->free = 0;
+  addbyaddress(newp);
+#ifndef NMEMDEBUG
+  {
+    pageid i, pnb = PAGENB(newp);
+
+    for (i = pnb; i < pnb + n; i++)
+      set_page_region(i, FREEPAGE);
+  }
+#endif
+
+  return newp;
+}
+
+struct page *alloc_split(struct page *split, int n, struct page *next)
+/* Assumes freepages_lock held */
+{
+#ifndef NMEMDEBUG
+  /* These pages had better be free */
+  pageid i, pnb = PAGENB(split);
+
+  assert(split->pagecount >= n);
+  for (i = pnb; i < pnb + split->pagecount; i++)
+    assert(page_region(i) == FREEPAGE);
+#endif
+  if (split->pagecount > n)
+    {
+      struct page *splitoff;
+
+      /* Keep first part of block */
+      split->pagecount -= n;
+      /* Return latter part of block */
+      splitoff = split;
+      split = (struct page *)((char *)split + (split->pagecount << RPAGELOG));
+
+      /* Update the by adress list */
+      insertbefore_address(split, splitoff->next_address);
+    }
+  else
+    {
+      /* remove split from list */
+      unlink_page(&unused_pages, split);
+    }
+  split->next = next;
+  split->pagecount = n;
+  split->free = 0;
+
+  return split;
+}
+
+struct page *alloc_pages(int n, struct page *next)
+{
+  struct page *best;
+  int bestn;
+  struct page *scan;
+
+  assert(n >= K);
+
+  scan = unused_pages;
+  /* Find first fit */
+  for (;;)
+    {
+      if (!scan)
+	return alloc_new(n, next);
+
+      if (scan->pagecount >= n) break;
+      scan = scan->next;
+    }
+
+  /* Now find best fit */
+  best = scan;
+  bestn = scan->pagecount;
+  for (;;)
+    {
+      scan = scan->next;
+      if (!scan)
+	return alloc_split(best, n, next);
+
+      if (scan->pagecount >=n && scan->pagecount < bestn)
+	{
+	  best = scan;
+	  bestn = scan->pagecount;
+	}
+    }
+}
+
+static void coalesce(struct page *p)
+{
+  struct page *prev = p->prev_address, *next;
+
+  p->free = 1;
+
+  /* Coalesce with predecessor ? */
+  if (prev->free && (char *)prev + (prev->pagecount << RPAGELOG) == (char *)p)
+    {
+      prev->pagecount += p->pagecount;
+      unlink_address(p);
+      p = prev;
+    }
+  else /* No, add to free pages list */
+    addfront(&unused_pages, p);
+
+  next = p->next_address;
+  /* Coalesce with successor ? */
+  if (next->free && (char *)p + (p->pagecount << RPAGELOG) == (char *)next)
+    {
+      unlink_page(&unused_pages, next);
+      p->pagecount += next->pagecount;
+      unlink_address(next);
+    }
+}
+
+void free_pages(region r, struct page *p)
+/* Assumes freepages_lock held */
+{
+#ifndef NMEMDEBUG
+  pageid i, pnb = PAGENB(p);
+
+  for (i = pnb; i < pnb + p->pagecount; i++)
+    {
+      assert(page_region(i) == r);
+      set_page_region(i, FREEPAGE);
+    }
+#endif
+
+  coalesce(p);
+}
+
+
+/* Single page management */
+/* ---------------------- */
+
+static int single_page_count;
+
+static void add_single_pages(struct page *base)
+/* Effects: Adds pages at base to the single_pages list */
+{
+  pageid n = base->pagecount;
+  struct page *prev = base->prev_address, *basenext = base->next_address,
+    *next;
+
+  single_page_count += n;
+
+  for (;;)
+    {
+      ASSERT_FREE(base);
+      base->free = 0; /* Not free so that coalesce won't steal these back */
+      base->prev_address = prev;
+      prev = base;
+      base->next = single_pages;
+      single_pages = base;
+      if (--n == 0)
+	break;
+      next = (struct page *)((char *)base + RPAGESIZE);
+      base->next_address = next;
+      base = next;
+    }
+  base->next_address = basenext;
+  basenext->prev_address = base;
+}
+
+void scavenge_single_pages(int n)
+{
+  /* Add n pages to the single_pages list */
+  struct page *scan, *best;
+  __rcintptr bestn;
+
+  /* Take any group in unused_pages that is <= n or < K.
+     Remember smallest entry > n too. This is sortof equivalent to
+     a best fit where we allow partial allocations to make up a whole */
+  best = NULL;
+  bestn = (__rcintptr)1 << (sizeof(__rcintptr) * CHAR_BIT - 2);
+  scan = unused_pages;
+  while (scan)
+    {
+      /* The pages < K can't be used for anything but single pages so we
+	 might as well grab them even if they are a little too big */
+      if (scan->pagecount <= n || scan->pagecount < K)
+	{
+	  struct page *adding = scan;
+
+	  scan = scan->next;
+	  n -= adding->pagecount;
+	  unlink_page(&unused_pages, adding);
+	  add_single_pages(adding);
+	  if (n <= 0) return;
+	}
+      else
+	{
+	  if (scan->pagecount < bestn)
+	    {
+	      bestn = scan->pagecount;
+	      best = scan;
+	    }
+	  scan = scan->next;
+	}
+    }
+  /* Still not enough. Split the best block if there is one, allocate
+     new pages otherwise */
+  if (!best)
+    add_single_pages(alloc_new(n, NULL));
+  else if (best->pagecount - n < K)
+    {
+      unlink_page(&unused_pages, best);
+      add_single_pages(best);
+    }
+  else
+    add_single_pages(alloc_split(best, n, NULL));
+}
+
+struct page *alloc_single_page(struct page *next)
+{
+  struct page *p;
+
+  if (!single_pages)
+    {
+      scavenge_single_pages(PAGE_GROUP_SIZE);
+    }
+  ASSERT_FREE(single_pages);
+  p = single_pages;
+  single_pages = p->next;
+  p->next = next;
+
+  single_page_count--;
+
+  return p;
+}
+
+void free_single_page(region r, struct page *p)
+/* Assumes freepages_lock held */
+{
+#ifndef NMEMDEBUG
+  ASSERT_INUSE(p, r);
+  set_page_region(PAGENB(p), FREEPAGE);
+#endif
+
+  /* Once free list is big enough just coalesce the pages.
+     The actual threshold to use might merit further study (something
+     adaptive ? e.g., proportional to allocated single pages) */
+  if (single_page_count > PAGE_GROUP_SIZE * 2)
+    {
+      p->pagecount = 1;
+      coalesce(p);
+    }
+  else
+    {
+      p->next = single_pages;
+      single_pages = p;
+      single_page_count++;
+    }
+}
diff --git a/libbanshee/libcompat/profile.c b/libbanshee/libcompat/profile.c
new file mode 100644
index 00000000000..0a30a55e41e
--- /dev/null
+++ b/libbanshee/libcompat/profile.c
@@ -0,0 +1,521 @@
+/*
+ * Copyright (c) 1999-2001
+ *      The Regents of the University of California.  All rights reserved.
+ *
+ * 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. Neither the name of the University 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 REGENTS 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 REGENTS 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.
+ *
+ */
+
+#include <assert.h>
+#include <string.h>
+#include <unistd.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <sys/types.h>
+#include <signal.h>
+#undef REGION_PROFILE
+#include "regions.h"
+#include "profile.h"
+
+typedef struct Alloc_info
+{
+  struct Alloc_info *next;
+  char *file;
+  int line;
+  unsigned long size;
+  unsigned long calls;
+} *ainfo;
+
+static ainfo ainfos = NULL;
+static region profile_region = NULL;
+
+/* perror(s) then exit */
+void pfail(const char *s)
+{
+  perror(s);
+  exit(EXIT_FAILURE);
+}
+
+/**************************************************************************
+ *                                                                        *
+ * Log information about an allocation -- generic                         *
+ *                                                                        *
+ **************************************************************************/
+
+static int registered_exit = 0;
+
+static ainfo find_ainfo(char *file, int line)
+{
+  ainfo ai;
+
+  for (ai = ainfos; ai; ai = ai->next)
+    if (line == ai->line && !strcmp(file, ai->file))
+      return ai;
+
+  if (!registered_exit)
+    {
+      if (atexit(profile))
+	fprintf(stderr, "Registration of profile at exit failed\n");
+      registered_exit = 1;
+    }
+
+  if (!profile_region)
+    profile_region = newregion();
+  ai = ralloc(profile_region, struct Alloc_info);
+  ai->file = file;
+  ai->line = line;
+  ai->size = 0;
+  ai->calls = 0;
+  ai->next = ainfos;
+  ainfos = ai;
+  return ai;
+}
+
+/**************************************************************************
+ *                                                                        *
+ * Log information about an allocation -- GCC                             *
+ *                                                                        *
+ * WARNING:  This code uses __builtin_return_address, a non-portable      *
+ * feature of gcc, to trace the call chain back.   You'll also get ugly   *
+ * output unless the addr2line (in GNU binutils) is installed.            *
+ *                                                                        *
+ * ANOTHER WARNING:  The depths hard-coded in find_cinfo are only correct *
+ * if find_cinfo is inlined.  Ack!                                        *
+ *                                                                        *
+ **************************************************************************/
+
+#define REGION_PROFILE_DEPTH 2
+#undef TRACE_STACK
+#if defined(__GNUC__) && defined(__OPTIMIZE__) && REGION_PROFILE_DEPTH > 1
+#define TRACE_STACK
+#endif
+
+#ifdef TRACE_STACK
+
+#if REGION_PROFILE_DEPTH > 6
+#error "REGION_PROFILE_DEPTH must be less than 6.  See find_cinfo()."
+#endif
+
+typedef struct Call_info
+{
+  struct Call_info *next;
+  void **stack;         /* Array holding the call chain */
+  unsigned long size;
+  unsigned long calls;
+} *cinfo;
+
+static cinfo cinfos = NULL;
+
+/* Find the current call chain and return a pointer to our status for
+   it, or allocate a new entry if there is none. */
+static cinfo find_cinfo(void)
+{
+  void *calls[REGION_PROFILE_DEPTH];
+  int i;
+  cinfo ci;
+
+  /* Compute the call chain.  This is an awful hack. */
+  i = 0;
+  if (i < REGION_PROFILE_DEPTH)
+    calls[i++] = __builtin_return_address(1);
+  if (i < REGION_PROFILE_DEPTH)
+    calls[i++] = __builtin_return_address(2);
+  if (i < REGION_PROFILE_DEPTH)
+    calls[i++] = __builtin_return_address(3);
+  if (i < REGION_PROFILE_DEPTH)
+    calls[i++] = __builtin_return_address(4);
+  if (i < REGION_PROFILE_DEPTH)
+    calls[i++] = __builtin_return_address(5);
+  if (i < REGION_PROFILE_DEPTH)
+    calls[i++] = __builtin_return_address(6);
+  /* Add more if you want a higher call-depth (why would you?) */
+
+  /* Find it */
+  for (ci = cinfos; ci; ci = ci->next)
+    if (!memcmp(calls, ci->stack, REGION_PROFILE_DEPTH*sizeof(void *)))
+      return ci;
+
+  if (!profile_region)
+    profile_region = newregion();
+  ci = ralloc(profile_region, struct Call_info);
+  ci->stack = rarrayalloc(profile_region, REGION_PROFILE_DEPTH, void *);
+  memcpy(ci->stack, calls, REGION_PROFILE_DEPTH*sizeof(void *));
+  ci->size = 0;
+  ci->calls = 0;
+  ci->next = cinfos;
+  cinfos = ci;
+  return ci;
+  
+}
+#endif
+
+static void add_alloc(char *file, int line, int size)
+{
+  ainfo ai = find_ainfo(file, line);
+  ai->calls++;
+  ai->size += size;
+#ifdef TRACE_STACK
+  {
+    cinfo ci;
+
+    ci = find_cinfo();
+    ci->calls++;
+    ci->size += size;
+  }
+#endif
+}
+
+/**************************************************************************
+ *                                                                        *
+ * Intercept and log calls to region library                              *
+ *                                                                        *
+ **************************************************************************/
+
+void *profile_typed_ralloc(region r, size_t size, type_t type, char *file,
+			   int line)
+{
+  add_alloc(file, line, size);
+  return typed_ralloc(r, size, type);
+}
+
+void *profile_typed_rarrayalloc(region r, size_t n, size_t size, type_t type,
+				char *file, int line)
+{
+  add_alloc(file, line, n*size);
+  return typed_rarrayalloc(r, n, size, type);
+}
+
+void *profile_typed_rarrayextend(region r, void *old, size_t n, size_t size,
+				 type_t type, char *file, int line)
+{
+  add_alloc(file, line, n*size); /* XXX: Fix */
+  return typed_rarrayextend(r, old, n, size, type);
+}
+
+char *profile_rstralloc(region r, size_t size, char *file, int line)
+{
+  add_alloc(file, line, size);
+  return rstralloc(r, size);
+}
+
+char *profile_rstralloc0(region r, size_t size, char *file, int line)
+{
+  add_alloc(file, line, size);
+  return rstralloc0(r, size);
+}
+
+char *profile_rstrdup(region r, const char *s, char *file, int line)
+{
+  add_alloc(file, line, strlen(s));
+  return rstrdup(r, s);
+}
+
+char *profile_rstrextend(region r, const char *old, size_t newsize,
+			 char *file, int line)
+{
+  add_alloc(file, line, newsize); /* XXX: Fix */
+  return rstrextend(r, old, newsize);
+}
+
+char *profile_rstrextend0(region r, const char *old, size_t newsize,
+			  char *file, int line)
+{
+  add_alloc(file, line, newsize); /* XXX: Fix */
+  return rstrextend0(r, old, newsize);
+}
+
+/**************************************************************************
+ *                                                                        *
+ * Display results -- generic                                             *
+ *                                                                        *
+ **************************************************************************/
+
+static FILE *out = NULL;
+
+/* Generic list -- used for generic sorting.  Note that next field is
+   at the top. */
+typedef struct List
+{
+  struct List *next;
+} *list;
+
+/* Sort a list.  cmp should sort in reverse order. */
+static list sort_list(list l, int (*cmp)(const void *, const void *))
+{
+  list cur, result;
+  list *sorted;
+  int i, length;
+  region temp_region;
+
+  /* Compute length of list */
+  for (cur = l, length = 0; cur; cur = cur->next, length++);
+
+  temp_region = newregion();
+  sorted = rarrayalloc(temp_region, length, list *);
+  for (cur = l, i = 0; cur; cur = cur->next)
+    sorted[i++] = cur;
+  qsort(sorted, length, sizeof(list *), cmp);
+
+  result = NULL;
+  for (i = 0; i < length; i++)
+    {
+      cur = result;
+      result = sorted[i];
+      result->next = cur;
+    }
+  deleteregion(temp_region);
+  return result;
+}
+
+
+typedef struct File_info
+{
+  struct File_info *next;
+  char *file;
+  unsigned long size;
+  unsigned long calls;
+  unsigned long sites;
+} *finfo;
+
+static finfo finfos = NULL;
+
+static int finfo_cmp(const void *a, const void *b)
+{
+  finfo *afi = (finfo *) a;
+  finfo *bfi = (finfo *) b;
+  return (*afi)->size - (*bfi)->size;  /* Reverse order */
+}
+
+static void print_finfos(void)
+{
+  finfo fi;
+  unsigned long size, sites, calls;
+
+  finfos = (finfo) sort_list((list) finfos, finfo_cmp);
+  size = sites = calls = 0;
+  fprintf(out, "        Bytes | Sites |    Calls | File\n");
+  fprintf(out, "  ------------+-------+----------+---------------------\n");
+  for (fi = finfos; fi; fi = fi->next)
+    {
+      size += fi->size;
+      sites += fi->sites;
+      calls += fi->calls;
+      fprintf(out, " %12lu | %5lu | %8lu | %s\n",
+	      fi->size, fi->sites, fi->calls, fi->file);
+    }
+  fprintf(out, "  ------------+-------+----------+---------------------\n");
+    fprintf(out, " %12lu | %5lu | %8lu | Total\n",
+	    size, sites, calls);
+
+}
+
+static int ainfo_cmp(const void *a, const void *b)
+{
+  ainfo *afi = (ainfo *) a;
+  ainfo *bfi = (ainfo *) b;
+  return (*afi)->size - (*bfi)->size;  /* Reverse order */
+}
+
+static void print_ainfos(void)
+{
+  ainfo ai;
+
+  unsigned long size, calls;
+
+  ainfos = (ainfo) sort_list((list) ainfos, ainfo_cmp);
+  size = calls = 0;
+  fprintf(out, "        Bytes |    Calls | Site\n");
+  fprintf(out, "  ------------+----------+---------------------\n");
+  for (ai = ainfos; ai; ai = ai->next)
+    {
+      size += ai->size;
+      calls += ai->calls;
+      fprintf(out, " %12lu | %8lu | %s:%d\n",
+	      ai->size, ai->calls, ai->file, ai->line);
+    }
+  fprintf(out, "  ------------+----------+---------------------\n");
+    fprintf(out, " %12lu | %8lu | Total\n",
+	    size, calls);
+}
+
+static finfo find_finfo(char *file)
+{
+  finfo fi;
+
+  for (fi = finfos; fi; fi = fi->next)
+    if (!strcmp(file, fi->file))
+      return fi;
+
+  fi = ralloc(profile_region, struct File_info);
+  fi->file = file;
+  fi->size = 0;
+  fi->calls = 0;
+  fi->sites = 0;
+  fi->next = finfos;
+  finfos = fi;
+  return fi;
+}
+
+static void gather_finfo(void)
+{
+  ainfo ai;
+
+  for (ai = ainfos; ai; ai = ai->next)
+    {
+      finfo fi = find_finfo(ai->file);
+      fi->size += ai->size;
+      fi->calls += ai->calls;
+      fi->sites++;
+    }
+}
+
+/**************************************************************************
+ *                                                                        *
+ * Display results -- GCC                                                 *
+ *                                                                        *
+ **************************************************************************/
+
+#ifdef TRACE_STACK
+
+pid_t child_pid = 0;
+int child_in[2], child_out[2]; /* pipes to child process */
+
+static void start_prettiness(void)
+{
+  if (pipe(child_in) || pipe(child_out))
+    pfail("Unable to open pipe to child process");
+  if (!(child_pid = fork()))
+    {
+      /* Child process */
+      pid_t parent_pid;
+      char filename[64];
+
+      if (dup2(child_in[0], STDIN_FILENO) == -1)
+	pfail("Unable to open pipe from parent");
+      close(child_in[0]);
+      close(child_in[1]);
+      if (dup2(child_out[1], STDOUT_FILENO) == -1)
+	pfail("Unable to open pipe to parent");
+      close(child_out[0]);
+      close(child_out[1]);
+
+      parent_pid = getppid();
+      snprintf(filename, 64, "/proc/%d/exe", parent_pid);
+      filename[63] = '\0';
+      execlp("addr2line", "addr2line", "-s", "-e", filename, 0);
+      fprintf(stderr, "Unable to fork addr2line\n");
+      exit(EXIT_FAILURE);
+    }
+  else
+    {
+      close(child_in[0]);
+      close(child_out[1]);
+    }
+}
+
+/* Turn p into a file:line string */
+static char *prettify(void *p)
+{
+#define BUFSIZE 1024
+  static char buf[BUFSIZE];
+  int size;
+
+  /*printf("To child: %p\n", p);*/
+  size = snprintf(buf, BUFSIZE, "%p\n", p);
+  write(child_in[1], buf, size);
+  size = read(child_out[0], buf, BUFSIZE - 1);
+  if (!size)
+    pfail("Unable to read from child process");
+  buf[size-1] = '\0'; /* Kill \n */
+  /*printf("Read: [%s]\n", buf);*/
+  return buf;
+}
+
+static void end_prettiness(void)
+{
+  if (child_pid)
+    kill(child_pid, SIGHUP);
+}
+
+static int cinfo_cmp(const void *a, const void *b)
+{
+  cinfo *aci = (cinfo *) a;
+  cinfo *bci = (cinfo *) b;
+  return (*aci)->size - (*bci)->size;  /* Reverse order */
+}
+
+/* Print the call chain information out to a file. */
+static void print_cinfos(void)
+{
+  cinfo ci;
+  unsigned long size, calls;
+  int i;
+
+  cinfos = (cinfo) sort_list((list) cinfos, cinfo_cmp);
+  size = calls = 0;
+  start_prettiness();
+  fprintf(out, "        Bytes |    Calls | Call Stack\n");
+  fprintf(out, "  ------------+----------+---------------------\n");
+  for (ci = cinfos; ci; ci = ci->next)
+    {
+      size += ci->size;
+      calls += ci->calls;
+      fprintf(out, " %12lu | %8lu | ", ci->size, ci->calls);
+      for (i = 0; i < REGION_PROFILE_DEPTH; i++)
+	fprintf(out, "%s ", prettify(ci->stack[i]));
+      fprintf(out, "\n");
+    }
+  fprintf(out, "  ------------+----------+---------------------\n");
+    fprintf(out, " %12lu | %8lu | Total\n",
+	    size, calls);
+    end_prettiness();
+}
+#endif
+
+
+void profile(void)
+{
+  if (profile_region == NULL)
+    return;
+
+  gather_finfo();
+
+  if (!(out = fopen("profile.out", "w")))
+    pfail("Unable to open profile.out");
+
+  fprintf(out, "---------------------------\n");
+  fprintf(out, "Region Library Memory Usage\n");
+  fprintf(out, "---------------------------\n\n");
+
+  print_finfos();
+  fprintf(out, "\n");
+  print_ainfos();
+#ifdef TRACE_STACK
+  fprintf(out, "\n");
+  print_cinfos();
+#endif
+
+  fclose(out);
+}
diff --git a/libbanshee/libcompat/profile.h b/libbanshee/libcompat/profile.h
new file mode 100644
index 00000000000..b07034e2191
--- /dev/null
+++ b/libbanshee/libcompat/profile.h
@@ -0,0 +1,59 @@
+/*
+ * Copyright (c) 1999-2001
+ *      The Regents of the University of California.  All rights reserved.
+ *
+ * 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. Neither the name of the University 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 REGENTS 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 REGENTS 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.
+ *
+ */
+#ifndef PROFILE_H
+#define PROFILE_H
+
+/* Should only be included in regions.h and profile.c */
+
+void *profile_typed_ralloc(region r, size_t size, type_t type, char *file, int line);
+void *profile_typed_rarrayalloc(region r, size_t n, size_t size, type_t type, char *file, int line);
+void *profile_typed_rarrayextend(region r, void *old, size_t n, size_t size, type_t type, char *file, int line);
+char *profile_rstralloc(region r, size_t size, char *file, int line);
+char *profile_rstralloc0(region r, size_t size, char *file, int line);
+char *profile_rstrdup(region r, const char *s, char *file, int line);
+char *profile_rstrextend(region r, const char *old, size_t newsize, char *file, int line);
+char *profile_rstrextend0(region r, const char *old, size_t newsize, char *file, int line);
+
+#ifdef REGION_PROFILE
+#define typed_ralloc(r, size, type) profile_typed_ralloc(r, size, type, __FILE__, __LINE__)
+#define typed_rarrayalloc(r, n, size, type) profile_typed_rarrayalloc(r, n, size, type, __FILE__, __LINE__)
+#define typed_rarrayextend(r, old, n, size, type) profile_typed_rarrayextend(r, old, n, size, type, __FILE__, __LINE__)
+
+#define rstralloc(r, size) profile_rstralloc(r, size, __FILE__, __LINE__)
+#define rstralloc0(r, size) profile_rstralloc0(r, size, __FILE__, __LINE__)
+#define rstrdup(r, s) profile_rstrdup(r, s, __FILE__, __LINE__)
+
+#define rstrextend(r, old, newsize) profile_rstrextend(r, old, newsize, __FILE__, __LINE__)
+#define rstrextend0(r, old, newsize) profile_rstrextend0(r, old, newsize, __FILE__, __LINE__)
+#endif
+
+void profile(void);
+
+#endif
diff --git a/libbanshee/libcompat/radix-tree.c b/libbanshee/libcompat/radix-tree.c
new file mode 100644
index 00000000000..18f8929ad2d
--- /dev/null
+++ b/libbanshee/libcompat/radix-tree.c
@@ -0,0 +1,364 @@
+/*
+ * Modified to work in GCC in 2003 by Daniel Berlin 
+ * Copyright (C) 2001 Momchil Velikov
+ * Portions Copyright (C) 2001 Christoph Hellwig
+ *
+ * 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 2, 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, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ */
+#include <unistd.h>
+#include <stdio.h>
+#include <errno.h>
+#include <stdlib.h>
+#include  "radix-tree.h"
+#define ARRAY_SIZE(a) (sizeof (a) / sizeof ((a)[0]))
+/*
+ * Radix tree node definition.
+ */
+#define RADIX_TREE_MAP_SHIFT  6
+#define RADIX_TREE_MAP_SIZE  (1UL << RADIX_TREE_MAP_SHIFT)
+#define RADIX_TREE_MAP_MASK  (RADIX_TREE_MAP_SIZE-1)
+
+struct radix_tree_node {
+  unsigned int	count;
+  void		*slots[RADIX_TREE_MAP_SIZE];
+};
+
+struct radix_tree_path {
+  struct radix_tree_node *node, **slot;
+};
+
+#define RADIX_TREE_INDEX_BITS  (8 /* CHAR_BIT */ * sizeof(unsigned long))
+#define RADIX_TREE_MAX_PATH (RADIX_TREE_INDEX_BITS/RADIX_TREE_MAP_SHIFT + 2)
+
+static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH];
+
+
+/*
+ * This assumes that the caller has performed appropriate preallocation, and
+ * that the caller has pinned this thread of control to the current CPU.
+ */
+static struct radix_tree_node *
+radix_tree_node_alloc(struct radix_tree_root *root)
+{
+  struct radix_tree_node *ret;
+  
+  ret = (struct radix_tree_node *)
+    calloc (1, sizeof (struct radix_tree_node));
+  if (!ret)
+    abort ();
+  return ret;
+}
+
+static inline void
+radix_tree_node_free(struct radix_tree_node *node)
+{
+  free (node);
+}
+
+
+/*
+ *	Return the maximum key which can be store into a
+ *	radix tree with height HEIGHT.
+ */
+static inline unsigned long radix_tree_maxindex(unsigned int height)
+{
+  return height_to_maxindex[height];
+}
+
+/*
+ *	Extend a radix tree so it can store key @index.
+ */
+static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
+{
+  struct radix_tree_node *node;
+  unsigned int height;
+  
+  /* Figure out what the height should be.  */
+  height = root->height + 1;
+  while (index > radix_tree_maxindex(height))
+    height++;
+  
+  if (root->rnode) {
+    do {
+      if (!(node = radix_tree_node_alloc(root)))
+	return -ENOMEM;
+      
+      /* Increase the height.  */
+      node->slots[0] = root->rnode;
+      node->count = 1;
+      root->rnode = node;
+      root->height++;
+    } while (height > root->height);
+  } else 
+    root->height = height;
+  
+  return 0;
+}
+
+/**
+ *	radix_tree_insert    -    insert into a radix tree
+ *	@root:		radix tree root
+ *	@index:		index key
+ *	@item:		item to insert
+ *
+ *	Insert an item into the radix tree at position @index.
+ */
+int radix_tree_insert(struct radix_tree_root *root, unsigned long index,
+		      void *item)
+{
+  struct radix_tree_node *node = NULL, *tmp, **slot;
+  unsigned int height, shift;
+  int error;
+  
+  /* Make sure the tree is high enough.  */
+  if (index > radix_tree_maxindex(root->height)) {
+    error = radix_tree_extend(root, index);
+    if (error)
+      return error;
+  }
+  
+  slot = &root->rnode;
+  height = root->height;
+  shift = (height-1) * RADIX_TREE_MAP_SHIFT;
+  
+  while (height > 0) {
+    if (*slot == NULL) {
+      /* Have to add a child node.  */
+      if (!(tmp = radix_tree_node_alloc(root)))
+	return -ENOMEM;
+      *slot = tmp;
+      if (node)
+	node->count++;
+    }
+    
+    /* Go a level down.  */
+    node = *slot;
+    slot = (struct radix_tree_node **)
+      (node->slots + ((index >> shift) & RADIX_TREE_MAP_MASK));
+    shift -= RADIX_TREE_MAP_SHIFT;
+    height--;
+  }
+  
+  if (*slot != NULL)
+    return -EEXIST;
+  if (node)
+    node->count++;
+  
+  *slot = item;
+  return 0;
+}
+
+/**
+ *	radix_tree_lookup    -    perform lookup operation on a radix tree
+ *	@root:		radix tree root
+ *	@index:		index key
+ *
+ *	Lookup them item at the position @index in the radix tree @root.
+ */
+void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
+{
+  unsigned int height, shift;
+  struct radix_tree_node **slot;
+  
+  height = root->height;
+  if (index > radix_tree_maxindex(height))
+    return NULL;
+  
+  shift = (height-1) * RADIX_TREE_MAP_SHIFT;
+  slot = &root->rnode;
+  
+  while (height > 0) {
+    if (*slot == NULL)
+      return NULL;
+    
+    slot = (struct radix_tree_node **)
+      ((*slot)->slots + ((index >> shift) & RADIX_TREE_MAP_MASK));
+    shift -= RADIX_TREE_MAP_SHIFT;
+    height--;
+  }
+  
+  return (void *) *slot;
+}
+
+static /* inline */ unsigned int
+__lookup(struct radix_tree_root *root, void **results, unsigned long index,
+	 unsigned int max_items, unsigned long *next_index)
+{
+  unsigned int nr_found = 0;
+  unsigned int shift;
+  unsigned int height = root->height;
+  struct radix_tree_node *slot;
+  
+  shift = (height-1) * RADIX_TREE_MAP_SHIFT;
+  slot = root->rnode;
+  
+  while (height > 0) {
+    unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK;
+    
+    for ( ; i < RADIX_TREE_MAP_SIZE; i++) {
+      if (slot->slots[i] != NULL)
+	break;
+      index &= ~((1 << shift) - 1);
+      index += 1 << shift;
+      if (index == 0)
+	goto out;	/* 32-bit wraparound */
+    }
+    if (i == RADIX_TREE_MAP_SIZE)
+      goto out;
+    height--;
+    if (height == 0) {	/* Bottom level: grab some items */
+      unsigned long j = index & RADIX_TREE_MAP_MASK;
+      
+      for ( ; j < RADIX_TREE_MAP_SIZE; j++) {
+	index++;
+	if (slot->slots[j]) {
+	  results[nr_found++] = slot->slots[j];
+	  if (nr_found == max_items)
+	    goto out;
+	}
+      }
+    }
+    shift -= RADIX_TREE_MAP_SHIFT;
+    slot = slot->slots[i];
+  }
+ out:
+  *next_index = index;
+  return nr_found;
+}
+
+/**
+ *	radix_tree_gang_lookup - perform multiple lookup on a radix tree
+ *	@root:		radix tree root
+ *	@results:	where the results of the lookup are placed
+ *	@first_index:	start the lookup from this key
+ *	@max_items:	place up to this many items at *results
+ *
+ *	Performs an index-ascending scan of the tree for present items.  Places
+ *	them at *@results and returns the number of items which were placed at
+ *	*@results.
+ *
+ *	The implementation is naive.
+ */
+unsigned int
+radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
+		       unsigned long first_index, unsigned int max_items)
+{
+  const unsigned long max_index = radix_tree_maxindex(root->height);
+  unsigned long cur_index = first_index;
+  unsigned int ret = 0;
+  
+  if (root->rnode == NULL)
+    goto out;
+  if (max_index == 0) {			/* Bah.  Special case */
+    if (first_index == 0) {
+      if (max_items > 0) {
+	*results = root->rnode;
+	ret = 1;
+      }
+    }
+    goto out;
+  }
+  while (ret < max_items) {
+    unsigned int nr_found;
+    unsigned long next_index;	/* Index of next search */
+    
+    if (cur_index > max_index)
+      break;
+    nr_found = __lookup(root, results + ret, cur_index,
+			max_items - ret, &next_index);
+    ret += nr_found;
+    if (next_index == 0)
+      break;
+    cur_index = next_index;
+  }
+ out:
+  return ret;
+}
+
+/**
+ *	radix_tree_delete    -    delete an item from a radix tree
+ *	@root:		radix tree root
+ *	@index:		index key
+ *
+ *	Remove the item at @index from the radix tree rooted at @root.
+ *
+ *	Returns the address of the deleted item, or NULL if it was not present.
+ */
+void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
+{
+  struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path;
+  unsigned int height, shift;
+  void *ret = NULL;
+  
+  height = root->height;
+  if (index > radix_tree_maxindex(height))
+    goto out;
+  
+  shift = (height-1) * RADIX_TREE_MAP_SHIFT;
+  pathp->node = NULL;
+  pathp->slot = &root->rnode;
+  
+  while (height > 0) {
+    if (*pathp->slot == NULL)
+      goto out;
+    
+    pathp[1].node = *pathp[0].slot;
+    pathp[1].slot = (struct radix_tree_node **)
+      (pathp[1].node->slots + ((index >> shift) & RADIX_TREE_MAP_MASK));
+    pathp++;
+    shift -= RADIX_TREE_MAP_SHIFT;
+    height--;
+  }
+  
+  ret = *pathp[0].slot;
+  if (ret == NULL)
+    goto out;
+  
+  *pathp[0].slot = NULL;
+  while (pathp[0].node && --pathp[0].node->count == 0) {
+    pathp--;
+    *pathp[0].slot = NULL;
+    radix_tree_node_free(pathp[1].node);
+  }
+  
+  if (root->rnode == NULL)
+    root->height = 0;  /* Empty tree, we can reset the height */
+ out:
+  return ret;
+}
+
+
+static unsigned long __maxindex(unsigned int height)
+{
+  unsigned int tmp = height * RADIX_TREE_MAP_SHIFT;
+  unsigned long index = (~0UL >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1;
+  
+  if (tmp >= RADIX_TREE_INDEX_BITS)
+    index = ~0UL;
+  return index;
+}
+
+static void radix_tree_init_maxindex(void)
+{
+  unsigned int i;
+  
+  for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++)
+    height_to_maxindex[i] = __maxindex(i);
+}
+
+void radix_tree_init(void)
+{
+  radix_tree_init_maxindex();
+}
diff --git a/libbanshee/libcompat/radix-tree.h b/libbanshee/libcompat/radix-tree.h
new file mode 100644
index 00000000000..a6b6dc185a3
--- /dev/null
+++ b/libbanshee/libcompat/radix-tree.h
@@ -0,0 +1,51 @@
+/*
+ * Copyright (C) 2001 Momchil Velikov
+ * Portions Copyright (C) 2001 Christoph Hellwig
+ *
+ * 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 2, 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, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ */
+#ifndef _LINUX_RADIX_TREE_H
+#define _LINUX_RADIX_TREE_H
+
+
+struct radix_tree_node;
+
+struct radix_tree_root {
+  unsigned int		height;
+  struct radix_tree_node	*rnode;
+};
+
+#define RADIX_TREE_INIT()	{0, NULL}
+
+#define RADIX_TREE(name) \
+  struct radix_tree_root name = RADIX_TREE_INIT()
+
+#define INIT_RADIX_TREE(root)		\
+do {					\
+	(root)->height = 0;		\
+	(root)->rnode = NULL;		\
+} while (0)
+
+extern int radix_tree_insert(struct radix_tree_root *, unsigned long, void *);
+extern void *radix_tree_lookup(struct radix_tree_root *, unsigned long);
+extern void *radix_tree_delete(struct radix_tree_root *, unsigned long);
+extern unsigned int radix_tree_gang_lookup(struct radix_tree_root *root, 
+					   void **results, 
+					   unsigned long first_index,
+					   unsigned int max_items);
+extern void radix_tree_init(void);
+
+
+#endif /* _LINUX_RADIX_TREE_H */
diff --git a/libbanshee/libcompat/regions.c b/libbanshee/libcompat/regions.c
new file mode 100644
index 00000000000..6426fd68d1e
--- /dev/null
+++ b/libbanshee/libcompat/regions.c
@@ -0,0 +1,387 @@
+/*
+ * Copyright (c) 1999-2001
+ *      The Regents of the University of California.  All rights reserved.
+ *
+ * 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. Neither the name of the University 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 REGENTS 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 REGENTS 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.
+ *
+ */
+/* Idea: clear on page alloc rather than individual alloc
+   Turns out not so good (on lcc at least, seems a wash on mudlle):
+   logically should be bad for small regions (less than a few pages)
+*/
+#undef PRECLEAR
+#undef REGION_PROFILE
+#include "regions.h"
+#include <assert.h>
+#include <stdio.h>
+#include <string.h>
+#include "radix-tree.h"
+#define RPAGESIZE (1 << RPAGELOG)
+#define PAGE_GROUP_SIZE 32
+#define K 4
+#define MAXPAGE (1 << (32 - RPAGELOG))
+
+#define PAGENB(x) ((__rcintptr)(x) >> RPAGELOG)
+
+#define ALIGN(x, n) (((x) + ((n) - 1)) & ~((n) - 1))
+#define PALIGN(x, n) ((void *)ALIGN((__rcintptr)(x), n))
+#ifdef __GNUC__
+#define RALIGNMENT __alignof(double)
+#define PTRALIGNMENT __alignof(void *)
+#define ALIGNMENT_LONG __alignof(unsigned long)
+#else
+#define RALIGNMENT 8
+#define PTRALIGNMENT 4
+#define ALIGNMENT_LONG 4
+#endif
+
+typedef unsigned long __rcintptr;
+
+struct ablock {
+  char *base, *allocfrom;
+};
+
+struct allocator {
+  struct ablock page;
+  struct ablock superpage;
+  struct ablock hyperpage;
+  struct page *pages;
+  struct page *bigpages;
+};
+
+struct Region {
+  struct allocator normal;
+  struct Region *parent, *sibling, *children;
+};
+
+nomem_handler nomem_h;
+
+/* dummy region for NULL and malloc memory */
+struct Region zeroregion;
+
+static void clear(void *start, __rcintptr size)
+{
+  long *clear, *clearend;
+
+  clear = (long *)start;
+  clearend = (long *)((char *)start + size);
+  do *clear++ = 0;
+  while (clear < clearend) ;
+}
+
+#ifdef PRECLEAR
+#define preclear clear
+#define postclear(s, e)
+#else
+#define preclear(s, e)
+#define postclear clear
+#endif
+
+#include "pages.c"
+#include "alloc.c"
+
+static void nochildren(region r)
+{
+  if (r->children)
+    abort();
+}
+
+static void unlink_region(region r)
+{
+  region *scan;
+
+  scan = &r->parent->children;
+  while (*scan != r)
+    scan = &(*scan)->sibling;
+  *scan = (*scan)->sibling;
+}
+
+static void link_region(region r, region parent)
+{
+  r->sibling = parent->children;
+  r->parent = parent;
+  parent->children = r;
+}
+
+static int rstart;
+
+void initregion(region r)
+{
+  char *first =
+    (char *)r - rstart - offsetof(struct page, previous);
+
+  /* Start using page with region header as a pointer-containing page */
+  r->normal.page.base = first;
+  r->normal.page.allocfrom = (char *)(r + 1);
+
+  /* Guarantee failure for all other blocks */
+  r->normal.superpage.allocfrom = (char *)(K * RPAGESIZE + 1);
+  r->normal.hyperpage.allocfrom = (char *)(K * K * RPAGESIZE + 1);
+
+  /* Remember that r owns this page. */
+  r->normal.pages = (struct page *)first;
+  set_region(r->normal.pages, 1, r);
+}
+
+region newregion(void)
+{
+  return newsubregion(&zeroregion);
+}
+
+region newsubregion(region parent)
+{
+  char *first;
+  region r;
+
+  first = (char *)alloc_single_page(NULL);
+  preclear(first + offsetof(struct page, pagecount), RPAGESIZE - offsetof(struct page, pagecount));
+
+  /* stagger regions across cache lines a bit */
+  rstart += 64;
+  if (rstart > RPAGESIZE / K) rstart = 0;
+  r = (region)(first + rstart + offsetof(struct page, previous));
+  postclear(r, sizeof *r);
+  initregion(r);
+
+  link_region(r, parent);
+
+  return r;
+}
+
+void *typed_ralloc(region r, size_t size, type_t t)
+{
+  return rstralloc0(r, size);
+}
+
+void *typed_rarrayextend(region r, void *old, size_t n, size_t size, type_t t)
+{
+  return rstrextend0(r, old, n * size);
+}
+
+void *typed_rarrayalloc(region r, size_t n, size_t size, type_t t)
+{
+  return typed_ralloc(r, n * size, t);
+}
+
+char *rstralloc(region r, size_t size)
+{
+  void *mem, *dummy;
+
+  qalloc(r, &r->normal, &dummy, 0, 1, &mem, size, RALIGNMENT, 0);
+
+  return mem;
+}
+
+char *rstralloc0(region r, size_t size)
+{
+  char *mem;
+
+  mem = rstralloc(r, size);
+  clear(mem, size);
+
+  return mem;
+}
+
+char *rstrdup(region r, const char *s)
+{
+  char *news = rstralloc(r, strlen(s) + 1);
+
+  strcpy(news, s);
+
+  return news;
+}
+
+static char *internal_rstrextend(region r, const char *old, size_t newsize,
+				 int needsclear)
+{
+  /* For now we don't attempt to extend the old storage area */
+  void *newmem, *hdr;
+  unsigned long *oldhdr, oldsize;
+
+  qalloc(r, &r->normal, &hdr, sizeof(unsigned long), ALIGNMENT_LONG,
+	 &newmem, newsize, RALIGNMENT, 0);
+
+  /* If we don't do this we can't find the header: */
+  hdr = (char *)newmem - sizeof(unsigned long);
+
+  *(unsigned long *)hdr = newsize;
+
+  if (old)
+    {
+      oldhdr = (unsigned long *)(old - ALIGNMENT_LONG);
+      oldsize = *oldhdr;
+
+      if (oldsize > newsize)
+	oldsize = newsize;
+      else if (needsclear)
+	clear((char *) newmem + oldsize, newsize - oldsize);
+      memcpy(newmem, old, oldsize);
+    }
+  else if (needsclear)
+    clear(newmem, newsize);
+
+  return newmem;
+}
+
+char *rstrextend(region r, const char *old, size_t newsize)
+{
+  return internal_rstrextend(r, old, newsize, 0);
+}
+
+char *rstrextend0(region r, const char *old, size_t newsize)
+{
+  return internal_rstrextend(r, old, newsize, 1);
+}
+
+void typed_rarraycopy(void *to, void *from, size_t n, size_t size, type_t type)
+{
+  memcpy(to, from, n * size);
+}
+
+static void delregion(region r)
+{
+  nochildren(r);
+  free_all_pages(r, &r->normal);
+}
+
+void deleteregion(region r)
+{
+  unlink_region(r);
+  delregion(r);
+}
+
+void deleteregion_ptr(region *r)
+{
+  region tmp = *r;
+
+  *r = NULL;
+  deleteregion(tmp);
+}
+
+void deleteregion_array(int n, region *regions)
+{
+  int i;
+
+  for (i = 0; i < n; i++)
+    unlink_region(regions[i]);
+
+  for (i = 0; i < n; i++)
+    {
+      delregion(regions[i]);
+      regions[i] = NULL;
+    }
+}
+
+region regionof(void *ptr)
+{
+  return radix_tree_lookup (&__rcregionmap, (unsigned long)ptr >> RPAGELOG);
+}
+
+void region_init(void)
+{
+  static int initialized = 0;
+  radix_tree_init ();
+  if ( initialized )
+    return;
+  else
+    {
+      rstart = -64; /* Save 64 bytes of memory! (sometimes ;-)) */
+      init_pages();
+    }
+
+  initialized = 1;
+}
+
+nomem_handler set_nomem_handler(nomem_handler newhandler)
+{
+  nomem_handler oldh = nomem_h;
+
+  nomem_h = newhandler;
+
+  return oldh;
+}
+
+/*
+int region_main(int argc, char **argv, char **envp);
+
+int main(int argc, char **argv, char **envp)
+{
+  region_init();
+  return region_main(argc, argv, envp);
+}
+*/
+
+
+/* Debugging support */
+
+static FILE *out;
+
+static void printref(void *x)
+{
+/*  if (x >= (void *)__rcregionmap && x < (void *)&__rcregionmap[MAXPAGE])
+    return;
+*/
+#ifdef RCPAIRS
+  if (x >= (void *)__rcregions && x < (void *)&__rcregions[MAXREGIONS])
+    return;
+
+#endif
+
+  fprintf(out, "info symbol 0x%p\n", x);
+}
+
+void findrefs(region r, void *from, void *to)
+{
+  char *f;
+
+  if (!out)
+    out = fopen("/dev/tty", "w");
+
+  for (f = PALIGN(from, PTRALIGNMENT); f < (char *)to; f += PTRALIGNMENT)
+    if (regionof(*(void **)f) == r)
+      printref(f);
+
+  fflush(out);
+}
+
+#ifdef sparc
+extern void _DYNAMIC, _end;
+
+void findgrefs(region r)
+{
+  findrefs(r, &_DYNAMIC, &_end);
+}
+#endif
+
+void findrrefs(region r, region from)
+{
+  struct page *p;
+
+  for (p = from->normal.pages; p; p = p->next)
+    findrefs(r, (char *)&p->previous, (char *)p + RPAGESIZE);
+
+  for (p = r->normal.bigpages; p; p = p->next)
+    findrefs(r, (char *)&p->previous, (char *)p + p->pagecount * RPAGESIZE);
+}
diff --git a/libbanshee/libcompat/regions.h b/libbanshee/libcompat/regions.h
new file mode 100644
index 00000000000..9f0231ddd82
--- /dev/null
+++ b/libbanshee/libcompat/regions.h
@@ -0,0 +1,86 @@
+/*
+ * Copyright (c) 1999-2001
+ *      The Regents of the University of California.  All rights reserved.
+ *
+ * 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. Neither the name of the University 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 REGENTS 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 REGENTS 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.
+ *
+ */
+#ifndef REGIONS_H
+#define REGIONS_H
+
+#define RPAGELOG 13
+
+typedef struct Region *region;
+
+#include <stdlib.h>
+
+void region_init(void); /* You MUST call this function before using any
+			   part of this library */
+
+region newregion(void);
+region newsubregion(region parent);
+
+typedef int type_t;
+#define rctypeof(type) 0
+
+/* Low-level alloc with dynamic type info */
+void *typed_ralloc(region r, size_t size, type_t type);
+void *typed_rarrayalloc(region r, size_t n, size_t size, type_t type);
+void *typed_rarrayextend(region r, void *old, size_t n, size_t size, type_t type);
+void typed_rarraycopy(void *to, void *from, size_t n, size_t size, type_t type);
+
+#define ralloc(r, type) typed_ralloc((r), sizeof(type), rctypeof(type))
+#define rarrayalloc(r, n, type) typed_rarrayalloc((r), (n), sizeof(type), rctypeof(type))
+#define rarrayextend(r, old, n, type) typed_rarrayextend((r), (old), (n), sizeof(type), rctypeof(type))
+#define rarraycopy(to, from, n, type) typed_rarraycopy((to), (from), (n), sizeof(type), rctypeof(type))
+
+char *rstralloc(region r, size_t size);
+char *rstralloc0(region r, size_t size);
+char *rstrdup(region r, const char *s);
+
+/* rstrextend is used to extend an old string. The string MUST have been
+   initially allocated by a call to rstrextend with old == NULL (you cannot
+   initially allocate the string with rstralloc) */
+char *rstrextend(region r, const char *old, size_t newsize);
+char *rstrextend0(region r, const char *old, size_t newsize);
+
+void deleteregion(region r);
+void deleteregion_ptr(region *r);
+void deleteregion_array(int n, region *regions);
+region regionof(void *ptr);
+
+typedef void (*nomem_handler)(void);
+nomem_handler set_nomem_handler(nomem_handler newhandler);
+
+/* Debugging support */
+void findrefs(region r, void *from, void *to);
+void findgrefs(region r);
+void findrrefs(region r, region from);
+
+#ifdef REGION_PROFILE
+#include "profile.h"
+#endif
+
+#endif