US 5,706,462 A · Self optimizing font width cache

Abstract

A self-optimizing font width cache provides an efficient caching mechanism for providing font widths to an application program. The font width cache acts as a font width server that services requests for widths for any given character. The font width cache maintains good system performance by minimizing the number of calls to the operating system without requiring an inordinate amount of memory for the font width cache. The font width cache is designed for use in conjunction with the Unicode character set, which assigns phonetic-based characters to a lower subrange of character codes and ideographic characters to an upper subrange. Each font realization is associated with a font width cache, which include two hash tables. One hash table is associated with each subrange of character codes. Both hash tables start out small and grow dynamically in response to the demands placed on the hash table by the data being displayed. The decision to increase the size of a hash table depends on the percentage of hash table slots that are in use and the number of collisions that have occurred when trying to access that hash table.

Claims50

Dependent claims

A method for providing a dynamically expandable cache for storing data associated with elements, comprising the steps of:

providing a hash table for storing said data, said hash table including n slots for storing said data for up to n of said elements;
applying a hashing function to a code corresponding to a selected element, said hashing function providing a hash key identifying a selected slot in said hash table;
determining whether said data corresponding to said selected element is stored in said selected slot in said hash table;
if said data corresponding to said selected element is stored in said selected slot, retrieving said data corresponding to said selected element, otherwise, obtaining said data corresponding to said selected element and storing said data in said hash table;
determining whether the performance of said hash table falls below a predetermined threshold;
and
increasing, if said performance falls below said predetermined threshold, the number of slots in said hash table.

4 more elements

A method for providing a memory cache for storing data associated with an element set having first and second element code subranges, comprising the steps of:

providing a plurality of hash tables including a first hash table for storing data corresponding to elements in said first element code subrange and a second hash table for storing data corresponding to elements in said second element code subrange;
receiving an element code corresponding to a selected element;
selecting said first hash table if said element code corresponds to said first element code subrange;
selecting said second hash table if said element code corresponds to said second element code subrange;
applying a hashing function to said element code, said hashing function providing a hash key identifying a selected slot in said selected hash table;
determining whether said data corresponding to said selected element is stored in said selected slot in said selected hash table;
and
if said data corresponding to said selected element is stored in said selected slot, retrieving said data corresponding to said selected element, otherwise, obtaining said data corresponding to said selected element and storing said data in said selected hash table.

5 more elements

A method for providing a dynamically expandable memory cache for an element set having first and second element code subranges, comprising the steps of:

providing a first hash table for storing data corresponding to elements in said first element code subrange;
providing a second hash table for storing data corresponding to elements in said second element code subrange;
receiving an element code corresponding to a selected element;
selecting said first hash table if said element code corresponds to said first element code subrange;
selecting said second hash table if said element code corresponds to said second element code subrange;
applying a hashing function to said element code, said hashing function providing a hash key identifying a selected slot in said selected hash table;
determining whether said data corresponding to said selected element is stored in said selected slot in said selected hash table;
if said data corresponding to said selected element is stored in said selected slot, retrieving said data corresponding to said selected element, otherwise, obtaining said data corresponding to said selected element and storing said data in said selected hash table;
determining whether the performance of said selected hash table falls below a predetermined threshold;
and
increasing, if said performance falls below said predetermined threshold, the number of slots in said selected hash table.

8 more elements

In a computer system having memory, a font, and an operating system, a dynamically expandable font property memory cache for a character set having first and second character code subranges, comprising:

a central processing unit (CPU) connected to said memory;
said CPU being operative to:
provide a plurality of hash tables in said memory including a first hash table for storing font properties corresponding to characters in said first character code subrange and a second hash table for storing font properties corresponding to characters in said second character code subrange;
receive a character code corresponding to a selected character;
select said first hash table if said character code corresponds to said first character code subrange;
select said second hash table if said character code corresponds to said second character code subrange;
apply a hashing function to said character code, said hashing function providing a hash key identifying a selected slot in said selected hash table;
determine whether said font property corresponding to said selected character is stored in said selected slot in said selected hash table;
if said data corresponding to said selected character is stored in said selected slot, retrieve said font property corresponding to said selected character, otherwise, obtain said font property corresponding to said selected character and storing said font property in said selected hash table;
determine whether the performance of said selected hash table falls below a predetermined threshold;
and
increase, if said performance falls below said predetermined threshold, the number of slots in said selected hash table.

9 more elements

A computer-readable medium on which is stored a computer program for operating a dynamically expandable memory cache for an element set having first and second element code subranges, said computer program comprising instructions which, when executed by a computer, perform the steps of:

providing a plurality of hash tables including a first hash table for storing font properties corresponding to elements in said first element code subrange and a second hash table for storing font properties corresponding to elements in said second element code subrange;
receiving an element code corresponding to a selected element;
selecting said first hash table if said element code corresponds to said first element code subrange;
selecting said second hash table if said element code corresponds to said second element code subrange;
applying a hashing function to said element code;
said hashing function providing a hash key identifying a selected slot in said selected hash table;
determining whether said data corresponding to said selected element is stored in said selected slot in said selected hash table;
if said data corresponding to said selected element is stored in said selected slot, retrieving said data corresponding to said selected element, otherwise, obtaining said data corresponding to said selected element and storing said data in said selected hash table;
determining whether the performance of said selected hash table falls below a predetermined threshold;
and
increasing, if said performance falls below said predetermined threshold, the number of slots in said selected hash table.

8 more elements

A computer-readable medium on which is stored a computer program for operating a dynamically expandable memory cache for storing data associated with an element set, said computer program comprising instructions which, when executed by a computer, perform the steps of:

providing a hash table for storing said data, said hash table including n slots for storing said data;
receiving an element code corresponding to a selected element;
applying a hashing function to said element code;
said hashing function providing a hash key identifying a selected slot in said hash table;
determining whether said data corresponding to said selected element is stored in said selected slot in said hash table;
if said data corresponding to said selected element is stored in said selected slot, retrieving said data corresponding to said selected element, otherwise, obtaining said data corresponding to said selected element and storing said data in said hash table;
determining whether the performance of said hash table falls below a predetermined threshold;
and
increasing, if said performance falls below said predetermined threshold, the number of slots in said hash table.

6 more elements

Dependencies are inferred from the claim text.

Self optimizing font width cache

Life of this patent

Self optimizing font width cache

Life of this patent

Abstract

Claims50