/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* Copyright by The HDF Group. *
* Copyright by the Board of Trustees of the University of Illinois. *
* All rights reserved. *
* *
* This file is part of HDF5. The full HDF5 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, or in https://support.hdfgroup.org/ftp/HDF5/releases. *
* If you do not have access to either file, you may request a copy from *
* help@hdfgroup.org. *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
#include "H5Omodule.h" /* This source code file is part of the H5O module */
#define H5S_FRIEND /*prevent warning from including H5Spkg.h */
#include "H5private.h" /* Generic Functions */
#include "H5Dprivate.h" /* Datasets */
#include "H5Eprivate.h" /* Error handling */
#include "H5FLprivate.h" /* Free lists */
#include "H5Gprivate.h" /* Groups */
#include "H5MMprivate.h" /* Memory management */
#include "H5Opkg.h" /* Object headers */
#include "H5Spkg.h" /* Dataspaces */
/* PRIVATE PROTOTYPES */
static void * H5O__sdspace_decode(H5F_t *f, H5O_t *open_oh, unsigned mesg_flags, unsigned *ioflags,
size_t p_size, const uint8_t *p);
static herr_t H5O__sdspace_encode(H5F_t *f, uint8_t *p, const void *_mesg);
static void * H5O__sdspace_copy(const void *_mesg, void *_dest);
static size_t H5O__sdspace_size(const H5F_t *f, const void *_mesg);
static herr_t H5O__sdspace_reset(void *_mesg);
static herr_t H5O__sdspace_free(void *_mesg);
static herr_t H5O__sdspace_pre_copy_file(H5F_t *file_src, const void *mesg_src, hbool_t *deleted,
const H5O_copy_t *cpy_info, void *_udata);
static herr_t H5O__sdspace_debug(H5F_t *f, const void *_mesg, FILE *stream, int indent, int fwidth);
/* Set up & include shared message "interface" info */
#define H5O_SHARED_TYPE H5O_MSG_SDSPACE
#define H5O_SHARED_DECODE H5O__sdspace_shared_decode
#define H5O_SHARED_DECODE_REAL H5O__sdspace_decode
#define H5O_SHARED_ENCODE H5O__sdspace_shared_encode
#define H5O_SHARED_ENCODE_REAL H5O__sdspace_encode
#define H5O_SHARED_SIZE H5O__sdspace_shared_size
#define H5O_SHARED_SIZE_REAL H5O__sdspace_size
#define H5O_SHARED_DELETE H5O__sdspace_shared_delete
#undef H5O_SHARED_DELETE_REAL
#define H5O_SHARED_LINK H5O__sdspace_shared_link
#undef H5O_SHARED_LINK_REAL
#define H5O_SHARED_COPY_FILE H5O__sdspace_shared_copy_file
#undef H5O_SHARED_COPY_FILE_REAL
#define H5O_SHARED_POST_COPY_FILE H5O__sdspace_shared_post_copy_file
#undef H5O_SHARED_POST_COPY_FILE_REAL
#undef H5O_SHARED_POST_COPY_FILE_UPD
#define H5O_SHARED_DEBUG H5O__sdspace_shared_debug
#define H5O_SHARED_DEBUG_REAL H5O__sdspace_debug
#include "H5Oshared.h" /* Shared Object Header Message Callbacks */
/* This message derives from H5O message class */
const H5O_msg_class_t H5O_MSG_SDSPACE[1] = {{
H5O_SDSPACE_ID, /* message id number */
"dataspace", /* message name for debugging */
sizeof(H5S_extent_t), /* native message size */
H5O_SHARE_IS_SHARABLE | H5O_SHARE_IN_OHDR, /* messages are sharable? */
H5O__sdspace_shared_decode, /* decode message */
H5O__sdspace_shared_encode, /* encode message */
H5O__sdspace_copy, /* copy the native value */
H5O__sdspace_shared_size, /* size of symbol table entry */
H5O__sdspace_reset, /* default reset method */
H5O__sdspace_free, /* free method */
H5O__sdspace_shared_delete, /* file delete method */
H5O__sdspace_shared_link, /* link method */
NULL, /* set share method */
NULL, /*can share method */
H5O__sdspace_pre_copy_file, /* pre copy native value to file */
H5O__sdspace_shared_copy_file, /* copy native value to file */
H5O__sdspace_shared_post_copy_file, /* post copy native value to file*/
NULL, /* get creation index */
NULL, /* set creation index */
H5O__sdspace_shared_debug /* debug the message */
}};
/* Declare external the free list for H5S_extent_t's */
H5FL_EXTERN(H5S_extent_t);
/* Declare external the free list for hsize_t arrays */
H5FL_ARR_EXTERN(hsize_t);
/*--------------------------------------------------------------------------
NAME
H5O__sdspace_decode
PURPOSE
Decode a simple dimensionality message and return a pointer to a memory
struct with the decoded information
USAGE
void *H5O__sdspace_decode(f, mesg_flags, p)
H5F_t *f; IN: pointer to the HDF5 file struct
unsigned mesg_flags; IN: Message flags to influence decoding
const uint8 *p; IN: the raw information buffer
RETURNS
Pointer to the new message in native order on success, NULL on failure
DESCRIPTION
This function decodes the "raw" disk form of a simple dimensionality
message into a struct in memory native format. The struct is allocated
within this function using malloc() and is returned to the caller.
--------------------------------------------------------------------------*/
static void *
H5O__sdspace_decode(H5F_t *f, H5O_t H5_ATTR_UNUSED *open_oh, unsigned H5_ATTR_UNUSED mesg_flags,
unsigned H5_ATTR_UNUSED *ioflags, size_t H5_ATTR_UNUSED p_size, const uint8_t *p)
{
H5S_extent_t *sdim = NULL; /* New extent dimensionality structure */
unsigned flags, version;
unsigned i; /* Local counting variable */
void * ret_value = NULL; /* Return value */
FUNC_ENTER_STATIC
/* check args */
HDassert(f);
HDassert(p);
/* decode */
if (NULL == (sdim = H5FL_CALLOC(H5S_extent_t)))
HGOTO_ERROR(H5E_DATASPACE, H5E_NOSPACE, NULL, "dataspace structure allocation failed")
/* Check version */
version = *p++;
if (version < H5O_SDSPACE_VERSION_1 || version > H5O_SDSPACE_VERSION_2)
HGOTO_ERROR(H5E_OHDR, H5E_CANTINIT, NULL, "wrong version number in dataspace message")
sdim->version = version;
/* Get rank */
sdim->rank = *p++;
if (sdim->rank > H5S_MAX_RANK)
HGOTO_ERROR(H5E_OHDR, H5E_CANTINIT, NULL, "simple dataspace dimensionality is too large")
/* Get dataspace flags for later */
flags = *p++;
/* Get or determine the type of the extent */
if (version >= H5O_SDSPACE_VERSION_2) {
sdim->type = (H5S_class_t)*p++;
if (sdim->type != H5S_SIMPLE && sdim->rank > 0)
HGOTO_ERROR(H5E_OHDR, H5E_BADVALUE, NULL, "invalid rank for scalar or NULL dataspace")
} /* end if */
else {
/* Set the dataspace type to be simple or scalar as appropriate */
if (sdim->rank > 0)
sdim->type = H5S_SIMPLE;
else
sdim->type = H5S_SCALAR;
/* Increment past reserved byte */
p++;
} /* end else */
HDassert(sdim->type != H5S_NULL || sdim->version >= H5O_SDSPACE_VERSION_2);
/* Only Version 1 has these reserved bytes */
if (version == H5O_SDSPACE_VERSION_1)
p += 4; /*reserved*/
/* Decode dimension sizes */
if (sdim->rank > 0) {
if (NULL == (sdim->size = (hsize_t *)H5FL_ARR_MALLOC(hsize_t, (size_t)sdim->rank)))
HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed")
for (i = 0; i < sdim->rank; i++)
H5F_DECODE_LENGTH(f, p, sdim->size[i]);
if (flags & H5S_VALID_MAX) {
if (NULL == (sdim->max = (hsize_t *)H5FL_ARR_MALLOC(hsize_t, (size_t)sdim->rank)))
HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed")
for (i = 0; i < sdim->rank; i++)
H5F_DECODE_LENGTH(f, p, sdim->max[i]);
} /* end if */
} /* end if */
/* Compute the number of elements in the extent */
if (sdim->type == H5S_NULL)
sdim->nelem = 0;
else {
for (i = 0, sdim->nelem = 1; i < sdim->rank; i++)
sdim->nelem *= sdim->size[i];
} /* end else */
/* Set return value */
ret_value = (void *)sdim; /*success*/
done:
if (!ret_value && sdim) {
H5S__extent_release(sdim);
sdim = H5FL_FREE(H5S_extent_t, sdim);
} /* end if */
FUNC_LEAVE_NOAPI(ret_value)
} /* end H5O__sdspace_decode() */
/*--------------------------------------------------------------------------
NAME
H5O__sdspace_encode
PURPOSE
Encode a simple dimensionality message
USAGE
herr_t H5O__sdspace_encode(f, raw_size, p, mesg)
H5F_t *f; IN: pointer to the HDF5 file struct
size_t raw_size; IN: size of the raw information buffer
const uint8 *p; IN: the raw information buffer
const void *mesg; IN: Pointer to the extent dimensionality struct
RETURNS
Non-negative on success/Negative on failure
DESCRIPTION
This function encodes the native memory form of the simple
dimensionality message in the "raw" disk form.
--------------------------------------------------------------------------*/
static herr_t
H5O__sdspace_encode(H5F_t *f, uint8_t *p, const void *_mesg)
{
const H5S_extent_t *sdim = (const H5S_extent_t *)_mesg;
unsigned flags = 0;
unsigned u; /* Local counting variable */
FUNC_ENTER_STATIC_NOERR
/* check args */
HDassert(f);
HDassert(p);
HDassert(sdim);
/* Version */
HDassert(sdim->version > 0);
HDassert(sdim->type != H5S_NULL || sdim->version >= H5O_SDSPACE_VERSION_2);
*p++ = (uint8_t)sdim->version;
/* Rank */
*p++ = (uint8_t)sdim->rank;
/* Flags */
if (sdim->max)
flags |= H5S_VALID_MAX;
*p++ = (uint8_t)flags;
/* Dataspace type */
if (sdim->version > H5O_SDSPACE_VERSION_1)
*p++ = (uint8_t)sdim->type;
else {
*p++ = 0; /*reserved*/
*p++ = 0; /*reserved*/
*p++ = 0; /*reserved*/
*p++ = 0; /*reserved*/
*p++ = 0; /*reserved*/
} /* end else */
/* Encode dataspace dimensions for simple dataspaces */
if (H5S_SIMPLE == sdim->type) {
/* Encode current & maximum dimensions */
if (sdim->rank > 0) {
for (u = 0; u < sdim->rank; u++)
H5F_ENCODE_LENGTH(f, p, sdim->size[u]);
if (flags & H5S_VALID_MAX)
for (u = 0; u < sdim->rank; u++)
H5F_ENCODE_LENGTH(f, p, sdim->max[u]);
} /* end if */
} /* end if */
FUNC_LEAVE_NOAPI(SUCCEED)
} /* end H5O__sdspace_encode() */
/*--------------------------------------------------------------------------
NAME
H5O__sdspace_copy
PURPOSE
Copies a message from MESG to DEST, allocating DEST if necessary.
USAGE
void *H5O__sdspace_copy(_mesg, _dest)
const void *_mesg; IN: Pointer to the source extent dimensionality struct
const void *_dest; IN: Pointer to the destination extent dimensionality struct
RETURNS
Pointer to DEST on success, NULL on failure
DESCRIPTION
This function copies a native (memory) simple dimensionality message,
allocating the destination structure if necessary.
--------------------------------------------------------------------------*/
static void *
H5O__sdspace_copy(const void *_mesg, void *_dest)
{
const H5S_extent_t *mesg = (const H5S_extent_t *)_mesg;
H5S_extent_t * dest = (H5S_extent_t *)_dest;
void * ret_value = NULL; /* Return value */
FUNC_ENTER_STATIC
/* check args */
HDassert(mesg);
if (!dest && NULL == (dest = H5FL_CALLOC(H5S_extent_t)))
HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed")
/* Copy extent information */
if (H5S__extent_copy_real(dest, mesg, TRUE) < 0)
HGOTO_ERROR(H5E_DATASPACE, H5E_CANTCOPY, NULL, "can't copy extent")
/* Set return value */
ret_value = dest;
done:
if (NULL == ret_value)
if (dest && NULL == _dest)
dest = H5FL_FREE(H5S_extent_t, dest);
FUNC_LEAVE_NOAPI(ret_value)
} /* end H5O__sdspace_copy() */
/*--------------------------------------------------------------------------
NAME
H5O__sdspace_size
PURPOSE
Return the raw message size in bytes
USAGE
void *H5O__sdspace_size(f, mesg)
H5F_t *f; IN: pointer to the HDF5 file struct
const void *mesg; IN: Pointer to the source extent dimensionality struct
RETURNS
Size of message on success, zero on failure
DESCRIPTION
This function returns the size of the raw simple dimensionality message on
success. (Not counting the message type or size fields, only the data
portion of the message). It doesn't take into account alignment.
--------------------------------------------------------------------------*/
static size_t
H5O__sdspace_size(const H5F_t *f, const void *_mesg)
{
const H5S_extent_t *space = (const H5S_extent_t *)_mesg;
size_t ret_value = 0; /* Return value */
FUNC_ENTER_STATIC_NOERR
/* Basic information for all dataspace messages */
ret_value = (size_t)(1 + /* Version */
1 + /* Rank */
1 + /* Flags */
1 + /* Dataspace type/reserved */
((space->version > H5O_SDSPACE_VERSION_1) ? 0 : 4)); /* Eliminated/reserved */
/* Add in the dimension sizes */
ret_value += space->rank * H5F_SIZEOF_SIZE(f);
/* Add in the space for the maximum dimensions, if they are present */
ret_value += space->max ? (space->rank * H5F_SIZEOF_SIZE(f)) : 0;
FUNC_LEAVE_NOAPI(ret_value)
} /* end H5O__sdspace_size() */
/*-------------------------------------------------------------------------
* Function: H5O__sdspace_reset
*
* Purpose: Frees the inside of a dataspace message and resets it to some
* initial value.
*
* Return: Non-negative on success/Negative on failure
*
* Programmer: Robb Matzke
* Thursday, April 30, 1998
*
*-------------------------------------------------------------------------
*/
static herr_t
H5O__sdspace_reset(void *_mesg)
{
H5S_extent_t *mesg = (H5S_extent_t *)_mesg;
FUNC_ENTER_STATIC_NOERR
H5S__extent_release(mesg);
FUNC_LEAVE_NOAPI(SUCCEED)
} /* end H5O__sdspace_reset() */
/*-------------------------------------------------------------------------
* Function: H5O__sdsdpace_free
*
* Purpose: Frees the message
*
* Return: Non-negative on success/Negative on failure
*
* Programmer: Quincey Koziol
* Thursday, March 30, 2000
*
*-------------------------------------------------------------------------
*/
static herr_t
H5O__sdspace_free(void *mesg)
{
FUNC_ENTER_STATIC_NOERR
HDassert(mesg);
mesg = H5FL_FREE(H5S_extent_t, mesg);
FUNC_LEAVE_NOAPI(SUCCEED)
} /* end H5O__sdspace_free() */
/*-------------------------------------------------------------------------
* Function: H5O__sdspace_pre_copy_file
*
* Purpose: Perform any necessary actions before copying message between
* files
*
* Return: Success: Non-negative
*
* Failure: Negative
*
* Programmer: Quincey Koziol
* November 30, 2006
*
*-------------------------------------------------------------------------
*/
static herr_t
H5O__sdspace_pre_copy_file(H5F_t H5_ATTR_UNUSED *file_src, const void *mesg_src,
hbool_t H5_ATTR_UNUSED *deleted, const H5O_copy_t *cpy_info, void *_udata)
{
const H5S_extent_t *src_space_extent = (const H5S_extent_t *)mesg_src; /* Source dataspace extent */
H5D_copy_file_ud_t *udata = (H5D_copy_file_ud_t *)_udata; /* Dataset copying user data */
herr_t ret_value = SUCCEED; /* Return value */
FUNC_ENTER_STATIC
/* check args */
HDassert(file_src);
HDassert(src_space_extent);
HDassert(cpy_info);
HDassert(cpy_info->file_dst);
/* Check to ensure that the version of the message to be copied does not exceed
the message version allowed by the destination file's high bound */
if (src_space_extent->version > H5O_sdspace_ver_bounds[H5F_HIGH_BOUND(cpy_info->file_dst)])
HGOTO_ERROR(H5E_OHDR, H5E_BADRANGE, FAIL, "dataspace message version out of bounds")
/* If the user data is non-NULL, assume we are copying a dataset
* and make a copy of the dataspace extent for later in the object copying
* process. (We currently only need to make a copy of the dataspace extent
* if the layout is an early version, but that information isn't
* available here, so we just make a copy of it in all cases)
*/
if (udata) {
/* Allocate copy of dataspace extent */
if (NULL == (udata->src_space_extent = H5FL_CALLOC(H5S_extent_t)))
HGOTO_ERROR(H5E_DATASPACE, H5E_NOSPACE, FAIL, "dataspace extent allocation failed")
/* Create a copy of the dataspace extent */
if (H5S__extent_copy_real(udata->src_space_extent, src_space_extent, TRUE) < 0)
HGOTO_ERROR(H5E_DATASPACE, H5E_CANTCOPY, FAIL, "can't copy extent")
} /* end if */
done:
FUNC_LEAVE_NOAPI(ret_value)
} /* end H5O_dspace_pre_copy_file() */
/*--------------------------------------------------------------------------
NAME
H5O__sdspace_debug
PURPOSE
Prints debugging information for a simple dimensionality message
USAGE
void *H5O__sdspace_debug(f, mesg, stream, indent, fwidth)
H5F_t *f; IN: pointer to the HDF5 file struct
const void *mesg; IN: Pointer to the source extent dimensionality struct
FILE *stream; IN: Pointer to the stream for output data
int indent; IN: Amount to indent information by
int fwidth; IN: Field width (?)
RETURNS
Non-negative on success/Negative on failure
DESCRIPTION
This function prints debugging output to the stream passed as a
parameter.
--------------------------------------------------------------------------*/
static herr_t
H5O__sdspace_debug(H5F_t H5_ATTR_UNUSED *f, const void *mesg, FILE *stream, int indent, int fwidth)
{
const H5S_extent_t *sdim = (const H5S_extent_t *)mesg;
FUNC_ENTER_STATIC_NOERR
/* check args */
HDassert(f);
HDassert(sdim);
HDassert(stream);
HDassert(indent >= 0);
HDassert(fwidth >= 0);
HDfprintf(stream, "%*s%-*s %lu\n", indent, "", fwidth, "Rank:", (unsigned long)(sdim->rank));
if (sdim->rank > 0) {
unsigned u; /* local counting variable */
HDfprintf(stream, "%*s%-*s {", indent, "", fwidth, "Dim Size:");
for (u = 0; u < sdim->rank; u++)
HDfprintf(stream, "%s%" PRIuHSIZE, u ? ", " : "", sdim->size[u]);
HDfprintf(stream, "}\n");
HDfprintf(stream, "%*s%-*s ", indent, "", fwidth, "Dim Max:");
if (sdim->max) {
HDfprintf(stream, "{");
for (u = 0; u < sdim->rank; u++) {
if (H5S_UNLIMITED == sdim->max[u])
HDfprintf(stream, "%sUNLIM", u ? ", " : "");
else
HDfprintf(stream, "%s%" PRIuHSIZE, u ? ", " : "", sdim->max[u]);
} /* end for */
HDfprintf(stream, "}\n");
} /* end if */
else
HDfprintf(stream, "CONSTANT\n");
} /* end if */
FUNC_LEAVE_NOAPI(SUCCEED)
} /* end H5O__sdspace_debug() */
_encoding'>dkf_alias_encoding
Tcl is a high-level, general-purpose, interpreted, dynamic programming language. It was designed with the goal of being very simple but powerful.
/* * tclHash.c -- * * Implementation of in-memory hash tables for Tcl and Tcl-based * applications. * * Copyright (c) 1991-1993 The Regents of the University of California. * Copyright (c) 1994 Sun Microsystems, Inc. * * See the file "license.terms" for information on usage and redistribution of * this file, and for a DISCLAIMER OF ALL WARRANTIES. */#include"tclInt.h"/* * Prevent macros from clashing with function definitions. */#undef Tcl_FindHashEntry#undef Tcl_CreateHashEntry/* * When there are this many entries per bucket, on average, rebuild the hash * table to make it larger. */#define REBUILD_MULTIPLIER 3/* * The following macro takes a preliminary integer hash value and produces an * index into a hash tables bucket list. The idea is to make it so that * preliminary values that are arbitrarily similar will end up in different * buckets. The hash function was taken from a random-number generator. */#define RANDOM_INDEX(tablePtr, i) \ (((((long) (i))*1103515245) >> (tablePtr)->downShift) & (tablePtr)->mask)/* * Prototypes for the array hash key methods. */static Tcl_HashEntry *AllocArrayEntry(Tcl_HashTable *tablePtr, VOID *keyPtr);static intCompareArrayKeys(VOID *keyPtr, Tcl_HashEntry *hPtr);static unsigned intHashArrayKey(Tcl_HashTable *tablePtr, VOID *keyPtr);/* * Prototypes for the one word hash key methods. */#if 0static Tcl_HashEntry *AllocOneWordEntry(Tcl_HashTable *tablePtr,
VOID *keyPtr);static intCompareOneWordKeys(VOID *keyPtr, Tcl_HashEntry *hPtr);static unsigned intHashOneWordKey(Tcl_HashTable *tablePtr, VOID *keyPtr);#endif/* * Prototypes for the string hash key methods. */static Tcl_HashEntry *AllocStringEntry(Tcl_HashTable *tablePtr,
VOID *keyPtr);static intCompareStringKeys(VOID *keyPtr, Tcl_HashEntry *hPtr);static unsigned intHashStringKey(Tcl_HashTable *tablePtr, VOID *keyPtr);/* * Function prototypes for static functions in this file: */static Tcl_HashEntry *BogusFind(Tcl_HashTable *tablePtr,const char*key);static Tcl_HashEntry *BogusCreate(Tcl_HashTable *tablePtr,const char*key,int*newPtr);static Tcl_HashEntry *CreateHashEntry(Tcl_HashTable *tablePtr,const char*key,int*newPtr);static Tcl_HashEntry *FindHashEntry(Tcl_HashTable *tablePtr,const char*key);static voidRebuildTable(Tcl_HashTable *tablePtr);
Tcl_HashKeyType tclArrayHashKeyType = {
TCL_HASH_KEY_TYPE_VERSION,/* version */
TCL_HASH_KEY_RANDOMIZE_HASH,/* flags */
HashArrayKey,/* hashKeyProc */
CompareArrayKeys,/* compareKeysProc */
AllocArrayEntry,/* allocEntryProc */
NULL /* freeEntryProc */};
Tcl_HashKeyType tclOneWordHashKeyType = {
TCL_HASH_KEY_TYPE_VERSION,/* version */0,/* flags */
NULL,/* HashOneWordKey, *//* hashProc */
NULL,/* CompareOneWordKey, *//* compareProc */
NULL,/* AllocOneWordKey, *//* allocEntryProc */
NULL /* FreeOneWordKey, *//* freeEntryProc */};
Tcl_HashKeyType tclStringHashKeyType = {
TCL_HASH_KEY_TYPE_VERSION,/* version */0,/* flags */
HashStringKey,/* hashKeyProc */
CompareStringKeys,/* compareKeysProc */
AllocStringEntry,/* allocEntryProc */
NULL /* freeEntryProc */};/* *---------------------------------------------------------------------- * * Tcl_InitHashTable -- * * Given storage for a hash table, set up the fields to prepare the hash * table for use. * * Results: * None. * * Side effects: * TablePtr is now ready to be passed to Tcl_FindHashEntry and * Tcl_CreateHashEntry. * *---------------------------------------------------------------------- */#undef Tcl_InitHashTablevoidTcl_InitHashTable(register Tcl_HashTable *tablePtr,/* Pointer to table record, which is supplied * by the caller. */int keyType)/* Type of keys to use in table: * TCL_STRING_KEYS, TCL_ONE_WORD_KEYS, or an * integer >= 2. */{/* * Use a special value to inform the extended version that it must not * access any of the new fields in the Tcl_HashTable. If an extension is * rebuilt then any calls to this function will be redirected to the * extended version by a macro. */Tcl_InitCustomHashTable(tablePtr, keyType, (Tcl_HashKeyType *) -1);}/* *---------------------------------------------------------------------- * * Tcl_InitCustomHashTable -- * * Given storage for a hash table, set up the fields to prepare the hash * table for use. This is an extended version of Tcl_InitHashTable which * supports user defined keys. * * Results: * None. * * Side effects: * TablePtr is now ready to be passed to Tcl_FindHashEntry and * Tcl_CreateHashEntry. * *---------------------------------------------------------------------- */voidTcl_InitCustomHashTable(register Tcl_HashTable *tablePtr,/* Pointer to table record, which is supplied * by the caller. */int keyType,/* Type of keys to use in table: * TCL_STRING_KEYS, TCL_ONE_WORD_KEYS, * TCL_CUSTOM_TYPE_KEYS, TCL_CUSTOM_PTR_KEYS, * or an integer >= 2. */
Tcl_HashKeyType *typePtr)/* Pointer to structure which defines the * behaviour of this table. */{#if (TCL_SMALL_HASH_TABLE != 4)Tcl_Panic("Tcl_InitCustomHashTable: TCL_SMALL_HASH_TABLE is %d, not 4",
TCL_SMALL_HASH_TABLE);#endif
tablePtr->buckets = tablePtr->staticBuckets;
tablePtr->staticBuckets[0] = tablePtr->staticBuckets[1] =0;
tablePtr->staticBuckets[2] = tablePtr->staticBuckets[3] =0;
tablePtr->numBuckets = TCL_SMALL_HASH_TABLE;
tablePtr->numEntries =0;
tablePtr->rebuildSize = TCL_SMALL_HASH_TABLE*REBUILD_MULTIPLIER;
tablePtr->downShift =28;
tablePtr->mask =3;
tablePtr->keyType = keyType;
tablePtr->findProc = FindHashEntry;
tablePtr->createProc = CreateHashEntry;if(typePtr == NULL) {/* * The caller has been rebuilt so the hash table is an extended * version. */}else if(typePtr != (Tcl_HashKeyType *) -1) {/* * The caller is requesting a customized hash table so it must be an * extended version. */
tablePtr->typePtr = typePtr;}else{/* * The caller has not been rebuilt so the hash table is not extended. */}}/* *---------------------------------------------------------------------- * * Tcl_FindHashEntry -- * * Given a hash table find the entry with a matching key. * * Results: * The return value is a token for the matching entry in the hash table, * or NULL if there was no matching entry. * * Side effects: * None. * *---------------------------------------------------------------------- */
Tcl_HashEntry *Tcl_FindHashEntry(
Tcl_HashTable *tablePtr,/* Table in which to lookup entry. */const char*key)/* Key to use to find matching entry. */{return(*((tablePtr)->findProc))(tablePtr, key);}static Tcl_HashEntry *FindHashEntry(
Tcl_HashTable *tablePtr,/* Table in which to lookup entry. */const char*key)/* Key to use to find matching entry. */{returnCreateHashEntry(tablePtr, key, NULL);}/* *---------------------------------------------------------------------- * * Tcl_CreateHashEntry -- * * Given a hash table with string keys, and a string key, find the entry * with a matching key. If there is no matching entry, then create a new * entry that does match. * * Results: * The return value is a pointer to the matching entry. If this is a * newly-created entry, then *newPtr will be set to a non-zero value; * otherwise *newPtr will be set to 0. If this is a new entry the value * stored in the entry will initially be 0. * * Side effects: * A new entry may be added to the hash table. * *---------------------------------------------------------------------- */
Tcl_HashEntry *Tcl_CreateHashEntry(
Tcl_HashTable *tablePtr,/* Table in which to lookup entry. */const char*key,/* Key to use to find or create matching * entry. */int*newPtr)/* Store info here telling whether a new entry * was created. */{return(*((tablePtr)->createProc))(tablePtr, key, newPtr);}static Tcl_HashEntry *CreateHashEntry(
Tcl_HashTable *tablePtr,/* Table in which to lookup entry. */const char*key,/* Key to use to find or create matching * entry. */int*newPtr)/* Store info here telling whether a new entry * was created. */{register Tcl_HashEntry *hPtr;const Tcl_HashKeyType *typePtr;unsigned int hash;int index;if(tablePtr->keyType == TCL_STRING_KEYS) {
typePtr = &tclStringHashKeyType;}else if(tablePtr->keyType == TCL_ONE_WORD_KEYS) {
typePtr = &tclOneWordHashKeyType;}else if(tablePtr->keyType == TCL_CUSTOM_TYPE_KEYS
|| tablePtr->keyType == TCL_CUSTOM_PTR_KEYS) {
typePtr = tablePtr->typePtr;}else{
typePtr = &tclArrayHashKeyType;}if(typePtr->hashKeyProc) {
hash = typePtr->hashKeyProc(tablePtr, (VOID *) key);if(typePtr->flags & TCL_HASH_KEY_RANDOMIZE_HASH) {
index =RANDOM_INDEX(tablePtr, hash);}else{
index = hash & tablePtr->mask;}}else{
hash =PTR2UINT(key);
index =RANDOM_INDEX(tablePtr, hash);}/* * Search all of the entries in the appropriate bucket. */if(typePtr->compareKeysProc) {
Tcl_CompareHashKeysProc *compareKeysProc = typePtr->compareKeysProc;for(hPtr = tablePtr->buckets[index]; hPtr != NULL;
hPtr = hPtr->nextPtr) {#if TCL_HASH_KEY_STORE_HASHif(hash !=PTR2UINT(hPtr->hash)) {continue;}#endifif(compareKeysProc((VOID *) key, hPtr)) {if(newPtr) {*newPtr =0;}return hPtr;}}}else{for(hPtr = tablePtr->buckets[index]; hPtr != NULL;
hPtr = hPtr->nextPtr) {#if TCL_HASH_KEY_STORE_HASHif(hash !=PTR2UINT(hPtr->hash)) {continue;}#endifif(key == hPtr->key.oneWordValue) {if(newPtr) {*newPtr =0;}return hPtr;}}}if(!newPtr) {return NULL;}/* * Entry not found. Add a new one to the bucket. */*newPtr =1;if(typePtr->allocEntryProc) {
hPtr = typePtr->allocEntryProc(tablePtr, (VOID *) key);}else{
hPtr = (Tcl_HashEntry *)ckalloc((unsigned)sizeof(Tcl_HashEntry));
hPtr->key.oneWordValue = (char*) key;
hPtr->clientData =0;}
hPtr->tablePtr = tablePtr;#if TCL_HASH_KEY_STORE_HASH
hPtr->hash =UINT2PTR(hash);
hPtr->nextPtr = tablePtr->buckets[index];
tablePtr->buckets[index] = hPtr;#else
hPtr->bucketPtr = &(tablePtr->buckets[index]);
hPtr->nextPtr = *hPtr->bucketPtr;*hPtr->bucketPtr = hPtr;#endif
tablePtr->numEntries++;/* * If the table has exceeded a decent size, rebuild it with many more * buckets. */if(tablePtr->numEntries >= tablePtr->rebuildSize) {RebuildTable(tablePtr);}return hPtr;}/* *---------------------------------------------------------------------- * * Tcl_DeleteHashEntry -- * * Remove a single entry from a hash table. * * Results: * None. * * Side effects: * The entry given by entryPtr is deleted from its table and should never * again be used by the caller. It is up to the caller to free the * clientData field of the entry, if that is relevant. * *---------------------------------------------------------------------- */voidTcl_DeleteHashEntry(
Tcl_HashEntry *entryPtr){register Tcl_HashEntry *prevPtr;const Tcl_HashKeyType *typePtr;
Tcl_HashTable *tablePtr;
Tcl_HashEntry **bucketPtr;#if TCL_HASH_KEY_STORE_HASHint index;#endif
tablePtr = entryPtr->tablePtr;if(tablePtr->keyType == TCL_STRING_KEYS) {
typePtr = &tclStringHashKeyType;}else if(tablePtr->keyType == TCL_ONE_WORD_KEYS) {
typePtr = &tclOneWordHashKeyType;}else if(tablePtr->keyType == TCL_CUSTOM_TYPE_KEYS
|| tablePtr->keyType == TCL_CUSTOM_PTR_KEYS) {
typePtr = tablePtr->typePtr;}else{
typePtr = &tclArrayHashKeyType;}#if TCL_HASH_KEY_STORE_HASHif(typePtr->hashKeyProc == NULL
|| typePtr->flags & TCL_HASH_KEY_RANDOMIZE_HASH) {
index =RANDOM_INDEX(tablePtr,PTR2UINT(entryPtr->hash));}else{
index =PTR2UINT(entryPtr->hash) & tablePtr->mask;}
bucketPtr = &(tablePtr->buckets[index]);#else
bucketPtr = entryPtr->bucketPtr;#endifif(*bucketPtr == entryPtr) {*bucketPtr = entryPtr->nextPtr;}else{for(prevPtr = *bucketPtr; ; prevPtr = prevPtr->nextPtr) {if(prevPtr == NULL) {Tcl_Panic("malformed bucket chain in Tcl_DeleteHashEntry");}if(prevPtr->nextPtr == entryPtr) {
prevPtr->nextPtr = entryPtr->nextPtr;break;}}}
tablePtr->numEntries--;if(typePtr->freeEntryProc) {
typePtr->freeEntryProc(entryPtr);}else{ckfree((char*) entryPtr);}}/* *---------------------------------------------------------------------- * * Tcl_DeleteHashTable -- * * Free up everything associated with a hash table except for the record * for the table itself. * * Results: * None. * * Side effects: * The hash table is no longer useable. * *---------------------------------------------------------------------- */voidTcl_DeleteHashTable(register Tcl_HashTable *tablePtr)/* Table to delete. */{register Tcl_HashEntry *hPtr, *nextPtr;const Tcl_HashKeyType *typePtr;int i;if(tablePtr->keyType == TCL_STRING_KEYS) {
typePtr = &tclStringHashKeyType;}else if(tablePtr->keyType == TCL_ONE_WORD_KEYS) {
typePtr = &tclOneWordHashKeyType;}else if(tablePtr->keyType == TCL_CUSTOM_TYPE_KEYS
|| tablePtr->keyType == TCL_CUSTOM_PTR_KEYS) {
typePtr = tablePtr->typePtr;}else{
typePtr = &tclArrayHashKeyType;}/* * Free up all the entries in the table. */for(i =0; i < tablePtr->numBuckets; i++) {
hPtr = tablePtr->buckets[i];while(hPtr != NULL) {
nextPtr = hPtr->nextPtr;if(typePtr->freeEntryProc) {
typePtr->freeEntryProc(hPtr);}else{ckfree((char*) hPtr);}
hPtr = nextPtr;}}/* * Free up the bucket array, if it was dynamically allocated. */if(tablePtr->buckets != tablePtr->staticBuckets) {if(typePtr->flags & TCL_HASH_KEY_SYSTEM_HASH) {TclpSysFree((char*) tablePtr->buckets);}else{ckfree((char*) tablePtr->buckets);}}/* * Arrange for panics if the table is used again without * re-initialization. */
tablePtr->findProc = BogusFind;
tablePtr->createProc = BogusCreate;}/* *---------------------------------------------------------------------- * * Tcl_FirstHashEntry -- * * Locate the first entry in a hash table and set up a record that can be * used to step through all the remaining entries of the table. * * Results: * The return value is a pointer to the first entry in tablePtr, or NULL * if tablePtr has no entries in it. The memory at *searchPtr is * initialized so that subsequent calls to Tcl_NextHashEntry will return * all of the entries in the table, one at a time. * * Side effects: * None. * *---------------------------------------------------------------------- */
Tcl_HashEntry *Tcl_FirstHashEntry(
Tcl_HashTable *tablePtr,/* Table to search. */
Tcl_HashSearch *searchPtr)/* Place to store information about progress * through the table. */{
searchPtr->tablePtr = tablePtr;
searchPtr->nextIndex =0;
searchPtr->nextEntryPtr = NULL;returnTcl_NextHashEntry(searchPtr);}/* *---------------------------------------------------------------------- * * Tcl_NextHashEntry -- * * Once a hash table enumeration has been initiated by calling * Tcl_FirstHashEntry, this function may be called to return successive * elements of the table. * * Results: * The return value is the next entry in the hash table being enumerated, * or NULL if the end of the table is reached. * * Side effects: * None. * *---------------------------------------------------------------------- */
Tcl_HashEntry *Tcl_NextHashEntry(register Tcl_HashSearch *searchPtr)/* Place to store information about progress * through the table. Must have been * initialized by calling * Tcl_FirstHashEntry. */{
Tcl_HashEntry *hPtr;
Tcl_HashTable *tablePtr = searchPtr->tablePtr;while(searchPtr->nextEntryPtr == NULL) {if(searchPtr->nextIndex >= tablePtr->numBuckets) {return NULL;}
searchPtr->nextEntryPtr =
tablePtr->buckets[searchPtr->nextIndex];
searchPtr->nextIndex++;}
hPtr = searchPtr->nextEntryPtr;
searchPtr->nextEntryPtr = hPtr->nextPtr;return hPtr;}/* *---------------------------------------------------------------------- * * Tcl_HashStats -- * * Return statistics describing the layout of the hash table in its hash * buckets. * * Results: * The return value is a malloc-ed string containing information about * tablePtr. It is the caller's responsibility to free this string. * * Side effects: * None. * *---------------------------------------------------------------------- */char*Tcl_HashStats(
Tcl_HashTable *tablePtr)/* Table for which to produce stats. */{#define NUM_COUNTERS 10int count[NUM_COUNTERS], overflow, i, j;double average, tmp;register Tcl_HashEntry *hPtr;char*result, *p;const Tcl_HashKeyType *typePtr;if(tablePtr->keyType == TCL_STRING_KEYS) {
typePtr = &tclStringHashKeyType;}else if(tablePtr->keyType == TCL_ONE_WORD_KEYS) {
typePtr = &tclOneWordHashKeyType;}else if(tablePtr->keyType == TCL_CUSTOM_TYPE_KEYS