The present invention relates to a data processing system and method for concurrently manipulating data objects.

A multi-threaded computing environments allows data structures, and hence data objects stored therein, to be concurrently shared among a plurality of users or threads. For example, a data base or other data structure, comprising a plurality of independently accessible data objects, may be concurrently accessed and manipulated by a plurality of users or threads. Each user or thread has the capability of deleting or editing the data stored in the data structure independently of any of the other users or threads. Accordingly, a situation may arise in which one thread is currently manipulating a data object while a further thread instigates deletion of the data object. Conventionally such conflicts have been avoided using locks or semaphores as are well known within the art; using such locks prevents all other access to or manipulation of the data objects stored in the data structure. US 5,319,778 discloses a set of machine level instructions that perform primitive operations on singly or doubly linked lists. The instructions allow linked lists to be manipulated in such a way as to allow multiple processes in a parallel computing environment to access shared lists without the need for additional synchronisation. For example, assuming the data structure to be a tree and one thread is traversing the tree from the root node to a leaf node at which the data object intended to be accessed by that thread resides. If a further thread manipulates a node on the route taken by the first' thread, the data object at that node will be locked and the traversing thread will not be able to access the pointers of the data object needed to continue the traversal. If locks were not used, the following may result from the above situation if the second thread deleted the data object currently being accessed by the traversing thread. The pointers of its parent data object would be altered to point to its child data and the pointers of the data object currently being accessed would be set to NULL values. Accordingly, the traversing thread is unable to continue the traversal and is isolated from the rest of the tree.

Accordingly, the present invention provides a method for processing a sharable data structure having a plurality of linked concurrently accessible data objects, said method comprising, for a selected data object currently being accessed by a plurality of processes and in response to one process of said plurality instigating deletion of said selected data object, the steps of maintaining links from said selected data object to at least one other data object of data structure to provide an exit route from said selected data object for said plurality of processes; determining that all of said plurality of processes currently

accessing said selected data object have now ceased to access said selected data object, then deleting said selected data object.

Each operator interacts with said data structure and can represent a thread, a process or any data object, such as a smart-pointer.

Maintaining current links or establishing new links from the data object for which deletion has been instigated provides an access path from that data object to neighbouring data objects and advantageously obviates the possibility of isolation of any other process currently interacting with that data object.

Embodiments of the present invention will now be described, by way of example only, with reference to the accompanying drawings in which:

figure 1 is a high level block diagram of a data processing system utilised to realise an embodiment;

figure 2a illustrates the operation of an embodiment in terms of a doubly linked data structure,

figure 2b illustrates a general graph-based data structure,

figure 3 illustrates the data structure after a deletion has been instigated by a pointer P ₃ ,

figure 4 illustrates the state of the data structure after all interest in the data object D0 ₃ has terminated,

figure 5 shows a further embodiment in which each data object of the data structure also comprises at least two of further pointers,

figure 6 illustrates the state of the data structure after instigation of deletion of data object Dθ ₂ by pointer P ₃ ,

figure 7 illustrates the re-assignment of pointer values,

figure 8 illustrates the data structure after data object Dθ ₂ has been removed

figure 9 illustrates the insertion or addition of a data object DO by pointer P _x between data objects D0 ₂ and Dθ ₃ , and

figure 10 illustrates insertion of a data object into a data structure.

Referring to figure 1, there is depicted a block diagram of a personal computer system 10, such as an IBM PS/2 personal computer. The computer system 10 includes a 32-bit processor and system bus 12. Connected to system bus 12 is a central processing unit (CPU) 14, for example an Intel 486 or equivalent microprocessor. CPU 14 passes data to and receives data from other devices attached to system bus 12 over the system bus. Traffic on the bus is controlled by a bus controller 16. An interrupt controller 18 handles interrupts passed between CPU 14 and the remaining devices.

Read only memory (ROM) 20 is non-volatile memory storing power on test processes and a basic input/output system (BIOS or ROM-BIOS) . The system memory 22 is random access memory into which an operating system, preferably a 32-bit operating system such as IBM OS/2 WARP which supports concurrent processes or multiple concurrent threads, is loaded for execution to support execution of applications. Additional hardware components of computer 10 attached to system bus 12 include a memory controller 24 and a system configuration store 26, provided by random access memory (RAM) .

Auxiliary data storage is provided by peripheral controllers and associated storage devices including, a floppy disk or diskette controller 28 and drive 30, a hard drive controller 32 and hard drive device 34, and a compact disk (CD) read only memory (ROM) controller 36 with CD-ROM drive 38. An SVGA controller 40 includes a RAM buffer 44 in which the current frame for display is stored. In some computers, the buffer 44 may be loaded directly from system memory 22 or from an auxiliary storage controller.

Direct memory access (DMA) controller 46 handles data transfers between auxiliary storage devices or other input/output devices, and system memory 22 without interaction by CPU 14. Keyboard controller 48 provides an interface to a keyboard 50, for user entries, and may be used to provide an interface to a "mouse ¹¹ . Parallel controller 52 is a device controller for an input or output device (e.g. a printer connected to computer 10 by a parallel cable) .

Figure 2a illustrates the operation of the invention in terms of a doubly linked list stored in memory. It will be appreciated that the present invention is applicable to any graph based or linked data structure as shown in figure 2b in which data objects A to G are interlinked. Each data object in figure 2b has at least one adjoining

data object and in some instances up to four adjoining data objects. Referring again to figure 2a, the data objects are such as can be defined using any object-oriented technology such as the IBM/SOM product available from International Business Machines or the commonly available implementations of C++. Generally, each data object D0 ₁ ..D0 ₄ in a graph based data structure has pointers 200..235 to or from at least one or each preceding or parent data object and at least one or each succeeding or child data object. The conventional operation and traversal of such a doubly linked data structure and access to the data objects stored therein is well known within the art and will not be described in great detail. The terms parent and child objects are used in a relative sense and according to the direction of traversal of the data structure and data objects. Hence, data object DO-, is the parent of data object Dθ ₂ and D0 ₂ is the child of data object Dθj for the purposes of a transition from OO _x to D0 ₂ whereas the designations are reversed for the reverse transition from Dθ ₂ to DOj. In a data structure where each data object thereof is connected to a plurality of other data objects, a parent data object of a given data object is that data object which has links to the given data object and a child data object of the given data object is that data object which has links to it from the given data object. In certain circumstances it is possible that a given data object is both a parent and a child data object. Further, a given pair of data objects may be the both parent and child data objects of each other.

Still referring to figure 2a, each data object D0j..D0 ₄ contains a respective function F _U ..F ₁₄ which maintains an indication of whether or not any thread or process is currently interested the data object (such as a count of the number of threads currently accessing the data object or a list of pointers or other data objects not being part of the data structure currently interacting with the data object) and contains a function F ₂₁ ..F*, ₄ capable of removing the data object from the data structure when one of the threads sends a delete message to the data object and all interest therein has terminated or all access thereto has ceased.

In the embodiment described each operator on the data structure e.g. thread, process or other data object accesses the data objects using a pointer object and sends a message to the data object invoking the function F _U ..F ₁₄ which maintains the indication of current interest in the data object to increment that indication by one or to add that pointer to the list. Each thread interacts with the data object in an unfettered manner irrespective of whether or not other threads are currently interested in or interacting with that data object. The interaction between objects in an object-orient environment is well known within the art. For example, the thread may request copies of particular data stored

within the data object or invoke public functions within the data object to effect operations in relation to either that data object or the data stored therein.

It can be seen from the example depicted in figure 2a that there are three threads currently accessing data objects D0 ₂ , D0 ₃ stored within the data structure via respective pointers Pi..?-,. Pointer P _x is interacting with data object D0 ₂ and pointers P ₂ and P ₃ are both interacting with data object Dθ ₃ .

Assume that pointer P ₂ is traversing the data structure and in turn reading the data stored by each data object and that pointer P ₃ , also traversing the data structure, has sent a message to data object Dθ ₃ to invoke the function F ₂₃ which removes that data object D0 ₃ from the data structure. If effect were given to the deletion before pointer P ₂ had moved on the pointers 210 and 230 would conventionally be set so as to contain NULL values and pointer P ₂ would be isolated from and unable to traverse the remainder of the data structure. Hence, the data object D0 ₃ upon invocation of function F ₂₃ checks to determine whether or not there exists any interest in the data object Dθ ₃ and if so amends the pointers thereto belonging to the parent and child data objects so as to point to each other and maintains its pointers to the parent and child data objects rather than setting them to NULL values. Accordingly, further threads or pointers cannot access or interact with the data object D0 ₃ and the pointer P ₂ does not become isolated and can continue to traverse the data structure. As each pointer leaves a data object it invokes the function F _n ..F ₁₄ which maintains the indication of current interest in the data object and that function determines whether or not the data object should be removed from the data structure in light of an earlier instigated deletion or deletions. Therefore, after instigation of the deletion of the data object and the pointer P ₃ moves on, the function to maintain the above indication is invoked to reduce by one the indication of current interest in the data object or to remove the pointer P ₃ from the list. Effect is given to the deletion instigated by pointer P ₃ only after pointer P ₂ leaves the data object Dθ ₃ . Although the above embodiment removes the data object when all interest therein has ceased and a deletion message has been sent thereto, a further embodiment can be realised in which the data object is not removed from the data structure unless at least a predetermined number of deletions have been instigated for a particular data object. The deletions need not necessarily have been instigated by different data objects.

It can be seen that maintaining links from the data object D0 ₃ for which deletion has been instigated to at least one other data object, Dθ ₂ and D0 ₄ in this case, or establishing such links provides means by which

the pointer P ₂ can leave the data object D0 ₃ and continue traversal of the data structure.

An alternative manner of preventing further access to a data object for which deletion has been instigated may be realised by, for example, setting a respective flag in the data objects connected to the data object to be deleted upon instigation of said deletion and ensuring that the operators or threads interrogate the status of the flag before attempting to access that data object. If the flag in one data object indicates that its neighbouring data object should not be accessed then traversal thereto from said one data object should be prevented. Still further each data object may maintain a list of data objects to which it is connected and for which respective deletions have been instigated; such a list would be similarly interrogated before allowing traversal to a connected data object.

A further embodiment can be realised in which only data objects of a particular type or having authorisation can delete data objects from the data structure. In such a scenario the data object instigating the deletion would send a message to the data object to be deleted describing its type or authorisation, in addition to the delete message. The data object to be deleted would then determine whether or not deletion should be allowed and respond accordingly.

The situation after a deletion has been instigated by pointer P ₃ is illustrated in figure 3. The pointer 205 from data object Dθ ₂ links to data 'object Dθ ₄ , the pointer 235 from data object Dθ ₄ links to data object D0 ₂ and the pointers 210,230 emanating from data object Dθ ₃ remain to afford the pointer P ₂ currently interested therein an exit route therefrom. Hence, it can be seen that all other pointers P _ι ,P ₃ traversing the data structure cannot gain access to the data object Dθ ₃ while threads or pointers P ₂ currently accessing the deleted data object Dθ ₃ can continue to do so and to traverse the data structure unimpeded. From the perspective of pointers Pi or threads which were not interacting with the data object at the time the deletion thereof was instigated, the data object appears to have been removed from the data structure whereas from the perspective of the threads or pointers P ₂ , other than the one instigating deletion, which were interacting with the data object Dθ ₃ at that time, the data object still appears to be part of the data structure.

It is only after a deletion has been instigated by a pointer and the current interest data object has terminated that the data object is removed from the data structure. Figure 4 illustrates the state of the data structure after all interest in the data object D0 ₃ has terminated. The data structure comprises data objects DOi, D0 ₂ , D0 ₄ and Dθ ₅ together

with links therebetween. The memory allocated to accommodate the deleted data object D0 ₃ is relinquished to reduce the demands made on system resources. Alternatively, the resources utilised by the recently deleted data object may be cached and used again at a later stage.

Referring to figure 5, there is shown a further embodiment in which each data object DO-...D0 ₄ of the data structure also comprises at least two of further pointers 240..275 initially set to NULL values, for enabling access to and from data objects for which respective deletions have been instigated but which have not yet been removed from the data structure. Each data object also contains an indication of the status of the data object which reflects whether or not a deletion has been instigated for that data object. The indication is represented by both of the conventional pointers emanating therefrom having NULL values. in the case of a singly linked data structure the data objects will each contain only one further pointer. In the case of a more general graph each data object will have a plurality of pairs of conventional and further pointers linking the data objects of the graph; one pair per data object to which a particular data object is connected.

Assume that pointers P ₂ and P ₃ are interacting with data object D0 ₂ . Upon receiving a delete message from, for example, pointer P ₃ , a thread or other data object, the data object Dθ ₂ sets the pointers 200, 230 thereof to equal the values of pointers 205 and 225 respectively. The further pointers 240,270 of the parent DOi and child D0 ₃ data objects of the data object Dθ ₂ to be deleted are also amended to point to the data object to be deleted Dθ ₂ . The pointers 205 and 225 remain to provide exit routes from the data object. After instigation of the deletion of data object Dθ ₂ pointer P ₃ moves on to data object Dθ ₄ . Transitions between data objects are made using the conventional pointers 200..235. Hence, to all pointers interacting with a data object at the time when deletion thereof was instigated, that data object continues to form part of the data structure whereas to other pointers that data object ceases to form part of the data structure. Figure 6 illustrates the state of the data structure after instigation of deletion of data object D0 ₂ by pointer P ₃ ; the latter having then moved on the data object D0 ₃ .

Data objects having further pointers particularly enables effect to be given to deletions instigated in relation to contiguous data objects. Referring again to figure 6, assume that pointer P ₃ has instigated deletion of data object Dθ ₃ . Hence, the data structure comprises two contiguous data objects Dθ ₂ , Dθ ₃ for which respective deletions have been instigated. It can be seen that one data object Dθ ₂ still has a pointer P ₂ thereto and hence an interest therein still exists. As pointer P_ is still interacting with data object D0 ₃ , the latter cannot yet be removed

from the data structure. Firstly, pointers 200, 205 and 235 are set to equal pointers 210 and 230 respectively thereby removing the access paths to data object D0 ₃ , further pointer 245 is set to point to D0 ₃ , further pointer 275 is set to point to D0 ₃ , pointers 210 and 230 are left as they are to preserve the exit paths from the data object D0 ₃ . The above assignments of pointer values are reflected in figure 7. Hence, if either of pointers P ₂ or P ₃ leave their respective data objects D0 ₂ and D0 ₃ they encounter data objects which are part of the data structure from the perspective of all threads or pointers interacting therewith. It can be seen that the pointers P ₂ and P-. can still continue to traverse the list notwithstanding the deletion of their respective data objects by pointer P ₃ and that any other pointers i.e. P ₃ can only access data objects DO _j or D0 ₄ .

Data object Dθ ₃ or data object D0 ₂ will be removed from the data structure when all interest therein ceases. Hence, if pointer p-_ moves on to data object D0 ₄ , data object D0 ₃ will be removed from the data structure as follows.

Figure 8 illustrates the data structure after data object D0 ₂ has been removed. As a deletion for data object Dθ ₃ has been instigated, pointer 240 of data object DO-, is set to point to data object Dθ ₃ . Pointer 270 of data object D0 ₃ is no longer required to point to data object D0 ₂ and is therefore set to a NULL value. All other pointers 200, 210, 230, 235, 250 remain the same.

' Referring to figure 9 there is illustrated the insertion or addition of a data object Dθ ₅ by thread between data objects Dθ ₂ and Dθ ₃ . From the perspective of thread the preceding and succeeding data objects are D0 ₂ and D0 ₃ respectively. Insertion of data objects is accomplished in the conventional manner when the insertion is between contiguous data objects for respective deletions have not been instigated. Accordingly, pointers 500 and 505 of data object Dθ ₅ will be set to point to data objects Dθ ₂ and D0 ₃ respectively. Pointers 205 and 230 will be arranged to point to data object D0 ₅ and pointers 510 and 515 are set to NULL values.

Figure 10 illustrates the insertion of a data object Dθ ₅ between two data objects O0 _{l t} D0 ₄ having other data objects D0 ₂ , Dθ ₃ therebetween for which respective deletions have been instigated. It can be seen that pointer 500 is set to equal pointer 200 thereby ensuring that data object D0 ₅ points to a data object Dθ ₄ for which a deletion has not been instigated. Pointers 200, 225, 230 and 235 are arranged to point to the newly inserted data object Dθ ₅ . Pointer 505 is arranged to point to data object DOi. Further pointer 270 still points to data object Dθ ₂ . Further pointer 245 still points to data object D0 ₃ . One 510 of the further

pointers of data object D0 ₅ is arranged to point to data object D0 ₂ while the other further pointer 515 is set to a NULL value. All other pointers remain as they were immediately prior to the insertion of data object D0 ₅

Table 1 below illustrates pseudo-code suitable for defining a data object or node of a data structure for implementing an embodiment in, for example, C++.

1 class CNode {

2 public

3 inline CNodeO; /'Initialises object variables below to NULL

4 inline void I_EXPORT FreeObject0 ; /* remove data object to be deleted or cached from

DS

5 inline void I_EXPORT DeleteObject0 ; /* delete object from DS

6 inline void AddObject(); /*Add object to DS

7 PCnode pNext; /'pointer to the next data object in DS

8 PCnode pPrev; /'pointer to preceding data object in DS

9 PCnode pDNext; /'pointer to next "dead" data object in DS

10 PCnode pDPrev; /'pointer to preceding "dead" data object in

DS

11 pvoid data; /'pointer to the data stored by the object

12 uslong mRefCount, ListRefCount /* number of threads interacting with node, number of deletions required to be instigated before node removed

};

TABLE 1

It can be seen that the data object has pointers "pPrev" and "pNext" which points to the parent and child data objects. The further pointers "pDPrev" and "pDNext" are used to point contiguous parent or child data objects for which deletion has been instigated but not yet effected. The functions of the data object, CNode, FreeObject, DeleteObject and AddObject, initialise the variables thereof, remove the data object from the data structure and relinquish system resources associated therewith, instigate deletion of the data object from the data structure and add a data object to the data structure respectively. The definition "pvoid data" defines a pointer to the data stored by the data object.

Referring to table 2, there is shown psuedo-code which defines the functionally required by the object CNodeO . It can be seen that CnodeO initialises all of the pointers used by the data objects of the data structure. The variable mRefCount maintains an indication of the number

of pointers or threads which are interested in the data object. The remaining variables or pointers have the function as defined above in relation to table 1.

CNode: :CNode()

{ mRefCount = 0;

ListRefCount= 0; data = NULL pNext = NULL pPrev = NULL pDNext = NULL pDPrev = NULL

TABLE 2

Table 3 illustrates psuedo-code which functionally defines the object FreeObject() in the above object. FreeObject removes the data object, "this", from the data structure and relinquishes the resources used to store that data object.

1 void CNode::FreeObject() {

{

// Remove data object from data structure as must be one for which deletion has been instigated and for which interest therein has ' ceased

2 if (pDPrev) pDPrev->pDNext =■ pDNext

// set previous deleted data object "pDNext" pointer to equal current data objects "pDNext" else

{ if (pPrev) pPrev->pDNext = pDNext

} if (DNext)

{ // if data object has a preceding deleted data object set the latters pDPrev to equal the current data object's PDPrev pDNext->pDPrev = pDPrev; } else { // Set the pDnext of following deleted data object equal to pDPrev of current data object if (pNext) pNext->pDNext = pDPrev;

}

PNext = NULL;

10 pPrev = NULL ;

11 pDNext = NULL ;

12 pDPrev = NULL ;

13 include code appropriate to relinquish system resource used by deleted data object

}

TABLE 3

A test is performed at line 2 to determine whether or not the data object should be removed from the data structure. If "mRefCount" is zero then all interest in the data object, "this", has ceased and the data object can be removed from the data structure. Lines 2 to 9 ensure that the pointers of neighbouring data objects for which respective deletions have been instigated are updated prior to removal of the data object from the data structure.

Table 4 illustrates psuedo-code for defining the functionality of the object DeleteObject() which instigates deletion of a data object, this, from the data structure. Line 2 defines a "current_neighbour" which is used to hold information relating to either the parent or child data object of the data object, "this", which is intended to be deleted. Lines 3 and 4 ensure that the pointers of the parent and child data objects of the data object to be deleted reference one another thereby preventing further access to the data object to be deleted. Lines 5 to 10 that the pointers of child data objects for which deletions have been instigated which point to the current data object to be deleted are amended to point to a tiata object for which a deletion has not been instigated i.e. the parent data object of the data object to be deleted. Lines 11 and 12 update the further pointers of the next child data object for which deletion has not been instigated. Lines 13 to 18 updates the parent data objects, for which deletion have been instigated, of the current data object which is intended to be deleted such that the pointers of the former all point to a child data object, for which deletion has not been instigated, of the data object intended to be deleted. Lines 19 to 20 set the further pointers of the child data object for which deletion has not been instigated to point to the current data object for which deletion is intended.

1 void CNode: :DeleteObject() {

2 pCNode current_neighbour;

// update neighbouring data object for which deletion has not been // instigated of own deletion

3 if (pNext) pNext -> pPrev = pPrev; 4 if (pPrev) pPrev -> pNext = pNext;

5 current__neighbour = pDNext;

6 if (current_neighbour) { // if deleted data object after this object inform that data object "this" is deleted as well

7 current__neighbour -> pDPrev = this;

// Update "pPrev" pointer of other deleted data objects in chain 8 while (current_neighbour)

{

9 current_neighbour->pPrev = pPrev;

10 current_neighbour = current_neighbour->pDNext } }

11 else {

// contiguous data object has not been deleted or last data object in data structure. 12 if (pNext) pNext -> pDPrev = this;

}

13 current_neighbour = this->pDPrev

14 if (current_neighbour) { // parent data object also had deletion instigated

15 current_neighbour->pDNext = this;

// update pPrev pointers of preceding data objects for which deletion has been instigated.

16 while (current_neighbour) {

17 current_neighbour->pNext = pNext;

18 current_neighbour = current_neighbour->pDPrev }

19 else {

// this data object does not have a contiguous deleted data object hence data object following is one for which deletion has not been instigated or the end of the data structure has been reached. 20 if (pNext) pNext->pDPrev = this;

TABLE 4

Table 5 illustrates psuedo-code for defining the functionality of the object AddObject 0 which adds a new data object to a data structure comprising deleted data objects. Pointers, pNewPrev and pNewNext, to the new data object's parent and child data objects are setup at lines 3 and 4. Lines 5 and 6 set the new data object's further pointers to NUL1 values. Line 7 updates the "pPrev" pointer of the child data object, for which deletion has not been instigated, to point to the new data object. Line 9 updates "this" object's further pointer to be the parent's further pointer. Line 10 sets the parent's next pointer to be to "this" object. Line 11 sets the parent's further pointer to be NULL. Lines 9 to 11 are necessary because an insertion may have been effected before data objects for which deletions have been instigated. Lines 13 to 20 deals with the situation where the first data object for which a deletion has not been instigated is preceded only by data objects for which respective deletions have been instigated.

I void CNode: :AddDataObject ( pCNode pNewPrev, pCNode pNewNext) { 2 pCNode current_neighbour;

// establish pointers of new data object; pointing to new parent and child data objects and setting further pointers to NULL values. 3 pNext = pNewNext; 4 pPrev = pNewPrev;

5 pDPrev = NULL:

6 ' pDNext = NULL;

// Update pointers of parent and child data objects for which deletions have not been instigated.

7 if (pNext) pNext->pPrev = this;

8 if (pPrev) {

// insert new data object between a pair of data objects for which deletions have not been instigated but before all data objects for which deletions have been instigated between the pair.

9 pDNext = pPrev -> pDNext;

10 pPrev -> pNext = this:

II pPrev -> pDNext = NULL; }

12 else {

13 if (pNext) {

14 current_neighbour = pNext->pDPrev }

15 if (current_neighbour) { // If only one data object for which deletion has not been instigated and that object is preceded by deleted data objects then locate first deleted data object

16 while (current_neighbour)

{ 17 current_neighbour->pPrev = this;

18 pDNext = current_neighbour;

19 current_neighbour = current_neighbour->ρDPrev; }

20 return; }

// Update pointers of deleted data objects

21 if (current—neighbour) {

22 while(current—neighbour) {

23 current_neighbour->pPrev = pPrev;

24 current_neighbour = current—neighbour->pDNext

}

}

TABLE 5

Although the above embodiments were explained in terms of singly and doubly linked lists, embodiments can be realised using any other graph based or linked data structures. For example, the present invention can be utilised in manipulating data objects stored so as to form a tree or other hierarchical data structure. In such a structure a data object typically has one higher or preceding data object and multiple lower or succeeding data objects. Similarly the data objects can represent any data objects. For example, each data object may represent a record of a data base or a page of memory in a virtual memory management system or packet of data to be transmitted over a communication channel.