Browse Prior Art Database

Retrieval of Qualified Variables using Extendible Hashing

IP.com Disclosure Number: IPCOM000106732D
Original Publication Date: 1993-Dec-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 4 page(s) / 123K

Publishing Venue

IBM

Related People

Stride, CD: AUTHOR

Abstract

Disclosed is a method for storing and retrieving fully qualified, partially qualified or unqualified variables. The method described uses a forest of k-ary trees for storing variables and extendible hashing for retrieving variables. This disclosure highlights a modification to the extendible hashing algorithm to use linked lists for duplicate hash values and also highlights the combined use of exclusive-or and multiplicative hashing for calculating hash keys.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Retrieval of Qualified Variables using Extendible Hashing

      Disclosed is a method for storing and retrieving fully
qualified, partially qualified or unqualified variables.  The method
described uses a forest of k-ary trees for storing variables and
extendible hashing for retrieving variables.  This disclosure
highlights a modification to the extendible hashing algorithm to use
linked lists for duplicate hash values and also highlights the
combined use of exclusive-or and multiplicative hashing for
calculating hash keys.

      The variable list is stored as a forest of k-ary trees and
contains information about all of the valid variables declared in a
program.  Each node in the variable list contains three positional
pointers.  These are the pointer to the next variable or subfield at
the same level as the current node, the pointer to the current node's
parent, and the pointer to the current node's leftmost child.  Fig. 1
demonstrates how the variables in a series of PL/I declares are
represented in the variable list.  From the first node in the
variable list a preorder traversal will list all variables in the
order in which they were declared.

      Extendible hashing is used to simplify and shorten searches
through the variable list.  The variable list directory consists of
an array of pointers to fixed size leaf pages, containing a list of
hash keys and their corresponding pointers into the variable list.

Hash keys are calculated from the variable names and provide search
keys into the variable list.

      The hash table directory depth, D, dictates the size of the
directory.  There must be a directory entry for each possible
combination of D bits, so, since there are 2 sup D possible
combinations the size of the directory is 2 sup D.  To store a hash
key the first D bits of the hash key are used as the directory index
and the key is stored on the leaf page pointed to by this directry
entry.

      Each directory entry points to a leaf page which is capable of
holding a fixed number of hash keys.  Associated with each hash key
is a pointer to a linked list of variable list node pointers.  Each
node in a linked list will consist of a pointer to a node in the
variable list and a pointer to the next node in the linked list.
There will be one linked list for each hash key so that for each
different hash key generated there will be only one leaf page item
stored.

      A page depth, d, is given for each leaf page in the directory.
It indicates that the first d bits of each hash key on this leaf page
will be the same as the first d bits of the directory indices
pointing to the page.  The number of directory pointers addressing
this page can be calculated to be (2 sup (D minus d)), where D is the
directory depth and d is the page depth.  Fig. 2 outlines the
structure of the hash table directory and its leaf pages.

To insert an entry in the hash...