table.c File Reference

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

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

Include dependency graph for table.c:


Data Structures

struct  table_t
struct  table_t::table_t::binding

Functions

table_t *() table_new (int hint, int cmp(const void *, const void *), unsigned hash(const void *))
 creates a new table.
void *() table_get (const table_t *table, const void *key)
 gets data for a key from a table.
void *() table_put (table_t *table, const void *key, void *value)
 puts a value for a key to a table.
size_t() table_length (const table_t *table)
 returns the length of a table.
void() table_map (table_t *table, void apply(const void *key, void **value, void *cl), void *cl)
 calls a user-provided function for each key-value pair in a table.
void *() table_remove (table_t *table, const void *key)
 removes a key-value pair from a table.
void **() table_toarray (const table_t *table, void *end)
 converts a table to an array.
void() table_free (table_t **ptable)
 destroys a table.

Detailed Description

Source for Table Library (CDSL).


Function Documentation

void() table_free ( table_t **  ptable  ) 

destroys a table.

table_free() destroys a table by deallocating the stroage for it and set a given pointer to the null pointer. As always, table_free() does not deallocate storages for values in the table, which must be done by a user.

Possible exceptions: assert_exceptfail

Unchecked errors: pointer to foreign data structure given for ptable

Parameters:
[in,out] ptable pointer to table to destroy
Returns:
nothing

void*() table_get ( const table_t table,
const void *  key 
)

gets data for a key from a table.

table_get() returns a value associated with a given key.

Possible exceptions: assert_exceptfail

Unchecked errors: foreign data structure given for table

Parameters:
[in] table table in which key-value pair to be found
[in] key key for which value to be returned
Returns:
value for given key or null pointer
Return values:
non-null value found
NULL value not found
Warning:
If the stored value was a null pointer, an ambiguous situation may occur.

size_t() table_length ( const table_t table  ) 

returns the length of a table.

table_length() returns the length of a table which is the number of all key-value pairs in a table.

Possible exceptions: assert_exceptfail

Unchecked errors: foreign data structure given for table

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

void() table_map ( table_t table,
void   applyconst void *key, void **value, void *cl,
void *  cl 
)

calls a user-provided function for each key-value pair in a table.

For each key-value pair in a table, table_map() calls a user-provided callback function; it is useful when doing some common task for each node. 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 table_map() and the callback. Since the callback has the address of value (as opposed to the value of value) through the second parameter, it is free to change its content. A macro like LIST_FOREACH() provided in the List Library is not provided for a table.

Possible exceptions: assert_exceptfail

Unchecked errors: foreign data structure given for table

Warning:
The order in which a user-provided function is called for each key-value pair is unspecified.
Parameters:
[in,out] table table with which apply called
[in] apply user-provided function (callback)
[in] cl passing-by argument to apply
Returns:
nothing
Todo:
Improvements are possible and planned:
  • it sometimes serves better to call a user callback for key-value pairs in order they are stored.

table_t*() table_new ( int  hint,
int   cmpconst void *, const void *,
unsigned   hashconst void * 
)

creates a new table.

table_new() creates a new table. It takes some information on a table it will create:

  • hint: an estimate for the size of a table;
  • cmp: a user-provided function for comparing keys;
  • hash: a user-provided function for generating a hash value from a key

table_new() determines the size of the internal hash table kept in a table based on hint. It never restricts the number of entries one can put into a table, 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 key and returns a hash value that is to be used as an index for the internal hash table in a table. If the cmp function returns zero (which means they are equal) for some two keys, 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 keys are assumed to be hash strings generated by the Hash Library. An example is given below:

      table_t *mytable = table_new(hint, NULL, NULL);
      int *pi, val1, val2;
      ...
      table_put(hash_string("key1"), &val1);
      table_put(hash_string("key2"), &val2);
      pi = table_get(hash_string(key1));
      assert(pi == &val1);

hash. They are all required in the interface to allow for vairous implementation approaches.

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 table created

void*() table_put ( table_t table,
const void *  key,
void *  value 
)

puts a value for a key to a table.

table_put() replaces an existing value for a given key with given one and returns the previous value. If there is no existing one, the given value is saved for the key and returns a null pointer.

Note that both a key and a value are pointers. If values are, say, integers in an application, objects to contain them are necessary to put them into a table.

Possible exceptions: assert_exceptfail, mem_exceptfail

Unchecked errors: foreign data structure given for table

Parameters:
[in,out] table table to which value to be stored
[in] key key for which value to be stored
[in] value value to store to table
Returns:
previous value for key or null pointer
Return values:
non-null previous value
NULL no previous value found
Warning:
If the stored value was a null pointer, an ambiguous situation may occur.

void*() table_remove ( table_t table,
const void *  key 
)

removes a key-value pair from a table.

table_remove() gets rid of a key-value pair for a given key from a table. Note that table_remove() does not deallocate any storage for the pair to remove, which must be done by an user.

Possible exceptions: assert_exceptfail

Unchecked errors: foreign data structure given for table

Parameters:
[in,out] table table from which key-value pair removed
[in] key key for which key-value pair removed
Returns:
previous value for given key or null pointer
Return values:
non-null previous value for key
NULL key not found
Warning:
If the stored value is a null pointer, an ambiguous situation may occur.

void**() table_toarray ( const table_t table,
void *  end 
)

converts a table to an array.

table_toarray() converts key-value pairs stored in a table 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.

The resulting array is consisted of key-value pairs: its elements with even indices have keys and those with odd indices have corresponding values. For example, the second element of a resulting array has a value corresponding to a key stored in the first element. Note that the end-marker given as end has no corresponding value element.

Possible exceptions: assert_exceptfail, mem_exceptfail

Unchecked errors: foreign data structure given for table

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

As in table_map(), the order in which an array is created for each key-value pair is unspecified.

Parameters:
[in] table table for which array generated
[in] end end-mark to save in last element of array
Returns:
array generated from table
Todo:
Improvements are possible and planned:
  • it sometimes serves better to call a user callback for key-value pairs in order they are stored.


Generated on Mon Jan 24 01:13:08 2011 for The Table Library by  doxygen 1.5.8