[Mono-list] [PATCH] bitset doc
Dennis Haney
davh@davh.dk
02 Jun 2002 23:11:59 +0200
--=-=-=
Paolo Molaro <lupus@ximian.com> writes:
> On 06/02/02 Dennis Haney wrote:
> > Was this unecessary for such a easy interface... Well, could you guess
> > that if you used mono_bitset_mem_new it is not freed even if
> > mono_bitset_free is called on it?
>
> :-)
> I would add to the docs that the mem arguments must hold at least the
> number of bytes returned by a call to mono_bitset_alloc_size()
Done
> and since the lib didn't allocate the memory (the user did), it
> can't free it (since it may be stack memory, for example).
Wording changed a bit.
> Also, I would remove references to malloc in the docs (it's also
> incorrect, since we use g_malloc) and to g_return_if_fail() because
> that is a debug check that mean the user has screwed up, but it's not
> part of the interface (it gets removes in non-debug builds).
Done
> We put the documentation in the C file:
Moved there.
> can you prepare a new patch with these changes?
Yes ;)
> Otherwise I'll move the comments to the C file myself on Monday.
No need ;)
I found two new errors. In clone the new_size was used as arg in
memcpy, VERY WRONG! my_g_bit_nth_lsf was hardcoded to 32 bit machines
:( Both have been corrected!
If someone else has to much time, a few test cases should be added to
test 64bit machines also get things right...
And I added at equal_smallest that only checks the first bits upto the
smallest bitset's size. And added test and doc for it.
And I changed all the params that were actually used const to reflect
that fact, that should give the compiler a little bone in optimization
;) Plus it also makes it easiere to see which param is altered in
copy/intersect/union etc.
> Thanks!
Again you are welcome ;)
> > [OT]:
> > Does anyone know why my messages seem to take hours to make it to the
> > list? And why does mailman fail to send acknowledgements that it
> > received my messages even when I said it should do so?
>
> Mailman is stupid and it uses the Sender: header instead of the From:
> one so I need to approve your posts (and your sender address bounces
> so you don't get the message back).
Upgrade to 2.0?
--
Dennis
use Inline C => qq{void p(char*g){printf("Just Another %s Hacker\n",g);}};p("Perl");
--=-=-=
Content-Disposition: attachment; filename=monobitset-doc2.diff
Content-Description: bitset doc + fix
Index: monobitset.c
===================================================================
RCS file: /mono/mono/mono/utils/monobitset.c,v
retrieving revision 1.5
diff -u -b -B -r1.5 monobitset.c
--- monobitset.c 1 Jun 2002 08:27:27 -0000 1.5
+++ monobitset.c 2 Jun 2002 21:12:51 -0000
@@ -18,19 +18,31 @@
};
/*
+ * mono_bitset_alloc_size:
+ * @max_size: The numer of bits you want to hold
+ * @flags: unused
+ *
* Return the number of bytes required to hold the bitset.
* Useful to allocate it on the stack or with mempool.
* Use with mono_bitset_mem_new ().
*/
guint32
-mono_bitset_alloc_size (guint32 max_size, guint32 flags) {
+mono_bitset_alloc_size (const guint32 max_size, const guint32 flags) {
guint32 real_size = (max_size + BITS_PER_CHUNK - 1) / BITS_PER_CHUNK;
return sizeof (MonoBitSet) + sizeof (guint32) * (real_size - MONO_ZERO_LEN_ARRAY);
}
+/*
+ * mono_bitset_new:
+ * @max_size: The numer of bits you want to hold
+ * @flags: bitfield of flags
+ *
+ * Return a bitset of size max_size. It must be free using
+ * mono_bitset_free.
+ */
MonoBitSet *
-mono_bitset_new (guint32 max_size, guint32 flags) {
+mono_bitset_new (const guint32 max_size, const guint32 flags) {
guint32 real_size = (max_size + BITS_PER_CHUNK - 1) / BITS_PER_CHUNK;
MonoBitSet *result;
@@ -41,11 +53,21 @@
}
/*
+ * mono_bitset_mem_new:
+ * @mem: The location the bitset is stored
+ * @max_size: The number of bits you want to hold
+ * @flags: bitfield of flags
+ *
+ * Return mem, which is now a initialized bitset of size max_size. Is
+ * not freed even if called with mono_bitset_free. mem must at least
+ * as big as mono_bitset_alloc_size returns for the same max_size.
+ */
+MonoBitSet *
+mono_bitset_mem_new (gpointer mem, const guint32 max_size, const guint32 flags) {
+/*
* We could require mem_size here, instead of max_size, so we could do
* some out of range checking...
*/
-MonoBitSet *
-mono_bitset_mem_new (gpointer mem, guint32 max_size, guint32 flags) {
guint32 real_size = (max_size + BITS_PER_CHUNK - 1) / BITS_PER_CHUNK;
MonoBitSet *result = mem;
@@ -54,14 +76,30 @@
return result;
}
+/*
+ * mono_bitset_free:
+ * @set: bitset ptr to free
+ *
+ * Free bitset unless flags have MONO_BITSET_DONT_FREE set. Does not
+ * free anything if flag MONO_BITSET_DONT_FREE is set or bitset was
+ * made with mono_bitset_mem_new.
+ */
void
mono_bitset_free (MonoBitSet *set) {
if (!(set->flags & MONO_BITSET_DONT_FREE))
g_free (set);
}
+/*
+ * mono_bitset_set:
+ * @set: bitset ptr
+ * @pos: set bit at this pos
+ *
+ * Set bit at pos 'pos', counted from 0. set is untouched if with pos
+ * out of bounds.
+ */
void
-mono_bitset_set (MonoBitSet *set, guint32 pos) {
+mono_bitset_set (MonoBitSet *set, const guint32 pos) {
int j = pos / BITS_PER_CHUNK;
int bit = pos % BITS_PER_CHUNK;
@@ -70,8 +108,16 @@
set->data [j] |= 1 << bit;
}
+/*
+ * mono_bitset_test:
+ * @set: bitset ptr
+ * @pos: test bit at this pos
+ *
+ * Test bit at pos 'pos', counted from 0. Returns 0 if if pos out of
+ * bounds. Return anything but 0 if set.
+ */
int
-mono_bitset_test (MonoBitSet *set, guint32 pos) {
+mono_bitset_test (const MonoBitSet *set, const guint32 pos) {
int j = pos / BITS_PER_CHUNK;
int bit = pos % BITS_PER_CHUNK;
@@ -80,8 +126,16 @@
return set->data [j] & (1 << bit);
}
+/*
+ * mono_bitset_clear:
+ * @set: bitset ptr
+ * @pos: unset bit at this pos
+ *
+ * Unset bit at pos 'pos', counted from 0. set is untouched if with pos
+ * out of bounds.
+ */
void
-mono_bitset_clear (MonoBitSet *set, guint32 pos) {
+mono_bitset_clear (MonoBitSet *set, const guint32 pos) {
int j = pos / BITS_PER_CHUNK;
int bit = pos % BITS_PER_CHUNK;
@@ -90,6 +144,12 @@
set->data [j] &= ~(1 << bit);
}
+/*
+ * mono_bitset_clear_all:
+ * @set: bitset ptr
+ *
+ * Unset all bits.
+ */
void
mono_bitset_clear_all (MonoBitSet *set) {
int i;
@@ -97,6 +157,12 @@
set->data [i] = 0;
}
+/*
+ * mono_bitset_invert:
+ * @set: bitset ptr
+ *
+ * Flip all bits.
+ */
void
mono_bitset_invert (MonoBitSet *set) {
int i;
@@ -104,17 +170,30 @@
set->data [i] = ~set->data [i];
}
+/*
+ * mono_bitset_size:
+ * @set: bitset ptr
+ *
+ * return number of bits this bitset can hold.
+ */
guint32
-mono_bitset_size (MonoBitSet *set) {
+mono_bitset_size (const MonoBitSet *set) {
return set->size;
}
-#if 1
/*
* should test wich version is faster.
*/
+#if 1
+
+/*
+ * mono_bitset_count:
+ * @set: bitset ptr
+ *
+ * return number of bits that is set.
+ */
guint32
-mono_bitset_count (MonoBitSet *set) {
+mono_bitset_count (const MonoBitSet *set) {
static const unsigned char table [16] = {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4
};
@@ -140,7 +219,7 @@
}
#else
guint32
-mono_bitset_count (MonoBitSet *set) {
+mono_bitset_count (const MonoBitSet *set) {
static const guint32 table [] = {
0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF
};
@@ -188,14 +267,20 @@
nth_bit++;
if (mask & (1 << (gulong) nth_bit))
return nth_bit;
- } while (nth_bit < 31);
+ } while (nth_bit < BITS_PER_CHUNK - 1);
return -1;
}
#define my_g_bit_nth_lsf_nomask(m) (my_g_bit_nth_lsf((m),-1))
#endif
+/*
+ * mono_bitset_find_start:
+ * @set: bitset ptr
+ *
+ * Equivalent to mono_bitset_find_first (set, -1) but faster
+ */
int
-mono_bitset_find_start (MonoBitSet *set)
+mono_bitset_find_start (const MonoBitSet *set)
{
int i;
@@ -206,13 +291,21 @@
return -1;
}
+/*
+ * mono_bitset_find_first:
+ * @set: bitset ptr
+ * @pos: pos to search _after_ (not including)
+ *
+ * return pos of first set bit after pos. If pos < 0 begin search from
+ * start. Return -1 if all unset or if pos out of bounds.
+ */
int
-mono_bitset_find_first (MonoBitSet *set, gint pos) {
+mono_bitset_find_first (const MonoBitSet *set, const gint pos) {
int j;
int bit;
int result, i;
- if (pos == -1) {
+ if (pos <= -1) {
j = 0;
bit = -1;
} else {
@@ -234,17 +327,26 @@
return -1;
}
+/*
+ * mono_bitset_find_last:
+ * @set: bitset ptr
+ * @pos: pos to search _before_ (not including)
+ *
+ * return pos of first set bit before pos. If pos < 0 search is
+ * started from the end. Return -1 if all unset or if pos out of
+ * bounds.
+ */
int
-mono_bitset_find_last (MonoBitSet *set, gint pos) {
- int j, bit, result, i;
+mono_bitset_find_last (const MonoBitSet *set, const gint pos) {
+ int j, bit, result, i, pos2=pos;
- if (pos == -1)
- pos = set->size - 1;
+ if (pos <= -1)
+ pos2 = set->size - 1;
- j = pos / BITS_PER_CHUNK;
- bit = pos % BITS_PER_CHUNK;
+ j = pos2 / BITS_PER_CHUNK;
+ bit = pos2 % BITS_PER_CHUNK;
- g_return_val_if_fail (pos < set->size, -1);
+ g_return_val_if_fail (pos2 < set->size, -1);
if (set->data [j]) {
result = g_bit_nth_msf (set->data [j], bit);
@@ -258,20 +360,38 @@
return -1;
}
+/*
+ * mono_bitset_clone:
+ * @set: bitset ptr to clone
+ * @new_size: number of bits the cloned bitset can hold
+ *
+ * Return a cloned bitset of size new_size. MONO_BITSET_DONT_FREE
+ * unset in cloned bitset. If new_size is 0, the cloned object is just
+ * as big.
+ */
MonoBitSet*
-mono_bitset_clone (MonoBitSet *set, guint32 new_size) {
+mono_bitset_clone (const MonoBitSet *set, const guint32 new_size) {
MonoBitSet *result;
+ int size = new_size;
- if (!new_size)
- new_size = set->size;
- result = mono_bitset_new (new_size, set->flags);
+ if (!size)
+ size = set->size;
+ result = mono_bitset_new (size, set->flags);
result->flags &= ~MONO_BITSET_DONT_FREE;
- memcpy (result->data, set->data, result->size / 8);
+ memcpy (result->data, set->data, set->size / 8);
return result;
}
+/*
+ * mono_bitset_copyto:
+ * @src: bitset ptr to copy from
+ * @dest: bitset ptr to copy to
+ *
+ * Copy one bitset to another. dest is untouched if dest is smaller
+ * than src.
+ */
void
-mono_bitset_copyto (MonoBitSet *src, MonoBitSet *dest) {
+mono_bitset_copyto (const MonoBitSet *src, MonoBitSet *dest) {
int i;
g_return_if_fail (dest->size <= src->size);
@@ -280,8 +400,16 @@
dest->data [i] = src->data [i];
}
+/*
+ * mono_bitset_union:
+ * @dest: bitset ptr to hold union
+ * @src: bitset ptr to copy
+ *
+ * Make union of one bitset and another. dest is untouched if src is
+ * smaller than dest.
+ */
void
-mono_bitset_union (MonoBitSet *dest, MonoBitSet *src) {
+mono_bitset_union (MonoBitSet *dest, const MonoBitSet *src) {
int i;
g_return_if_fail (src->size <= dest->size);
@@ -290,8 +418,16 @@
dest->data [i] |= src->data [i];
}
+/*
+ * mono_bitset_intersection:
+ * @dest: bitset ptr to hold intersection
+ * @src: bitset ptr to copy
+ *
+ * Make intersection of one bitset and another. dest is untouched if
+ * src is smaller than dest.
+ */
void
-mono_bitset_intersection (MonoBitSet *dest, MonoBitSet *src) {
+mono_bitset_intersection (MonoBitSet *dest, const MonoBitSet *src) {
int i;
g_return_if_fail (src->size <= dest->size);
@@ -300,8 +436,16 @@
dest->data [i] = dest->data [i] & src->data [i];
}
+/*
+ * mono_bitset_sub:
+ * @dest: bitset ptr to hold bitset - src
+ * @src: bitset ptr to copy
+ *
+ * Unset all bits in dest, which are set in src. dest is untouched if
+ * src is smaller than dest.
+ */
void
-mono_bitset_sub (MonoBitSet *dest, MonoBitSet *src) {
+mono_bitset_sub (MonoBitSet *dest, const MonoBitSet *src) {
int i;
g_return_if_fail (src->size <= dest->size);
@@ -310,8 +454,16 @@
dest->data [i] &= ~src->data [i];
}
+/*
+ * mono_bitset_equal:
+ * @src: bitset ptr
+ * @src1: bitset ptr
+ *
+ * return TRUE if their size are the same and the same bits are set in
+ * both bitsets.
+ */
gboolean
-mono_bitset_equal (MonoBitSet *src, MonoBitSet *src1) {
+mono_bitset_equal (const MonoBitSet *src, const MonoBitSet *src1) {
int i;
if (src->size != src1->size)
return FALSE;
@@ -322,6 +474,35 @@
return TRUE;
}
+/*
+ * mono_bitset_equal_smallest:
+ * @src: bitset ptr
+ * @src1: bitset ptr
+ *
+ * return TRUE the same bits are set in both bitsets upto the smallest
+ * bitset's size.
+ */
+gboolean
+mono_bitset_equal_smallest (const MonoBitSet *src, const MonoBitSet *src1) {
+ int i;
+ int size = src->size < src1->size ? src->size : src1->size;
+
+ for (i = 0; i < size / BITS_PER_CHUNK; ++i)
+ if (src->data [i] != src1->data [i])
+ return FALSE;
+ return TRUE;
+}
+
+
+/*
+ * mono_bitset_foreach:
+ * @set: bitset ptr
+ * @func: Function to call for every set bit
+ * @data: pass this as second arg to func
+ *
+ * Calls func for every bit set in bitset. Argument 1 is the number of
+ * the bit set, argument 2 is data
+ */
void
mono_bitset_foreach (MonoBitSet *set, MonoBitSetFunc func, gpointer data)
{
@@ -359,7 +540,7 @@
return error;
error++;
- g_print("should be 33: %d\n", mono_bitset_find_first (set1, 0));
+ //g_print("should be 33: %d\n", mono_bitset_find_first (set1, 0));
if (mono_bitset_find_first (set1, 0) != 33)
return error;
@@ -369,6 +550,11 @@
return error;
error++;
+ /* test 5 */
+ if (mono_bitset_find_first (set1, -100) != 33)
+ return error;
+ error++;
+
if (mono_bitset_find_last (set1, -1) != 33)
return error;
error++;
@@ -377,10 +563,15 @@
return error;
error++;
+ if (mono_bitset_find_last (set1, -100) != 33)
+ return error;
+ error++;
+
if (mono_bitset_find_last (set1, 34) != 33)
return error;
error++;
+ /* test 10 */
if (!mono_bitset_test (set1, 33))
return error;
error++;
@@ -389,7 +580,6 @@
return error;
error++;
- /* test 10 */
set2 = mono_bitset_clone (set1, 0);
if (mono_bitset_count (set2) != 1)
return error;
@@ -405,6 +595,7 @@
return error;
error++;
+ /* test 15 */
set3 = mono_bitset_clone (set2, 0);
mono_bitset_union (set3, set1);
if (mono_bitset_count (set3) != (mono_bitset_size (set3) - 1))
@@ -431,20 +622,47 @@
count = 0;
for (i = mono_bitset_find_first (set4, -1); i != -1; i = mono_bitset_find_first (set4, i)) {
count ++;
- g_print ("count got: %d at %d\n", count, i);
+ switch (count) {
+ case 1:
+ if (i != 0)
+ return error;
+ break;
+ case 2:
+ if (i != 1)
+ return error;
+ break;
+ case 3:
+ if (i != 10)
+ return error;
+ break;
+ }
+ //g_print ("count got: %d at %d\n", count, i);
}
if (count != 3)
return error;
error++;
- g_print ("count passed\n");
if (mono_bitset_find_first (set4, -1) != 0)
return error;
error++;
+ /* 20 */
mono_bitset_set (set4, 31);
if (mono_bitset_find_first (set4, 10) != 31)
return error;
+ error++;
+
+ mono_bitset_free (set1);
+
+ set1 = mono_bitset_new (200, 0);
+ mono_bitset_set (set1, 0);
+ mono_bitset_set (set1, 1);
+ mono_bitset_set (set1, 10);
+ mono_bitset_set (set1, 31);
+ mono_bitset_set (set1, 150);
+
+ if (mono_bitset_equal_smallest(set1,set4) != TRUE)
+ return error;
error++;
mono_bitset_free (set1);
Index: monobitset.h
===================================================================
RCS file: /mono/mono/mono/utils/monobitset.h,v
retrieving revision 1.3
diff -u -b -B -r1.3 monobitset.h
--- monobitset.h 31 May 2002 09:47:59 -0000 1.3
+++ monobitset.h 2 Jun 2002 21:12:51 -0000
@@ -10,52 +10,52 @@
MONO_BITSET_DONT_FREE = 1
};
-guint32 mono_bitset_alloc_size (guint32 max_size, guint32 flags);
+/*
+ * Interface documentation can be found in the c-file.
+ * Interface documentation by Dennis Haney.
+ */
+
+guint32 mono_bitset_alloc_size (guint32 max_size, const guint32 flags);
-MonoBitSet* mono_bitset_new (guint32 max_size, guint32 flags);
+MonoBitSet* mono_bitset_new (guint32 max_size, const guint32 flags);
-MonoBitSet* mono_bitset_mem_new (gpointer mem, guint32 max_size, guint32 flags);
+MonoBitSet* mono_bitset_mem_new (gpointer mem, const guint32 max_size, const guint32 flags);
void mono_bitset_free (MonoBitSet *set);
-void mono_bitset_set (MonoBitSet *set, guint32 pos);
+void mono_bitset_set (MonoBitSet *set, const guint32 pos);
-int mono_bitset_test (MonoBitSet *set, guint32 pos);
+int mono_bitset_test (const MonoBitSet *set, const guint32 pos);
-void mono_bitset_clear (MonoBitSet *set, guint32 pos);
+void mono_bitset_clear (MonoBitSet *set, const guint32 pos);
void mono_bitset_clear_all (MonoBitSet *set);
void mono_bitset_invert (MonoBitSet *set);
-guint32 mono_bitset_size (MonoBitSet *set);
+guint32 mono_bitset_size (const MonoBitSet *set);
-guint32 mono_bitset_count (MonoBitSet *set);
+guint32 mono_bitset_count (const MonoBitSet *set);
-/*
- * Find the first bit set _after_ (not including) pos.
- */
-int mono_bitset_find_first (MonoBitSet *set, gint pos);
-/* Equivalent to find_first (set, -1) but faster */
-int mono_bitset_find_start (MonoBitSet *set);
+int mono_bitset_find_start (const MonoBitSet *set);
-/*
- * Find the first bit set _before_ (not including) pos.
- * Use -1 to start from the end.
- */
-int mono_bitset_find_last (MonoBitSet *set, gint pos);
+int mono_bitset_find_first (const MonoBitSet *set, const gint pos);
+
+int mono_bitset_find_last (const MonoBitSet *set, const gint pos);
+
+MonoBitSet* mono_bitset_clone (const MonoBitSet *set, const guint32 new_size);
-MonoBitSet* mono_bitset_clone (MonoBitSet *set, guint32 new_size);
+void mono_bitset_copyto (const MonoBitSet *src, MonoBitSet *dest);
-void mono_bitset_copyto (MonoBitSet *src, MonoBitSet *dest);
+void mono_bitset_union (MonoBitSet *dest, const MonoBitSet *src);
-void mono_bitset_union (MonoBitSet *dest, MonoBitSet *src);
+void mono_bitset_intersection (MonoBitSet *dest, const MonoBitSet *src);
-void mono_bitset_intersection (MonoBitSet *dest, MonoBitSet *src);
+void mono_bitset_sub (MonoBitSet *dest, const MonoBitSet *src);
-void mono_bitset_sub (MonoBitSet *dest, MonoBitSet *src);
+gboolean mono_bitset_equal (const MonoBitSet *src, const MonoBitSet *src1);
-gboolean mono_bitset_equal (MonoBitSet *src, MonoBitSet *src1);
+gboolean mono_bitset_equal_smallest (const MonoBitSet *src, const MonoBitSet *src1);
void mono_bitset_foreach (MonoBitSet *set, MonoBitSetFunc func, gpointer data);
--=-=-=--