libclc: bitset interface 
Author Message
 libclc: bitset interface

Here's an interface for some code which may have its place in libclc. I
hope that this post and the discussion will teach us more about how we
should submit code to libclc.

Since this is the first submittal, it raises some questions:
- Do we need/want this code? How do we decide/vote?
- I deliberately chose code that uses an ADT. Do we want ADT's in libclc?
- The submitted interface is stripped of comments. How do we describe
the interface? (Since this post is a bit experimental, I have included a
version of clc_bitset.h which has comments.)
- I chose to submit the interface first and will submit the proposed
implementation later if the interface is accepted. Is that OK?

Here we go ;-)
Bj?rn

Summary
--------
clc_bitset is an ADT which implements a set of bits. Each bit can be set
or cleared using functions provided. You can create a bitset in two
ways, either by providing your own memory (clc_bitset_map) or by having
clc_bitset_new allocate sufficient memory.

Interface(clc_bitset.h):
#ifndef CLC_BITSET_H
#define CLC_BITSET_H

#include <stdlib.h>

#ifdef __cplusplus
extern "C" {
#endif

typedef struct clc_bitset_tag* clc_bitset;

clc_bitset clc_bitset_new(size_t bitcount);
void clc_bitset_free(clc_bitset b);

void clc_bitset_set(clc_bitset b, size_t i);
void clc_bitset_set_all(clc_bitset b);
int  clc_bitset_is_set(clc_bitset b, size_t i);

void clc_bitset_clear(clc_bitset b, size_t i);
void clc_bitset_clear_all(clc_bitset b);

size_t clc_bitset_size(clc_bitset b);
void* clc_bitset_data(clc_bitset b);

clc_bitset clc_bitset_map(void* mem, size_t cb);
void clc_bitset_remap(clc_bitset b, void* mem, size_t cb);
void clc_bitset_unmap(clc_bitset b);

#ifdef __cplusplus

Quote:
}

#endif

#endif

------ End of clc_bitset.h

[ clc_bitset.txt 4K ]
#ifndef CLC_BITSET_H
#define CLC_BITSET_H

#include <stdlib.h>

#ifdef __cplusplus
extern "C" {
#endif

/**

 * A clc_bitset is nothing more than a very long integer with bits to indicate
 * true or false.
 * All you have to do to use a clc_bitset is to decide how many bits you want,
 * and then create the clc_bitset. Now you're ready to set and clear bits, and
 * test to see if a given bit is set or not.
 *
 * This class can also do a lot more. You can assign a specific memory area
 * to the clc_bitset and then manipulate that area bit by bit. The memory area
 * may be e.g. a memory mapped file or even an automatic variable.
 *
 * The clc_bitset is reentrant, but not thread safe. This means that multiple threads
 * cannot read and write to the same clc_bitset at the same time. Use a lock to control
 * access to the clc_bitset if needed.
 *
 */

typedef struct clc_bitset_tag* clc_bitset;

/**
 * Creates a new clc_bitset.
 *


 */
clc_bitset clc_bitset_new(size_t bitcount);

/**
 * Frees a clc_bitset created by clc_bitset_new().
 *

 *

 */
void clc_bitset_free(clc_bitset b);

/**
 * sets the bit spesified by index
 *


 */
void clc_bitset_set(clc_bitset b, size_t i);

/**
 * Clears the bit spesified by index
 *


 */
void clc_bitset_clear(clc_bitset b, size_t i);

/**
 * Tests if the specified bit is set or not.
 *



 */
int clc_bitset_is_set(clc_bitset b, size_t i);

/**
 * Sets all bits in the clc_bitset to 0.
 *

 */
void clc_bitset_clear_all(clc_bitset b);

/**
 * Sets all bits in the clc_bitset to 1.
 *

 */
void clc_bitset_set_all(clc_bitset b);

/**
 * Returns the number of bytes used by the clc_bitset to
 * store bits. Use it if you e.g. want to write the
 * clc_bitset to a file.
 *

 * // Writes a clc_bitset to file.
 * write(fd, clc_bitset_data(b), clc_bitset_size(b));

 *



 */
size_t clc_bitset_size(clc_bitset b);

/**
 * Use clc_bitset_map() if you have a clc_bitset in memory or want to
 * create one in memory. Typical use will be if you have a memory
 * mapped file and parts of that file is a clc_bitset.
 *

 * This pointer can point to just about anything, but is most
 * meaningful if it points to memory previously used as a clc_bitset.
 *
 * It is possible to memorymap e.g. an executable and then manipulate
 * each bit of that executable using a clc_bitset.
 *


 * by a mapped clc_bitset. Calling clc_bitset_free() will most probably
 * crash your application, as the data pointed to hasn't been allocated.
 *

 */
clc_bitset clc_bitset_map(void* mem, size_t cb);

/**
 * Frees old memory and starts using the memory pointed to by mem.
 * Typical usage is when you e.g. create a new memory mapped indexed file with
 * a bitmap created in memory and you want it moved to the new memory mapped file.
 *


 */
void clc_bitset_remap(clc_bitset b, void* mem, size_t cb);

/**
 * Frees memory allocated by clc_bitset, but the memory used to store
 * bits is untouched. Memory mapped clc_bitsets must be unmapped using
 * this function. Do not use clc_bitset_free() if the clc_bitset was
 * created using clc_bitset_map() or clc_bitset_remap().
 *



 */
void clc_bitset_unmap(clc_bitset b);

/**
 * Returns a void pointer to the data that implements the clc_bitset.
 * You might ask why this function is needed? The reason is that
 * we then can 'move' the clc_bitset from memory to e.g. a memory mapped file.
 * We can write the clc_bitsets to files using this function and
 * clc_bitset_size() as arguments to write().
 *

 */
void* clc_bitset_data(clc_bitset b);

#ifdef __cplusplus

Quote:
}

#endif

#endif



Sun, 14 Aug 2005 20:38:18 GMT  
 libclc: bitset interface

Quote:

> Here's an interface for some code which may have its place in
> libclc. I hope that this post and the discussion will teach us
> more about how we should submit code to libclc.

... snip ...

> - The submitted interface is stripped of comments. How do we
> describe the interface? (Since this post is a bit experimental,
> I have included a version of clc_bitset.h which has comments.)

Don't put attachments in newsgroups - the better ISPs will
immediately strip them anyhow. This is a pure text medium.

The #include <stdio.h> should not exist in the header.

The important thing is the interface.  It sounds as if you want to
implement the equivalent of a Pascal set.  Nothing needs to know
*how* it is implemented.  The first thing is to be able to create
(and destroy) such a set.  Thus a fundamental construct would be:

   thing = makebitset(size);

and all other operations should be of the form:

   dosomethingwith(thing, <whatever>);

and the discussions should be about what sort of dosomethingwith's
need to be implemented. Then the actual code can be improved,
whatnot at any time, without affecting the code using it.  Of
course to take advantage it would have to be relinked.

If you don't start by keeping the interfaces clean, the whole
thing will not be used. Things that are already defined by the
standard are another matter.

--

   Available for consulting/temporary embedded and systems.
   <http://cbfalconer.home.att.net>  USE worldnet address!



Sun, 14 Aug 2005 22:15:39 GMT  
 libclc: bitset interface

Quote:

> Here's an interface for some code which may have its place in libclc. I
> hope that this post and the discussion will teach us more about how we
> should submit code to libclc.

> Since this is the first submittal, it raises some questions:
> - Do we need/want this code? How do we decide/vote?
> - I deliberately chose code that uses an ADT. Do we want ADT's in libclc?
> - The submitted interface is stripped of comments. How do we describe
> the interface? (Since this post is a bit experimental, I have included a
> version of clc_bitset.h which has comments.)
> - I chose to submit the interface first and will submit the proposed
> implementation later if the interface is accepted. Is that OK?

[snip]

Looks good, but there should be:
* A function to resize the bitset, assuming it's allocated by
clc_bitset_new()
* A function to map and create a bitset

These are more convenience than anything (except the resizer - we'd have
to completely copy the bitset otherwise!), but I feel they're important.
--
Freenet distribution (temporary): http://24.25.175.161:8891/yHEdSC8HOuY/
"If the code and the comments disagree, then both are probably wrong."
-- Norm Schryer



Mon, 15 Aug 2005 05:55:39 GMT  
 libclc: bitset interface

Quote:


>>Here's an interface for some code which may have its place in libclc. I
>>hope that this post and the discussion will teach us more about how we
>>should submit code to libclc.

>>Since this is the first submittal, it raises some questions:
>>- Do we need/want this code? How do we decide/vote?
>>- I deliberately chose code that uses an ADT. Do we want ADT's in libclc?
>>- The submitted interface is stripped of comments. How do we describe
>>the interface? (Since this post is a bit experimental, I have included a
>>version of clc_bitset.h which has comments.)
>>- I chose to submit the interface first and will submit the proposed
>>implementation later if the interface is accepted. Is that OK?

> [snip]

> Looks good, but there should be:
> * A function to resize the bitset, assuming it's allocated by
> clc_bitset_new()

Good idea. How about
     int clc_bitset_resize(clc_bitset bs, size_t new_bitcount);

returning 0 on error and 1 on success? The semantics can be like
realloc, where reducing the bit count frees memory. Will this do?

Quote:
> * A function to map and create a bitset

Not quite sure what you mean here. Please provide more info.

Bj?rn
[snip]



Mon, 15 Aug 2005 06:32:30 GMT  
 libclc: bitset interface

Quote:



>>>Here's an interface for some code which may have its place in libclc. I
>>>hope that this post and the discussion will teach us more about how we
>>>should submit code to libclc.

>>>Since this is the first submittal, it raises some questions:
>>>- Do we need/want this code? How do we decide/vote?
>>>- I deliberately chose code that uses an ADT. Do we want ADT's in libclc?
>>>- The submitted interface is stripped of comments. How do we describe
>>>the interface? (Since this post is a bit experimental, I have included a
>>>version of clc_bitset.h which has comments.)
>>>- I chose to submit the interface first and will submit the proposed
>>>implementation later if the interface is accepted. Is that OK?

>> [snip]

>> Looks good, but there should be:
>> * A function to resize the bitset, assuming it's allocated by
>> clc_bitset_new()

> Good idea. How about
>      int clc_bitset_resize(clc_bitset bs, size_t new_bitcount);

> returning 0 on error and 1 on success? The semantics can be like
> realloc, where reducing the bit count frees memory. Will this do?

>> * A function to map and create a bitset

> Not quite sure what you mean here. Please provide more info.

Like this:
clc_bitset clt_bitset_new_map(void *buf, size_t bytecount);
That's essentially clc_bitset_new() and clc_bitset_map() rolled into one.

Also, how about having the set/unset operations return the clc_bitset
instead of void?
--
Freenet distribution (temporary): http://24.25.175.161:8891/bXDwZdyjMO4/
We are each only one drop in a great ocean -- but some of the drops sparkle!



Mon, 15 Aug 2005 09:09:43 GMT  
 libclc: bitset interface

Quote:



>>>Here's an interface for some code which may have its place in libclc. I
>>>hope that this post and the discussion will teach us more about how we
>>>should submit code to libclc.

>>>Since this is the first submittal, it raises some questions:
>>>- Do we need/want this code? How do we decide/vote?

I think you should decide after reading people's comments.

Quote:
>>>- I deliberately chose code that uses an ADT. Do we want ADT's in
>>>libclc?

Oh yes, I think so.

Quote:
>>>- The submitted interface is stripped of comments. How do we describe
>>>the interface? (Since this post is a bit experimental, I have included a
>>>version of clc_bitset.h which has comments.)
>>>- I chose to submit the interface first and will submit the proposed
>>>implementation later if the interface is accepted. Is that OK?

I think so.

Quote:
>> [snip]

>> Looks good, but there should be:
>> * A function to resize the bitset, assuming it's allocated by
>> clc_bitset_new()

> Good idea. How about
>      int clc_bitset_resize(clc_bitset bs, size_t new_bitcount);

> returning 0 on error and 1 on success? The semantics can be like
> realloc, where reducing the bit count frees memory. Will this do?

Personally, I find 0 on success and non-zero on error much more intuitive.

Or maybe typedef enum {clc_success, clc_failure} clc_status;

then return clc_status.

Also, consider this scenario:
Someone resizes the bitset upwards, and it works, but the whole bitset has
to be copied to another location. How will the caller know what that new
location is?

If you are planning on using double indirection, then there might be no
problem with this interface, but if you don't want to do that, then you
should probably return a clc_bitset.

[snip]

Mac
--



Mon, 15 Aug 2005 14:12:52 GMT  
 libclc: bitset interface
[snip]
Quote:
> Here we go ;-)
> Bj?rn

> Summary
> --------
> clc_bitset is an ADT which implements a set of bits. Each bit can be set
> or cleared using functions provided. You can create a bitset in two
> ways, either by providing your own memory (clc_bitset_map) or by having
> clc_bitset_new allocate sufficient memory.

[snip]

Is this too ugly?

/* bit_array.h */
#ifndef BIT_ARRAY_H
#define BIT_ARRAY_H 1

#include <limits.h>

typedef unsigned long int bit_elem_T;
#define BIT_ELEM_SIZE (CHAR_BIT * sizeof(bit_elem_T))

/* How many elements are needed to accomodate "nbits" bits? */
#define BIT_ARRAY_CALC_ELEMS(nbits) \
    (((nbits)/BIT_ELEM_SIZE) + (((nbits)%BIT_ELEM_SIZE)?1:0))

/* BIT toggling */
#define BIT_ARRAY_SETBIT(arr,bit) \
    (*((arr)+((bit)/BIT_ELEM_SIZE)) |= (1UL << ((bit)%BIT_ELEM_SIZE)))

#define BIT_ARRAY_CLEARBIT(arr,bit) \
    (*((arr)+((bit)/BIT_ELEM_SIZE)) &= ~(1UL << ((bit)%BIT_ELEM_SIZE)))

#define BIT_ARRAY_FLIPBIT(arr,bit) \
    (*((arr)+((bit)/BIT_ELEM_SIZE)) ^= (1UL << ((bit)%BIT_ELEM_SIZE)))

#define BIT_ARRAY_ISSET(arr,bit) \
    (*((arr)+((bit)/BIT_ELEM_SIZE)) & (1UL << (bit)%BIT_ELEM_SIZE))

#endif

Use like:

   enum fishes {LOST_BAIT, COHO_SALMON, CHINOOK_SALMON, SOCKEYE_SALMON,
                CHUM_SALMON, STEELHEAD_TROUT, CUTTHROAT_TROUT, RAINBOW_TROUT,
                BROWN_TROUT, GOLDEN_TROUT, DOLLY_VARDEN, PERCH, CARP,
                BASS, GREEN_STURGEON, WHITE_STURGEON, SUNFISH,
                MOSQUITOFISH, LUNGFISH, ROCKFISH, COD, TUNA, SHEEPSHEAD,
                BLOWFISH, SHARK, PIRANHA, SCULPIN, STICKLEBACK,
                YELLOWFIN, SNAPPER, EEL, CATFISH, WALLEYE, PIKE, MINNOW,
                PIKE_MINNOW, FISHES_MAX};

   bit_elem_T  fishing_trip[BIT_ARRAY_CALC_ELEMS(FISHES_MAX)] = {0};

   BIT_ARRAY_SETBIT (fishing_trip, MINNOW);
   BIT_ARRAY_FLIPBIT (fishing_trip, SHARK);
   BIT_ARRAY_CLEARBIT (fishing_trip, SHARK);
   if (BIT_ARRAY_ISSET (fishing_trip, TUNA))  {
       make_sushi();
   }

--



Mon, 15 Aug 2005 14:44:49 GMT  
 libclc: bitset interface

Quote:




>>>>Here's an interface for some code which may have its place in libclc. I
>>>>hope that this post and the discussion will teach us more about how we
>>>>should submit code to libclc.

>>>>Since this is the first submittal, it raises some questions:
>>>>- Do we need/want this code? How do we decide/vote?
>>>>- I deliberately chose code that uses an ADT. Do we want ADT's in libclc?
>>>>- The submitted interface is stripped of comments. How do we describe
>>>>the interface? (Since this post is a bit experimental, I have included a
>>>>version of clc_bitset.h which has comments.)
>>>>- I chose to submit the interface first and will submit the proposed
>>>>implementation later if the interface is accepted. Is that OK?

>>>[snip]

>>>Looks good, but there should be:
>>>* A function to resize the bitset, assuming it's allocated by
>>>clc_bitset_new()

>>Good idea. How about
>>     int clc_bitset_resize(clc_bitset bs, size_t new_bitcount);

>>returning 0 on error and 1 on success? The semantics can be like
>>realloc, where reducing the bit count frees memory. Will this do?

>>>* A function to map and create a bitset

>>Not quite sure what you mean here. Please provide more info.

> Like this:
> clc_bitset clt_bitset_new_map(void *buf, size_t bytecount);
> That's essentially clc_bitset_new() and clc_bitset_map() rolled into one.

Now I see what you mean. The proposed interface has two ways of creating
a bitset. You either call clc_bitset_new() *or* you create a bitset from
an existing piece of memory using clc_bitset_map(). I believe
clc_bitset_map already does what you want.

This confusion is actually very beneficial. How do we document proposed
functionality? This case would probably have been solved using some
sample code plus a better description of clc_bitset_map().

Quote:

> Also, how about having the set/unset operations return the clc_bitset
> instead of void?

Maybe, but what is the benefit?

Bj?rn



Mon, 15 Aug 2005 16:51:31 GMT  
 libclc: bitset interface

Quote:

> Summary
> --------
> clc_bitset is an ADT which implements a set of bits. Each bit can be set
> or cleared using functions provided. You can create a bitset in two
> ways, either by providing your own memory (clc_bitset_map) or by having
> clc_bitset_new allocate sufficient memory.

> Interface(clc_bitset.h):
> #ifndef CLC_BITSET_H
> #define CLC_BITSET_H

> typedef struct clc_bitset_tag* clc_bitset;

> clc_bitset clc_bitset_new(size_t bitcount);
> void clc_bitset_free(clc_bitset b);

> void clc_bitset_set(clc_bitset b, size_t i);
> void clc_bitset_set_all(clc_bitset b);
> int  clc_bitset_is_set(clc_bitset b, size_t i);

> void clc_bitset_clear(clc_bitset b, size_t i);
> void clc_bitset_clear_all(clc_bitset b);

> size_t clc_bitset_size(clc_bitset b);
> void* clc_bitset_data(clc_bitset b);

> clc_bitset clc_bitset_map(void* mem, size_t cb);
> void clc_bitset_remap(clc_bitset b, void* mem, size_t cb);
> void clc_bitset_unmap(clc_bitset b);

* Bitsets are sets, so operations on sets could be in the interface.
* Also bitsets are ordered sets, so operations on ranges [ i... j [
(i included, j excluded)  could be defined.
* Facilities to toggle bits could be added to operations set()/clear().
* One should be able to copy/clone easily objects.
* miscellaneous queries about the cardinality()...

clc_bitset    clc_bitset_clone (clc_bitset);
void   clc_bitset_copy (clc_bitset target, clc_bitset source);
void clc_bitset_copy_range (clc_bitset target, clc_bitset src, size_t i, size_t j);

void    clc_bitset_toggle (clc_bitset, size_t);
void    clc_bitset_toggle_all (clc_bitset);
void    clc_bitset_toggle_range (clc_bitset, size_t i, size_t j);

void    clc_bitset_set_range (clc_bitset, size_t i, size_t j);
void    clc_bitset_clear_range (clc_bitset, size_t i, size_t j);
clc_bitset   clc_bitset_get_range (clc_bitset, size_t i, size_t j);

clc_bitset   clc_bitset_get_union (clc_bitset, clc_bitset);
void   clc_bitset_unite_with (clc_bitset accumulator, clc_bitset);
clc_bitset   clc_bitset_get_intersection (clc_bitset, clc_bitset);
void   clc_bitset_intersect_with (clc_bitset accumulator, clc_bitset);
clc_bitset   clc_bitset_get_difference (clc_bitset, clc_bitset);
void   clc_bitset_substract_with (clc_bitset accumulator, clc_bitset);
clc_bitset   clc_bitset_get_symmetric_difference (clc_bitset, clc_bitset);
etc.

int    clc_bitset_is_empty (clc_bitset);
int    clc_bitset_is_full (clc_bitset);
size_t    clc_bitset_get_cardinality  (clc_bitset);
size_t    clc_bitset_get_capacity (clc_bitset);

--
Regis



Mon, 15 Aug 2005 21:25:32 GMT  
 libclc: bitset interface

Quote:


> > Summary
> > --------
> > clc_bitset is an ADT which implements a set of bits. Each bit can be set
> > or cleared using functions provided. You can create a bitset in two
> > ways, either by providing your own memory (clc_bitset_map) or by having
> > clc_bitset_new allocate sufficient memory.

> > Interface(clc_bitset.h):
> > #ifndef CLC_BITSET_H
> > #define CLC_BITSET_H

> > typedef struct clc_bitset_tag* clc_bitset;

> > clc_bitset clc_bitset_new(size_t bitcount);
> > void clc_bitset_free(clc_bitset b);

> > void clc_bitset_set(clc_bitset b, size_t i);
> > void clc_bitset_set_all(clc_bitset b);
> > int  clc_bitset_is_set(clc_bitset b, size_t i);

> > void clc_bitset_clear(clc_bitset b, size_t i);
> > void clc_bitset_clear_all(clc_bitset b);

> > size_t clc_bitset_size(clc_bitset b);
> > void* clc_bitset_data(clc_bitset b);

> > clc_bitset clc_bitset_map(void* mem, size_t cb);
> > void clc_bitset_remap(clc_bitset b, void* mem, size_t cb);

> > void clc_bitset_unmap(clc_bitset b);

> * Bitsets are sets, so operations on sets could be in the interface.
> * Also bitsets are ordered sets, so operations on ranges [ i... j [
> (i included, j excluded)  could be defined.
> * Facilities to toggle bits could be added to operations set()/clear().
> * One should be able to copy/clone easily objects.
> * miscellaneous queries about the cardinality()...

> clc_bitset    clc_bitset_clone (clc_bitset);
> void   clc_bitset_copy (clc_bitset target, clc_bitset source);
> void clc_bitset_copy_range (clc_bitset target, clc_bitset src, size_t i, size_t j);

> void    clc_bitset_toggle (clc_bitset, size_t);
> void    clc_bitset_toggle_all (clc_bitset);
> void    clc_bitset_toggle_range (clc_bitset, size_t i, size_t j);

> void    clc_bitset_set_range (clc_bitset, size_t i, size_t j);
> void    clc_bitset_clear_range (clc_bitset, size_t i, size_t j);

> clc_bitset   clc_bitset_get_range (clc_bitset, size_t i, size_t j);

> clc_bitset   clc_bitset_get_union (clc_bitset, clc_bitset);
> void   clc_bitset_unite_with (clc_bitset accumulator, clc_bitset);
> clc_bitset   clc_bitset_get_intersection (clc_bitset, clc_bitset);
> void   clc_bitset_intersect_with (clc_bitset accumulator, clc_bitset);
> clc_bitset   clc_bitset_get_difference (clc_bitset, clc_bitset);
> void   clc_bitset_substract_with (clc_bitset accumulator, clc_bitset);
> clc_bitset   clc_bitset_get_symmetric_difference (clc_bitset, clc_bitset);
> etc.

Thinking of it, for all functions returning a new clc_bitset,
a better interface could be :
clc_bitset   clc_bitset_function (clc_bitset result, usual_args);

a new clc_bitset being created only if result is NULL,
and the argument result being returned otherwise.
This would also eliminate the versions with accumulators...

Quote:
> int    clc_bitset_is_empty (clc_bitset);
> int    clc_bitset_is_full (clc_bitset);
> size_t    clc_bitset_get_cardinality  (clc_bitset);
> size_t    clc_bitset_get_capacity (clc_bitset);

Maybe a simple default printing function could be handy too...

int   clc_bitset_print (clc_bitset, FILE *);

--
Regis



Mon, 15 Aug 2005 21:39:18 GMT  
 libclc: bitset interface

Quote:


>>Summary
>>--------
>>clc_bitset is an ADT which implements a set of bits. Each bit can be set
>>or cleared using functions provided. You can create a bitset in two
>>ways, either by providing your own memory (clc_bitset_map) or by having
>>clc_bitset_new allocate sufficient memory.

>>Interface(clc_bitset.h):
>>#ifndef CLC_BITSET_H
>>#define CLC_BITSET_H

>>typedef struct clc_bitset_tag* clc_bitset;

>>clc_bitset clc_bitset_new(size_t bitcount);
>>void clc_bitset_free(clc_bitset b);

>>void clc_bitset_set(clc_bitset b, size_t i);
>>void clc_bitset_set_all(clc_bitset b);
>>int  clc_bitset_is_set(clc_bitset b, size_t i);

>>void clc_bitset_clear(clc_bitset b, size_t i);
>>void clc_bitset_clear_all(clc_bitset b);

>>size_t clc_bitset_size(clc_bitset b);
>>void* clc_bitset_data(clc_bitset b);

>>clc_bitset clc_bitset_map(void* mem, size_t cb);
>>void clc_bitset_remap(clc_bitset b, void* mem, size_t cb);

>>void clc_bitset_unmap(clc_bitset b);

> * Bitsets are sets, so operations on sets could be in the interface.
> * Also bitsets are ordered sets, so operations on ranges [ i... j [
> (i included, j excluded)  could be defined.
> * Facilities to toggle bits could be added to operations set()/clear().
> * One should be able to copy/clone easily objects.
> * miscellaneous queries about the cardinality()...

> clc_bitset    clc_bitset_clone (clc_bitset);
> void   clc_bitset_copy (clc_bitset target, clc_bitset source);
> void clc_bitset_copy_range (clc_bitset target, clc_bitset src, size_t i, size_t j);

> void    clc_bitset_toggle (clc_bitset, size_t);
> void    clc_bitset_toggle_all (clc_bitset);
> void    clc_bitset_toggle_range (clc_bitset, size_t i, size_t j);

> void    clc_bitset_set_range (clc_bitset, size_t i, size_t j);
> void    clc_bitset_clear_range (clc_bitset, size_t i, size_t j);
> clc_bitset   clc_bitset_get_range (clc_bitset, size_t i, size_t j);

> clc_bitset   clc_bitset_get_union (clc_bitset, clc_bitset);
> void   clc_bitset_unite_with (clc_bitset accumulator, clc_bitset);
> clc_bitset   clc_bitset_get_intersection (clc_bitset, clc_bitset);
> void   clc_bitset_intersect_with (clc_bitset accumulator, clc_bitset);
> clc_bitset   clc_bitset_get_difference (clc_bitset, clc_bitset);
> void   clc_bitset_substract_with (clc_bitset accumulator, clc_bitset);
> clc_bitset   clc_bitset_get_symmetric_difference (clc_bitset, clc_bitset);
> etc.

> int    clc_bitset_is_empty (clc_bitset);
> int    clc_bitset_is_full (clc_bitset);
> size_t    clc_bitset_get_cardinality  (clc_bitset);
> size_t    clc_bitset_get_capacity (clc_bitset);

All in all a great set of functions. A general question regarding the
interfaces. What if the bitsets have different size, e.g. for
clc_bitset_copy? Should we return a "size mismatch" status code or just
copy as much as possible and silently ignore the mismatch?

Bj?rn



Mon, 15 Aug 2005 21:44:41 GMT  
 libclc: bitset interface

Quote:



> >>Summary
> >>--------
> >>clc_bitset is an ADT which implements a set of bits. Each bit can be set
> >>or cleared using functions provided. You can create a bitset in two
> >>ways, either by providing your own memory (clc_bitset_map) or by having
> >>clc_bitset_new allocate sufficient memory.

> >>Interface(clc_bitset.h):
> >>#ifndef CLC_BITSET_H
> >>#define CLC_BITSET_H

> >>typedef struct clc_bitset_tag* clc_bitset;

> >>clc_bitset clc_bitset_new(size_t bitcount);
> >>void clc_bitset_free(clc_bitset b);

> >>void clc_bitset_set(clc_bitset b, size_t i);
> >>void clc_bitset_set_all(clc_bitset b);
> >>int  clc_bitset_is_set(clc_bitset b, size_t i);

> >>void clc_bitset_clear(clc_bitset b, size_t i);
> >>void clc_bitset_clear_all(clc_bitset b);

> >>size_t clc_bitset_size(clc_bitset b);
> >>void* clc_bitset_data(clc_bitset b);

> >>clc_bitset clc_bitset_map(void* mem, size_t cb);
> >>void clc_bitset_remap(clc_bitset b, void* mem, size_t cb);

> >>void clc_bitset_unmap(clc_bitset b);

> > * Bitsets are sets, so operations on sets could be in the interface.
> > * Also bitsets are ordered sets, so operations on ranges [ i... j [
> > (i included, j excluded)  could be defined.
> > * Facilities to toggle bits could be added to operations set()/clear().
> > * One should be able to copy/clone easily objects.
> > * miscellaneous queries about the cardinality()...

> > clc_bitset    clc_bitset_clone (clc_bitset);
> > void   clc_bitset_copy (clc_bitset target, clc_bitset source);
> > void clc_bitset_copy_range (clc_bitset target, clc_bitset src, size_t i, size_t j);

> > void    clc_bitset_toggle (clc_bitset, size_t);
> > void    clc_bitset_toggle_all (clc_bitset);
> > void    clc_bitset_toggle_range (clc_bitset, size_t i, size_t j);

> > void    clc_bitset_set_range (clc_bitset, size_t i, size_t j);
> > void    clc_bitset_clear_range (clc_bitset, size_t i, size_t j);
> > clc_bitset   clc_bitset_get_range (clc_bitset, size_t i, size_t j);

> > clc_bitset   clc_bitset_get_union (clc_bitset, clc_bitset);
> > void   clc_bitset_unite_with (clc_bitset accumulator, clc_bitset);
> > clc_bitset   clc_bitset_get_intersection (clc_bitset, clc_bitset);
> > void   clc_bitset_intersect_with (clc_bitset accumulator, clc_bitset);
> > clc_bitset   clc_bitset_get_difference (clc_bitset, clc_bitset);
> > void   clc_bitset_substract_with (clc_bitset accumulator, clc_bitset);
> > clc_bitset   clc_bitset_get_symmetric_difference (clc_bitset, clc_bitset);
> > etc.

> > int    clc_bitset_is_empty (clc_bitset);
> > int    clc_bitset_is_full (clc_bitset);
> > size_t    clc_bitset_get_cardinality  (clc_bitset);
> > size_t    clc_bitset_get_capacity (clc_bitset);

> All in all a great set of functions. A general question regarding the
> interfaces. What if the bitsets have different size, e.g. for
> clc_bitset_copy? Should we return a "size mismatch" status code or just
> copy as much as possible and silently ignore the mismatch?

As a first thought, I'd say  it most often will reveal a bug in the user code,
so I would go for a noisy failure. But copying only on the common prefix
range is also meaningful...

As an alternative, an additional enum
could be passed as an argument by the user to specify
whether potential size mismatches are intentional,
But the interface should should be as simple to use as possible
so it is not necessarily a good idea...

CLC_BITSET_TRUNCATE:
copy only the common part, the shortest is not resized
CLC_BITSET_RESIZE:
clc_bitset_resize() is invoked to resize the shortest on the longest
CLC_BITSET_FAIL:
some noisy failure whose mechanism should be somewhat common
for most of the library features.



Mon, 15 Aug 2005 23:31:04 GMT  
 libclc: bitset interface

Quote:

> Maybe a simple default printing function could be handy too...

> int   clc_bitset_print (clc_bitset, FILE *);

Thi function is primarily a help for the user to debug his code.
But long outputs will be unreadable by any human if chunk of bits
are not separated on a regular short basis by a space or something else,
so:

int clc_bitset_print (clc_bitset, int chunk_length, char separator, FILE *);
for chunk_length==0, no separator would occurs.
An output for chunk_length==8 and separator==' ' could be:

000011111 00110011 1110

--
Regis



Mon, 15 Aug 2005 23:45:40 GMT  
 libclc: bitset interface

Quote:


>>Maybe a simple default printing function could be handy too...

>>int   clc_bitset_print (clc_bitset, FILE *);

> Thi function is primarily a help for the user to debug his code.
> But long outputs will be unreadable by any human if chunk of bits
> are not separated on a regular short basis by a space or something else,
> so:

> int clc_bitset_print (clc_bitset, int chunk_length, char separator, FILE *);
> for chunk_length==0, no separator would occurs.
> An output for chunk_length==8 and separator==' ' could be:

> 000011111 00110011 1110

Hmm. To be able to print a bitset is a good idea, but should the
printing function be a part of the adt? The current interface already
exposes enough of its internals to print the bitset. Here's one
way(never compiled):

void myprinter(FILE *f, clc_bitset b)
{
     char* data;
     size_t i, cb;

     data = clc_bitset_data(b);
     cb = clc_bitset_size(b);

     for(i = 0; i < cb; i++) {
         print_char_bit_pattern(f, data[i]);
         fprintf(f, my_favourite_separator);
     }

Quote:
}

I believe that it is better to separate FILE and clc_bitset, and instead
use adaptor functions like the one above.

Bj?rn



Tue, 16 Aug 2005 01:35:30 GMT  
 libclc: bitset interface

Quote:





> >>>>Here's an interface for some code which may have its place in libclc. I
> >>>>hope that this post and the discussion will teach us more about how we
> >>>>should submit code to libclc.

> >>>>Since this is the first submittal, it raises some questions:
> >>>>- Do we need/want this code? How do we decide/vote?
> >>>>- I deliberately chose code that uses an ADT. Do we want ADT's in libclc?
> >>>>- The submitted interface is stripped of comments. How do we describe
> >>>>the interface? (Since this post is a bit experimental, I have included a
> >>>>version of clc_bitset.h which has comments.)
> >>>>- I chose to submit the interface first and will submit the proposed
> >>>>implementation later if the interface is accepted. Is that OK?

> >>>[snip]

> >>>Looks good, but there should be:
> >>>* A function to resize the bitset, assuming it's allocated by
> >>>clc_bitset_new()

> >>Good idea. How about
> >>     int clc_bitset_resize(clc_bitset bs, size_t new_bitcount);

> >>returning 0 on error and 1 on success? The semantics can be like
> >>realloc, where reducing the bit count frees memory. Will this do?

> >>>* A function to map and create a bitset

> >>Not quite sure what you mean here. Please provide more info.

> > Like this:
> > clc_bitset clt_bitset_new_map(void *buf, size_t bytecount);
> > That's essentially clc_bitset_new() and clc_bitset_map() rolled into one.

> Now I see what you mean. The proposed interface has two ways of creating
> a bitset. You either call clc_bitset_new() *or* you create a bitset from
> an existing piece of memory using clc_bitset_map(). I believe
> clc_bitset_map already does what you want.

> This confusion is actually very beneficial. How do we document proposed
> functionality? This case would probably have been solved using some
> sample code plus a better description of clc_bitset_map().

Oh, I see. I missed the return type.

Quote:

> > Also, how about having the set/unset operations return the clc_bitset
> > instead of void?

> Maybe, but what is the benefit?

eg. clc_bitset_set(clc_bitset_set(set, 1), 2);


Tue, 16 Aug 2005 02:23:54 GMT  
 
 [ 25 post ]  Go to page: [1] [2]

 Relevant Pages 

1. libclc: bitset interface, new final vote

2. libclc bitset import/export

3. libclc: clc_bitset interface, final vote

4. libclc: clc_assert interface

5. Bitset examples from the FAQ (unsigned char?)

6. Help in finding the bitsets?

7. C++ to C# std::bitset

8. BITSET

9. bitsets

10. bitset

11. bitset?

12. template-Klasse bitset

 

 
Powered by phpBB® Forum Software