System and method for buffering data

• US 6,032,219 A
• Filed: 08/01/1997
• Issued: 02/29/2000
• Est. Priority Date: 08/01/1997
• Status: Expired due to Term

• Current Assignee: Garmin Corporation (Garmin Limited)
• Original Assignee: Garmin Corporation (Garmin Limited)
• Inventors: Beesley, Darin J., Walters, Thomas H., Robinson, Stephen C.
• Primary Examiner(s): Cabeca, John W.
• Assistant Examiner(s): TZENG, FRED
• Application Number:
  US08/904,638
• Time in Patent Office: 942 Days
• Field of Search: 711/1, 711/168, 711/170, 711/156, 711/4, 711/118, 711/103, 711/114, 710/53, 710/56, 710/74, 710/21, 709/300, 709/303, 709/231, 705/32
• US Class Current: 711/1
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/0674 Disk device

Abstract

A system for buffering data has a processor connected to a memory for storing mass data, connected to a single buffer having a plurality of buffer storage locations in a chain, and connected to a plurality of counters, wherein each counter corresponds to one of the buffer storage locations. The processor selects a sector of memory containing desired data associated with an open file, scans the buffer storage locations to determine whether the data is in the buffer and, when the data is not within the buffer, reads the data from the selected sector of memory into a selected buffer storage location that is unallocated to an open file. The processor then points to that allocated buffer storage location, so that the data can be retrieved from the buffer for processing. As additional data is desired that is not found in the buffer, the buffer storage location allocated to the open file is de-allocated and, if not allocated to any other open files, moved to the beginning of the chain of buffers. The sector of data containing the desired data is then read into a selected buffer that is not allocated to an open file, preferably the last unallocated buffer in the chain of buffers. In accordance with the present invention, a buffer storage location can be allocated to multiple open files. De-allocation of a buffer storage location from an open file will not cause the buffer storage location to be moved to the beginning of the chain when the buffer storage location is allocated to one or more other open files. When data within a buffer storage location has been modified, prior to de-allocation of that buffer storage location with respect to an open file, the processor writes the data, including the modifications, back to the associated sector in mass memory. In one embodiment, the system of the present invention is incorporated in a portable electronic device including a keyboard and a display, and a housing for housing the keyboard, display, processor, buffer, and memory. In a preferred embodiment, the portable electronic device is a navigation aid and selected data is map data.

Claims

1. A method of buffering data in a system having a memory, organized into sectors, with a plurality of files of data stored therein, a processor connected to said memory, a buffer having a plurality of buffer storage locations organized in a chain, said buffer connected to said processor, and a plurality of counters wherein each said counter corresponds to one of said buffer storage locations, said method comprising:

(a) selecting a said sector of said memory containing desired data associated with an open one of said files;

(b) scanning the buffer storage locations to determine whether said desired data is in said buffer;

(c) keeping track of a selected buffer storage location that is not allocated to a file;

(d) when the desired data is not found within a buffer storage location, reading the desired data from said selected sector of said memory into said selected unallocated buffer storage location;

(e) considering said buffer storage location into which data of said selected sector was just stored as a matching buffer storage location for said open file;

(f) pointing said processor to said matching buffer storage location; and

(g) retrieving said selected data from said matching buffer storage location for processing by said processor.

2. The method as set forth in claim 1 further comprising:

incrementing the said counter corresponding to said buffer storage location considered the said matching buffer storage location.

3. The method as set forth in claim 2 further comprising:

(a) selecting an additional said sector of said memory containing additional desired data associated with said open one of said files;

(b) scanning the buffer storage locations to determine whether said additional desired data is in said buffer;

(c) keeping track of a selected buffer storage location that is not allocated to a file;

(d) when the desired data is not found within a buffer storage location, de-allocating the buffer storage location currently considered as the matching buffer storage location;

(e) reordering the location of said buffer storage locations such that said de-allocated buffer storage location moves to the beginning of said chain of buffer storage locations;

(f) reading said additional desired data from said selected sector of said memory into said selected unallocated buffer storage location; and

(g) repeating steps (e)-(g) of claim 1.

4. The method as set forth in claim 3 further comprising:

decrementing the said counter corresponding to the said buffer storage location that is de-allocated.

5. The method as set forth in claim 4, wherein said open file is a first open file, said method further comprising the steps of:

opening a second said file;

selecting a said sector of said memory containing desired data associated with said second open file; and

repeating steps (c)-(g) of claim 1 with respect to said data associated with said second open file.

6. The method as set forth in claim 5 further comprising:

incrementing the said counter corresponding to the said buffer storage location considered the said matching buffer storage location with respect to said second open file.

7. The method as set forth in claim 6 further comprising:

selecting an additional said sector of memory containing additional desired data associated with said second open file;

scanning the buffer storage locations to determine whether said additional desired data with respect to said second file is in said buffer; and

keeping track of a selected buffer storage location that is riot allocated to a file.

8. The method as set forth in claim 7 further comprising:

when the said desired data associated with said second open file is not found within a buffer storage location, de-allocating the buffer storage location currently considered as the matching buffer storage location with respect to said second open file;

decrementing the said counter associated with said de-allocated buffer storage location with respect to said second open file; and

when said decremented counter is a selected minimum value, reordering the locations of said buffer storage locations such that said de-allocated buffer storage location with respect to said second open file is moved to the beginning of said buffer chain.

9. The method as set forth in claim 7 further comprising:

when the said desired data associated with said second open file is found within the buffer storage location considered the said matching buffer storage location with respect to said first open file, de-allocating the buffer storage location currently considered said matching buffer storage Location with respect to said second open file;

decrementing the said counter associated with said de-allocated buffer storage location with respect to said second open file;

when said decremented counter is a selected minimum value, reordering the locations of said buffer storage locations such that said de-allocated buffer storage location with respect to said second open file is moved to the beginning of said buffer chain;

considering said buffer storage location containing said desired data with respect to said second open file to be a matching buffer storage location with respect to said second open file;

updating said processor to point to said buffer storage location considered said matching buffer storage location with respect to said second open file; and

incrementing said counter associated with said buffer storage location considered said matching buffer storage location with respect to said second file.

10. The method as set forth in claim 7, further comprising:

when the said desired data associated with said second open file is found within the buffer storage location considered the said matching buffer storage location with respect to said second open file, retrieving said desired data from said matching buffer storage location with respect to said second open file for processing of said desired data.

11. The method as set forth in claim 2, wherein said the step of de-allocating said buffer storage location further comprises:

determining, prior to de-allocating the buffer storage location, whether data in said buffer storage location has been modified; and

when it is determined that the data in said buffer storage location to be de-allocated has been modified, writing the data within said buffer storage location, including said modification, to the said sector of said memory to which said data corresponds.

12. A system for buffering data associated with a plurality of files, said system comprising:

a mass data storage unit for storing said data, said mass data storage unit organized into a plurality of sectors;

a single buffer having a plurality of buffer storage locations organized in a chain;

a plurality of counters, each said counter corresponding to one of said buffer storage locations;

a processor, having a pointer, said processor connected to said mass data storage unit, said buffer, and said counters, wherein said processor (a) selects a said sector of said mass data storage unit containing desired data associated with an open one of said files, (b) scans said buffer storage locations to determine whether said desired data is in said buffer, (c) reads said desired data from said selected sector of said mass data storage unit into a selected buffer storage location when said processor determines, as a result of scanning, that said desired data is not within said buffer and, (d) allocates said selected buffer storage location to said open file.

13. The system for buffering data as set forth in claim 12, wherein said selected buffer storage location is a last buffer storage location in said chain that is not allocated to an open file.

14. The system for buffering data as set forth in claim 13, wherein said processor selects an additional said sector of said mass data storage unit containing additional desired data associated with said open file, said processor scans said buffer storage locations to determine whether said additional desired data is in said buffer, and when said additional desired data is not found within a buffer storage location, said processor de-allocates said selected buffer storage location currently allocated to said open file, reads the data associated with said additional said sector into a next selected buffer storage location, and allocates said open file to said next selected buffer location.

15. The system as set forth in claim 14, wherein said open file is a first open file, wherein said processor opens a second said file, selects a said sector of said mass data storage unit containing the desired data associated with said second open file, scans said buffer storage locations to determine whether said desired data with respect to said second open file is within said buffer, reads the data from said selected sector associated with said second open file into a selected buffer storage location that is not allocated to an open file, and allocates said selected buffer storage location into which said data was just read with said second open file.

16. The system as set forth in claim 15, wherein the said counter associated with a buffer storage location allocated to an open file is incremented when said associated buffer storage location is allocated, said counter being decremented when its said associated buffer storage location is deallocated from said open file.

17. The system as set forth in claim 16, further comprising:

a display connected to said processor;

a keypad connected to said processor; and

a housing for housing said processor, said counters, said buffer, said mass data storage unit, said display, and said keypad.

18. The system as set forth in claim 17, wherein said system is incorporated in a portable electronic device.

19. The system as set forth in claim 18, wherein said portable electronic device is a navigation aid.