Patent ID: 6675171
Filing Date: 2004-01-06
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, the method comprising:using a directory structure comprising: a tree-shaped hierarchy having nodes at several different levels, at least some of the nodes are associated with a logical element table, the individual element may contain a pointer pointing to a lower node in the tree-shaped hierarchy, or may be empty, in which case the content of the element corresponds to a nil pointer, the number of elements in the table corresponding to a power of two; computing an address in the directory structure, the computation comprising: selecting a given number of bits from a bit string formed by search keys; forming from selected bits a search word with which an address of a next node is sought in the node, and proceeding to the next node; selecting a predetermined number of bits from unselected bits in the bit string formed by the search keys employed, and forming from the predetermined number of bits a search word with which the address of a further new node at a lower level is sought in the next node that has been accessed; and repeating selection of the predetermined number of bits until an element containing a nil pointer is encountered or until a node at the lowest level is accessed; employing width-compressed nodes in which non-nil pointers are physically stored and additionally a bit pattern which has one bit for each element and wherein a given value of an individual bit indicates that the content of the element corresponds to a pointer pointing downward in the directory structure and a complement value of the given value indicates that the content of the element corresponds to a nil pointer; determining a physical storage location in a node corresponding to the element table index associated with the search word on the basis of the bit pattern, the determination of the physical storage location comprising: storing at least one search table in which numbers of bits having the given value are stored in different combinations of a word whose total number of bits is a predetermined portion of the total number of bits in the bit pattern; setting all bits in the bit pattern corresponding to an index that is greater than an element table index to indicate a nil pointer; and performing a certain number of reading operations from at least one search table in accordance with a value of the element table index as compared to the total number of bits in the word, the numbers obtained being added together when there are more than one reading operations.