Version bump.

[mLib] / sub.c

diff --git a/sub.c b/sub.c
index 2f0fed3c1161ab5eaf122f36776c474d62c2d14e..ef4307583c887d975dd0089246c1a86716ce4e7a 100644 (file)
--- a/sub.c
+++ b/sub.c
@@ -1,43 +1,62 @@
 /* -*-c-*-
  *
 /* -*-c-*-
  *

- * $Id: sub.c,v 1.1 1998/06/17 23:44:42 mdw Exp $
+ * $Id: sub.c,v 1.7 2003/05/18 15:10:20 mdw Exp $

  *
  * Allocation of known-size blocks
  *
  * (c) 1998 Straylight/Edgeware
  */
 
  *
  * Allocation of known-size blocks
  *
  * (c) 1998 Straylight/Edgeware
  */
 

-/*----- Licensing notice --------------------------------------------------*
+/*----- Licensing notice --------------------------------------------------* 

  *
  * This file is part of the mLib utilities library.
  *
  * mLib is free software; you can redistribute it and/or modify
  *
  * This file is part of the mLib utilities library.
  *
  * mLib 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 of the License, or
- * (at your option) any later version.
- *
+ * it under the terms of the GNU Library General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ * 

  * mLib 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
  * mLib 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 mLib; if not, write to the Free Software Foundation,
- * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ * GNU Library General Public License for more details.
+ * 
+ * You should have received a copy of the GNU Library General Public
+ * License along with mLib; if not, write to the Free
+ * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
+ * MA 02111-1307, USA.

  */
 
 /*----- Revision history --------------------------------------------------*
  *
  * $Log: sub.c,v $
  */
 
 /*----- Revision history --------------------------------------------------*
  *
  * $Log: sub.c,v $

- * Revision 1.1  1998/06/17 23:44:42  mdw
- * Initial revision
+ * Revision 1.7  2003/05/18 15:10:20  mdw
+ * Add debugging mode which just uses the underlying arena.
+ *
+ * Revision 1.6  2000/06/17 10:35:51  mdw
+ * Major overhaul for arena support.
+ *
+ * Revision 1.5  1999/05/19 20:27:11  mdw
+ * Change naming to match newer mLib conventions.
+ *
+ * Revision 1.4  1999/05/13 22:48:55  mdw
+ * Change `-ise' to `-ize' throughout.
+ *
+ * Revision 1.3  1999/05/06 19:51:35  mdw
+ * Reformatted the LGPL notice a little bit.
+ *
+ * Revision 1.2  1999/05/05 18:50:31  mdw
+ * Change licensing conditions to LGPL.
+ *
+ * Revision 1.1.1.1  1998/06/17 23:44:42  mdw
+ * Initial version of mLib

  *
  */
 
 /*----- The big idea ------------------------------------------------------*
  *
  * This file provides an extra layer over @malloc@.  It provides fast
  *
  */
 
 /*----- The big idea ------------------------------------------------------*
  *
  * This file provides an extra layer over @malloc@.  It provides fast

- * turnover for small blocks, and tries to minimise the per-block overhead.
+ * turnover for small blocks, and tries to minimize the per-block overhead.

  *
  * To do its job, @alloc@ must place an extra restriction on you: you must
  * know the size of a block when you free it.  Usually you'll have this
  *
  * To do its job, @alloc@ must place an extra restriction on you: you must
  * know the size of a block when you free it.  Usually you'll have this


@@ -67,157 +86,277 @@
 
 /* --- ANSI headers --- */
 
 
 /* --- ANSI headers --- */
 

+#include <assert.h>

 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 
 /* --- Local headers --- */
 
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 
 /* --- Local headers --- */
 

-#undef TRACK_ENABLE                    /* Can't track suballoc routines */
-#include "alloc.h"
+#include "arena.h"
+#include "exc.h"
+#include "sub.h"

 
 

-/*----- Configuration and tuning ------------------------------------------*/
+/*----- Configuration tweaks ----------------------------------------------*/

 
 

-/* --- The largest block I'll handle here --- *
- *
- * Anything larger will be handed on to @malloc@.
- */
+/* #define SUBARENA_TRIVIAL */

 
 

-#define SUB_MAXBIN 256
+/*----- Static variables --------------------------------------------------*/

 
 

-/* --- Preferred chunk size --- *
- *
- * When a bin is empty, I'll allocate a large chunk of approximately this
- * size and divvy it up into small bin-sized blocks.
- */
+static size_t sizes[SUB_BINS];

 
 

-#define SUB_CHUNK 4096
+/*----- Global variables --------------------------------------------------*/

 
 

-/*----- Other useful macros -----------------------------------------------*/
+subarena sub_global;

 
 

-/* --- The granularity of bin buffers --- *
- *
- * All blocks allocated by the binner are a multiple of this size.  I've
- * chosen @void *@ because I need to store @void *@ things in here.
- */
+#ifdef SUBARENA_TRIVIAL
+
+typedef struct sub_link {
+  struct sub_link *next;
+  void *p;
+  size_t sz;
+} sub_link;

 
 

-#define SUB_GRANULE sizeof(void *)
+#endif

 
 

-/* --- Finding the right bin for a given size --- *
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @subarena_create@ --- *
+ *
+ * Arguments:  @subarena *s@ = pointer to arena to initialize
+ *             @arena *a@ = pointer to underlying arena block

  *
  *

- * This chooses the correct bin for an allocation.  Input is the size of
- * block wanted; result is the bin index.
+ * Returns:    ---
+ *
+ * Use:                Initialize a suballocation arena based on an underlying large
+ *             blocks arena.

  */
 
  */
 

-#define SUB_BIN(x) (((x) + SUB_GRANULE - 1) / SUB_GRANULE)
+void subarena_create(subarena *s, arena *a)
+{
+#ifdef SUBARENA_TRIVIAL
+  s->bin[0] = 0;
+#else
+  size_t i;
+  if (!sizes[1])
+    sub_init();
+  for (i = 0; i < SUB_BINS; i++)
+    s->bin[i] = 0;
+#endif
+  s->a = a;
+}

 
 

-/* --- Convert a bin back to the block size --- *
+/* --- @subarena_destroy@ --- *
+ *
+ * Arguments:  @subarena *s@ = pointer to arena to destroy

  *
  *

- * This gives the size of block contained in a given bin.
+ * Returns:    ---
+ *
+ * Use:                Destroys a suballocation arena, freeing all of the memory it
+ *             contains back to the underlying large blocks arena.

  */
 
  */
 

-#define SUB_BINSZ(x) ((x) * SUB_GRANULE)
+void subarena_destroy(subarena *s)
+{
+#ifdef SUBARENA_TRIVIAL

 
 

-/* --- Number of bins required --- */
+  sub_link *l, *ll;

 
 

-#define SUB_BINS (SUB_MAXBIN / SUB_GRANULE + 1)
+  for (l = s->bin[0]; l; l = ll) {
+    ll = l;
+    a_free(s->a, l->p);
+    a_free(s->a, l);
+  }
+  s->bin[0] = 0;

 
 

-/*----- Static variables --------------------------------------------------*/
+#else

 
 

-static void *sub__bins[SUB_BINS];
-static size_t sub__sizes[SUB_BINS];
+  size_t i;
+  for (i = 0; i < SUB_BINS; i++) {
+    void *p = s->bin[i];
+    while (p) {
+      void *q = p;
+      p = *(void **)q;
+      A_FREE(s->a, q);
+    }
+  }

 
 

-/*----- Main code ---------------------------------------------------------*/
+#endif
+}

 
 

-/* --- @sub_alloc@ --- *
+/* --- @subarena_alloc@ --- *

  *
  *

- * Arguments:   @size_t s@ = size of chunk wanted
+ * Arguments:   @subarena *s@ = pointer to arena
+ *             @size_t s@ = size of chunk wanted

  *
  * Returns:     Pointer to a block at least as large as the one wanted.
  *
  *
  * Returns:     Pointer to a block at least as large as the one wanted.
  *

- * Use:         Allocates a small block of memory.  If there is no more
- *             memory left, the exception @EXC_NOMEM@ is raised.
+ * Use:         Allocates a small block of memory from the given pool.  The
+ *             exception @EXC_NOMEM@ is raised if the underlying arena is
+ *             full.

  */
 
  */
 

-void *sub_alloc(size_t s)
+void *subarena_alloc(subarena *s, size_t sz)

 {
 {

-  int bin = SUB_BIN(s);
+#ifdef SUBARENA_TRIVIAL
+
+  sub_link *l;
+  void *p;
+
+  if (!s->a)
+    subarena_create(s, arena_global);
+
+  if ((l = a_alloc(s->a, sizeof(*l))) == 0)
+    return (0);
+  if ((p = a_alloc(s->a, sz)) == 0) {
+    a_free(s->a, l);
+    return (0);
+  }
+  l->p = p;
+  l->sz = sz;
+  l->next = s->bin[0];
+  s->bin[0] = l;
+  return (p);
+
+#else
+
+  int bin;

   void *p;
 
   void *p;
 

+  /* --- Ensure that everything is initialized --- */
+
+  if (!s->a)
+    subarena_create(s, arena_global);
+

   /* --- Handle oversize blocks --- */
 
   /* --- Handle oversize blocks --- */
 

-  if (bin >= SUB_BINS)
-    return (xmalloc(s));
+  bin = SUB_BIN(sz);
+  if (bin >= SUB_BINS) {
+    void *p = A_ALLOC(s->a, sz);
+    if (!p)
+      THROW(EXC_NOMEM);
+    return (p);
+  }

 
   /* --- If the bin is empty, find some memory --- */
 
 
   /* --- If the bin is empty, find some memory --- */
 

-  if (!sub__bins[bin]) {
+  if (!s->bin[bin]) {

     char *p, *q;
 
     char *p, *q;
 

-    p = xmalloc(sub__sizes[bin]);
-    q = p + sub__sizes[bin];
+    p = A_ALLOC(s->a, sizes[bin]);
+    if (!p)
+      THROW(EXC_NOMEM);
+    q = p + sizes[bin];

 
 

-    s = SUB_BINSZ(bin);
+    sz = SUB_BINSZ(bin);

 
 

-    q -= s;
+    q -= sz;

     *(void **)q = 0;
 
     while (q > p) {
     *(void **)q = 0;
 
     while (q > p) {

-      q -= s;
-      *(void **)q = q + s;
+      q -= sz;
+      *(void **)q = q + sz;

     }
 
     }
 

-    sub__bins[bin] = p;
+    s->bin[bin] = p;

   }
 
   /* --- Extract the first block in the list --- */
 
   }
 
   /* --- Extract the first block in the list --- */
 

-  p = sub__bins[bin];
-  sub__bins[bin] = *(void **)p;
+  p = s->bin[bin];
+  s->bin[bin] = *(void **)p;

   return (p);
   return (p);

+
+#endif

 }
 
 }
 

-/* --- @sub_free@ --- *
+/* --- @subarena_free@ --- *

  *
  *

- * Arguments:   @void *p@ = address of block to free
+ * Arguments:   @subarena *s@ = pointer to arena
+ *             @void *p@ = address of block to free

  *              @size_t s@ = size of block
  *
  * Returns:     ---
  *
  *              @size_t s@ = size of block
  *
  * Returns:     ---
  *

- * Use:         Frees a block allocated by @sub_alloc@.
+ * Use:         Frees a block allocated by @subarena_alloc@.

  */
 
  */
 

-void sub_free(void *p, size_t s)
+void subarena_free(subarena *s, void *p, size_t sz)

 {
 {

-  int bin = SUB_BIN(s);
+#ifdef SUBARENA_TRIVIAL
+
+  sub_link *lh = s->bin[0], **l, *ll;
+
+  for (l = &lh; *l && (*l)->p != p; l = &(*l)->next)
+    ;
+  ll = *l;
+  assert(ll);
+  assert(ll->sz == sz);
+  *l = ll->next;
+  a_free(s->a, ll);
+  a_free(s->a, p);
+  s->bin[0] = lh;
+
+#else
+
+  int bin = SUB_BIN(sz);

 
   if (bin >= SUB_BINS)
 
   if (bin >= SUB_BINS)

-    free(p);
+    A_FREE(s->a, p);

   else {
   else {

-    *(void **)p = sub__bins[bin];
-    sub__bins[bin] = p;
+    *(void **)p = s->bin[bin];
+    s->bin[bin] = p;

   }
   }

+
+#endif

 }
 
 }
 

+/*----- Compatibility stuff -----------------------------------------------*/
+
+/* --- @sub_alloc@ --- *
+ *
+ * Arguments:   @size_t s@ = size of chunk wanted
+ *
+ * Returns:     Pointer to a block at least as large as the one wanted.
+ *
+ * Use:         Allocates a small block of memory from the @sub_global@ pool.
+ */
+
+void *(sub_alloc)(size_t sz) { return sub_alloc(sz); }
+
+/* --- @sub_free@ --- *
+ *
+ * Arguments:   @void *p@ = address of block to free
+ *              @size_t s@ = size of block
+ *
+ * Returns:     ---
+ *
+ * Use:         Frees a block allocated by @sub_alloc@.
+ */
+
+void (sub_free)(void *p, size_t sz) { sub_free(p, sz); }
+

 /* --- @sub_init@ --- *
  *
  * Arguments:   ---
  *
  * Returns:     ---
  *
 /* --- @sub_init@ --- *
  *
  * Arguments:   ---
  *
  * Returns:     ---
  *

- * Use:         Initialises the magic allocator.
+ * Use:         Initializes the magic allocator.

  */
 
 void sub_init(void)
 {
  */
 
 void sub_init(void)
 {

+#ifndef SUBARENA_TRIVIAL

   int i;
 
   int i;
 

-  /* --- Initialise the sizes bins --- */
+  /* --- Initialize the sizes bins --- */

 
   for (i = 1; i < SUB_BINS; i++) {
 
   for (i = 1; i < SUB_BINS; i++) {

-    sub__sizes[i] = ((SUB_CHUNK + SUB_BINSZ(i) - 1) /
+    sizes[i] = ((SUB_CHUNK + SUB_BINSZ(i) - 1) /

                     SUB_BINSZ(i) * SUB_BINSZ(i));
   }
                     SUB_BINSZ(i) * SUB_BINSZ(i));
   }

+#endif

 }
 
 /*----- Debugging code ----------------------------------------------------*/
 }
 
 /*----- Debugging code ----------------------------------------------------*/