|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
- 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
- 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.
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?
2. Suggest a reason for disallowing insertion of a null item.
3. Write generic implementations of tbl_insert() and tbl_replace() in
terms of tbl_probe().