%
% Cache.tex -- Almost all about the various caches within LessTif
%
% (c) 1996 The Hungry Programmers
% (c) 1996 Harald Albrecht (albrecht@igpm.rwth-aachen.de)
% See the file PUBLIC for details.
%
\chapter[Hash \& Cache]{Hash \& Cache}
\by{Harald Albrecht}

\section{Introduction}

Caches within \LessTif{} serve two main purposes: avoiding unnecessary
round-trips to the X server as well as resource sharing. The resource
sharing can either occur on the server side (pixmaps, graphics
contexts,...) or on the side of the client (images, memory).  Caching
can also improve performance (although this is at some times only an
idle wish...).

When working with caches, very often you need to check a cache for the
existence of a particular item. Because the cache may contain many
items this lookup has to be fast. In almost every case a simple linked
list isn't suitable when you need speed -- but (at least) a linked
list is easy to code.

As a way out the \code{XContext}s of the Xlib come to
mind. Unfortunately, they can only be used if you have a display
pointer ready at hand. And a \code{XContext} is destroyed when the
display it belongs to is closed. Therefore the \code{XContext}s are
neither suitable for all caching purposes nor as a general associative
array.

\section{The Hash Table Module}

\index{hash table}
Whenever you need a cache or an associative array that must be
independent of a particular display pointer then you should use the
generic hash table mechanism within \LessTif{}. Generally, it offers
much better performance than a simple linked list, especially if there
are many items to manage. The hash table mechanism makes reinventing
the wheel unnecessary in almost every case.

You can think of a hash table as some kind of associative array. You
first put a value named by an identifier into the hash table. Lateron
you can ask for the value using the identifier. Both an identifier and
its associated value make up an ``item''.  The values and identifiers
for the hash tables within \LessTif{} are typedef'ed in a portable fashion:

\codeindex{LTHashItemID}\codeindex{LTHashItemValue}%
\begin{verbatim}
typedef XtPointer LTHashItemID;
typedef XtPointer LTHashItemValue;
\end{verbatim}

This allows you to use the broad range of integral data types in C for
both values and identifiers. And if the space provided by these data
types isn't sufficient, you can use the identifiers and values as
pointers to structures instead. Because of this broad range of data
types you may have to provide functions for comparing two items and
calculating a hash value of an item:

\begin{verbatim}
typedef unsigned int (*LTHashGetHashFunction)(LTHashItemID);
typedef Boolean (*LTHashCompareFunction)(LTHashItemID, LTHashItemID);
\end{verbatim}

A \code{LTHashGetHashFunction} returns an unsigned integer that
represents the hash value for that particular item specified as the
parameter to the function. A \code{LTHashCompareFunction} must return
\code{True} if the two items specified by the parameters are equal.

Hash tables are created and destroyed using the following two
functions.  You don't have to supply a size when creating a hash table
because \LessTif{}'s hash tables grow as needed whenever new entries
are added.

\begin{itemdescription}
\codeindex{LTHashTableCreate}%
\ITEM[\shortstackl{LTHashTable LTHashTableCreate(LTHashGetHashFunction GetHash,
\\{}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~LTHashCompareFunction Compare,
\\{}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~unsigned int IDSize);}]
Creates a fresh hash table and returns a pointer to it for subsequent
use. You can either specify your own functions for calculating a
hash key and comparing items (more precisely: comparing their
identifiers) in \code{GetHash} and \code{Compare} or
\code{NULL}. In the latter case the hash table will use default functions.
If you use data structures as identifiers then you probable have to
supply your own functions.

The final parameter \code{IDSize} indicates what type of identifiers
you're working with and whether the memory occupied by the identifier
belongs to the hash table. If you specify here
\code{LTHASH\_ID\_NOCOPY}, then the hash table will not make a copy of
a data structure an identifier points to when adding or replacing
items. Another special case are strings for which you can specify
\code{LTHASH\_ID\_STRING}. The hash table will then take care of copying
and freeing the string identifiers. If you specify for \code{IDSize}
any size (other than zero or one, as these ones are reserved), then
the hash table mechanism will copy the data structure of that size
pointed to by a \code{LTHashItemID} to private allocated storage
whenever you add or replace items in the hash table.

\codeindex{LTHashTableDelete}%
\ITEM[void LTHashTableDelete(LTHashTable ht);]
Deletes a hash table and frees all memory occupied by it.
\end{itemdescription}

At any time you can ask a hash table how much items it currently contains.

\begin{itemdescription}
\codeindex{LTHashTableGetNumItems}%
\ITEM[int LTHashTableGetNumItems(LTHashTable ht);]
\end{itemdescription}

After creating a hash table you can add (or remove) items to (from) it.

\begin{itemdescription}
\codeindex{LTHashTableAddItem}%
\ITEM[\shortstackl{Boolean LTHashTableAddItem(LTHashTable ht, LTHashItemID id,
\\{}~~~~~~~~~~~~~~~~~~~~~~~~~~~LTHashItemValue value);}]
Adds the item identified by \code{id} with the value \code{value} to
the hash table. If there is already an item with the same identifier
in the hash table then the function doesn't modify the value of that
item and returns \code{False}. Otherwise, the function adds the item
to the table and indicates success by returning \code{True}.

If either \code{id} or \code{value} are pointers to data structures,
make sure that these data structues are not allocated in automatic
storage. Because the hash table only stores the pointers you must not
free the data structures until the item is removed from the hash
table. The only exception occurs when you have specified the size of
the data structure of your item identifiers when creating the hash
table. In this case the hash table will make a copy of the identifier.

\codeindex{LTHashTableReplaceItem}%
\ITEM[\shortstackl{Boolean LTHashTableReplaceItem(LTHashTable ht,
\\{}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~LTHashItemID id,
\\{}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~LTHashItemValue value,
\\{}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~LTHashItemValue *value\_ret);}]
Much the same as \code{LTHashTableAddItem()}. But when the hash table
already contains an item with the identifier \code{id}, then
\code{LTHashTableReplaceItem()} replaces the item's value with \code{value}.
The item's previous value is returned in \code{*value\_ret} as long as
you don't specify a \code{NULL} pointer for the final parameter. If a
replace took place then the function returns \code{True}. This return
value is especially useful if the value of an item is a pointer to
memory allocated using \code{XtMalloc()}. In this case you can free
the memory occupied by the old value whenever
\code{LTHashTableReplaceItem()} returns \code{True}.

\codeindex{LTHashTableReplaceItemAndID}%
\ITEM[\shortstackl{Boolean LTHashTableReplaceItemAndID(LTHashTable ht,
\\{}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~LTHashItemID id,
\\{}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~LTHashItemValue value,
\\{}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~LTHashItemID *id\_ret,
\\{}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~LTHashItemValue *value\_ret);}]
Much the same as \code{LTHashTableReplaceItem} but this time even the
identifier of the item will be replaced with the new identifier. If
you don't specify \code{NULL} for \code{id\_ret} then you'll get the
old identifier of the item. In the cases where the hash table
mechanism takes care of the memory occupied by identifiers (within the
hash table), it'll free that storage if the identifier of an item was
replaced.

\codeindex{LTHashTableRemoveItem}%
\ITEM[\shortstackl{Boolean LTHashTableRemoveItem(LTHashTable ht, LTHashItemID id,
\\{}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~LTHashItemID *id\_ret,
\\{}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~LTHashItemValue *value\_ret);}]
Removes an item identified by \code{id} from the hash table and returns
\code{True} if it succeeds In this case you will get back the
identifier and the value of the item in \code{*id\_ret} and
\code{*value\_ret} as long as you don't specify \code{NULL} for these
pointers. The information returned can help you to free the data
allocated to hold the identifier and the value. In the cases where the
hash table mechanism takes care of the memory occupied by identifiers
(within the hash table), it'll free the storage used by the
identifier.

\codeindex{LTHashTableLookupItem}%
\ITEM[\shortstackl{Boolean LTHashTableLookupItem(LTHashTable ht, LTHashItemID id,
\\{}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~LTHashItemValue *value);}]
Looks up an item identified by \code{id} within the hash table \code{ht}.
If it succeeds then it returns the value of the item in \code{value} and
returns \code{True}. Otherwise the function returns \code{False} if the
item can't be found.

\ITEM[\shortstackl{int LTHashTableForEachItem(LTHashTable ht,
\\{}~~~~~~~~~~~~~~~~~~~~~~~~~~~LTHashForEachFunction iter,
\\{}~~~~~~~~~~~~~~~~~~~~~~~~~~~XtPointer ClientData);}]
From time to time you need to iterate over the contents of a hash table.
This is where you'll use this iterator function. For every item in the
hash table the iterator function \code{iter} is called. The function
prototype for such an iterator function is as follows:
\begin{verbatim}
typedef LTHashForEachIteratorResult
    (*LTHashForEachFunction)(LTHashTable,
                             LTHashItemID, LTHashItemValue, XtPointer);
\end{verbatim}
The iterator gets as its final parameter the \code{ClientData}
parameter from the call to \code{LT\-HashTableForEachItem}. The
iterator function then should return one of the following results
depending on whether the iteration process should continue or not.
\begin{table}[h]\begin{center}\begin{tabular}[!ht]{|l|l|}
\hline
Identifier & Operation\\
\hline
\code{LTHASH\_BREAK} & Exit the iteration loop. \\
\code{LTHASH\_CONT} & Continue. \\
\code{LTHASH\_COUNT} & Continue and increment the counter. \\
\code{LTHASH\_COUNTANDBREAK} & Increment the counter but exit the iteration
loop. \\
\hline
\end{tabular}%
{\caption{\label{Foreach_iterator_ids}Results the iterator function of
a hash table can return.}}
\vspace*{-0.4cm}
\end{center}\end{table}
The function \code{LTHashTableForEachItem} returns the value of a
counter that is initialized at the start of the iteration process and
is incremented whenever the iterator function indicates this.
\end{itemdescription}


% End of Cache.tex
