[svn-r7553] Purpose:

    Improved algorithm (bug fix, sorta)

Description:
    The internal algorithm for adding new IDs in the ID manager code (H5I) was
adding new IDs to the front of the linked list and never adjusting the order
of the items on the list (unless an ID was deleted).  If many new objects were
created, they would push earlier ones _way_ down the list (especially if the
objects were being leaked in the application, as they appear to be in the
current HDF-EOS5 library) and would cause O(n) search time for items on the
list.
    The ID caching code in the ID manager was avoiding this behavior sometimes,
but it was adding IDs that were looked up to the very tail of the cache and
they would frequently leave the cache before helping.

Solution:
    Implemented a "move to front" scheme for the linked list of IDs, which
improves the lookup situation for frequently accessed objects.

    Removed ID caching code now, as the "move to front" algorithm actually
works better.

Platforms tested:
    FreeBSD 4.9 (sleipnir)
    too minor to require h5committest

1 files changed, 2 insertions, 0 deletions

diff --git a/release_docs/RELEASE.txt b/release_docs/RELEASE.txt
index 0cbdfa7..8133a50 100644
--- a/release_docs/RELEASE.txt
+++ b/release_docs/RELEASE.txt
@@ -76,6 +76,8 @@ Bug Fixes since HDF5-1.6.0 release
 
     Library
     -------
+        - Changed implementation of internal ID searching algorithm to avoid
+            O(n) behavior for many common cases.  QAK 2003/10/06
         - Allow partial parallel writing to compact datasets.  QAK - 2003/10/06
         - Correctly create reference to shared datatype in attribute, instead
             of making a copy of the shared datatype in the attribute.