multimap.h File Reference

#include "common.h"
#include "rb.h"
#include "hashlist.h"
#include "vector.h"
#include "mempool.h"

Go to the source code of this file.

Data Structures
struct	_cp_index_map_node
struct	_cp_index_map
struct	_cp_multimap

---

Detailed Description

cp_multimap is a data structure designed to support multiple indices. Indices may be defined at creation time or added dynamically after creation. The map supports access by key, by index or by CP_OP_* operator to match the closest entry to the requested entry.

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.

The table is instantiated with a primary index. 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.

Example:

struct subscriber { char first_name[32]; char last_name[32]; char phone_num[32]; };

int subscriber_name_compare(void *a, void *b) { int cmp; struct subscriber *s1 = (struct subscriber *) a; struct subscriber *s2 = (struct subscriber *) b;

cmp = strcmp(s1->last_name, s2->last_name); if (cmp == 0) cmp = strcmp(s1->first_name, s2->first_name);

return cmp; }

int subscriber_number_compare(void *a, void *b) { int n1, n2;

n1 = atoi((char *) s1); n2 = atoi((char *) s2);

return n1 - n2; }

int subscriber_number_key(void *entry) { struct subscriber *s = (struct subscriber *) entry; return &s->phone_num; }

...

int err; cp_index *index; char number[32]; struct subscriber x, *res;

struct subscriber *a = create_subscriber("Duck", "Daffy", "123"); struct subscriber *b = create_subscriber("Fudge", "Elmore", "456"); struct subscriber *c = create_subscriber("Fudge", "Elvis", "789");

cp_multimap *subscriber_list = cp_multimap_create(NULL, subscriber_name_compare);

index = cp_multimap_create_index(subscriber_list, CP_UNIQUE, subscriber_number_key, subscriber_number_compare, &err); if (index == NULL) cp_error(err, "can\'t create index"); // ... handle error

// find Daffy's number

sprintf(x.first_name, "Daffy"); sprintf(x.last_name, "Duck");

res = cp_multi_map_get(subscriber_list, &x); if (res) printf("Daffy Duck: %s\n", res->phone_number); else printf("No entry for Daffy Duck\n");

// reverse lookup phone number 789

sprintf(number, "789"); res = cp_multimap_get_by_index(subscriber_list, index, number); if (res) printf("number 789 belongs to %s %s\n", res->first_name, res->last_name); else printf("no subscriber with number 789\n");

...

Definition in file multimap.h.

---

Function Documentation

CPROPS_DLL void cp_multimap_dump (  cp_multimap *  tree  )

print tree to stdout Definition at line 1715 of file multimap.c.

---