cuoo/hctem.h: Boilerplates for Hash-Consing
[cuoo: Dynamic Objects and Operations]


#define cuoo_hctem_key_size(prefix)   (sizeof(struct prefix) - CUOO_HCOBJ_SHIFT)
#define cuoo_hctem_decl(prefix, tem)   struct prefix tem
#define cuoo_hctem_init(prefix, key)   (memset(cuoo_hctem_key(prefix, key), 0, cuoo_hctem_key_size(prefix)))
#define cuoo_hctem_get(prefix, key)   (&(key))
#define cuoo_hctem_key(prefix, tem)   cu_ptr_add(&(tem), CUOO_HCOBJ_SHIFT)
#define cuoo_hctem_new(prefix, key)
#define cuoo_hctem_new_of_type(prefix, key, type)

Detailed Description

These macros simplifies the allocation of hash-consed objects. They are documented individually below, but how they work together is maybe best understood by a simple example, here the creation of a dynamically typed and hash-consed pair:

 struct pair {
     cuex_t left;
     cuex_t right;

 cuoo_type_t pair_type();

 struct pair *pair_new(cuex_t left, cuex_t right)
     cuoo_hctem_decl(pair, key);
     cuoo_hctem_init(pair, key);
     cuoo_hctem_get(pair, key)->left = left;
     cuoo_hctem_get(pair, key)->right = right;
     return cuoo_hctem_new(pair, key);

The cuoo_hctem_* macros only work when following the above naming conventions for the struct and dynamic-type functions. Otherwise, use the generic functions from cuoo/halloc.h.

Define Documentation

#define cuoo_hctem_decl ( prefix,
tem   )     struct prefix tem

This macro emits a declaration of a key-template used for hash-consed allocation. key must be initialised with cuoo_hctem_init and assigned through the pointer returned by cuoo_hctem_get.

#define cuoo_hctem_get ( prefix,
key   )     (&(key))

Given a prefix and a template variable key, returns a pointer to the template struct, which has type prefix_s *.

#define cuoo_hctem_init ( prefix,
key   )     (memset(cuoo_hctem_key(prefix, key), 0, cuoo_hctem_key_size(prefix)))

This macro initialises the template key, which must be declared with cuoo_hctem_decl. This macro should be invoked before assigning to the struct fields to ensure a predictable hash-key. In particular, calling cuoo_hctem_init zeros any padding at the end of the struct or holes within the struct due to alignment constraints, so that they do not contain arbitrary data which would affect the hash key.

Inspection of generated code generated by GCC at -O2 suggests that it's able to optimise the cuoo_hctem_init invokation against subsequent unconditional cuoo_hctem_get invocations.

#define cuoo_hctem_key ( prefix,
tem   )     cu_ptr_add(&(tem), CUOO_HCOBJ_SHIFT)

The address of the key of a template, in case you need to use cuoo_halloc or cuoo_hxalloc_init instead of cuoo_hctem_new.

#define cuoo_hctem_key_size ( prefix   )     (sizeof(struct prefix) - CUOO_HCOBJ_SHIFT)

Assuming a declaration of struct prefix which starts with a CUOO_HCOBJ statement, this macro returns the key-size to use for hash-consing object of the struct.

#define cuoo_hctem_new ( prefix,
key   ) 
((struct prefix *) \
     cuoo_halloc(prefix##_type(), cuoo_hctem_key_size(prefix), \
                 cuoo_hctem_key(prefix, key)))

Given previous definition of a struct prefix_s and a function prefix_type() returning the corresponding dynamic type, this macro returns a hash-consed object from the pre-initialised template key. This macro is used in conjunction with cuoo_hctem_decl, cuoo_hctem_init, cuoo_hctem_get.

#define cuoo_hctem_new_of_type ( prefix,
type   ) 
((struct prefix *) \
     cuoo_halloc(type, cuoo_hctem_key_size(prefix), \
                 cuoo_hctem_key(prefix, key)))
Generated 2009-11-23 for culibs-0.25 using Doxygen. Maintained by Petter Urkedal.