path.c: Re-format path() to make it more clear what's happening.

[nmh] / sbr / vector.c

diff --git a/sbr/vector.c b/sbr/vector.c
index c2bd0df913b3003e5781ab42ac33fd7aa7b69f01..6afe62aa29e2aecc1ad446c59ed175b81201476a 100644 (file)
--- a/sbr/vector.c
+++ b/sbr/vector.c
@@ -19,8 +19,14 @@
 #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)
 #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 SVEC_INIT_SIZE 256

+
+/* The default number of ints in a struct ivector. */

 #define IVEC_INIT_SIZE 256
 
 /*
 #define IVEC_INIT_SIZE 256
 
 /*


@@ -34,70 +40,69 @@
 #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)
 #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)

-#define BVEC_WORD(max) ((max) / BVEC_BITS_BITS)
-#define BVEC_OFFSET(max) ((max) % BVEC_BITS_BITS)
-#define BVEC_BYTES(n) \
-    ((BVEC_WORD(n) + (BVEC_OFFSET(n) == 0 ? 0 : 1)) * BVEC_SIZEOF_BITS)
-
-struct bvector {
-    unsigned long *bits;
-    size_t maxsize;
-    unsigned long tiny[2];
-};
-
-static void bvector_resize (bvector_t, size_t);
+/* 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_create (void) {

     bvector_t vec;
     bvector_t vec;

-    size_t bytes;

 
     /* See "wider than unsigned long" comment above. */
     assert (sizeof *vec->bits <= sizeof 1ul);
 
     NEW(vec);
 
     /* See "wider than unsigned long" comment above. */
     assert (sizeof *vec->bits <= sizeof 1ul);
 
     NEW(vec);

-
-    if (init_size <= BVEC_INIT_SIZE) {
-        vec->bits = vec->tiny;
-        vec->maxsize = BVEC_INIT_SIZE;
-        memset(vec->tiny, 0, sizeof vec->tiny);
-        return vec;
-    }
-
-    bytes = BVEC_BYTES(init_size);
-    vec->bits = mh_xcalloc (1, bytes);
-    vec->maxsize = bytes * CHAR_BIT;
+    bvector_init(vec);

 
     return vec;
 }
 
 
     return vec;
 }
 

+void bvector_init(struct bvector *bv)
+{
+    bv->bits = bv->tiny;
+    bv->maxsize = BVEC_INIT_SIZE;
+    memset(bv->tiny, 0, sizeof bv->tiny);
+}
+

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

-    dest->bits = mh_xmalloc (bytes);
+    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
 bvector_free (bvector_t vec) {
     memcpy (dest->bits, src->bits, bytes);
     dest->maxsize = src->maxsize;
 }
 
 void
 bvector_free (bvector_t vec) {

-    if (vec->bits != vec->tiny)
-        free(vec->bits);
+    bvector_fini(vec);

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

+void bvector_fini(struct bvector *bv)
+{
+    if (bv->bits != bv->tiny)
+        free(bv->bits);
+}
+

 void
 bvector_clear (bvector_t vec, size_t n) {
 void
 bvector_clear (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);
-
-    vec->bits[word] &= ~(1ul << offset);
+    if (n < vec->maxsize)
+        vec->bits[BVEC_WORD(n)] &= ~(1ul << BVEC_OFFSET(n));

 }
 
 
 }
 
 


@@ -119,20 +124,18 @@ bvector_set (bvector_t vec, size_t n) {
 
 unsigned int
 bvector_at (bvector_t vec, size_t i) {
 
 unsigned int
 bvector_at (bvector_t vec, size_t i) {

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

 
 

-    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;
 

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

         ;
     bytes = BVEC_BYTES(vec->maxsize);
     if (vec->bits == vec->tiny) {
         ;
     bytes = BVEC_BYTES(vec->maxsize);
     if (vec->bits == vec->tiny) {


@@ -141,8 +144,8 @@ bvector_resize (bvector_t vec, size_t maxsize) {
     } else
         vec->bits = mh_xrealloc(vec->bits, bytes);
 
     } else
         vec->bits = mh_xrealloc(vec->bits, bytes);
 

-    memset(vec->bits + (old_maxsize / BVEC_BITS_BITS), 0,
-        (vec->maxsize - old_maxsize) / CHAR_BIT);
+    memset(vec->bits + (oldsize / BVEC_BITS_BITS), 0,
+        (vec->maxsize - oldsize) / CHAR_BIT);

 }
 
 unsigned long
 }
 
 unsigned long