Browse Prior Art Database

LRC Protected Linked List

IP.com Disclosure Number: IPCOM000032414D
Original Publication Date: 2004-Nov-03
Included in the Prior Art Database: 2004-Nov-03
Document File: 2 page(s) / 35K

Publishing Venue

IBM

Abstract

Using an LRC Protected Linked List to Maintain its Data Integrity

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

Page 1 of 2

LRC Protected Linked List

Disclosed is a data structure and accompanying management methodologies by which the data in a linked list may be preserved and verified using Longitudinal Redundancy Checking (LRC). A linked list allows data to be organized in a linear fashion and have elements added and removed from it dynamically. When a list element is added it is said to have a link to one or more elements in the list. When it is removed, that link is broken. Without LRC, it is unknown whether the data inserted into the list is exactly the same as the data currently in the list. A similar situation exists for links. This creates an exposure for data stored in linked lists because either data or links could have been destroyed causing list corruption.

The core idea of the disclosure is to add LRC fields to both the list anchor and to each list element, which are updated when changes to the list structure or data occurs.

An LRC field is stored in the list anchor. Two LRC fields are stored in each list node, one protecting LINKs and one protecting DATA. List READ operations such as searches and queries are the same as normal linked list operations. List WRITE operations, such as list creates, node ADDs and node REMOVEs require either the node LINK LRC field or anchor LRC field to be updated. Updates to the DATA in list elements require the node's DATA LRC to be updated.

For a LIST create, the list anchor LRC field is calculated after other fields of the anchor structur...