2.8 Insertion and Deletion

These functions insert and delete items in tables. There is also a function for searching a table without modifying it.

The design behind the insertion functions takes into account a couple of important issues:

• What should happen if there is a matching item already in the tree? If the items contain only keys and no values, then there's no point in doing anything. If the items do contain values, then we might want to leave the existing item or replace it, depending on the particular circumstances. The tbl_insert() and tbl_replace() functions are handy in simple cases like these.
• Occasionally it is convenient to insert one item into a table, then immediately replace it by a different item that has identical key data. For instance, if there is a good chance that a data item already exists within a table, then it might make sense to insert data allocated as a local variable into a table, then replace it by a dynamically allocated copy if it turned out that the item wasn't already in the table. That way, we save the time required to make an additional copy of the item to insert. The tbl_probe() function allows for this kind of flexibility.

10. <Table insertion and deletion function prototypes 10> =
void **tbl_probe (struct tbl_table *, void *);
void *tbl_insert (struct tbl_table *, void *);
void *tbl_replace (struct tbl_table *, void *);
void *tbl_delete (struct tbl_table *, const void *);
void *tbl_find (const struct tbl_table *, const void *);

This code is included in 15.

Each of these functions takes a table to manipulate as its first argument and a table item as its second argument, here called table and item, respectively. Both arguments must be non-null in all cases. All but tbl_probe() return a table item or a null pointer.

• tbl_probe(): Searches in table for an item matching item. If found, a pointer to the void * data item is returned. Otherwise, item is inserted into the table and a pointer to the copy within the table is returned. Memory allocation failure causes a null pointer to be returned.

  The pointer returned can be used to replace the item found or inserted by a different item. This must only be done if the replacement item has the same position relative to the other items in the table as did the original item. That is, for existing item e, replacement item r, and the table's comparison function f(), the return values of f(e, x) and f(r, x) must have the same sign for every other item x currently in the table. Calling any other table function invalidates the pointer returned and it must not be referenced subsequently.

• tbl_insert(): Inserts item into table, but not if a matching item exists. Returns a null pointer if successful or if a memory allocation error occurs. If a matching item already exists in the table, returns that item.
• tbl_replace(): Inserts item into table, replacing and returning any matching item. Returns a null pointer if the item was inserted but there was no matching item to replace, or if a memory allocation error occurs.
• tbl_delete(): Removes from table and returns an item matching item. Returns a null pointer if no matching item exists in the table.
• tbl_find(): Searches table for an item matching item and returns any item found. Returns a null pointer if no matching item exists in the table.

Exercises:

1. Functions tbl_insert() and tbl_replace() return NULL in two very different situations: an error or successful insertion. Why is this not necessarily a design mistake? [answer]

2. Suggest a reason for disallowing insertion of a null item. [answer]

3. Write generic implementations of tbl_insert() and tbl_replace() in terms of tbl_probe(). [answer]