cleanup: All the whitespace fixes, all at once.

[mLib] / sub.c

diff --git a/sub.c b/sub.c
index 2f0fed3c1161ab5eaf122f36776c474d62c2d14e..06570b609b0e629e68198faf04b6aaeefa99ff75 100644 (file)
--- a/sub.c
+++ b/sub.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
 /* -*-c-*-
  *

- * $Id: sub.c,v 1.1 1998/06/17 23:44:42 mdw Exp $
+ * $Id: sub.c,v 1.9 2004/04/08 01:36:13 mdw Exp $

  *
  * Allocation of known-size blocks
  *
  *
  * Allocation of known-size blocks
  *


@@ -12,32 +12,25 @@
  * 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.
- */
-
-/*----- Revision history --------------------------------------------------*
- *
- * $Log: sub.c,v $
- * Revision 1.1  1998/06/17 23:44:42  mdw
- * Initial revision
+ * 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.

  */
 
 /*----- 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 +60,278 @@
 
 /* --- 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

 
 

-#define SUB_GRANULE sizeof(void *)
+typedef struct sub_link {
+  struct sub_link *next;
+  void *p;
+  size_t sz;
+} sub_link;
+
+#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
+ *
+ * Returns:    ---

  *
  *

- * This chooses the correct bin for an allocation.  Input is the size of
- * block wanted; result is the bin index.
+ * 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
+ *
+ * Returns:    ---

  *
  *

- * This gives the size of block contained in a given bin.
+ * 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);
+    }
+    s->bin[i] = 0;
+  }

 
 

-/*----- 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;
 
   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;
+
+  /* --- 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
- *              @size_t s@ = size of block
+ * Arguments:  @subarena *s@ = pointer to arena
+ *             @void *p@ = address of block to free
+ *             @size_t s@ = size of block

  *
  *

- * Returns:     ---
+ * 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@ --- *
  *
 /* --- @sub_init@ --- *
  *

- * Arguments:   ---
+ * Arguments:  ---

  *
  *

- * Returns:     ---
+ * 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 ----------------------------------------------------*/