Patent ID: 6499032
Filing Date: 2002-12-24
Classification: G06F,Y10S

Abstract:
A method for implementing a memory, in which memory data is stored as data units for each of which a dedicated storage space is assigned in the memory, in accordance with which methodthe memory is implemented as a directory structure comprising a tree-shaped hierarchy having nodes at several different levels, wherein an individual node can be (i) a trie; node comprising an array wherein an individual element may contain the address of a lower node in the tree-shaped hierarchy and wherein an individual element may also be empty, the number of elements in the array corresponding to a power of two, or (ii) a bucket containing at least one element in such a way that the type of an individual element in the bucket is selected from a group including a data unit, a pointer to a stored data unit, a pointer to another directory structure and another directory structure, address computation performed in the directory structure comprises the steps of (a) selecting in the trie node at the uppermost level of the tree-shaped hierarchy a node-specific number of bits from the bit string formed by the search keys employed, forming from the selected bits a search word with which the address of the next node is sought in the node, and proceeding to said node, (b) selecting from the unselected bits in the bit string formed by the search keys employed a node-specific number of bits and forming from the selected bits a search word with which the address of a further new node at a lower level is sought from the array of the node that has been accessed, repeating step (b) until an empty element is encountered or until the address of the new node at a lower level is the address of a bucket, characterized in that trie nodes are maintained in the directory structure in such a way that (c) in a trie node, the number of empty elements is smaller than or equal to half the number of elements in said node or alternatively the number of elements pointing to other trie nodes is greater than a fourth of the number of elements in the node, and (d) the number of addresses in the trie node pointing to other trie nodes is smaller than or equal to half the number of elements in the node, wherein when condition (c) is false the node is halved and when condition (d) is false the node is duplicated.