QuakeForge  0.7.2.210-815cf
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Modules Pages
Set handling

Data Structures

struct  set_iter_s
 Represent the state of a scan through a set. More...
 
struct  set_pool_s
 
struct  set_s
 Represent a set using a bitmap. More...
 

Macros

#define SET_BITS   (sizeof (set_bits_t) * 8)
 
#define SET_DEFMAP_SIZE
 
#define SET_ONE   ((set_bits_t) 1)
 
#define SET_SIZE(x)   (((x) + SET_BITS) & ~(SET_BITS - 1))
 
#define SET_TEST_MEMBER(s, x)   ((s)->map[(x) / SET_BITS] & (SET_ONE << ((x) % SET_BITS)))
 
#define SET_WORDS(s)   ((s)->size / SET_BITS)
 
#define SET_ZERO   ((set_bits_t) 0)
 

Typedefs

typedef uint32_t set_bits_t
 
typedef struct set_iter_s set_iter_t
 Represent the state of a scan through a set. More...
 
typedef struct set_pool_s set_pool_t
 
typedef struct set_s set_t
 Represent a set using a bitmap. More...
 

Functions

set_tset_add (set_t *set, unsigned x)
 Add an element to a set. More...
 
const char * set_as_string (const set_t *set)
 Return a human-readable string representing the set. More...
 
set_tset_assign (set_t *dst, const set_t *src)
 Make a set equivalent to another. More...
 
void set_del_iter (set_iter_t *set_iter)
 Delete a set iterator that is no longer needed. More...
 
void set_del_iter_r (set_pool_t *set_pool, set_iter_t *set_iter)
 
void set_delete (set_t *set)
 Delete a set that is no longer needed. More...
 
void set_delete_r (set_pool_t *set_pool, set_t *set)
 
set_tset_difference (set_t *dst, const set_t *src)
 Compute the diffedrence of two sets. More...
 
set_tset_empty (set_t *set)
 Make a set the empty set. More...
 
set_tset_everything (set_t *set)
 Make a set the set of everything. More...
 
set_iter_tset_first (const set_t *set)
 Find the first "member" of the set. More...
 
set_iter_tset_first_r (set_pool_t *set_pool, const set_t *set)
 
set_tset_intersection (set_t *dst, const set_t *src)
 Compute the intersection of two sets. More...
 
set_tset_invert (set_t *set)
 Compute the inverse of a set. More...
 
int set_is_disjoint (const set_t *s1, const set_t *s2)
 Test if two sets are disjoint. More...
 
int set_is_empty (const set_t *set)
 Test if a set is the set of everything. More...
 
int set_is_equivalent (const set_t *s1, const set_t *s2)
 Test if two sets are equivalent. More...
 
int set_is_everything (const set_t *set)
 Test if a set is the set of everything. More...
 
int set_is_intersecting (const set_t *s1, const set_t *s2)
 Test if two sets intersect. More...
 
int set_is_member (const set_t *set, unsigned x)
 Test an element for membership in a set. More...
 
int set_is_subset (const set_t *set, const set_t *sub)
 Test if a set is a subset of another set. More...
 
set_tset_new (void)
 Create a new set. More...
 
set_tset_new_r (set_pool_t *set_pool)
 
set_tset_new_size (int size)
 Create a new set with space pre-allocated for the specified set size. More...
 
set_tset_new_size_r (set_pool_t *set_pool, int size)
 
set_iter_tset_next (set_iter_t *set_iter)
 Find the next "member" of the set. More...
 
set_iter_tset_next_r (set_pool_t *set_pool, set_iter_t *set_iter)
 
void set_pool_init (set_pool_t *set_pool)
 
set_tset_remove (set_t *set, unsigned x)
 Remove an element from a set. More...
 
set_tset_reverse_difference (set_t *dst, const set_t *src)
 Compute the diffedrence of two sets. More...
 
unsigned set_size (const set_t *set)
 Obtain the number of members (or non-members) of a set. More...
 
set_tset_union (set_t *dst, const set_t *src)
 Compute the union of two sets. More...
 

Detailed Description

Macro Definition Documentation

#define SET_BITS   (sizeof (set_bits_t) * 8)
#define SET_DEFMAP_SIZE
Value:
((32 - sizeof (struct set_s *) \
- sizeof (set_bits_t *) \
- sizeof (int) - sizeof (unsigned))\
/ sizeof (set_bits_t))
int(PASCAL FAR *pWSAStartup)(WORD wVersionRequired
Represent a set using a bitmap.
Definition: set.h:68
uint32_t set_bits_t
Definition: set.h:45
#define SET_ONE   ((set_bits_t) 1)
#define SET_SIZE (   x)    (((x) + SET_BITS) & ~(SET_BITS - 1))
#define SET_TEST_MEMBER (   s,
  x 
)    ((s)->map[(x) / SET_BITS] & (SET_ONE << ((x) % SET_BITS)))
#define SET_WORDS (   s)    ((s)->size / SET_BITS)
#define SET_ZERO   ((set_bits_t) 0)

Typedef Documentation

typedef uint32_t set_bits_t
typedef struct set_iter_s set_iter_t

Represent the state of a scan through a set.

Very useful in for-loops:

1 set_t *set;
2 set_iter_t *iter;
3 
4 create_and_populate (set);
5 for (iter = set_first (set); iter; iter = set_next (iter))
6  do_something (iter->element);
typedef struct set_pool_s set_pool_t
typedef struct set_s set_t

Represent a set using a bitmap.

When inverted is zero, ones in the bitmap represent members, but when inverted is non-zero, zeros in the bitmap represent members. However, this really is all private implementation details and it is best to treat set_t as a black box.

Function Documentation

set_t* set_add ( set_t set,
unsigned  x 
)

Add an element to a set.

It is not an error to add an element that is already a member of the set.

Note
set is modified.
Parameters
setThe set to which the element will be added.
xThe element to be added.
Returns
The modified set.
const char* set_as_string ( const set_t set)

Return a human-readable string representing the set.

Empty sets will be represented by the string "[empty]". Sets of everything will be represented by the string "[everything]". Inverted sets will have the first implicit member followed by "..." (eg, "256 ...").

Parameters
setThe set to be converted to a string.
Returns
The human readable representation of the string.
Warning
The string is kept in a static variable, so subsequent calls will overwrite the results of preceeding calls.
set_t* set_assign ( set_t dst,
const set_t src 
)

Make a set equivalent to another.

Note
dst is modified.
Parameters
dstThe destination set to make equivalent.
srcThe source set to assign to dst.
Returns
The modified destination set.
void set_del_iter ( set_iter_t set_iter)

Delete a set iterator that is no longer needed.

Parameters
set_iterThe set iterator to be deleted.
void set_del_iter_r ( set_pool_t set_pool,
set_iter_t set_iter 
)
void set_delete ( set_t set)

Delete a set that is no longer needed.

Parameters
setThe set to be deleted.
void set_delete_r ( set_pool_t set_pool,
set_t set 
)
set_t* set_difference ( set_t dst,
const set_t src 
)

Compute the diffedrence of two sets.

The computation is done as dst = dst - src.

Note
dst is modified.
Parameters
dstThe destination set to be modified.
srcThe source set.
Returns
The destination set modified to be dst - src.
set_t* set_empty ( set_t set)

Make a set the empty set.

Note
set is modified.
Parameters
setThe set to make the empty set.
Returns
set.
set_t* set_everything ( set_t set)

Make a set the set of everything.

Note
set is modified.
Parameters
setThe set to make the set of everything.
Returns
set.
set_iter_t* set_first ( const set_t set)

Find the first "member" of the set.

Warning
For normal sets, the set iterator represents a member of the set, but for inverted sets, the set iterator represetns a non-member of the set.
Parameters
setThe set to scan.
Returns
A pointer to a set iterator indicating the first (non-)member of the set, or null if the set is empty or of everything.
set_iter_t* set_first_r ( set_pool_t set_pool,
const set_t set 
)
set_t* set_intersection ( set_t dst,
const set_t src 
)

Compute the intersection of two sets.

The computation is done as dst = dst & src.

Note
dst is modified.
Parameters
dstThe destination set to be modified.
srcThe source set.
Returns
The destination set modified to be dst & src.
set_t* set_invert ( set_t set)

Compute the inverse of a set.

The computation is done as set = ~set.

Note
set is modified.
Parameters
setThe set to be inverted.
Returns
The set modified to be ~src.
int set_is_disjoint ( const set_t s1,
const set_t s2 
)

Test if two sets are disjoint.

Parameters
s1The first set to test.
s2The second set to test.
Returns
1 if s2 is disjoint from s1, 0 if not.
Note
The emtpy set is disjoint with itself.
int set_is_empty ( const set_t set)

Test if a set is the set of everything.

Parameters
setThe set to test.
Returns
1 if set is empty (non-inverted).
int set_is_equivalent ( const set_t s1,
const set_t s2 
)

Test if two sets are equivalent.

Parameters
s1The first set to test.
s2The second set to test.
Returns
1 if s2 is equivalent to s1, 0 if not.
int set_is_everything ( const set_t set)

Test if a set is the set of everything.

Parameters
setThe set to test.
Returns
1 if set is the set of everything (empty inverted set).
int set_is_intersecting ( const set_t s1,
const set_t s2 
)

Test if two sets intersect.

Parameters
s1The first set to test.
s2The second set to test.
Returns
1 if s2 intersects s1, 0 if not.
Note
Equivalent non-empty sets are treated as intersecting.
int set_is_member ( const set_t set,
unsigned  x 
)

Test an element for membership in a set.

Parameters
setThe set to test.
xThe element to test.
Returns
1 if the element is a member of the set, otherwise 0.
int set_is_subset ( const set_t set,
const set_t sub 
)

Test if a set is a subset of another set.

An equivalent set is considered to be a subset.

Parameters
setThe potential super-set.
subThe potential subset.
Returns
1 if sub is a subset of set, or if the sets are equivalent.
set_t* set_new ( void  )

Create a new set.

The set is initialized to be the empty set.

Returns
The newly created, empty set.
set_t* set_new_r ( set_pool_t set_pool)
inline
set_t* set_new_size ( int  size)

Create a new set with space pre-allocated for the specified set size.

Although sets automatically grow to accommodate new members as necessary, sometimes the maximum set size is known in advance and it can be more efficient to grow the set in advance.

The set is initialized to be the empty set.

Parameters
sizeThe number of elements for which space is to be allocated.
Returns
The newly created, empty set.
set_t* set_new_size_r ( set_pool_t set_pool,
int  size 
)
inline
set_iter_t* set_next ( set_iter_t set_iter)

Find the next "member" of the set.

Warning
For normal sets, the set iterator represents a member of the set, but for inverted sets, the set iterator represetns a non-member of the set.
Parameters
set_iterThe set iterator representing the state of the current scan.
Returns
A pointer to a set iterator indicating the next (non-)member of the set, or null if no mor (non-)members are available.
Note
The set iterator is automatically deleted when the end of the set is reached.
set_iter_t* set_next_r ( set_pool_t set_pool,
set_iter_t set_iter 
)
void set_pool_init ( set_pool_t set_pool)
set_t* set_remove ( set_t set,
unsigned  x 
)

Remove an element from a set.

It is not an error to remove an element that is not a member of the set.

Note
set is modified.
Parameters
setThe set from which the element will be removed.
xThe element to be removed.
Returns
The modified set.
set_t* set_reverse_difference ( set_t dst,
const set_t src 
)

Compute the diffedrence of two sets.

The computation is done as dst = src - dst.

Note
dst is modified.
Parameters
dstThe destination set to be modified.
srcThe source set.
Returns
The destination set modified to be src - dst.
unsigned set_size ( const set_t set)

Obtain the number of members (or non-members) of a set.

Normal sets return the number of members, inverted sets return the number of non-members.

Parameters
setThe set from which the number of (non-)members will be obtained.
Returns
The number of (non-)members. Both empty sets and sets of evertything will return 0.
set_t* set_union ( set_t dst,
const set_t src 
)

Compute the union of two sets.

The computation is done as dst = dst | src.

Note
dst is modified.
Parameters
dstThe destination set to be modified.
srcThe source set.
Returns
The destination set modified to be dst | src.