Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Method for hardware assisted data structure node look-ups

IP.com Disclosure Number: IPCOM000126997D
Publication Date: 2005-Aug-16
Document File: 3 page(s) / 37K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method for hardware assisted data structure node look-ups. Benefits include improved performance and improved design flexibility.

This text was extracted from a Microsoft Word document.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 56% of the total text.

Method for hardware assisted data structure node look-ups

Disclosed is a method for hardware assisted data structure node look-ups. Benefits include improved performance and improved design flexibility.

Background

              Many applications use linked lists or doubly linked lists to store arbitrary-length lists of data structures that can be added or removed from the list at arbitrary times. Many applications use data structure arrays to store lists of data structures. But many of these applications require the capability to search the linked list or data structure array for a member node structure with a particular value in a particular one of its data elements. Searching for a data structure with a particular value in one of its elements can be fairly expensive (in terms of processing overhead) if the code is required to check every data structure in the list or array until it finds the one it is looking for or finds that it is not present.

              To reduce the overhead, numerous strategies make use of variations of the linked list, including:

•             Binary tree

•             Balanced binary tree

•             Hash table

•             Sorted linked list

              Each of these approaches has its shortcomings. They can be expensive (in terms of processing overhead). They can be skewed in such a manner that their overhead can be unpredictable. They can also be cumbersome to design and debug.

      The classic algorithm has nodes joined as a linked list. The CPU scans and reads the value of each node until it finds the node with the requested value. Only then would it have the pointer to the required node.

General description

              The disclosed method is hardware assisted data structure node lookup.

              The key elements of the method include:

•             Instantaneous data structure node look-ups

•             Hardware that uses simple memory mapping

•             Programmed look-up or sort values for each node into a memory-mapper translation unit with its pointer as the resulting value

Advantages

              The disclosed method provides advantages, including:

•          ...