From 47f0e2bd1cc8942f5c92ffa2f37db416d98d9e9e Mon Sep 17 00:00:00 2001 From: Ralph Ronnquist Date: Fri, 8 Jul 2022 11:14:41 +1000 Subject: [PATCH] documentation edits --- vector/hashvector.h | 120 ++++++++++++++++++++++++++++++-------------- vector/itemkeyfun.h | 4 +- vector/relation.h | 98 ++++++++++++++++++++++++++++++------ 3 files changed, 168 insertions(+), 54 deletions(-) diff --git a/vector/hashvector.h b/vector/hashvector.h index a4f9f7f..ec7eb8f 100644 --- a/vector/hashvector.h +++ b/vector/hashvector.h @@ -7,7 +7,7 @@ /** * \file hashvector.h * - * A hashvector is a use of vector as a hashtable. The hashvector + * A hashvector is a use of \ref vector as a hashtable. The hashvector * includes three functions to, respectively, obtain the hashcode of a * given key, to obtain the key of a given item, and to tell whether * or not a given item has a given key. The hashvector manipulations @@ -15,10 +15,10 @@ * hascode is the primary place for an item, but then scanning upwards * with a rolling index in case of collisions. * - * The vector holds 0 pointers for free slots, (void*)1 pointers (aka - * HV_HOLE) to indicate slots of deleted items, and otherwise item - * pointers. Thus, deleting an item results in av HV_HOLE et the - * item's slot. + * The vector holds (void*)0 pointers for free slots, (void*)1 + * pointers (aka \ref HV_HOLE) to indicate slots of deleted items, and + * otherwise item pointers. Thus, deleting an item results in av + * HV_HOLE et the item's slot. * * The hashvector grows to double in size, with rehashing, when an * item is added to make the sum of fill and holes exceed 50% of the @@ -29,16 +29,17 @@ /** * \struct hashvector * - * hashvector combines a vector (for contents) with fill and hole - * counters, and itemkeyfun callback functions for abstracting items - * as being pairs of key and payload. + * hashvector combines a \ref vector (for contents) with fill and hole + * counters, and \ref itemkeyfun callback functions for abstracting + * items as being pairs of key and payload. + * * \extends vector */ typedef struct { /** - * This is the backing vector for the hashvector. Items are placed - * in the vector by means of their key hashcodes, at the first - * unused slot cyclically after the hashcode index. + * This is the backing \ref vector for the hashvector. Items are + * placed in the vector by means of their key hashcodes, at the + * first unused slot cyclically after the hashcode index. */ vector table; // the table space for items /** @@ -47,15 +48,15 @@ typedef struct { */ unsigned long fill; // current number of contained items /** - * This is a count of HV_HOLE markers in the backing vector, which - * hold the position of deleted items so as to not break the + * This is a count of \ref HV_HOLE markers in the backing vector, + * which hold the position of deleted items so as to not break the * lookup sequence for items placed cyclically after their * hashcode index due to hash collisions. */ unsigned long holes; // current number of slots marking deleted items /** - * This is a pointer to the itemkeyfun record that provides the - * key-and-payload abstraction for items. + * This is a pointer to the \ref itemkeyfun record that provides + * the key-and-payload abstraction for items. */ itemkeyfun *type; // the key type for the items } hashvector; @@ -73,59 +74,104 @@ typedef struct { /** * \brief Find next keyed item at or after the given index. - * \param hv is the hasvector concerned - * \param index is a pointer to the index to advance + * + * \param hv is the \ref hashvector concerned. + * + * \param index is a pointer to the index to advance. + * \ * \param key is the query key - * \returns the next matching item, or 0 if none, with the index updated. + * + * \returns the next matching item, or \b 0 if none, with the index + * updated. * * \related hashvector */ extern void *hashvector_next(hashvector *hv,vector_index *i,void *key); /** - * Add the given item into the hashvector, growing the hashvector as - * needed to ensure that its fill+holes is is no more than half the - * size. Note that this function first locates any item of the same - * key, and then doesn't add if there is already an item that has the - * same key. Returns 1 when an item is added, 0 when the item key - * is already present, and -1 upon OOM or ovefull hashvector. + * \brief Add the given item into the \ref hashvector, growing it as + * needed to ensure that its fill+holes is no more than half the size. + * + * \param hv is the \ref hashvector concerned. + * + * \param item is the item to add. + * + * \returns \b 1 when an item is added, \b 0 when the item key is + * already present, and \b -1 upon OOM or ovefull \ref hashvector. + * + * Note that this function first locates any item of the same key, and + * then doesn't add if there is already an item that has the same key. * * \related hashvector */ extern int hashvector_add(hashvector *hv,void *item); /** - * Delete the given item, and shrink the hashvector so that its size - * is at most double its fill, though at least 256 slots. Returns 1 - * when the item gets deleted (by replacing its slot with a HV_HOLE - * value, 0 if the hashvector has either no item or a different item - * for the item key, and -1 in case of OOM or overfull hashvector. + * \brief Delete the given item, and shrink the hashvector so that its + * size is at most double its fill, though at minimum a single index + * page corresponding to the \ref vector_variant in use. + * + * \param hv is the \ref hashvector concerned. + * + * \param item is the item to delete. + * + * \returns \b 1 when the item gets deleted (by replacing its slot + * with a \ref HV_HOLE value), \b 0 if the hashvector has either no + * item or a different item for the item key, and \b -1 in case of OOM + * or overfull hashvector. + * + * Note that the contained item that has the same key as the provided + * item is deleted. + * + * \see itemkeyfun * * \related hashvector */ extern int hashvector_delete(hashvector *hv,void *item); /** - * Copy content items into a vector, which must be empty. The - * function returns -1 if the resizing of the vector to the - * hashvector fill fails, otherwise 0 after having copied the - * hashvector items in their internal order of appearance into the - * vector. + * \brief Copy content items into a given empty \ref vector. + * + * \param hv is the \ref hashvector concerned. + * + * \param pv is the \ref vector to copy the content into. + * + * \returns \b -1 if the required resizing of the \ref vector to the + * \ref hashvector \b fill fails, otherwise \b 0 after having copied + * the hashvector items in their internal order of appearance into the + * \ref vector. * * \related hashvector */ extern int hashvector_contents(hashvector *hv,vector *pv); /** - * This is a utility function to compute and return a hashcode for a - * block of bytes. + * \brief This is a utility function to compute and return a hashcode + * for a block of bytes. + * + * \param key is the start of the block. + * + * \param n is the byte size of the block. * * \related hashvector */ extern unsigned long hashvector_hashcode(unsigned char *key,unsigned long n); /** - * Create a hashvector for of given variant for given itemkeyfun* + * \brief Create a \ref hashvector of given \ref vector_variant + * for given \ref itemkeyfun. + * + * \param variant is the \ref vector_variant to use. + * + * \param type is the \ref itemkeyfun to use. + * + * \returns the initialised \ref hashvector. + * + * The hashvector will be initialized with a single \ref vector_page. + * + * \note The \ref hashvector record is allocated with malloc and the + * caller is responsible for free-ing the memory block when it's no + * longer needed. */ extern hashvector *hashvector_create( enum vector_variant variant,itemkeyfun *type); diff --git a/vector/itemkeyfun.h b/vector/itemkeyfun.h index ee71ca5..1089a16 100644 --- a/vector/itemkeyfun.h +++ b/vector/itemkeyfun.h @@ -13,9 +13,9 @@ * items that have that key. Different keys may yield the same * hashcode. */ -typedef struct _itemkeyfun { +typedef struct { -#define SELF struct _itemkeyfun *this +#define SELF void *this /** * This callback function should return the hashcode of a key. The * hashcode is used for indexing into the backing vector for diff --git a/vector/relation.h b/vector/relation.h index af0756c..e66d570 100644 --- a/vector/relation.h +++ b/vector/relation.h @@ -6,10 +6,12 @@ /** * A relation is an implementation of a tuple set with (optional) key - * constraints. The store is a hashvector whose "type" is a + * constraints. The store is a \ref hashvector whose \b type is a \ref * tupleschema that defines the columns. The key constraints are - * represented as additional hashvectors whose tupleschemas are clones - * of the column schema with some columns excluded. + * represented as additional \ref hashvector "hashvectors" whose \ref + * tupleschema "tupleschemas" are clones of the column schema with + * some columns excluded. + * * \extends hashvector */ typedef struct { @@ -29,35 +31,101 @@ typedef struct { } relation; /** - * Create a relation for the given tupleschema. + * \brief Create a relation for the given tupleschema. + * + * \param schema is the column schema + * + * \returns the allocated relation record. + * + * The given tupleschema is set up as the type of the content + * hashvector, which also is initialised as a nibble_index_levels + * variant vector. + * + * \related relation */ extern relation *relation_create(tupleschema *schema); /** - * Add a a key index to the relation by identifying the value part for - * this index. + * \brief Add a key constraint to a \ref relation. + * + * \param r is the relation concerned. + * + * \param key is the constraint \ref tupleschema. + * + * \returns the index into the constraints \ref vector for the added + * constraint. + * + * This function adds a \ref hashvector with the provided \ref + * tupleschema as its item type. The \b key \ref tupleschema must be a + * clone of the \ref relation column schema with some (or all) value + * columns marked as \b 0. Such a \ref tupleschema may be obtained via + * the function \ref tupleschema_mask to clone the \ref relation + * content type (casted as \ref tupleschema*) and clear columns by + * their index. + * + * The constraint \ref hashvectors are used when tuples are added to + * the \ref relation so as to identify the already contained tuples + * that contradict the addition by means of having the same constraint + * key. The already contained tuples are then "knocked out" from the + * relation by the new addition. + * + * \see tupleschema_mask, relation_add + * \related relation */ -extern int relation_addindex(relation *r,tupleschema *ts); - +extern int relation_add_contraint(relation *r,tupleschema *key); /** - * \brief Add a tuple to a relation. - * \param r is th relation concerned. - * \param t is the tuple to add. + * \brief Add the tuple to the relation. + * + * \param r is the \ref relation concerned. + * + * \param t is the \ref tuple to add. * * \returns a vector of all knocked out tuples. + * + * This function adds the \ref tuple \b t to the \ref relation \b r, + * and it returns a \ref vector (single_index_level variant) of all + * same-key constraint tuples. The returned vector is malloc-ed and it + * must be free-ed by the caller. If the tuple is already contained or + * there are no other same-key tuples knocked out, then \b 0 is + * returned. + * + * \related relation */ extern vector *relation_add(relation *r,tuple *t); /** - * \brief Delete all tuples matching to the query. - * \returns all deleted tuples. + * \brief Delete all tuples matching to the query \ref tuple fromt the + * \ref relation. + * + * \param r is the \ref relation concerned. + * + * \param t is the \ref tuple to delete. + * + * \returns a \vector vector of all knocked out tuples, i.e. the + * same-key tuples, if any, contained in the relation + * + * Note that deletion uses a "query" tuple, which means that some + * columns may be null to mark that them match to any value. + * + * \related relation */ extern vector *relation_delete(relation *r,tuple *query); /** - * \brief Return next tuple matching the query at or after the index. - * \returns any such matching tuple and updates *index to its index. + * \brief Return the next \ref tuple in the \ref relation that matches + * to the query \ref tuple, at or after the index. + * + * \param r is the \ref relation concerned. + * + * \param index is a pointer to the \ref vector index to update. + * + * \param query is a query \tuple tuple for selection of certain + * column values. + * + * \returns any such matching \tuple tuple and an updateed *index. + * + * \related relation */ extern void *relation_next(relation *r,vector_index *index,tuple *query); -- 2.39.2