/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * Copyright by  The HDF Group and                                           *
 *               The Board of Trustees of the University of Illinois.        *
 * All rights reserved.                                                      *
 *                                                                           *
 * This file is part of H4H5TOOLS. The full H4H5TOOLS copyright notice,      *
 * including terms governing use, modification, and redistribution, is       *
 * contained in the COPYING file, which can be found at the root of the      *
 * source code distribution tree. The copyright notice can also be found     *
 * at https://www.hdfgroup.org/licenses.  If you do not have access to       *
 * either file, you may request a copy from help@hdfgroup.org.               *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

/* $Id$ */

/*
 * FILE:	H4TOH5I.c - Internal storage routines for handling "H4TOH5ID"
 *     
   H4TOH5I.c is a simplified version of ID handling function that was orginally   given in HDF5 library. 
   We will keep this version until HDF5 ID handler functions become public.
   
   FUNCTIONS used in h4toh5 converter library are:

   H4TOH5I_init_group,
   H4TOH5I_register
   H4TOH5I_object
   H4TOH5I_remove
   The rest comments in this section is from the original HDF5 library. Users
   can check H5I.c for the detailed information.
----------------cut here --------------------

 * REMARKS:	ID's which allow objects (void *'s currently) to be bundled
 *		into "groups" for more general storage.
 * 
 * DESIGN:	The groups are stored in an array of pointers to store each
 *		group in an element. Each "group" node contains a link to a
 *		hash table to manage the IDs in each group.  The allowed
 *		"groups" are stored in an enum (called group_t) in
 *		
 * AUTHOR:	Quincey Koziol
 *
 * MODIFICATIONS:
 *	1/3/96	- Starting writing specs & coding prototype
 *	1/7/96	- Finished coding prototype
 *	6/10/97 - Moved into HDF5 library
---------------end of the comments from H5I.c ------------------------
 */

#include "H4TOH5Iprivate.h"

/*
 * Define the following macro for fast hash calculations (but limited
 * hash sizes)
 */
#define HASH_SIZE_POWER_2

/* Define the following macro for atom caching over all the atoms */
#define IDS_ARE_CACHED

/*-------------------- Locally scoped variables -----------------------------*/

#ifdef IDS_ARE_CACHED
#define ID_CACHE_SIZE 4	      /*# of previous atoms cached	   */
#endif

/*
 * Number of bits to use for Group ID in each atom. Increase if H4TOH5I_NGROUPS
 * becomes too large (an assertion would fail in H4TOH5I_init_interface). 
 * This is
 * the only number that must be changed since all other bit field sizes and
 * masks are calculated from GROUP_BITS.
 */

#define GROUP_BITS	5
#define GROUP_MASK	((1<<GROUP_BITS)-1)

/*
 * Number of bits to use for the Atom index in each atom (assumes 8-bit
 * bytes). We don't use the sign bit.
 */

#define ID_BITS		((sizeof(hid_t)*8)-(GROUP_BITS+1))
#define ID_MASK		((1<<ID_BITS)-1)

/* Map an atom to a Group number */
#define H4TOH5I_GROUP(a)	((H4TOH5I_type_t)(((hid_t)(a)>>ID_BITS) & GROUP_MASK))

#ifdef HASH_SIZE_POWER_2
/*
 * Map an ID to a hash location (assumes s is a power of 2 and smaller
 * than the ID_MASK constant).
 */
#  define H4TOH5I_LOC(a,s)		((hid_t)((size_t)(a)&((s)-1)))
#  define POWER_OF_TWO(n)	((((n) - 1) & (n)) == 0 && (n) > 0)
#else
/*
 * Map an ID to a hash location.
 */
#  define H4TOH5I_LOC(a,s)	(((hid_t)(a)&ID_MASK)%(s))
#endif

/* Combine a Group number and an atom index into an atom */
#define H4TOH5I_MAKE(g,i)	((((hid_t)(g)&GROUP_MASK)<<ID_BITS)|	  \
			     ((hid_t)(i)&ID_MASK))

#ifdef IDS_ARE_CACHED
/* ID Cache */
static H4TOH5I_id_info_t *H4TOH5I_cache_g[ID_CACHE_SIZE];
#endif

/* Array of pointers to atomic groups */
static H4TOH5I_id_group_t *H4TOH5I_id_group_list_g[H4TOH5I_NGROUPS];


/*--------------------- Local function prototypes ---------------------------*/
static H4TOH5I_id_info_t *H4TOH5I_find_id(hid_t id);


/*-------------------------------------------------------------------------
 * Function:	H4TOH5I_init_group
 *
 * Purpose:	Initialize an ID group whose ID number is specified by GRP,
 *		If the group has already been initialized, this routine just
 *		increments the count of number of initializations and returns
 *		without trying to change the size of the hash table.  A
 *		specific number (RESERVED) of group entries may be reserved
 *		to enable "constant" values to be handed out which are valid
 *		IDs in the group, but which do not map to any data structures
 *		and are not allocated dynamicly later. HASH_SIZE is the
 *		minimum hash table size to use for the group. FREE_FUNC is
 *		called with an object pointer when the object is removed from
 *		the group.
 *
 * Return:	Success:	Non-negative
 *
 *		Failure:	Negative
 *
 * Programmer:	Robb Matzke
 *		Friday, February 19, 1999
 *
 * Modifications:
 * 		Bill Wendling, 2000-05-05
 * 		Instead of the ugly test of whether hash_size is a power of
 * 		two, I placed it in a macro POWER_OF_TWO which uses the fact
 * 		that a number that is a power of two has only 1 bit set.
 *
 * 		Bill Wendling, 2000-05-09
 * 		Changed POWER_OF_TWO macro to allow 1 as a valid power of two.
 * 		Changed test below accordingly.
 *
 *-------------------------------------------------------------------------
 */
int 
H4TOH5I_init_group(H4TOH5I_type_t grp, size_t hash_size, h4toh5_uint reserved,
	       H4TOH5I_free_t free_func)
{
    H4TOH5I_id_group_t	*grp_ptr = NULL;	/*ptr to the atomic group*/


    /* Check arguments */
    if ((grp <= H4TOH5I_BADID || grp >= H4TOH5I_NGROUPS) && hash_size > 0) {
      return -1;
    }
#ifdef HASH_SIZE_POWER_2
    if (!POWER_OF_TWO(hash_size) || hash_size == 1) return -1;
#endif /* HASH_SIZE_POWER_2 */

    if (H4TOH5I_id_group_list_g[grp] == NULL) {
	/* Allocate the group information for new group */
	if (NULL==(grp_ptr = calloc(1,sizeof(H4TOH5I_id_group_t)))) {
           return -1;
	}
	H4TOH5I_id_group_list_g[grp] = grp_ptr;
    } else {
	/* Get the pointer to the existing group */
	grp_ptr = H4TOH5I_id_group_list_g[grp];
    }

    if (grp_ptr->count == 0) {
	/* Initialize the ID group structure for new groups */
	grp_ptr->hash_size = hash_size;
	grp_ptr->reserved = reserved;
	grp_ptr->wrapped = 0;
	grp_ptr->ids = 0;
	grp_ptr->nextid = reserved;
	grp_ptr->free_func = free_func;
	grp_ptr->id_list = calloc(1,hash_size*sizeof(H4TOH5I_id_info_t *));
	if (NULL==grp_ptr->id_list) {
           return -1;
	}
    }
    
    /* Increment the count of the times this group has been initialized */
    grp_ptr->count++;

    return 0;
}

/*-------------------------------------------------------------------------
 * Function:	H4TOH5I_register
 *
 * Purpose:	Registers an OBJECT in a GROUP and returns an ID for it.
 *		This routine does _not_ check for unique-ness of the objects,
 *		if you register an object twice, you will get two different
 *		IDs for it.  This routine does make certain that each ID in a
 *		group is unique.  IDs are created by getting a unique number
 *		for the group the ID is in and incorporating the group into
 *		the ID which is returned to the user.
 *
 * Return:	Success:	New object id.
 *
 *		Failure:	Negative
 *
 * Programmer:	Unknown
 *
 * Modifications:
 *
 *-------------------------------------------------------------------------
 */
hid_t 
H4TOH5I_register(H4TOH5I_type_t grp, void *object)
{
    H4TOH5I_id_group_t	*grp_ptr=NULL;	/*ptr to the group		*/
    H4TOH5I_id_info_t	*id_ptr=NULL;	/*ptr to the new ID information */
    hid_t		new_id;		/*new ID			*/
    h4toh5_uint		hash_loc;	/*new item's hash table location*/
    hid_t		next_id;	/*next ID to check		*/
    hid_t		ret_value=0; /*return value		*/
    H4TOH5I_id_info_t	*curr_id;	/*ptr to the current atom	*/
    h4toh5_uint		i;		/*counter			*/
    

    /* Check arguments */
    if (grp <= H4TOH5I_BADID || grp >= H4TOH5I_NGROUPS) {
        return -1;
    }

    grp_ptr = H4TOH5I_id_group_list_g[grp];
    if (grp_ptr == NULL || grp_ptr->count <= 0) {
       return -1;
    }

    if((id_ptr = malloc(sizeof(H4TOH5I_id_info_t))) == NULL) {
      return -1;
    }

    /* Create the struct & it's ID */
    new_id = H4TOH5I_MAKE(grp, grp_ptr->nextid);
    id_ptr->id = new_id;
    id_ptr->count = 1; /*initial reference count*/
    id_ptr->obj_ptr = object;
    id_ptr->next = NULL;

    /* hash bucket already full, prepend to front of chain */
    hash_loc = grp_ptr->nextid % (h4toh5_uint) grp_ptr->hash_size;
    if (grp_ptr->id_list[hash_loc] != NULL) {
	id_ptr->next = grp_ptr->id_list[hash_loc];
    }

    /* Insert into the group */
    grp_ptr->id_list[hash_loc] = id_ptr;
    grp_ptr->ids++;
    grp_ptr->nextid++;

    /*
     * This next section of code checks for the 'nextid' getting too large and
     * wrapping around, thus necessitating checking for duplicate IDs being
     * handed out.
     */
    if (grp_ptr->nextid > (h4toh5_uint)ID_MASK) {
	grp_ptr->wrapped = 1;
	grp_ptr->nextid = grp_ptr->reserved;
    }

    /*
     * If we've wrapped around then we need to check for duplicate id's being
     * handed out.
     */
    if (grp_ptr->wrapped) {
	/*
	 * Make sure we check all available ID's.  If we're about at the end
	 * of the range then wrap around and check the beginning values.  If
	 * we check all possible values and didn't find any free ones *then*
	 * we can fail.
	 */
	for (i=grp_ptr->reserved; i<ID_MASK; i++) {
	    /* Handle end of range by wrapping to beginning */
	    if (grp_ptr->nextid>(h4toh5_uint)ID_MASK) {
		grp_ptr->nextid = grp_ptr->reserved;
	    }

	    /* new ID to check for */
	    next_id = H4TOH5I_MAKE(grp, grp_ptr->nextid);
	    hash_loc = H4TOH5I_LOC (grp_ptr->nextid, grp_ptr->hash_size);
	    curr_id = grp_ptr->id_list[hash_loc];
	    if (curr_id == NULL) break; /* Ha! this is not likely... */

	    while (curr_id) {
		if (curr_id->id == next_id) break;
		curr_id = curr_id->next;
	    }
	    if (!curr_id) break; /* must not have found a match */
	    grp_ptr->nextid++;
	}

	if (i>=(h4toh5_uint)ID_MASK) {
	    /* All the IDs are gone! */
            return -1;
	}
    }
    ret_value = new_id;
    return ret_value;
/*  done:*/
}


/*-------------------------------------------------------------------------
 * Function:	H4TOH5I_object
 *
 * Purpose:	Find an object pointer for the specified ID.
 *
 * Return:	Success:	Non-null object pointer associated with the
 *				specified ID.
 *
 *		Failure:	NULL
 *
 * Programmer:	
 *
 * Modifications:
 *
 *-------------------------------------------------------------------------
 */
void * 
H4TOH5I_object(hid_t id)
{
    H4TOH5I_id_info_t	*id_ptr = NULL;		/*ptr to the new atom	*/
    void		*ret_value = NULL;	/*return value		*/


    /* General lookup of the ID */
    if (NULL==(id_ptr = H4TOH5I_find_id(id))){
      return NULL;
    }
    /* Check if we've found the correct ID */
    if (id_ptr) ret_value = id_ptr->obj_ptr;
    if(ret_value == NULL) {
        return ret_value;
    }
    return ret_value;
}


/*-------------------------------------------------------------------------
 * Function:	H4TOH5I_get_type
 *
 * Purpose:	Given an object ID return the group (type) to which it
 *		belongs.  The ID need not be the ID of an object which
 *		currently exists because the group number (type) is encoded
 *		in the object ID.
 *
 * Return:	Success:	A valid group number (type)
 *
 *		Failure:	H4TOH5I_BADID, a negative value.
 *
 * Programmer:	Robb Matzke
 *		Friday, February 19, 1999
 *
 * Modifications:
 *
 *-------------------------------------------------------------------------
 */
H4TOH5I_type_t 
H4TOH5I_get_type(hid_t id)
{
    H4TOH5I_type_t		ret_value = H4TOH5I_BADID;


    if (id>0) ret_value = H4TOH5I_GROUP(id);
    assert(ret_value>=H4TOH5I_BADID && ret_value<H4TOH5I_NGROUPS);

    return ret_value;
}


/*-------------------------------------------------------------------------
 * Function:	H4TOH5Iget_type
 *
 * Purpose:	The public version of H4TOH5I_get_type(), obtains a group number
 *		(type) when given an ID.  The ID need not be the ID of an
 *		object which currently exists because the group number is
 *		encoded as part of the ID.
 *
 * Return:	Success:	Group number (type)
 *
 *		Failure:	H4TOH5I_BADID, a negative value
 *
 * Programmer:	
 *
 * Modifications:
 *		Robb Matzke, 1999-08-23
 *		Also fails if the ID has a valid group but no longer exists
 *		in the ID tables.
 *-------------------------------------------------------------------------
 */
H4TOH5I_type_t
H4TOH5Iget_type(hid_t id)
{
    H4TOH5I_type_t		ret_value = H4TOH5I_BADID;

    ret_value = H4TOH5I_get_type(id);

    if (ret_value <= H4TOH5I_BADID || ret_value >= H4TOH5I_NGROUPS ||
	NULL==H4TOH5I_object(id)) {
        return ret_value;
    }
    return ret_value;
}


/*-------------------------------------------------------------------------
 * Function:	H4TOH5I_remove
 *
 * Purpose:	Removes the specified ID from its group.
 *
 * Return:	Success:	A pointer to the object that was removed, the
 *				same pointer which would have been found by
 *				calling H4TOH5I_object().
 *
 *		Failure:	NULL
 *
 * Programmer:	
 *
 * Modifications:
 *
 *-------------------------------------------------------------------------
 */
void * 
H4TOH5I_remove(hid_t id)
{
    H4TOH5I_id_group_t	*grp_ptr = NULL;/*ptr to the atomic group	*/
    H4TOH5I_id_info_t	*curr_id;	/*ptr to the current atom	*/
    H4TOH5I_id_info_t	*last_id;	/*ptr to the last atom		*/
    H4TOH5I_type_t     	grp;		/*atom's atomic group		*/
    h4toh5_uint		hash_loc;	/*atom's hash table location	*/
#ifdef IDS_ARE_CACHED
    h4toh5_uint		i;		/*local counting variable	*/
#endif
    void *	      ret_value = NULL;	/*return value			*/


    /* Check arguments */
    grp = H4TOH5I_GROUP(id);
    if (grp <= H4TOH5I_BADID || grp >= H4TOH5I_NGROUPS){
        return NULL;
    } 
    grp_ptr = H4TOH5I_id_group_list_g[grp];
    if (grp_ptr == NULL || grp_ptr->count <= 0) {
        return NULL;
    }

    /* Get the bucket in which the ID is located */
    hash_loc = (h4toh5_uint) H4TOH5I_LOC(id, grp_ptr->hash_size);
    curr_id = grp_ptr->id_list[hash_loc];
    if (curr_id == NULL) {
      return NULL;
    }

    last_id = NULL;
    while (curr_id != NULL) {
        if (curr_id->id == id)
            break;
        last_id = curr_id;
        curr_id = curr_id->next;
    }

#ifdef IDS_ARE_CACHED
    /* Delete object from cache */
    for (i = 0; i < ID_CACHE_SIZE; i++)
        if (H4TOH5I_cache_g[i] && H4TOH5I_cache_g[i]->id == id) {
            H4TOH5I_cache_g[i] = NULL;
            break; /* we assume there is only one instance in the cache */
        }
#endif /* IDS_ARE_CACHED */

    if (curr_id != NULL) {
        if (last_id == NULL) {
            /* ID is the first in the chain */
            grp_ptr->id_list[hash_loc] = curr_id->next;
        } else {
            last_id->next = curr_id->next;
        }
        ret_value = curr_id->obj_ptr;
        free(curr_id);
    } else {
      return NULL;
    }

    /* Decrement the number of IDs in the group */
    (grp_ptr->ids)--;

    return ret_value;
}


/*-------------------------------------------------------------------------
 * Function:	H4TOH5I_dec_ref
 *
 * Purpose:	Decrements the number of references outstanding for an ID.
 *		This will fail if the group is not a reference counted group.
 *		The ID group's 'free' function will be called for the ID
 *		if the reference count for the ID reaches 0 and a free
 *		function has been defined at group creation time.
 *
 * Return:	Success:	New reference count.
 *
 *		Failure:	Negative
 *
 * Programmer:	Unknown
 *
 * Modifications:
 *
 *	Robb Matzke, 19 Feb 1998
 *	It is no longer an error when the reference count of an item reaches
 *	zero and no `free' function has been defined.  The object is still
 *	removed from the list.
 *
 *	Robb Matzke, 30 Dec 1998
 *	Fixed a bug where the return value was always zero instead of the new
 *	reference count.
 *
 *	Robb Matzke, 19 Feb 1999
 *	If the free method is defined and fails then the object is not
 *	removed from the group and its reference count is not decremented.
 *	The group number is now passed to the free method.
 *
 *-------------------------------------------------------------------------
 */
int
H4TOH5I_dec_ref(hid_t id)
{
    H4TOH5I_type_t	grp = H4TOH5I_GROUP(id);  /*group the object is in*/
    H4TOH5I_id_group_t	*grp_ptr = NULL;	/*ptr to the group	*/
    H4TOH5I_id_info_t	*id_ptr = NULL;		/*ptr to the new ID	*/
    int		ret_value = -1;	/*return value		*/


    /* Check arguments */
    grp_ptr = H4TOH5I_id_group_list_g[grp];
    if (grp_ptr == NULL || grp_ptr->count <= 0) 
       return ret_value;
    
    
    /* General lookup of the ID */
    if ((id_ptr=H4TOH5I_find_id(id))) {
	/*
	 * If this is the last reference to the object then invoke the group's
	 * free method on the object. If the free method is undefined or
	 * successful then remove the object from the group; otherwise leave
	 * the object in the group without decrementing the reference
	 * count. If the reference count is more than one then decrement the
	 * reference count without calling the free method.
	 *
	 * Beware: the free method may call other H4TOH5I functions.
	 */
	if (1==id_ptr->count) {
	    if (!grp_ptr->free_func ||
		(grp_ptr->free_func)(id_ptr->obj_ptr)>=0) {
		H4TOH5I_remove(id);
		ret_value = 0;
	    } else {
		ret_value = 1;
	    }
	} else {
	    ret_value = --(id_ptr->count);
	}
    }
    return ret_value;
}


/*-------------------------------------------------------------------------
 * Function:	H4TOH5I_inc_ref
 *
 * Purpose:	Increment the reference count for an object.
 *
 * Return:	Success:	The new reference count.
 *
 *		Failure:	Negative
 *
 * Programmer:	Robb Matzke
 *              Thursday, July 29, 1999
 *
 * Modifications:
 *
 *-------------------------------------------------------------------------
 */
int
H4TOH5I_inc_ref(hid_t id)
{
    H4TOH5I_type_t		grp = H4TOH5I_GROUP(id);	/*group the object is in*/
    H4TOH5I_id_group_t	*grp_ptr = NULL;	/*ptr to the group	*/
    H4TOH5I_id_info_t	*id_ptr = NULL;		/*ptr to the ID		*/


    /* Check arguments */
    if (id<0) /*HRETURN(FAIL)*/{
        return id;
    }
    grp_ptr = H4TOH5I_id_group_list_g[grp];
    if (!grp_ptr || grp_ptr->count<=0) {
       return -1;
    }

    /* General lookup of the ID */
    if (NULL==(id_ptr=H4TOH5I_find_id(id))) {
       return -1;
    }
    id_ptr->count++;

    return id_ptr->count;
}


/*-------------------------------------------------------------------------
 * Function:	H4TOH5I_search
 *
 * Purpose:	Apply function FUNC to each member of group GRP and return a
 *		pointer to the first object for which FUNC returns non-zero.
 *		The FUNC should take a pointer to the object and the KEY as
 *		arguments and return non-zero to terminate the search (zero
 *		to continue).
 *
 * Limitation:	Currently there is no way to start searching from where a
 *		previous search left off.
 *
 * Return:	Success:	The first object in the group for which FUNC
 *				returns non-zero. NULL if FUNC returned zero
 *				for every object in the group.
 *
 *		Failure:	NULL
 *
 * Programmer:	Robb Matzke
 *		Friday, February 19, 1999
 *
 * Modifications:
 *
 *-------------------------------------------------------------------------
 */
void *
H4TOH5I_search(H4TOH5I_type_t grp, H4TOH5I_search_func_t func, const void *key)
{
    H4TOH5I_id_group_t	*grp_ptr = NULL;	/*ptr to the group	*/
    H4TOH5I_id_info_t	*id_ptr = NULL;		/*ptr to the new ID	*/
    h4toh5_uint		i;			/*counter		*/
    void		*ret_value = NULL;	/*return value		*/


    /* Check arguments */
    if (grp <= H4TOH5I_BADID || grp >= H4TOH5I_NGROUPS) {
     return NULL;
    }
    grp_ptr = H4TOH5I_id_group_list_g[grp];
    if (grp_ptr == NULL || grp_ptr->count <= 0) {
	return NULL;
    }

    /* Start at the beginning of the array */
    for (i=0; i<grp_ptr->hash_size; i++) {
	id_ptr = grp_ptr->id_list[i];
	while (id_ptr) {
	    if ((*func)(id_ptr->obj_ptr, key)) {
                return id_ptr->obj_ptr;	/*found the item*/
	    }
	    id_ptr = id_ptr->next;
	}
    }
    return ret_value;
}


/*-------------------------------------------------------------------------
 * Function:	H4TOH5I_find_id
 *
 * Purpose:	Given an object ID find the info struct that describes the
 *		object.
 *
 * Return:	Success:	Ptr to the object's info struct.
 *
 *		Failure:	NULL
 *
 * Programmer:	
 *
 * Modifications:
 *
 *-------------------------------------------------------------------------
 */
static H4TOH5I_id_info_t *
H4TOH5I_find_id(hid_t id)
{
    H4TOH5I_id_group_t	*grp_ptr = NULL;	/*ptr to the group	*/
    H4TOH5I_id_info_t	*id_ptr = NULL;		/*ptr to the new ID	*/
    H4TOH5I_type_t		grp;		 /*ID's group		*/
    h4toh5_uint 		hash_loc;	 /*bucket pointer	*/
    H4TOH5I_id_info_t	*ret_value = NULL;	/*return value		*/

#ifdef IDS_ARE_CACHED
    int 		i;
#endif


    /* Check arguments */
    grp = H4TOH5I_GROUP(id);
    if (grp <= H4TOH5I_BADID || grp >= H4TOH5I_NGROUPS) {
        return NULL;
    }
    grp_ptr = H4TOH5I_id_group_list_g[grp];
    if (grp_ptr == NULL || grp_ptr->count <= 0) {
     return NULL;  
    }

#ifdef IDS_ARE_CACHED
    /*
     * Look for the ID in the cache first. Implement a simple "move
     * forward" caching scheme by swapping the found cache item with the
     * previous cache item.  This gradually migrates used cache items toward
     * the front of the cache and unused items toward the end.	For instance,
     * finding `e' in the cache results in:
     *
     * Before: a b c d e f g h i j
     *	       | | |  X	 | | | | |
     * After:  a b c e d f g h i j
     */
    for (i=0; i<ID_CACHE_SIZE; i++)
	if (H4TOH5I_cache_g[i] && H4TOH5I_cache_g[i]->id == id) {
	    ret_value = H4TOH5I_cache_g[i];
	    if (i > 0) {
		H4TOH5I_id_info_t *tmp = H4TOH5I_cache_g[i-1];
		H4TOH5I_cache_g[i-1] = H4TOH5I_cache_g[i];
		H4TOH5I_cache_g[i] = tmp;
	    }
	}
#endif /* IDS_ARE_CACHED */

    /* Get the bucket in which the ID is located */
    hash_loc = (h4toh5_uint)H4TOH5I_LOC(id, grp_ptr->hash_size);
    id_ptr = grp_ptr->id_list[hash_loc];
    if (id_ptr == NULL) {
      return ret_value;
    }

    /* Scan the bucket's linked list for a match */
    while (id_ptr) {
	if (id_ptr->id == id) break;
	id_ptr = id_ptr->next;
    }
    ret_value = id_ptr;

#ifdef IDS_ARE_CACHED
    /* Add id to the end of the cache */
    H4TOH5I_cache_g[ID_CACHE_SIZE-1] = id_ptr;
#endif /* IDS_ARE_CACHED */
return ret_value;
}
















