set.c File Reference

Source for Set Library (CDSL). More...

#include <limits.h>
#include <stddef.h>
#include "cbl/memory.h"
#include "cbl/assert.h"
#include "set.h"

Include dependency graph for set.c:


Data Structures

struct  set_t
struct  set_t::set_t::member

Defines

#define MAX(x, y)   ((x) > (y)? (x): (y))
#define MIN(x, y)   ((x) > (y)? (y): (x))

Functions

set_t *() set_new (int hint, int cmp(const void *, const void *), unsigned hash(const void *))
 creates a new set.
int() set_member (set_t *set, const void *member)
 inspects if a set contains a member.
void() set_put (set_t *set, const void *member)
 puts a member to a set.
void *() set_remove (set_t *set, const void *member)
 removes a member from a set.
size_t() set_length (set_t *set)
 returns the length of a set.
void() set_free (set_t **pset)
 destroys a set.
void() set_map (set_t *set, void apply(const void *member, void *cl), void *cl)
 calls a user-provided function for each member in a set.
void **() set_toarray (set_t *set, void *end)
 converts a set to an array.
set_t *() set_union (set_t *s, set_t *t)
 returns a union set of two sets.
set_t *() set_inter (set_t *s, set_t *t)
 returns an intersection of two sets.
set_t *() set_minus (set_t *s, set_t *t)
 returns a difference set of two sets
set_t *() set_diff (set_t *s, set_t *t)
 returns a symmetric difference of two sets.

Detailed Description

Source for Set Library (CDSL).


Define Documentation

#define MAX ( x,
 )     ((x) > (y)? (x): (y))

returns the larger of two

#define MIN ( x,
 )     ((x) > (y)? (y): (x))

returns the smaller of two


Function Documentation

set_t*() set_diff ( set_t s,
set_t t 
)

returns a symmetric difference of two sets.

set_diff() returns a symmetric difference of two sets, that is a set with members only one of two operand sets has. A symmetric difference set is identical to the union set of (s - t) and (t - s). See set_union() for more detailed explanation commonly applied to the set operation functions.

Possible exceptions: assert_exceptfail, mem_exceptfail

Unchecked errors: foreign data structure given for s or t

Parameters:
[in] s operand of set difference operation
[in] t operand of set difference operation
Returns:
symmetric difference set
Todo:
Improvements are possible and planned:
  • the code can be modified so that the operation is performed on each pair of corresponding buckets when two given sets have the same number of buckets.

Here is the call graph for this function:

void() set_free ( set_t **  pset  ) 

destroys a set.

set_free() destroys a set by deallocating the storage for it and set a given pointer to a null pointer. As always, set_free() does not deallocate any storage for members in the set, which must be done by a user.

Possible exceptions: assert_exceptfail

Unchecked errors: pointer to foreign data structure given for pset

Parameters:
[in,out] pset pointer to set to destroy
Returns:
nothing

set_t*() set_inter ( set_t s,
set_t t 
)

returns an intersection of two sets.

set_inter() returns an intersection of two sets, that is a set with only members that both have in common. See set_union() for more detailed explanation commonly applied to the set operation functions.

Possible exceptions: assert_exceptfail, mem_exceptfail

Unchecked errors: foreign data structure given for s or t

Parameters:
[in] s operand of set intersection operation
[in] t operand of set intersection operation
Returns:
intersection set
Todo:
Improvements are possible and planned:
  • the code can be modified so that the operation is performed on each pair of corresponding buckets when two given sets have the same number of buckets.

Here is the call graph for this function:

Here is the caller graph for this function:

size_t() set_length ( set_t set  ) 

returns the length of a set.

set_length() returns the length of a set which is the number of all members in a set.

Possible exceptions: assert_exceptfail

Unchecked errors: foreign data structure given for set

Parameters:
[in] set set whose length returned
Returns:
length of set

void() set_map ( set_t set,
void   applyconst void *member, void *cl,
void *  cl 
)

calls a user-provided function for each member in a set.

For each member in a set, set_map() calls a user-provided callback function; it is useful when doing some common task for each member. The pointer given in cl is passed to the third parameter of a user callback function, so can be used as a communication channel between the caller of set_map() and the callback. Differently from table_map(), set_map() gives a member (which is a pointer value) to apply() rather than a pointer to a member (which is a pointer to pointer value); compare the type of the member parameter of apply() to that of the value parameter of apply() in table_map(). This is very natural since a member plays a role of a hashing key in a set as a key does in a table. Also note that apply() is not able to modify a member itself but can do a value pointed by the member.

Possible exceptions: assert_exceptfail

Unchecked errors: foreign data structure given for set

Warning:
The order in which a user-provided function is called for each member is unspecified; a set is an unordered collection of members, so this is not a limiting factor, however.
Parameters:
[in,out] set set with which apply called
[in] apply user-provided function (callback)
[in] cl passing-by argument to apply
Returns:
nothing

int() set_member ( set_t set,
const void *  member 
)

inspects if a set contains a member.

set_member() inspects a set to see if it contains a given member.

Possible exceptions: assert_exceptfail

Unchecked errors: foreign data structure given for set

Parameters:
[in] set set to inspect
[in] member member to find in a set
Returns:
found/not found indicator
Return values:
0 member not found
1 member found

Here is the caller graph for this function:

set_t*() set_minus ( set_t s,
set_t t 
)

returns a difference set of two sets

set_inter() returns a difference of two sets, that is a set with members that t has but does not. See set_union() for more detailed explanation commonly applied to the set operation functions.

Possible exceptions: assert_exceptfail, mem_exceptfail

Unchecked errors: foreign data structure given for s or t

Parameters:
[in] s operand of set difference operation
[in] t operand of set difference operation
Returns:
difference set, s - t
Todo:
Improvements are possible and planned:
  • the code can be modified so that the operation is performed on each pair of corresponding buckets when two given sets have the same number of buckets.

Here is the call graph for this function:

set_t*() set_new ( int  hint,
int   cmpconst void *, const void *,
unsigned   hashconst void * 
)

creates a new set.

set_new() creates a new set. It takes some information on a set it will create:

  • hint: an estimate for the size of a set;
  • cmp: a user-provided function for comparing members;
  • hash: a user-provided function for generating a hash value from a member

set_new() determines the size of the internal hash table kept in a set based on hint. It never restricts the number of members one can put into a set, but a better estimate probably bring better performance.

A function given to cmp should be defined to take two arguments and to return a value less than, equal to or greater than zero to indicate that the first argument is less than, equal to or greater than the second argument, respectively.

A function given to hash takes a member and returns a hash value that is to be used as an index for internal hash table in a set. If the cmp function returns zero (which means they are equal) for some two members, the hash function must generate the same value for them.

If a null pointer is given for cmp or hash, the default comparison or hashing function is used; see defhashCmp() and defhashGen(), in which case members are assumed to be hash strings generated by the Hash Library. An example is given below:

      set_t *myset = set_new(hint, NULL, NULL);
      ...
      set_put(hash_string("member1"));
      set_put(hash_string("member2"));
      assert(set_member(hash_string("member1")));

Possible exceptions: mem_exceptfail

Unchecked errors: invalid functions for cmp and hash

Parameters:
[in] hint hint for size of hash table
[in] cmp user-defined comparison function
[in] hash user-defined hash generating function
Returns:
new set created

Here is the caller graph for this function:

void() set_put ( set_t set,
const void *  member 
)

puts a member to a set.

set_put() inserts a member to a set. If it fails to find a member matched to a given member, it inserts the given member to a set after proper storage allocation. If it finds a matched one, it replaces an existing member with a given one. Even if they compare equal by a user-defined comparison function, they may have different representations. Thus, replacing the old one with the new one makes sense.

Note that a member is a pointer. If members are, say, integers in an application, objects to contain them are necessary to put them into a set.

Possible exceptions: assert_exceptfail, mem_exceptfail

Unchecked errors: foreign data structure given for set

Parameters:
[in,out] set set to which member inserted
[in] member member to insert
Returns:
nothing

Here is the caller graph for this function:

void*() set_remove ( set_t set,
const void *  member 
)

removes a member from a set.

set_remove() gets rid of a member from a set. Note that set_remove() does not deallocate any storage for the member to remove, which must be done by a user.

Possible exceptions: assert_exceptfail

Unchecked errors: foreign data structure given for set

Parameters:
[in,out] set set from whcih member removed
[in] member member to remove
Returns:
previous member or null pointer
Return values:
non-null previous member
NULL member not found
Warning:
If the stored member is a null pointer, an ambiguous situation may occur.

void**() set_toarray ( set_t set,
void *  end 
)

converts a set to an array.

set_toarray() converts members stored in a set to an array. The last element of the constructed array is assigned by end, which is a null pointer in most cases. Do not forget deallocate the array when it is unnecessary.

Possible exceptions: assert_exceptfail, mem_exceptfail

Unchecked errors: foreign data structure given for set

Warning:
The size of an array generated from an empty set is not zero, since there is always an end-mark.

As in set_map(), the order in which an array is created for each member is unspecified.

Parameters:
[in] set set for which array generated
[in] end end-mark to save in last element of array
Returns:
array generated from set

set_t*() set_union ( set_t s,
set_t t 
)

returns a union set of two sets.

set_union() creates a union set of two given sets and returns it. One of those may be a null pointer, in which case a null pointer is considered an empty set. For every operation, its result constitutes a distinct set from its operand sets, which means the set operations always allocate storage for their results even when one of the operands is empty.

Note that the inferface of the Set Library does not assume the concept of a universe, which is the set of all possible members. Thus, a set operation like the complement of a set is not defined and not implemented.

Possible exceptions: assert_exceptfail, mem_exceptfail

Unchecked errors: foreign data structure given for s or t

Warning:
To create a union of two sets, they have to share the same comparison and hashing functions.
Parameters:
[in] s operand of set union operation
[in] t operand of set union operation
Returns:
union set
Todo:
Improvements are possible and planned:
  • the code can be modified so that the operation is performed on each pair of corresponding buckets when two given sets have the same number of buckets.

Here is the call graph for this function:


Generated on Mon Jan 24 01:13:03 2011 for The Set Library by  doxygen 1.5.8