System and method for linear object reallocation in place
A system and method for replacing an original linear object with an updated linear object. In a flash memory or other memory device storing groups of data objects, in replacing a linear object with an updated linear object of the same size, the present invention overwrites the original linear object in the same memory space as the original version. As a result, updating the data requires erasing and writing of the block of flash memory cells where the data object is stored. A copy of the original linear object is stored so that the original version of the linear object is available for undoing the update and/or facilitating recovery if the updated linear object becomes corrupted.
1. A computer readable medium having stored thereon a data structure for preserving an original linear object, the data structure comprising:
a plurality of data objects stored in one of a first list associated with a first end of a contiguous range of memory to which the data objects are related or a second list associated with a second end of a contiguous range of memory to which the data objects are related, each of the data objects comprising:
an index field indicating a position of a next data object in a respective list;
a key field uniquely identifying the data object;
a reallocation field storing a non-address value; and
a data storage area;
an updated linear object replacing the original linear object, the updated linear object having the same data length as the original linear object and, after the original linear object is invalidated and a memory space storing the original linear object is erased, being inserted in place of the original linear object in the first list; and
a copy of the original linear object, the copy of the original linear object being added to the second list, the reallocation field of the copy of the original linear object storing the position of the original linear object before the original linear object was replaced by the updated linear object in place of the non-address value before the original linear object was replaced by the updated linear object.
2. The computer readable medium of claim 1 wherein the copy of the original linear object being added to the second list is added to an end of the second list.
3. The computer readable medium of claim 1 wherein free space is reserved in a data volume containing the data structure sufficient to accommodate a largest linear object stored in the data volume and one or two additional memory blocks.
4. The computer readable medium of claim 3 wherein one of the one or two additional memory blocks is used to store partial copy data stored in a partially filled memory block storing part of another adjacent data object.
5. The computer readable medium of claim 1 wherein an index field of a previously preceding data object in the first list indicating a position of the original linear object in the first list indicates a position of the updated linear object in the first list.
6. The computer readable medium of claim 1 wherein an updated linear object index field indicating a subsequent data object position in the first list following the updated linear object is the same as an original object index field indicating the position of a subsequent data object in the first list.
7. The computer readable medium of claim 1 wherein a previously last data object index field in the second list indicates a position of the copy of the original linear object.
8. The computer readable medium of claim 1 further comprising an undo function allowing a command to replace the updated linear object by writing the copy of the original linear object over the updated linear object at the position of the original linear object.
9. The computer readable medium of claim 8 wherein the copy of the original linear object reallocation field is changed to the non-address value when the copy of the original linear object is written over the updated linear object.
10. The computer readable medium of claim 1 further comprising a recovery function allowing a corrupted updated linear object to be replaced by the copy of the original linear object at the position of the original linear object.
11. The computer readable medium of claim 1 wherein data space can be freed by erasing memory blocks containing the copy of the original linear object.
12. The computer readable medium of claim 11 wherein the data space is freed by moving data objects following the copy of the original data object in the second list to the end of the first list until no data objects follow the copy of the original data object in the second list and erasing the memory space containing the original linear object is stored.
13. A computer readable medium having stored thereon a data structure for storing a plurality of data objects and preserving an original linear object, the data structure comprising:
a first list associated with a first end of a contiguous range of memory to which the data objects are related;
a second list associated with a second end of the contiguous range of memory to which the data objects are related;
a copy of the original linear object; and
an updated linear object replacing the original linear object, the updated linear object having the same data length as the original linear object and, after the original linear object is invalidated and a memory space containing the original linear object is erased, being inserted in place of the original linear object in the first list, the copy of the original linear object being added to the second list.
14. The computer readable medium of claim 13 wherein the copy of the original linear object being added to the second list is added to an end of the second list.
15. The computer readable medium of claim 13 wherein free space is reserved in a data volume containing the data structure sufficient to accommodate a largest data object stored in the data volume and one or two additional memory blocks.
16. The computer readable medium of claim 15 wherein one of the one or two additional memory blocks is used to store partial copy data stored in a partially filled memory block storing part of another adjacent data object.
17. The computer readable medium of claim 13 wherein the plurality of data objects each include an index field, each of the index fields in data objects stored in the first list indicating a position of a next data object in the first list and each of the index fields in data objects stored in the second list indicating a position of a next data object in the second list.
18. The computer readable medium of claim 17 wherein an index field of a previously preceding data object in the first list indicating a position of the original linear object in the first list indicates a position of the updated linear object in the first list.
19. The computer readable medium of claim 17 wherein an updated linear object index field indicating a subsequent data object position in the first list following the updated linear object is the same as an original object index field indicating the position of a subsequent data object in the first list.
20. The computer readable medium of claim 17 wherein a previously last data object index field in the second list indicates a position of the copy of the original linear object.
21. The computer readable medium of claim 13 wherein the plurality of data objects include a reallocation field which stores a non-address value except for a copy of the original linear object reallocation field which stores the position of the original linear object before the original linear object was replaced by the updated linear object.
22. The computer readable medium of claim 13 further comprising an undo function allowing a command to replace the updated linear object with the original linear object by writing the copy of the original linear object over the updated linear object at the position of the original linear object.
23. The computer readable medium of claim 22 wherein the copy of the original linear object reallocation field is changed to the non-address value when the copy of the original linear object is written over the updated linear object.
24. The computer readable medium of claim 22 wherein the updated linear object is written over the copy of the original linear object and an updated linear object reallocation field is changed to the position of the original linear object.
25. The computer readable medium of claim 13 wherein data space can be freed by erasing a memory space containing the copy of the original linear object.
26. The computer readable medium of claim 25 wherein the data space is freed by moving data objects following the copy of the original data block in the second list to the end of the first list until no data objects follow the copy of the original data block in the second list and erasing the memory space containing the copy of the original linear object.
27. A flash memory device having stored thereon a data structure for storing a plurality of data objects and preserving an original linear object, the data structure comprising:
a plurality of data objects stored in one of a first list associated with a first end of a contiguous range of memory to which the data objects are related or a second list associated with a second end of a contiguous range of memory to which the data objects are related, each of the data objects comprising:
an index field indicating a position of a next data object in a respective list;
a key field uniquely identifying the data object;
a reallocation field storing a non-address value; and
a data storage area;
an updated linear object replacing the original linear object, the updated linear object having the same data length as the original linear object and, after the original linear object is invalidated and a memory space comprising at least one flash memory block storing the original linear object is erased, being inserted in place of the original linear object in the first list; and
a copy of the original linear object, the copy of the original linear object being added to the second list, the reallocation field of the copy of the original linear object storing the position of the original linear object before the original linear object was replaced by the updated linear object in place of the non-address value before the original linear object was replaced by the updated linear object.
28. The flash memory of claim 27 wherein the copy of the original linear object being added to the second list is added to an end of the second list.
29. The flash memory of claim 27 wherein free space is reserved in a data volume containing the data structure sufficient to accommodate a largest data object stored in the data volume and one or two additional memory blocks.
30. The flash memory of claim 29 wherein one of the one or two additional memory blocks is used to store partial copy data stored in a partially filled memory block storing part of another adjacent data object.
31. The flash memory of claim 27 wherein an index field of a previously preceding data object in the first list indicating a position of the original linear object in the first list indicates a position of the updated linear object in the first list.
32. The flash memory of claim 27 wherein an updated linear object index field indicating a subsequent data object position in the first list following the updated linear object is the same as an original object index field indicating the position of a subsequent data object in the first list.
33. The flash memory of claim 27 wherein a previously last data object index field in the second list indicates a position of the copy of the original linear object.
34. The flash memory of claim 27 further comprising an undo function allowing a command to replace the updated linear object by writing the copy of the original linear object over the updated linear object at the position of the original linear object.
35. The flash memory of claim 34 wherein the copy of the original linear object reallocation field is changed to the non-address value when the copy of the original linear object is written over the updated linear object.
36. The flash memory of claim 27 further comprising a recovery function allowing a corrupted updated linear object to be replaced by the copy of the original linear object at the position of the original linear object.
37. The flash memory of claim 27 wherein data space can be freed by erasing a memory space comprising at least one flash memory block containing the copy of the original linear object.
38. The flash memory of claim 37 wherein the data space is freed by moving data objects following the copy of the original data block in the second list to the end of the first list until no data objects follow the copy of the original data block in the second list and erasing the memory space comprising at least one flash memory block containing the copy of the original linear object.
39. A flash memory device having stored thereon a data structure for storing a plurality of data objects and preserving an original linear object, the data structure comprising:
a first list associated with a first end of a contiguous range of memory to which the data objects are related;
a second list associated with a second end of the contiguous range of memory to which the data objects are related;
a copy of the original linear object; and
an updated linear object replacing the original linear object, the updated linear object having the same data length as the original linear object and, after the original linear object is invalidated and a memory space comprising at least one flash memory block containing the original linear object is erased, being inserted in place of the original linear object in the first list, the copy of the original linear object being added to the second list.
40. The flash memory of claim 39 wherein the copy of the original linear object being added to the second list is added to an end of the second list.
41. The flash memory of claim 39 wherein free space is reserved in a data volume containing the data structure sufficient to accommodate a largest data object stored in the data volume and one or two additional memory blocks.
42. The flash memory of claim 41 wherein one of the one or two additional memory blocks is used to store partial copy data stored in a partially filled memory block storing part of another adjacent data object.
43. The flash memory of claim 39 wherein the plurality of data objects each include an index field, each of the index fields in data objects stored in the first list indicating a position of a next data object in the first list and each of the index fields in data objects stored in the second list indicating a position of a next data object in the second list.
44. The flash memory of claim 43 wherein an index field of a previously preceding data object in the first list indicating a position of the original linear object in the first list indicates a position of the updated linear object in the first list.
45. The flash memory of claim 43 wherein an updated linear object index field indicating a subsequent data object position in the first list following the updated linear object is the same as an original object index field indicating the position of a subsequent data object in the first list.
46. The flash memory of claim 43 wherein a previously last data object index field in the second list indicates a position of the copy of the original linear object.
47. The flash memory of claim 39 wherein the plurality of data objects include a reallocation field which stores a non-address value except for a copy of the original linear object reallocation field which stores the position of the original linear object before the original linear object was replaced by the updated linear object.
48. The flash memory of claim 39 further comprising an undo function allowing a command to replace the updated linear object with the original linear object by writing the copy of the original linear object over the updated linear object at the position of the original linear object.
49. The flash memory of claim 48 wherein the copy of the original linear object reallocation field is changed to the non-address value when the copy of the original linear object is written over the updated linear object.
50. The flash memory of claim 39 further comprising a recovery function allowing a corrupted updated linear object to be replaced by the copy of the original linear object at the position of the original linear object.
51. The flash memory of claim 39 wherein data space can be freed by erasing a memory space comprising at least one flash memory block containing the copy of the original linear object.
52. The flash memory of claim 51 wherein the data space is freed by moving data objects following the copy of the original data block in the second list to the end of the first list until no data objects follow the copy of the original data block in the second list and erasing the memory space comprising at least one flash memory block containing the copy of the original linear object.
53. A method of storing a plurality of data objects while preserving an original linear object, the method comprising:
maintaining a plurality of data objects stored in one of a first list associated with a first end of a contiguous range of memory and a second list associated with a second end of a contiguous range of memory, each of the data objects comprising:
an index field indicating a position of a next data object in a respective list;
a key field uniquely identifying the data object;
a reallocation field storing a non-address value; and
a data storage area;
replacing the original linear object with an updated linear object, the updated linear object having the same data length as the original linear object and, after the original linear object is invalidated and a memory space containing the original linear object is erased, being inserted in place of the original linear object in the first list;
making a copy of the original linear object, the reallocation field of the copy of the original linear object storing the position of the original linear object before the original linear object was replaced by the updated linear object in place of the non-address value before the original linear object was replaced by the updated linear object; and
inserting the copy of the original linear object in the second list.
54. The method of claim 53 further comprising adding the copy of the original linear object to an end of the second list.
55. The method of claim 53 further comprising reserving free space in a data volume containing the data structure sufficient to accommodate a largest data object stored in the data volume and one or two additional memory blocks.
56. The method of claim 55 wherein one of the one or two additional memory blocks is used to store partial copy data stored in a partially filled memory block storing part of another adjacent data object.
57. The method of claim 53 wherein an index field of a previously preceding data object in the first list indicating a position of the original linear object in the first list indicates a position of the updated linear object in the first list because the updated linear object replaces the original linear object in the first list.
58. The method of claim 57 wherein an updated linear object index field indicating a subsequent data object position in the first list following the updated linear object is the same as an original object index field indicating the position of a subsequent data object in the first list because the updated linear object has a same data length as the original linear object so that the subsequent data object in the first list remains at the subsequent data object position.
59. The method of claim 57 wherein a previously last data object index field in the second list indicates a position of the copy of the original data object.
60. The method of claim 53 further comprising an undo function allowing a command to replace the updated linear object with the original linear object by writing the copy of the original linear object over the updated linear object at the position of the original linear object.
61. The method of claim 60 further comprising changing the copy of the original linear object reallocation field to the non-address value when the copy of the original linear object is written over the updated linear object.
62. The method of claim 53 further comprising a recovery function allowing a corrupted updated linear object to be replaced by the copy of the original linear object at the position of the original linear object.
63. The method of claim 53 further comprising freeing data space by erasing a memory space containing the copy of the original linear object.
64. The method of claim 63 further comprising freeing the data space by moving data objects following the copy of the original data block in the second list to the end of the first list until no data objects follow the copy of the original data block in the second list and erasing the memory space containing the copy of the original linear object.
65. A method of storing a plurality of data objects while preserving an original linear object, the method comprising:
maintaining a first list of data objects associated with a first end of the contiguous range of memory to which the data objects are related;
maintaining a second list of data objects associated with a second end of the contiguous range of memory to which the data objects are related;
making a copy of the original linear object;
replacing the original linear object in the first list with an updated linear object after the original linear object is invalidated and a memory space containing the original linear object is erased, the updated linear object having the same data length as the original linear object; and
inserting the copy of the original linear object in the second list.
66. The method of claim 65 further comprising adding the copy of the original linear object to an end of the second list.
67. The method of claim 65 further comprising reserving free space in a data volume containing the data structure sufficient to accommodate a largest data object stored in the data volume and one or two additional memory blocks.
68. The method of claim 67 wherein one of the one or two additional memory blocks is used to store partial copy data stored in a partially filled memory block storing part of another data object.
69. The method of claim 65 further comprising writing in each of the plurality of data objects an index field, each of the index fields in data objects stored in the first list indicating a position of a next data object in the first list and each of the index fields in data objects stored in the second list indicating a position of a next data object in the second list.
70. The method of claim 69 wherein an index field of a previously preceding data object in the first list indicating a position of the original linear object in the first list indicates a position of the updated linear object in the first list because the updated linear object replaces the original linear object in the first list.
71. The method of claim 69 wherein an updated linear object index field indicating a subsequent data object position in the first list following the updated linear object is the same as an original object index field indicating the position of a subsequent data object in the first list because the updated linear object has a same data length as the original linear object so that the subsequent data object in the first list remains at the subsequent data object position.
72. The method of claim 69 wherein a previously last data object index field in the second list indicates a position of the copy of the original linear object.
73. The method of claim 69 wherein the plurality of data objects comprise a reallocation field which stores a non-address value except for a copy of the original linear object reallocation field which stores the position of the original linear object before the original linear object was replaced by the updated linear object.
74. The method of claim 69 further comprising an undo function allowing a command to replace the updated linear object with the original linear object by writing the copy of the original linear object over the updated linear object at the position of the original linear object.
75. The method of claim 74 further comprising changing the copy of the original linear object reallocation field to the non-address value when the copy of the original linear object is written over the updated linear object.
76. The method of claim 65 further comprising a recovery function allowing a corrupted updated linear object to be replaced by the copy of the original linear object at the position of the original linear object.
77. The method of claim 65 wherein data space can be freed by erasing a memory space containing the copy of the original linear object.
78. The method of claim 77 wherein the data space is freed by moving data objects following the copy of the original data block in the second list to the end of the first list until no data objects follow the copy of the original data block in the second list and erasing the memory space containing the copy of the original linear object.