System and method for using a hierarchical data structure to control and identify devices and represent connections between the devices

• US 5,903,894 A
• Filed: 03/03/1997
• Issued: 05/11/1999
• Est. Priority Date: 03/03/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Reneris, Kenneth S.
• Primary Examiner(s): Kulik, Paul V.
• Assistant Examiner(s): Wallace, Jr., Michael J.
• Application Number:
  US08/810,019
• Time in Patent Office: 799 Days
• Field of Search: 707/103, 707/100, 707/102, 395/828, 395/284, 395/200.54, 395/200.56
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

A hierarchical data structure is created in dynamic memory that is dynamically expanded or modified during run-time operations of the computer system. Information about the devices is loaded from a definition block into the hierarchical data structure. The information is a byte stream of data that is translated and stored as hierarchical information, such as device objects, data objects, and control method objects. These objects are hierarchically nested within the hierarchical data structure. A device object identifies a corresponding device in the computer system. The hierarchy formed between device objects represents the hierarchical I/O connections within the computer system. A data object identifies configuration and hardware dependency information associated with a corresponding device. A control method object is an executable reference for controlling a corresponding device. The control method object is a sequence of pseudocode instructions interpreted by the operating system providing an abstract, extensible, and portable mechanism for precise control of a device without calling routines from the BIOS.

The hierarchical data structure is preferably used by the operating system as a communication tool and reference to identify devices, to identify configuration and power management information about devices, to provide an executable control mechanism that is abstract and extensible to control devices, and to extensibly add functionality to a device.

Claims

1. A computer-implemented process for creating and using a hierarchical data structure to identify and control a plurality of devices connected to the computer including a first device physically connected to the computer and a second device physically connected to the first device, comprising the steps of:

storing a first device object within the hierarchical data structure, the first device object identifying the first device; and

storing a second device object positioned below the first device object within the hierarchical data structure, the second device object identifying the second device;

the relative positions of first and second device objects within the hierarchical data structure representing the physical connection between the first and second devices; and

referring to the hierarchical data structure when controlling the first and second devices.

2. The computer-implemented process of claim 1, further comprising the step of storing a first data object positioned below the first device object within the hierarchical data structure, the first data object containing information associated with the first device, the relative positions of the first device object and the first data object within the hierarchical data structure connoting an association between the first device and the first data object.

3. The computer-implemented process of claim 2 wherein the step of referring to the hierarchical data structure when controlling the first and second devices comprises the steps of:

ascertaining the association between the first device and the first data object by identifying the relative positions of first device object and the first data object within the hierarchical data structure;

retrieving the information associated with the first device from the first data object; and

using the information retrieved from the first data object to control the first device.

4. The computer-implemented process of claim 3, wherein:

the information contained in the first data object includes information selected from the group consisting essentially of configuration information about the first device, dependency information for the first device, power states for the first device, power resources associated with the first device in each of the power states, and an operational region associated with the first device.

5. The computer-implemented process of claim 3, wherein the information contained in the first data object includes executable pseudocode instructions defining a methodology for accessing controllable elements associated with the first device.

6. The computer-implemented process of claim 1, further comprising the step of storing a first control method object positioned below the first device object within the hierarchical data structure, the first control method object containing instructions for performing system-level hardware tasks associated with the first device, the relative positions of first device object and the first control method object within the hierarchical data structure connoting an association between the first device and the first control method object.

7. The computer-implemented process of claim 6, wherein the step of referring to the hierarchical data structure when controlling the first and second devices comprises the steps of:

ascertaining the association between the first device and the first control method object by identifying the relative positions of first device object and the first control method object within the hierarchical data structure;

retrieving the instructions for performing the system-level hardware tasks associated with the first device from the first control method object; and

using the information retrieved from the first control method object to perform one or more of the system-level hardware tasks associated with the first device.

8. The computer-implemented process of claim 7, wherein the information contained in the first control method object includes executable pseudocode instructions for performing the system-level hardware tasks associated with the first device.

9. The computer-implemented process of claim 1, further comprising the steps of:

reading a first byte stream of data from a definition block defining the first device object and the position of the first device object within the hierarchical data structure; and

reading a second byte stream of data from the definition block defining the second device object and the position of the second device object within the hierarchical data structure.

10. The computer-implemented process of claim 9, further comprising the steps of:

reading a third byte stream of data from the definition block defining a first data object and a position for the first data object below the first device object within the hierarchical data structure; and

storing the first data object below the first device object within the hierarchical data structure as defined by the third bye stream, the first data object containing information associated with the first device, the relative positions of first device object and the first data object within the hierarchical data structure connoting an association between the first device and the first control method object.

11. The computer-implemented process of claim 10, further comprising the steps of:

reading a fourth byte stream of data from the definition block defining a first control method object and a position for the first control method object below the first device object within the hierarchical data structure; and

storing the first control method object below the first device object within the hierarchical data structure as defined by the fourth byte stream, the first control method object containing instructions for performing system-level hardware tasks associated with the first device, the relative positions of first device object and the first control method object within the hierarchical data structure connoting an association between the first device and the first control method object.

12. The computer-implemented process of claim 2, further comprising the step of storing a second data object positioned below the second device object within the hierarchical data structure, the second data object containing information associated with the second device, the relative positions of the second device object and the second data object within the hierarchical data structure connoting an association between the second device and the second data object.

13. The computer-implemented process of claim 12, further comprising the steps of:

ascertaining the association between the second device and the second data object by identifying the relative positions of the second device object and the second data object within the hierarchical data structure;

retrieving the information associated with the second device from the second data object; and

using the information retrieved from the second data object to control the second device.

14. The computer-implemented process of claim 6, further comprising the step of storing a second control method object positioned below the second device object within the hierarchical data structure, the second control method object containing instructions for performing system-level hardware tasks associated with the second device, the relative positions of the second device object and the second control method object within the hierarchical data structure connoting an association between the second device and the second control method object.

15. The computer-implemented process of claim 14, further comprising the steps of:

ascertaining the association between the second device and the second control method object by identifying the relative positions of the second device object and the second control method object within the hierarchical data structure;

retrieving the instructions for performing the system-level hardware tasks associated with the second device from the second control method object; and

using the information retrieved from the second control method object to perform one or more of the system-level hardware tasks associated with the second device.

16. The computer-implemented process of claim 1, wherein the step of storing the second device object comprises the steps of:

sensing whether the second device is connected to the first device while the computer system is running; and

if the second device is connected to the first device, storing the second device object below the first device object within the hierarchical data structure.

17. The computer-implemented process of claim 1 further comprising the steps of:

sensing that the second device has been removed from connection with the computer; and

in response to sensing that the second device has been removed from connection with the computer;

removing the second device object from the hierarchical data structure; and

removing an affected object from the hierarchical data structure, the affected object being defined as an object positioned within the hierarchy below the second device to connote an association between the second device object and the affected object.

18. The computer-implemented process of claim 1, further comprising the steps of:

sensing that the second device has been removed from connection with the computer system; and

in response to sensing that the second device has been removed from connection with the computer;

setting a first status attribute associated with the second device object, and

setting a second status attribute associated with an affected object, the affected object defined as an object positioned within the hierarchy below the second device to connote an association between the second device object and the affected object.

19. A computer system for dynamically expanding a hierarchical data structure, comprising:

a processor;

a plurality of controllable devices functionally connected to the processor, the plurality of controllable devices comprising;

a first device physically connected to the processor, and

a second device physically connected to the first device;

a memory storage device connected to the processor and storing the hierarchical data structure including a first device object identifying the first device and a second device object positioned below the first device object, the second device object identifying the second device and the relative positions of first and second device objects within the hierarchical data structure representing the physical connection between the first and second devices; and

the processor being operative to;

interrogate the first device in response to a hardware event affecting the first device,

sense the second device is connected to the first device,

search the hierarchical data structure for the second device object,

obtain hierarchical information about the second device if the processor fails to locate the one of the hierarchically related objects that identifies the underlying device, and

store the hierarchical information about the second device at an insert location within the hierarchical data structure.

20. The computer system of claim 19, wherein the insert location within the hierarchical data structure is referenced relative to one of the hierarchically related objects existing within the hierarchical data structure.

21. The computer system of claim 19, wherein the insert location within the hierarchical data structure is referenced absolutely from a root level within the hierarchical data structure.

22. The computer system of claim 19, wherein the hierarchical information about the underlying device comprises one or more additional hierarchically related objects associated with the second device.

23. A computer system for dynamically modifying a hierarchical data structure having a plurality of hierarchically related objects that identify a plurality of controllable devices within the computer system, comprising:

a processor;

the plurality of controllable devices connected to the processor;

a memory storage device connected to the processor for storing the hierarchical data structure; and

the processor being operative to;

sense a request to remove one of the controllable devices from the computer system,

determine which of the controllable devices in the computer system are affected if the requested device is removed,

set a first status attribute of any of the hierarchically related objects within the hierarchical data structure associated with the requested device, the first status attribute indicating that the requested device is not present within the computer system; and

set a second status attribute of any of the hierarchically related objects within the hierarchical data structure associated with the affected devices, the second status attribute indicating that the affected devices are not present within the computer system.

24. The method of claim 23, wherein the processor is further operative to:

search dependency information corresponding to each of the devices identified within the hierarchical data structure; and

identify which of the controllable devices depend upon the requested device, the identified devices being the affected devices.

25. The method of claim 24, wherein the affected devices are represented by corresponding hierarchically related objects within the hierarchical data structure below the one of the hierarchically related objects associated with the requested device.

26. A computer-readable medium on which is stored a computer program for controlling a device within a computer system using a hierarchical data structure, the computer program comprising instructions, which when executed by a computer, perform the steps of:

receiving a request to control the device in a desired manner, the device having a controllable element;

identifying a first control method within the hierarchical data structure corresponding to the request, the first control method being a sequence of one or more pseudocode instructions;

executing the first control method by sequentially calling each of the pseudocode instructions; and

accessing a representation of the controllable element of the device in response to the executing step, wherein accessing the representation of the controllable element provides control of the device.

27. The computer-readable medium of claim 26, wherein the representation of the controllable element is an operational region associated with the device, the operation region providing an abstract representation of the controllable element of the device, wherein accessing the operational region provides indirect control of the device.

28. The computer-readable medium of claim 27, wherein the operational region is further defined as an abstract data object with a predetermined bit width corresponding to one or more bits of the controllable element.

29. The computer-readable medium of claim 26, wherein the pseudocode instructions correspond to object references, each object referenced performs a precise system function on the device.

30. The computer-readable medium of claim 26, wherein the first control method is contained in a control method object in the hierarchical data structure, and the control method object is associated with the device.

31. The computer-readable medium of claim 26, wherein the first control method includes a reference to a second control method contained in the hierarchical data structure.

32. A computer system for using a hierarchical data structure to provide enhanced functionality of a controllable device in the computer system, comprising:

a processor;

the controllable device coupled to the processor;

a memory storage device coupled to the processor for storing the hierarchical data structure; and

the processor being operative to;

identify the controllable device by reading the hierarchical data structure containing a device object, the device object corresponding to the controllable device,

load a device driver into memory from the memory storage device for supporting the device object,

determine if the controllable device supports additional functionality beyond the functionality supported by the device driver, and

create a new device object associated with the device driver if the controllable device supports the additional functionality, wherein the new device object, in response to a call to the device driver, references the hierarchical data structure to provide the additional functionality for the controllable device.

33. The computer system of claim 32, wherein processor is further operative to search within the hierarchical data structure for a data object associated with the controllable device in order to determine if the controllable device supports the additional functionality, the data object containing configuration information about the controllable device.

34. The computer system of claim 32, wherein the processor is further operative to search within the hierarchical data structure for a control method object associated with the controllable device in order to determine if the controllable device supports the additional functionality, the control method object providing an executable reference for controlling the controllable device.

35. A method for using a hierarchical data structure to power down one of a plurality of controllable devices within a computer system having a plurality of power resources, comprising the steps of:

(a) selecting one of the controllable devices to power down;

(b) identifying the power resources that must be on to support the selected device when powered down by reading one of a plurality of hierarchically related objects within the hierarchical data structure below a device object within the hierarchical data structure, the device object being one of the hierarchically related objects and associated with the selected device; and

(c) turning off all of the power resources that are not one of the identified power resources.

36. The method of claim 35, wherein the step (c) comprises the steps of:

(d) executing a first control method to turn off one of the power resources that is not one of the identified power resources, the first control method being referenced by a first control method object within the hierarchical data structure, the first control method object providing an executable mechanism for controlling the one of the power resources; and

(e) repeating step (d) for each of the power resources that is not one of the identified power resources.

37. The method of claim 35 further comprising the step of (f) turning on all of the identified power resources.

38. The method of claim 37, wherein the step (f) comprises the steps of:

(g) executing a second control method to turn on one of the identified power resources, the second control method being referenced by a second control method object within the hierarchical data structure, the second control method object providing an executable mechanism for controlling the one of the identified power resources; and

(h) repeating step (g) for each of the identified power resources.

39. The method of claim 35 further comprising the steps:

(i) selecting a sleeping system power state prior to step (a);

(j) repeating steps (a)-(c) for each of the controllable devices within the computer system;

(k) identifying the power resources that must be off to support the selected system power state by reading the hierarchical data structure; and

(m) turning off all of the selected power resources.

40. The method of claim 39, wherein the step (m) comprises the steps of:

(n) executing a first control method to turn off one of the power resources that is one of the identified power resources, the first control method being referenced by a first control method object within the hierarchical data structure, the first control method object providing an executable mechanism for controlling the one of the power resources; and

(p) repeating step (n) for each of the identified power resources.

41. A method for using a hierarchical data structure to turn on one of a plurality of controllable devices within a computer system having a plurality of power resources, comprising the steps of:

(a) selecting one of the controllable devices to turn on;

(b) identifying the power resources that must be on to support the selected device by reading one of a plurality of hierarchically related objects within the hierarchical data structure below a device object within the hierarchical data structure, the device object being one of the hierarchically related objects and associated with the selected device; and

(c) turning on all of the identified power resources.

42. The method of claim 41, wherein the step (c) comprises the steps of:

(d) executing a control method to turn on one of the identified power resources, the control method being referenced by a control method object within the hierarchical data structure, the control method object providing an executable mechanism for controlling the state of the one of the identified power resources; and

(e) repeating step (d) for each of the identified power resources.

43. The method of claim 41 further comprising the steps of:

prior to steps (a)-(c), prompting the computer system to turn on, restarting a processing unit within the computer system, and jumping to a restart vector in memory; and

in response to step (c), repeating steps (a)-(c) for one of the rest of the devices within the computer system.

44. The method of claim 43, wherein the prompting step is further defined as initiating a hardware wake event.