C.1.4 Container Templates Changes

csArray<> Index and Size Type Change

csArray<> has been changed to use `size_t' instead of `int' for array sizes and indices. Probably, the most significant semantic difference of this change is that `size_t' is usually unsigned as opposed to `int' which is signed.

Read this paragraph carefully. In actual code, this change may result in nothing more than simple-looking compiler warnings. However, it may have caused semantics to change subtly.

This has the greatest impact in the areas discussed below.

Iterating Over csArray<> Contents

For this purpose, usually, `int' typed variables were used for keeping track of the index of the current item of an array iteration. Fixing forward iteration over a csArray<> to instead use `size_t' is simple:

csArray<...> a;
for (int i = 0, n = a.Length(); i < n; i++)
{
  ...
}

Is changed to:

...
for (size_t i = 0, n = a.Length(); i < n; i++)
...

Backward iteration is a bit more problematic. As mentioned before, `size_t' typically is unsigned, so you do not have negative values. This can be a problem in constructs like:

csArray<...> a;
for (int i = a.Length() - 1; i >= 0; i--)
{
  ...
}

If the `int' is changed simply to a `size_t', this for-loop misbehaves unexpectedly. When `i' becomes 0, the body of the loop is executed correctly. However, decrementing `i' will not cause `i' to have a negative value--after all, `size_t' is unsigned. Instead, decrementing will make `i' wrap around from 0 to 0xffffffff (on 32-bit machines). Clearly, this is greater than 0, effectively causing an infinite loop. The same thing also happens when `a' has no items (i.e. `a.Length() == 0'). Here the -1 in the initialization of `i' causes wrap-around.

Possible solutions include:

• Use an int-typed counter variable and cast the array length to `int'. This is not entirely elegant, but it does the job in most cases.
• Re-write the loop to deal properly with the unsigned nature of `size_t':

  csArray<...> a; for (size_t i = a.Length(); i-- > 0;) { ... }

  This code does the same as the `int' version above, iterating from `a.Length() - 1' to 0, inclusively. It also correctly works in the case `a.Length() == 0'. The "trick" is to place the modification of `i' as a post-decrement in the loop condition. This way, as soon as `i' becomes 0, the loop is terminated. The post-decrement ensures that `i' has the expected value in the loop body.

Searching

Functions like csArray<>::FindSortedKey() and csArray<>::Find() used to return -1 to signify that an item was not found. This is still the case, but with a twist. Now, `(size_t)-1' is returned. For convenience, a constant, `csArrayItemNotFound', has been added, which has this exact value. It can be used in comparisons to make it clear what is actually being checked.

Apropros comparisons: Recall that `size_t' is unsigned, so checking whether an index returned by `FindSortedKey()' or `Find()' is actually a valid index by testing with `>= 0' no longer works since `(size_t)-1' is always >= 0. Replace such checks with tests of equality against `csArrayItemNotFound':

csArray<...> a;
int index = a.Find (...);
if (index >= 0)
{
  /* Item found */
  ...
}
else
{
  /* Item not found */
  ...
}

Must be replaced with:

csArray<...> a;
size_t index = a.Find (...);
if (index != csArrayItemNotFound)
{
  /* Item found */
  ...
}
else
{
  /* Item not found */
  ...
}

`csutil/garray.h' Deprecated

The `csutil/garray.h' file, containing the class csDirtyAccessArray<>, has been deprecated in favor of the more sensible file name `csutil/dirtyaccessarray.h'. No functional changes have been made to the class.

csList<>::Iterator Normalization

The behavior of csList<>::Iterator has been normalized so that it functions identically to all other iterators in Crystal Space. In the past, a newly created csList<>::Iterator already pointed at the first element in the container. This differed from all other iterator implementations, in which the first element, like all other elements, is accessed by an invocation of Next().

Old code which accessed the elements of a csList<>::Iterator required a non-standard idiom, such as:

csList<sometype> list = ...;
csList<sometype>::Iterator it(list);
if (it.HasCurrent())
{
  do_something(*it);         // First value.
  while (it.HasNext())
  {
    do_something(it.Next()); // Remaining values.
  }
}

Or, the slightly less complicated, though still somewhat convoluted:

csList<sometype>::Iterator it(list);
while (it.HasCurrent())
{
  do_something(*it);
  it.Next();
}

Following normalization, csList<>::Iterator now works like all other iterators throughout the toolkit. In particular, for forward iteration, all elements can be accessed via the standard HasNext() / Next() idiom:

csList<sometype>::Iterator it(list);
while (it.HasNext())
{
  do_something(it.Next());
}

Likewise, for backward iteration, the HasPrevious() / Previous() idiom works in the obvious and expected inverse fashion.

Finally, csList<>::Iterator::Next() and Previous() now return references to contained elements, rather than pointers. This makes the interface of csList<>::Iterator internally consistent, as well as consistent with other iterators throughout the toolkit, in which these methods return references.

csSet<> Relocation and Changes

The declaration of csSet<> was moved out from `csutil/hash.h' and into its own header file, `csutil/set.h'. The method csSet<>::GetHash() has likewise been removed since it unnecessarily exposed an underlying implementation detail of csSet<>.

However, this implementation detail still affects the use of csSet<> as for storage of pointers in a csSet<> the csPtrKey<> wrapper must be used.

csHash<> Changes

The way csHash<> handles support for arbitrary key types has been changed. Previously, a so-called "hash key handler" was passed as an optional third template parameter that computed hash keys and was able to compare keys. Now, the hash computation is handled through the new csHashComputer<> template, and key comparison through csComparator<>. To provide hash computation and comparisons for specific types used as hash keys, specializations of the templates mentioned above are needed. Alternatively the default comparator uses the `operator <' and `operator >' operators, so you can also implement those operators instead of a csComparator<> specialization. The default csHashComputer<> implementation assumes that a type provides a `GetHash()' method that computes the hash value for an object. However, this means that integral types need a specialization. As a convenience, Crystal Space already provides specializations of csHashComputer<> for a number of commonly used intergrals. Further, csComparator<> and/or csHashComputer<> specializations are provided for the commonly used types `csString', `const char*' and `csStrKey'; and the default comparison semantics of `operator <' and `operator >' handle the remaining fundamental types and any composite types which provide these operators. Pointers (other than `void*' for which exists a specialization) as hash keys are a special case: to use a pointer of type `Foo*' as a hash key, employ `csPtrKey<Foo>' as the key type in the hash declaration.

Default csHash<> (and csHashReversible<>) Table Size

The default hash table size and grow rate has been reduced from 257 and 64 to 23 and 5, respectively, to have hashes use less memory. If a hash is expected to contain a large quantity of elements, those two parameters can be tweaked upon construction of a csHash<> or csHashReversible<>. Consult the Public API Documentation of csHash<> for more information.

`csHashMap' and `csHashSet' Removal

The long-deprecated `csHashMap', `csHashMapReversible', and `csHashSet' classes have been removed. Instead, use the templated classes csHash<>, csHashReversible<>, and csSet<>. For string-related set functionality, you may also want to consider using `csStringHash' and `csStringSet'.

csObjectPool<> Removal

The csObjectPool<> utility class has been removed since it managed memory poorly, and failed to invoke the destructor of contained objects at the time they were recycled via csObjectPool<>::Free(), which meant that the objects might not release their own resources in a timely fashion. (It did correctly destroy the freed objects when the pool itself was destroyed, but should have been doing so at Free()-time.)

You can use csBlockAllocator<> (see `csutil/blockallocator.h') as a drop-in replacement for csObjectPool<> since the API of csBlockAllocator<> is a proper superset of the csObjectPool<> API. A global search and replace should be sufficient to account for this change.

`csStringSetIterator' and `csStringHashIterator' Removal

`csStringSetIterator' and `csStringHashIterator' have been replaced with the iterator classes `csStringSet::GlobalIterator' and `csStringHash::GlobalIterator', respectively. Rather than instantiating iterators directly, you now ask the set or hash for an iterator. This brings the `csStringSet' and `csStringHash' API's in line with other container classes which vend iterators. Given old code which is using `csStringSetIterator':

csStringSet set;
// ...populate set...
csStringSetIterator iter(&set);
while (iter.HasNext())
{
  char const* s = iter.Next();
  // ...do something with `s'...
}

Convert it like this:

csStringSet::GlobalIterator iter = set.GetIterator();
while (iter.HasNext())
{

Code using `csStringHashIterator' can be fixed using the same simple transformation.

This document was generated using texi2html 1.76.