Method and apparatus for freeing memory from an extensible markup language document object model tree active in an application cache

• US 20020165870A1
• Filed: 03/01/2001
• Published: 11/07/2002
• Est. Priority Date: 03/01/2001
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Visvanathan, Jayashri, Chakraborty, Krishnendu
• Granted Patent: US 6,542,911 B2
• Time in Patent Office: Days
• US Class Current: 707/206
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
• CPC Class Codes: G06F 12/127 using additional replacement algorithms
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

The present invention relates to a garbage collector that uses an LRU algorithm to free memory from an XML DOM tree active in an application cache. According to one or more embodiments of the present invention, a threshold for the amount of memory permitted to reside in an application cache is set. Then, a garbage collector removes entries from the cache until it falls below the threshold. In one or more embodiments, a node table is used. When nodes are added to the XML DOM tree in the application cache the node table is updated. When the threshold for the amount of memory permitted to reside in the application cache is exceeded, the garbage collector applies an LRU algorithm uses the node table to determine which nodes to remove from the application cache. In one embodiment, the LRU algorithm scans the node table to determine the least recently used node in the table by examining time stamp entries in the table. Then, the algorithm removes that node and repeats the process until the XML DOM tree uses less memory in the cache than the threshold.

Claims

1. A method for freeing memory from an XML DOM tree in a cache, said method comprising:

storing one or more identifiers in a node table which correspond to each of one or more nodes of said XML DOM tree;

scanning said node table to locate a least recently used node using said identifiers; and

removing said identifiers and said least recently used node, if said XML DOM tree occupies more memory then a threshold.

2. The method of claim 1 wherein one of said identifiers comprises a time stamp entry associated with each of said nodes.

3. The method of claim 2 wherein said scanning further comprises:

examining said time stamp entry to find said least recently used node.

4. The method of claim 3 wherein said scanning further comprises:

determining whether said least recently used node has a child node;

modifying said time stamp associated with said least recently used node.

5. The method of claim 4 wherein said modifying further comprises:

changing said time stamp to a value of a most recently used child plus a millisecond.

6. The method of claim 4 wherein said scanning further comprises:

determining whether a node is opened in multiple sessions by an identical user;

selecting a most recently used copy of said node;

placing one or more second identifiers for said node in an intermediate data structure;

choosing a least recently used node in said data structure using said second identifiers;

removing said second identifiers from said node table.

7. A computer program product comprising:

a computer usable medium having computer readable program code embodied therein configured to free memory from an XML DOM tree in a cache, said computer program product comprising;

computer readable code configured to cause a computer to store one or more identifiers for each of one or more nodes in said XML DOM tree in a node table;

computer readable code configured to cause a computer to scan said identifiers to locate a least recently used node; and

computer readable code configured to cause a computer to remove said identifiers and said least recently used node, if said XML DOM tree occupies more memory then a threshold.

8. The computer program product of claim 7 wherein one of said identifiers comprises a time stamp entry associated with each of said nodes.

9. The computer program product of claim 8 wherein said computer readable code configured to cause a computer to scan further comprises:

computer readable code configured to cause a computer to examine said time stamp entry to find said least recently used node.

10. The computer program product of claim 9 wherein said computer readable code configured to cause a computer to scan further comprises:

computer readable code configured to cause a computer to determine whether said least recently used node has a child node;

computer readable code configured to cause a computer to modify said time stamp associated with said least recently used node.

11. The computer program product of claim 10 wherein said computer readable code configured to cause a computer to modify further comprises:

computer readable code configured to cause a computer to change said time stamp to a value of a most recently used child plus a millisecond.

12. The computer program product of claim 10 wherein said computer readable code configured to cause a computer to scan further comprises:

computer readable code configured to cause a computer to determine whether a node is opened in multiple sessions by an identical user;

computer readable code configured to cause a computer to select a most recently used copy of said node;

computer readable code configured to cause a computer to place one or more second identifiers for said node in an intermediate data structure;

computer readable code configured to cause a computer to choose a least recently used node in said data structure using said second identifiers;

computer readable code configured to cause a computer to remove said second identifiers from said node table.

14. The garbage collector of claim 13 wherein one of said identifiers is a time stamp entry associated with each of said nodes.

15. The garbage collector of claim 14 wherein said scanner further comprises:

an examiner for looking at said time stamp entry to find said least recently used node.

16. The garbage collector of claim 15 wherein said step of scanning further comprises:

a determiner for determining whether said least recently used node has a child node;

a modifier for modifying said time stamp associated with said least recently used node.

17. The garbage collector of claim 16 wherein said modifier further comprises:

a second time stamp configured to be changed to a value of said time stamp for a most recently used child plus a millisecond.

18. The garbage collector of claim 16 wherein said step of scanning further comprises:

a second determiner for determining whether a node is opened in multiple sessions by an identical user;

a selector for obtaining a most recently used copy of said node;

an intermediate data structure to place one or more second identifiers relating to said node;

a chooser for choosing a least recently used node in said data structure using said second identifiers; and

a remover to remove every instance of said second identifiers in said node table.

13. A garbage collector for freeing memory from an XML DOM tree in a cache, said garbage collector comprising:

a threshold for a maximum amount of memory that may reside in said cache;

a node table configured to store one or more identifiers which correspond to each of one or more nodes of said XML DOM tree;

a scanner for examining said identifiers to locate a least recently used node; and

a garbage collector for removing said identifiers and said least recently used node, if said XML DOM tree occupies more memory then said threshold.