×

Method and means for managing linear mapped address spaces storing compressed data at the storage subsystem control unit or device level

  • US 5,666,114 A
  • Filed: 11/22/1994
  • Issued: 09/09/1997
  • Est. Priority Date: 11/22/1994
  • Status: Expired due to Fees
First Claim
Patent Images

1. A method of preserving locality of referencing of strings in a system for update writing-in-place of compressed images of fixed length symbol strings in counterpart addresses in a bounded (constant sum) addressable storage medium, the method comprising the steps of:

  • (a) partitioning the bounded addressable storage medium into N1 segments in a linearly addressable space and N2 segments in a linked list addressable space, each segment in N1 being of a first length less than an estimated average uncompressed symbol string length, each segment in N2 being of a second length less than the estimated average uncompressed symbol string length;

    (b) populating segments in N1 one-to-one and ONTO with compressed images of ones of the fixed length symbol strings;

    (c) updating-in-place ones of the compressed images of the fixed length symbol strings stored among said N1 address segments including;

    (1) writing portions of any compressed symbol string image exceeding the size of the segment in N1 to which it is addressed into one or more counterpart segments in N2, and(2) embedding a token in the counterpart segment in N1 pointing to the segment or segments in N2; and

    (d) recursively adjusting the size of all of the segments in N1 in a direction so that the number of segments in N2 lie within a predetermined percentage range of the current number of segments in N2.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×