[view source]
The table is instantiated with a primary index. If the primary index is not unique, an implicit unique index is created as well. Additional indices may be added subsequently. Adding an index implies a full tree scan to create an additional view on the tree sorted by the new index. cp_multimap_get() performs a lookup using the primary index, cp_multimap_get_by_index() performs a lookup using a secondary index. As a special case, cp_multimap_get_by_index() performs a lookup by the primary index if given a NULL index descriptor.
cp_multimap is somewhat different to other mapping collections in that there is no mapping as such. Client code supplies entries, a comparison function and optionaly a key function to extract a key from an entry. If no key function is given entries are passed directly to the comparison function for internal lookups.
Key functions match the prototype
void *key(void *a);
and return a pointer to the appropriate member within the given object. Comparison functions match
int comp(void *a, void *b);
The return value should be
> 0 if A > B
= 0 if A == B
< 0 if A < B
where A and B are the items pointed at by a and b respectively. If key functions are supplied, the cp_hash_compare_* functions defined in <cprops/hashtable.h> may be used here as well. Otherwise the comparison function must also extract the correct member from the object represented by the parameters a and b.
The general procedure for using
cp_multimap
is as follows:
Define key functions and comparison functions as required. Create a
cp_multimap
using
cp_multimap_create
or cp_multimap_create_by_option. Create indices by calling cp_multimap_create_index. Perform insertions and removals with
cp_multimap_insert
and cp_multimap_remove.
cp_multimap_remove_by_index
allows removing multiple entries that are identical respective to a given index.
cp_multimap_get
returns the requested entry using the primary index, and
cp_multimap_get_by_index
allows specifying a different index. The functions
cp_multimap_find
and
cp_multimap_find_by_index
allow lookups for entries by relational operator - the
op
parameter may be one of the following:
CP_OP_LT - returns an entry less than the given key
CP_OP_LE - returns an entry less than or equal to the given key
CP_OP_EQ - returns an entry equal to the given key - this is the same as cp_multimap_find
CP_OP_NE - returns an entry not equal to the given key
CP_OP_GE - returns an entry greater or equal to the given key
CP_OP_GT - returns an entry greater than the given key
Modifying fields on an object in the map that affect the sort order relative to any of the indices should be done by calling cp_multimap_reindex with the old entry and new entry as parameters.
The cp_multimap_callback and cp_multimap_callback_by_index allow a tree traversal by the primary or by a different index.
cp_multimap_lock and cp_multimap_unlock provide locking for maps not initialized with the COLLECTION_MODE_NOSYNC mode bit set. cp_multimap_rdlock and cp_multimap_wrlock are aliases for cp_multimap_lock with a type parameter of COLLECTION_LOCK_READ and COLLECTION_LOCK_WRITE respectively.
cp_multimap_get_mode, cp_multimap_set_mode and cp_multimap_unset_mode may be used to manage the collection mode, with the usual limitations.
cp_multimap_use_mempool and cp_multimap_share_mempool allow using built in memory pool functionality after map creation.
See documentation on specific functions for further details.
cp_multimap *cp_multimap_create(cp_key_fn key_fn, cp_compare_fn cmp);
cp_multimap*
cp_multimap_create_by_option(int mode, cp_key_fn key_fn,
cp_compare_fn cmp,
cp_copy_fn copy,
cp_destructor_fn dtr);
void cp_multimap_destroy(cp_multimap *tree);
void cp_multimap_destroy_custom(cp_multimap *tree,
cp_destructor_fn dtr);
cp_index *cp_multimap_create_index(cp_multimap *map,
cp_index_type type,
cp_key_fn key,
cp_compare_fn cmp,
int *err);
void *cp_multimap_insert(cp_multimap *tree, void *entry, int *err);
void *cp_multimap_get(cp_multimap *tree, void *entry);
void *cp_multimap_get_by_index(cp_multimap *map,
cp_index *index,
void *entry);
void *cp_multimap_find(cp_multimap *map, void *key, cp_op op);
void *cp_multimap_find_by_index(cp_multimap *map,
cp_index *index,
void *entry,
cp_op op);
int cp_multimap_contains(cp_multimap *tree, void *entry);
void *cp_multimap_remove(cp_multimap *tree, void *entry);
void *cp_multimap_remove_by_index(cp_multimap *map,
cp_index *index,
void *entry);
int cp_multimap_reindex(cp_multimap *map, void *before, void *after);
int cp_multimap_callback_preorder(cp_multimap *tree,
cp_callback_fn callback,
void *prm);
int cp_multimap_callback(cp_multimap *tree,
cp_callback_fn callback,
void *prm);
int cp_multimap_callback_by_index(cp_multimap *tree,
cp_index *index,
cp_callback_fn callback,
void *prm);
int cp_multimap_callback_postorder(cp_multimap *tree,
cp_callback_fn callback,
void *prm);
int cp_multimap_size(cp_multimap * map);
int cp_multimap_count(cp_multimap *tree);
int cp_multimap_lock(cp_multimap *tree, int type);
int cp_multimap_rdlock(cp_multimap *tree);
int cp_multimap_wrlock(cp_multimap *tree);
int cp_multimap_unlock(cp_multimap *tree);
int cp_multimap_get_mode(cp_multimap *tree);
int cp_multimap_set_mode(cp_multimap *tree, int mode);
int cp_multimap_unset_mode(cp_multimap *tree, int mode);
int cp_multimap_use_mempool(cp_multimap *tree, cp_mempool *pool);
int cp_multimap_share_mempool(cp_multimap *tree,
cp_shared_mempool *pool);
#include <stdio.h>
#include <stdlib.h>
#include <cprops/multimap.h>
struct box
{
float width;
float length;
float height;
};
struct box *create_box()
{
struct box *b = (struct box *) malloc(sizeof(struct box));
b->width = (float) (rand() % 10000) / 100;
b->length = (float) (rand() % 10000) / 100;
b->height = (float) (rand() % 10000) / 100;
return b;
}
void print_box(struct box *b)
{
printf("[%p] %02.02f x %02.02f x %02.02f = %02.02f cm^3\n",
b, b->width, b->length, b->height,
b->width * b->length * b->height);
}
int print_box_cb(cp_index_map_node *n, void *prm)
{
int i;
cp_vector *items = (cp_vector *) n->entry;
for (i = 0; i < cp_vector_size(items); i++)
print_box(cp_vector_element_at(items, i));
return 0;
}
void *box_width(void *p)
{
return &((struct box *) p)->width;
}
int box_width_cmp(void *p, void *q)
{
return *(float *) p - *(float *) q;
}
int box_volume_cmp(void *p, void *q)
{
struct box *pp = (struct box *) p;
struct box *qq = (struct box *) q;
return pp->width * pp->length * pp->height -
qq->width * qq->length * qq->height;
}
int main(int argc, char *argv[])
{
int i;
cp_multimap *t;
cp_index *volume_index;
srand(time(NULL));
t = cp_multimap_create_by_option(COLLECTION_MODE_MULTIPLE_VALUES |
COLLECTION_MODE_DEEP |
COLLECTION_MODE_NOSYNC,
(cp_key_fn) box_width,
(cp_compare_fn) box_width_cmp,
NULL, /* no copy function */
free);
volume_index =
cp_multimap_create_index(t, CP_MULTIPLE, NULL, box_volume_cmp, NULL);
printf("creating 10 boxes\n");
for (i = 0; i < 10; i++)
{
struct box *b = create_box();
print_box(b);
cp_multimap_insert(t, b, NULL);
}
printf("\nboxes sorted by width\n");
cp_multimap_callback(t, (cp_callback_fn) print_box_cb, NULL);
printf("\nboxes sorted by volume\n");
cp_multimap_callback_by_index(t, volume_index,
(cp_callback_fn) print_box_cb,
NULL);
cp_multimap_destroy(t);
return 0;
}