Implements a hashed list of string values.

stringhashlist.pas contains types, classes, and routines used to implement a hashed list of string values.

This file is part of the lazutils package.

Thanks to Markus Waldenburg.

Pointer to a TStringHashItem instance.
Record type used to represent a hash item for a String value.

TStringHashItem is a record type which represents a hash item for a String value. It has members for the Cardinal hash value, the String for the hash value, and a pointer to Data associated with the hash item.

TStringHashItem pointers are the type added to the TStringHashList container.

Cardinal hash value for the characters in Key.
String with the content used to generate the HashValue.
Untyped Pointer to arbitrary data associated with the Key and HashValue.
Pointer to a block of TStringHashItem instances.

Implements the storage used in the TStringHashList class.

Implements a container used to store hashed item values, keys, and data.

TStringHashList is a TObject descendant which implements a container for hash values, keys, and data for String types.

TStringHashList uses the PStringHashItem type to represent the items stored in the container. This provides a 32-bit hash value, which can reflect the case for the String value if desired. It also includes an untyped pointer to arbitrary data associated with the hashed item (when provided). Items in the container are stored in hash value order, and uses a binary search for retrieval.

Use the Add method to add String values, and optional pointers to their data, to the container.

Use the Find method to get the position of an item in the container using its String value.

Use the Remove method to delete a hash item with the specified String value.

Use the Clear method to remove all hashed items in the container.

Use the Count property to determine the number of hashed items stored in the container.

Use the List property to access the storage for the container. It can be used for indexed access to the PStringHashItemList pointers with the hash value, key, and data for the items.

Use the Data property to get an untyped pointer to the arbitrary data associated with the hash item with a given key (String). The pointer must be cast to the type needed in the application.

Use the CaseSensitive property to control whether the case for a Key value is used when the hash value is generated, or retrieved in the Find method. When set to False, the key value is converted to its uppercase equivalent when the hash value is generated or retrieved. The value in CaseSensitive must be assigned before any hash items are added to the container; an exception is raised when the property value is changed and the container is not empty.

Calculates the hash value for the specified String.

HashOf is a Cardinal function used to calculate and return the 32-bit hash value for the String in Key. HashOf examines all bytes values in Key (in reverse order). When CaseSensitive is set to False, the characters are converted to their uppercase equivalent for use in the hashing algorithm. Range and overflow checking are disabled in the HashOf method.

HashOf is used in the Add method to calculate the HashValue stored in the PStringHashItem entry for the hash item. It is also used in the Find method to get the hash value to locate in the storage for the List.

Cardinal hash value for the specified Key.
String used to calculate the hash value for an item in the list.
Stores a hash item at the specified position in the container.

Insert is a method used to store the pointer in Item to the internal storage in List. Insert re-allocates the memory used for List to include the addition space needed for the new item.

Index contains the ordinal position in List where the PStringHashItem instance is stored. Index must be in the range 0..Count. When Index has the value in Count, Insert behaves like an Append operation in the List. The value Index is adjusted if it exceeds either range limit.

When Index is not the newly added position (Count), the memory for existing entries in List are shifted upward by the size of the hash item in Item. The pointer in Item is stored in List at the ordinal position in Index.

Inserts increments the value in the Count property for the newly added item in the container.

Insert is used to implement the Add method.

Ordinal position in List for the specified hash item.
Hash item inserted in the method.
Constructor for the class instance.

Create is the constructor for the class instance. It sets the value in the CaseSensitive property to the value specified in the CaseSensitivity argument. Create calls the inherited (empty) constructor prior to exiting from the method.

Default value for the CaseSensitive property in the class instance.
Destructor for the class instance.

Destroy is the overridden destructor for the class instance. It calls the Clear method to remove free any hash items and the storage allocated in List. Destroy calls the inherited method prior to exit.

Adds a hash item and optional data to the container.

Add is an overloaded Integer function used to store a hash item (and optional data associated with item) in the List for the container. The return value contains the ordinal position in List where the hash item was stored.

S is a String with the key used to construct the hash value.

ItemData is an untyped pointer to the optional data associated with the key.

Add allocates a new PStringHashItem instance used to represent the hash item in ItemData. Values in S and itemData are stored in the instance. HashOf is called to get the 32-bit hash value stored in the instance.

Hash items in List are stored in hash value order. When Count has a non-zero value, the hash value for the new entry is used to locate the position in List where the new entry is stored. When Count is 0, the item is always stored at position 0 in List.

Use Remove to delete a hash item in List with a given key value.

Use Find to get the position in List for a hash item with a given key value.

Use the Data property to get an untyped pointer to the arbitrary data associated with the given key value. The pointer must be cast to the type needed in the application.

Use List to access the PStringHashItemList using an ordinal position in the storage.

Ordinal position in List where the new hash item was stored.
Key value for the hash item.
Untyped pointer to the optional data for the specified key.
Frees resources allocated for hash items and the storage for the list.

Clear is a method used to free resources allocated for the hash items, and the memory allocated for the List property.

Clear calls Dispose for each of the PStringHashItem instances stored in List to free the memory allocated for the typed pointer. Clear calls FreeMem to free the memory allocated for the List property, and sets the member reference to Nil.

The value in Count is set to 0 to indicate that the List is empty.

Clear is called from the Destroy method when the class instance is freed.

Gets the ordinal position in List where the specified key (and data) are stored.

Find is an Integer function used to the position in List where the hash item with the specified Key value is stored. The return value contains the ordinal position for the hash item in List, or -1 when a hash item is not found for the key value in S.

S contains the key value for the hash item locates in the method. HashOf is called to get the 32-bit hash value, and BinarySearch is called to locate the hash value in List.

An overloaded variant provides an untyped pointer in Data that is also used to locate the hash item. If the value in Data does not match the stored value in List, other candidates with the same hash value are considered. A match is found when the Key and Data for the hash item are the same. Otherwise, the return value is set to -1 to indicate that a match was not found.

Find is used in the Remove method, and to implement indexed access for the Data property.

Ordinal position for the requested hash item, or -1 when not found.
Key value for the hash item to locate in the List.
Untyped pointer to the optional data for the hash item.
Frees resources allocated for the hash item and deletes it from the List.

Remove is a method used to remove a hash item in List with the specified key value (and optional data).

S contains the key value to locate in the List.

Data is an untyped Pointer to the optional data associated with the key value.

Remove calls the Find method to get the ordinal position in List where the hash item is stored, or -1 when a hash item with the key (and optional data) is not found. The position is used as the return value for the method.

When a hash item was located, the Dispose routine is called to free the memory allocated for the typed Pointer to the hash item. Delete is called to remove the PHashStringItem instance and re-order the memory for hash items after the position in List. The Count property is decremented to reflect the new size for the List.

Ordinal position in List for the removed hash item, or -1 when not found.
Key value for the hash item removed in the method.
Untyped pointer to the optional data for the hash item.
Indicates if case sensitivity is used for hash item keys.

CaseSensitive is a Boolean property which indicates the case for the key values in hash items. The default value for the property is set to the argument passed to the Create constructor.

When set to False, key values are converted to their uppercase equivalent when hash values are calculate in the HashOf method. When set to True, the existing case for the key value is used.

The value in CaseSensitive must be set before hash items are added to the List. Setting a new value for the property when Count has a non-zero value causes an EListError Exception to be raised.

CaseSensitive is used in the Find method to ensure that the search uses the same logic employed when the hash item was created.

EListError
Number of hash items stored in the List property.

Count is a read-only Integer property which contains the number of hash items stored in List. The value is maintained when the Add, Insert, Remove, Delete, or Clear methods are called.

Count establishes the upper limit for indexed access to values in the List property; index values must be in the range 0..Count-1.

Provided indexed access to the data for a hash item using its key value.

Data is an indexed Pointer property which provides access to the storage for a hash item by its key value. The untyped Pointer in the property values is arbitrary data associated with the key value, and must be cast to the type expected in an application.

The Find method is called when reading or writing a value in the property. Finds gets the position where the hash item is stored in List using the setting in the CaseSensitive property. If the value in S does not exist when reading a property value, Nil is returned. If the value in S does not exist when writing a property value, the Add method is called to create a new hash item in List with the key in S.

Data is the default property for the container, and the value used in an enumerator for the class instance.

Key value for the hash item.
Provides indexed access to the storage used in the container.

List is a read-only indexed PStringHashItemList property which provides access to the storage used in the container. Resources in List are allocated and freed in methods like Add, Remove, Delete, and Clear.

The value is a Pointer to the first memory block allocated for the PHashStringItem instances stored in the container. The property values are accessed using the ordinal position for a given hash item.

Since the property value is a Pointer, it must be dereferenced to access the member values for a given hash item. For example:

// var AKey: Cardinal; // var AHashValue: String; // var AData: TObject; // var AHashes: TStringHashList;

AKey := AHashes.List[2]^.Key; AHashValue := AHashes.List[2]^.HashValue; AData := AHashes.List[2]^.Data;