escape_addresses.c: Move interface to own file.

[nmh] / sbr / vector.c

diff --git a/sbr/vector.c b/sbr/vector.c
index ca8c894ea398bce0d3f988f72daf4f5f774a3e0c..d0ebc33667c43c5fd18e8de2a1197d46a0b2c2c7 100644 (file)
--- a/sbr/vector.c
+++ b/sbr/vector.c
@@ -1,5 +1,4 @@
-/*
- * vector.c -- dynamically sized vectors
+/* vector.c -- dynamically sized vectors

  *
  * This code is Copyright (c) 2013, by the authors of nmh.  See the
  * COPYRIGHT file in the root directory of the nmh distribution for
  *
  * This code is Copyright (c) 2013, by the authors of nmh.  See the
  * COPYRIGHT file in the root directory of the nmh distribution for


@@ -17,10 +16,18 @@
  * can be as large as needed, as long as it fits in (virtual) memory.
  */
 
  * can be as large as needed, as long as it fits in (virtual) memory.
  */
 

-#include <h/mh.h>
-#include <h/utils.h>
+#include "h/mh.h"
+#include "h/utils.h"
+
+/* The default size of a struct bvector's bits, measured in bits.
+ * The struct's tiny member is used for storage. */
+#define BVEC_INIT_SIZE (sizeof *(((bvector_t)NULL)->tiny) * CHAR_BIT)
+
+/* The default number of char pointers in a struct svector. */
+#define SVEC_INIT_SIZE 256

 
 

-#define VEC_INIT_SIZE 256
+/* The default number of ints in a struct ivector. */
+#define IVEC_INIT_SIZE 256

 
 /*
  * These try to hide the type of the "bits" member of bvector.  But if
 
 /*
  * These try to hide the type of the "bits" member of bvector.  But if


@@ -28,109 +35,133 @@
  * constants in the code below must also be changed to a 1 that's at
  * least as wide as the new type.
  */
  * constants in the code below must also be changed to a 1 that's at
  * least as wide as the new type.
  */

-#ifndef Nbby
-# define Nbby 8
-#endif
-#define BVEC_WORD(vec, max) ((max) / (sizeof *vec->bits * Nbby))
-#define BVEC_OFFSET(vec, max) ((max) % (sizeof *vec->bits * Nbby))
-#define BVEC_BYTES(vec, n) \
-    ((BVEC_WORD (vec, n) + (BVEC_OFFSET (vec, n) == 0 ? 0 : 1))  * \
-    sizeof *vec->bits)
-
-struct bvector {
-    unsigned long *bits;
-    size_t maxsize;
-};

 
 

-static void bvector_resize (bvector_t, size_t);
+/* The *sizeof* struct bvector's bits member.  Not its size in bits. */
+#define BVEC_SIZEOF_BITS (sizeof *(((bvector_t)NULL)->bits))
+/* The number of bits held in one element of the bits member. */
+#define BVEC_BITS_BITS (BVEC_SIZEOF_BITS * CHAR_BIT)
+/* The index of bit n in struct bvector's bits member. */
+#define BVEC_WORD(n) ((n) / BVEC_BITS_BITS)
+/* The index of bit n within a single struct bvector's bits member. */
+#define BVEC_OFFSET(n) ((n) % BVEC_BITS_BITS)
+/* The number of elements bits needs to cover bit n, measured in bytes. */
+#define BVEC_BYTES(n) (((n) / BVEC_BITS_BITS + 1) * BVEC_SIZEOF_BITS)
+
+/* bvector_resize ensures the storage used for bits can cover bit
+ * newsize.  It always increases the size of the storage used for bits,
+ * even if newsize would have been covered by the existing storage.
+ * Thus it's normally only called when it's known the storage must grow. */
+static void bvector_resize (bvector_t vec, size_t newsize);

 
 bvector_t
 
 bvector_t

-bvector_create (size_t init_size) {
-    bvector_t vec = mh_xmalloc (sizeof *vec);
-    size_t bytes = BVEC_BYTES (vec, init_size  ?  init_size  :  VEC_INIT_SIZE);
+bvector_create (void)
+{
+    bvector_t vec;

 
 

-    vec->bits = mh_xmalloc (bytes);
-    memset (vec->bits, 0, bytes);
-    vec->maxsize = bytes * Nbby;
+    /* See "wider than unsigned long" comment above. */
+    assert (sizeof *vec->bits <= sizeof 1ul);
+
+    NEW(vec);
+    bvector_init(vec);

 
     return vec;
 }
 
 void
 
     return vec;
 }
 
 void

-bvector_copy (bvector_t dest, bvector_t src) {
-    size_t bytes = BVEC_BYTES (dest, src->maxsize);
+bvector_init(struct bvector *bv)
+{
+    bv->bits = bv->tiny;
+    bv->maxsize = BVEC_INIT_SIZE;
+    memset(bv->tiny, 0, sizeof bv->tiny);
+}

 
 

-    free (dest->bits);
-    dest->bits = mh_xmalloc (bytes);
+void
+bvector_copy (bvector_t dest, bvector_t src)
+{
+    size_t bytes = BVEC_BYTES(src->maxsize);
+
+    if (dest->bits != dest->tiny)
+        free(dest->bits);
+    if (bytes <= sizeof dest->tiny)
+        dest->bits = dest->tiny;
+    else
+        dest->bits = mh_xmalloc (bytes);

     memcpy (dest->bits, src->bits, bytes);
     dest->maxsize = src->maxsize;
 }
 
 void
     memcpy (dest->bits, src->bits, bytes);
     dest->maxsize = src->maxsize;
 }
 
 void

-bvector_free (bvector_t vec) {
-    free (vec->bits);
+bvector_free (bvector_t vec)
+{
+    bvector_fini(vec);

     free (vec);
 }
 
 void
     free (vec);
 }
 
 void

-bvector_clear (bvector_t vec, size_t n) {
-    size_t word = BVEC_WORD (vec,n);
-    size_t offset = BVEC_OFFSET (vec, n);
-
-    if (n >= vec->maxsize) bvector_resize (vec, n);
+bvector_fini(struct bvector *bv)
+{
+    if (bv->bits != bv->tiny)
+        free(bv->bits);
+}

 
 

-    assert (sizeof *vec->bits <= sizeof 1ul);
-    vec->bits[word] &= ~(1ul << offset);
+void
+bvector_clear (bvector_t vec, size_t n)
+{
+    if (n < vec->maxsize)
+        vec->bits[BVEC_WORD(n)] &= ~(1ul << BVEC_OFFSET(n));

 }
 
 
 void
 }
 
 
 void

-bvector_clear_all (bvector_t vec) {
-    memset (vec->bits, 0, BVEC_BYTES (vec, vec->maxsize));
+bvector_clear_all (bvector_t vec)
+{
+    memset (vec->bits, 0, BVEC_BYTES(vec->maxsize));

 }
 
 
 void
 }
 
 
 void

-bvector_set (bvector_t vec, size_t n) {
-    size_t word = BVEC_WORD (vec, n);
-    size_t offset = BVEC_OFFSET (vec, n);
+bvector_set (bvector_t vec, size_t n)
+{
+    size_t word = BVEC_WORD(n);
+    size_t offset = BVEC_OFFSET(n);

 
 

-    if (n >= vec->maxsize) bvector_resize (vec, n);
-    assert (sizeof *vec->bits <= sizeof 1ul);
+    if (n >= vec->maxsize)
+        bvector_resize (vec, n);

     vec->bits[word] |= 1ul << offset;
 }
 
 unsigned int
     vec->bits[word] |= 1ul << offset;
 }
 
 unsigned int

-bvector_at (bvector_t vec, size_t i) {
-    size_t word = BVEC_WORD (vec, i);
-    size_t offset = BVEC_OFFSET (vec, i);
+bvector_at (bvector_t vec, size_t i)
+{
+    if (i < vec->maxsize)
+        return !!(vec->bits[BVEC_WORD(i)] & (1ul << BVEC_OFFSET(i)));

 
 

-    assert (sizeof *vec->bits <= sizeof 1ul);
-    return i < vec->maxsize
-        ?  (vec->bits[word] & (1ul << offset) ? 1 : 0)
-        :  0;
+    return 0;

 }
 
 static void
 }
 
 static void

-bvector_resize (bvector_t vec, size_t maxsize) {
-    size_t old_maxsize = vec->maxsize;
+bvector_resize (bvector_t vec, size_t newsize)
+{
+    size_t oldsize = vec->maxsize;

     size_t bytes;
     size_t bytes;

-    size_t i;

 
 

-    while ((vec->maxsize *= 2) < maxsize) continue;
-    bytes = BVEC_BYTES (vec, vec->maxsize);
-    vec->bits = mh_xrealloc (vec->bits, bytes);
-    for (i = old_maxsize; i < vec->maxsize; ++i) bvector_clear (vec, i);
+    while ((vec->maxsize *= 2) < newsize)
+        ;
+    bytes = BVEC_BYTES(vec->maxsize);
+    if (vec->bits == vec->tiny) {
+        vec->bits = mh_xmalloc(bytes);
+        memcpy(vec->bits, vec->tiny, sizeof vec->tiny);
+    } else
+        vec->bits = mh_xrealloc(vec->bits, bytes);
+
+    memset(vec->bits + (oldsize / BVEC_BITS_BITS), 0,
+        (vec->maxsize - oldsize) / CHAR_BIT);

 }
 
 }
 

-const unsigned long *
-bvector_bits (bvector_t vec) {
-    return vec->bits;
-}
-
-size_t
-bvector_maxsize (bvector_t vec) {
-    return vec->maxsize;
+unsigned long
+bvector_first_bits (bvector_t vec)
+{
+    return *vec->bits;

 }
 
 
 }
 
 


@@ -143,55 +174,84 @@ struct svector {
 static void svector_resize (svector_t, size_t);
 
 svector_t
 static void svector_resize (svector_t, size_t);
 
 svector_t

-svector_create (size_t init_size) {
-    svector_t vec = mh_xmalloc (sizeof *vec);
+svector_create (size_t init_size)
+{
+    svector_t vec;

     size_t bytes;
 
     size_t bytes;
 

-    vec->maxsize = init_size ? init_size : VEC_INIT_SIZE;
+    NEW(vec);
+    vec->maxsize = init_size ? init_size : SVEC_INIT_SIZE;

     bytes = vec->maxsize * sizeof (char *);
     bytes = vec->maxsize * sizeof (char *);

-    vec->strs = mh_xmalloc (bytes);
-    memset (vec->strs, 0, bytes);
+    vec->strs = mh_xcalloc (1, bytes);

     vec->size = 0;
 
     return vec;
 }
 
 void
     vec->size = 0;
 
     return vec;
 }
 
 void

-svector_free (svector_t vec) {
+svector_free (svector_t vec)
+{

     free (vec->strs);
     free (vec);
 }
 
 char *
     free (vec->strs);
     free (vec);
 }
 
 char *

-svector_push_back (svector_t vec, char *s) {
-    if (++vec->size >= vec->maxsize) svector_resize (vec, vec->size);
+svector_push_back (svector_t vec, char *s)
+{
+    if (++vec->size >= vec->maxsize)
+        svector_resize (vec, vec->size);

     return vec->strs[vec->size-1] = s;
 }
 
 char *
     return vec->strs[vec->size-1] = s;
 }
 
 char *

-svector_at (svector_t vec, size_t i) {
-    if (i >= vec->maxsize) svector_resize (vec, i);
+svector_at (svector_t vec, size_t i)
+{
+    if (i >= vec->maxsize)
+        svector_resize (vec, i);

     return vec->strs[i];
 }
 
     return vec->strs[i];
 }
 

+/*
+ * Return address of first element that stringwise matches s.
+ * The caller can replace the contents of the return address.
+ */

 char **
 char **

-svector_strs (svector_t vec) {
+svector_find (svector_t vec, const char *s)
+{
+    size_t i;
+    char **str = vec->strs;
+
+    for (i = 0; i < vec->size; ++i, ++str) {
+        if (*str  &&  ! strcmp(*str, s)) {
+            return str;
+        }
+    }
+
+    return NULL;
+}
+
+char **
+svector_strs (svector_t vec)
+{

     return vec->strs;
 }
 
 size_t
     return vec->strs;
 }
 
 size_t

-svector_size (svector_t vec) {
+svector_size (svector_t vec)
+{

     return vec->size;
 }
 
 static void
     return vec->size;
 }
 
 static void

-svector_resize (svector_t vec, size_t maxsize) {
+svector_resize (svector_t vec, size_t maxsize)
+{

     size_t old_maxsize = vec->maxsize;
     size_t old_maxsize = vec->maxsize;

-    size_t i;

 
 

-    while ((vec->maxsize *= 2) < maxsize) continue;
+    while ((vec->maxsize *= 2) < maxsize)
+        ;

     vec->strs = mh_xrealloc (vec->strs, vec->maxsize * sizeof (char *));
     vec->strs = mh_xrealloc (vec->strs, vec->maxsize * sizeof (char *));

-    for (i = old_maxsize; i < vec->maxsize; ++i) vec->strs[i] = NULL;
+    memset(vec->strs + old_maxsize, 0,
+        (vec->maxsize - old_maxsize) * sizeof *vec->strs);

 }
 
 
 }
 
 


@@ -204,54 +264,59 @@ struct ivector {
 static void ivector_resize (ivector_t, size_t);
 
 ivector_t
 static void ivector_resize (ivector_t, size_t);
 
 ivector_t

-ivector_create (size_t init_size) {
-    ivector_t vec = mh_xmalloc (sizeof *vec);
+ivector_create (size_t init_size)
+{
+    ivector_t vec;

     size_t bytes;
 
     size_t bytes;
 

-    vec->maxsize = init_size ? init_size : VEC_INIT_SIZE;
+    NEW(vec);
+    vec->maxsize = init_size ? init_size : IVEC_INIT_SIZE;

     bytes = vec->maxsize * sizeof (int);
     bytes = vec->maxsize * sizeof (int);

-    vec->ints = mh_xmalloc (bytes);
-    memset (vec->ints, 0, bytes);
+    vec->ints = mh_xcalloc (1, bytes);

     vec->size = 0;
 
     return vec;
 }
 
 void
     vec->size = 0;
 
     return vec;
 }
 
 void

-ivector_free (ivector_t vec) {
+ivector_free (ivector_t vec)
+{

     free (vec->ints);
     free (vec);
 }
 
 int
     free (vec->ints);
     free (vec);
 }
 
 int

-ivector_push_back (ivector_t vec, int n) {
-    if (++vec->size >= vec->maxsize) ivector_resize (vec, vec->size);
+ivector_push_back (ivector_t vec, int n)
+{
+    if (++vec->size >= vec->maxsize)
+        ivector_resize (vec, vec->size);

     return vec->ints[vec->size-1] = n;
 }
 
 int
     return vec->ints[vec->size-1] = n;
 }
 
 int

-ivector_at (ivector_t vec, size_t i) {
-    if (i >= vec->maxsize) ivector_resize (vec, i);
+ivector_at (ivector_t vec, size_t i)
+{
+    if (i >= vec->maxsize)
+        ivector_resize (vec, i);

     return vec->ints[i];
 }
 
 int *
     return vec->ints[i];
 }
 
 int *

-ivector_atp (ivector_t vec, size_t i) {
-    if (i >= vec->maxsize) ivector_resize (vec, i);
+ivector_atp (ivector_t vec, size_t i)
+{
+    if (i >= vec->maxsize)
+        ivector_resize (vec, i);

     return &vec->ints[i];
 }
 
     return &vec->ints[i];
 }
 

-size_t
-ivector_size (ivector_t vec) {
-    return vec->size;
-}
-

 static void
 static void

-ivector_resize (ivector_t vec, size_t maxsize) {
+ivector_resize (ivector_t vec, size_t maxsize)
+{

     size_t old_maxsize = vec->maxsize;
     size_t old_maxsize = vec->maxsize;

-    size_t i;

 
 

-    while ((vec->maxsize *= 2) < maxsize) continue;
+    while ((vec->maxsize *= 2) < maxsize)
+        ;

     vec->ints = mh_xrealloc (vec->ints, vec->maxsize * sizeof (int));
     vec->ints = mh_xrealloc (vec->ints, vec->maxsize * sizeof (int));

-    for (i = old_maxsize; i < vec->maxsize; ++i) vec->ints[i] = 0;
+    memset(vec->ints + old_maxsize, 0,
+        (vec->maxsize - old_maxsize) * sizeof *vec->ints);

 }
 }