Patent ID: 6910043
Filing Date: 2005-06-21
Classification: G06F,Y10S

Abstract:
1. A method for implementing a functional memory, wherein memory data is stored as data units for each of which a dedicated storage space is assigned in the memory, the method comprising: implementing a memory as a directory structure comprising a tree-shaped hierarchy having nodes at several different levels, wherein an individual node includes (i) a trie node associated with a logical table wherein an individual element contains a pointer pointing to a lower node in the tree-shaped hierarchy, a number of elements in the logical table corresponding to a power of two, or (ii) a bucket containing at least one element wherein a type of said 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 said another directory structure; performing address computation in the directory structure by repeating step (b) until an element containing a nil pointer is encountered or until the address of the new node at said lower level is the address of said bucket, wherein the nodes to which a given node contains pointers are child nodes of said given node and the nodes to which the child nodes contain pointers are grandchild nodes of said given node; and implementing trie nodes as quad nodes of four elements, and replacing in at least part of the directory structure groups of successive nodes by compressed nodes by