TECHNICAL FIELD

The present disclosure relates to the field of data processing, and more particularly to a computer-implemented lock-free data structure and related methods and apparatuses.

BACKGROUND

In computer science, a data structure is a format for organizing, managing and storing data. A data structure is designed to organize data to suit a specific purpose so that it can be accessed and worked with in appropriate ways.

At least for some data structures, strong consistency reads and safe memory reclamation may be desirable. In strong consistency reads, all reads see the latest previously written values. Memory-constrained concurrent data structures are an example of a data structure that may require safe memory reclamation.

Strong consistency reads and safe memory reclamation have been traditionally provided e.g. via techniques including reference counting, latches or spinlocks, hazard pointers, and copy-read-update (RCU).

However, reference counting may produce a memory overhead on each data type or node found in a data structure for realizing a counter. E.g. on highly memory- constrained data structures this may not be desirable. Latches or spinlocks may be realized with a single bit of space per data type found in the data structure but they may strongly limit scalability of the data structure due to false sharing between threads. Hazard pointers and RCUs may require a whole infrastructure to be realized, and thus they may be very intricate and therefore difficult to implement.

SUMMARY

This summary is provided to introduce a selection of concepts in a simplified form that are further described below in the detailed description. This summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter. It is an object of the invention to provide an improved lock-free (i.e. non-blocking)data structure with strong consistency reads and safe memory reclamation, as well as related methods and apparatuses. The foregoing and other objects are achieved by the features of the independent claims. Further implementation forms are apparent from the dependent claims, the description and the figures.

According to a first aspect, a computer-implemented lock-free data structure is provided. The computer-implemented lock-free data structure comprises at least one data type. The computer-implemented lock-free data structure further comprises a memory pointer per each of the at least one data type, each memory pointer pointing to one of the at least one data type and each memory pointer comprising a tag indicating whether the pointed data type is a native data type or a dummy data type, wherein the presence of a dummy data type in the computer-implemented lock-free data structure indicates that a native data type first following the dummy data type is protected against writes. The invention allows an improved lock-free data structure with strong consistency reads and safe memory reclamation. Using tagged memory pointers allows using memory that has already been allocated in the data structure, and it allows avoiding introduction of a new data type to the structure. The space required by the dummy data type(s) is not persistent throughout the life of the data structure, and thus the invention can be used where reference counting is not possible. Furthermore, the space required to realize the dummy data type(s) is a function of concurrency (number of thread/clients accessing the data structure) and not a function of the number of data elements/types of the data structure. Thus, the invention allows significant space savings in the data structure. Furthermore, the dummy data type(s) may be placed and removed in a lock-free manner with a low-precision (e.g. 8-byte long) atomic operator compare-and-swap (CAS) currently supported by most processors. Also, (dis)placement of the dummy data type(s) does not affect scalability of the data structure. Furthermore, the dummy data type(s) are simple to program. For example, the dummy data type(s) require little intrusive changes to existing code to integrate them. If the data structure previously used e.g. reference counters, latches, or spinlocks, the space required by them is now free for other purposes - or the overall memory footprint of the data structure can be made smaller.

In an implementation form of the first aspect, the computer-implemented lock-free data structure further comprises at least two dummy data types before a native data type, each of the at least two dummy data types protecting the same native data type against writes and each of the at least two dummy data types inserted by a different party.

In an implementation form of the first aspect, the computer-implemented lock-free data structure further comprises a single dummy data type before a native data type protecting the native data type against writes, the single dummy data type comprising a counter value indicating the number of different parties accessing the native data type.

In an implementation form of the first aspect, at least one native data type comprises a key and each dummy data type protecting it against writes comprises a copy of the key or a pointer to the key.

In an implementation form of the first aspect, each party comprises a thread or a client.

In an implementation form of the first aspect, the computer-implemented lock-free data structure comprises one of a linked list and a binary search tree.

According to a second aspect, a method of performing a search operation on a computer-implemented lock-free data structure comprising at least one data type, and a memory pointer per each of the at least one data type, each memory pointer pointing to one of the at least one data type and each memory pointer comprising a tag indicating whether the pointed data type is a native data type or a dummy data type, wherein the presence of a dummy data type in the computer-implemented lock-free data structure indicates that a native data type first following said dummy data type is protected against writes is provided. The method comprises: starting, by a processor, a search for an object in the computer-implemented lock-free data structure. In response to finding the object with no dummy data type immediately preceding it, inserting, by the processor, a predetermined first positive number of linked dummy data types immediately before the found data type; or in response to finding the object with at least one dummy data type immediately preceding it, inserting, by the processor, the first predetermined positive number of linked dummy data types immediately before the first of the at least one dummy data type preceding the found data type. In response to a successful insertion of the first positive number of linked dummy data types, performing, by the processor, at least one read operation on the found object directly or via a callback function. According to an implementation form of the third aspect, the method of performing a search operation further comprises deleting, by the processor, the successfully inserted first predetermined positive number of linked dummy data types upon exiting said at least one read operation.

According to an implementation form of the third aspect, each dummy data type comprises a counter value indicating the number of different parties accessing its protected native data type, and the method further comprises in response to finding the object with a dummy data type immediately preceding it, incrementing, by the processor, the counter value of the immediately preceding dummy data type; decrementing, by the processor, the counter value upon exiting the at least one read operation; and deleting, by the processor, the successfully inserted dummy data type when its counter value falls below the predetermined first value. Preferably, before performing the search for an object, the counter value is initialized/set to a predetermined first value, greater or equal to one. Preferably, both incrementing and decrementing of the counter value occurs in units of the initial predefined first value.

According to a fourth aspect, a method of performing a delete operation on a computer-implemented lock-free data structure comprising at least one data type, and a memory pointer per each of the at least one data type, each memory pointer pointing to one of the at least one data type and each memory pointer comprising a tag indicating whether the pointed data type is a native data type or a dummy data type, wherein the presence of a dummy data type in the computer-implemented lock-free data structure indicates that a native data type first following said dummy data type is protected against writes, the method is provided. The method comprises: performing, by a processor, a search for an object in the computer-implemented lock-free data structure, and in response to finding the object with no dummy data type immediately preceding it, performing, by the processor, a lock-free delete; or in response to finding the object with at least one dummy data type immediately preceding it, ending, by the processor, the search.

According to a fifth aspect, a method of performing an update operation on a computer-implemented lock-free data structure comprising at least one data type, and a memory pointer per each of the at least one data type, each memory pointer pointing to one of the at least one data type and each memory pointer comprising a tag indicating whether the pointed data type is a native data type or a dummy data type, wherein the presence of a dummy data type in the computer-implemented lock-free data structure indicates that a native data type first following said dummy data type is protected against writes is provided. The method comprises: performing, by a processor, a search for an object in the computer-implemented lock-free data structure; and in response to finding the object with no dummy data type immediately preceding it, performing, by the processor, a lock-free update; or in response to finding the object with at least one dummy data type immediately preceding it, ending, by the processor, the search.

According to a sixth aspect, an apparatus is provided. The apparatus comprises at least one processor that is configured to implement a lock-free data structure, comprising at least one data type; and a memory pointer per each of the at least one data type, each memory pointer pointing to one of the at least one data type and each memory pointer comprising a tag indicating whether the pointed data type is a native data type or a dummy data type, wherein the presence of a dummy data type in the computer-implemented lock-free data structure indicates that a native data type first following the dummy data type is protected against writes. The at least one processor is further configured to perform an access operation on the implemented lock-free data structure.

In an implementation form of the sixth aspect, the at least one processor is configured to perform the access operation by performing a search operation comprising: starting a search for an object in the implemented lock-free data structure; in response to finding the object with no dummy data type immediately preceding it, inserting a predetermined first positive number of linked dummy data types immediately before the found data type; or in response to finding the object with at least one dummy data type immediately preceding it, inserting the first positive number of linked dummy data types immediately before the first of the at least one dummy data type preceding the found data type; in response to a successful insertion of the first positive number of linked dummy data types, performing at least one read operation on the found object directly or via a callback function; and deleting the successfully inserted first positive number of linked dummy data types upon exiting the at least one read operation.

In an implementation form of the sixth aspect, each dummy data type comprises a counter value indicating the number of different parties accessing its protected native data type, and the at least one processor is configured to perform the access operation by performing a search operation comprising: starting a search for an object in the implemented lock-free data structure; in response to finding the object with no dummy data type immediately preceding it, inserting a dummy data type immediately before the found data type and setting the counter value of the inserted dummy data type to a predetermined first value; or in response to finding the object with a dummy data type immediately preceding it, incrementing the counter value of the immediately preceding dummy data type by the predetermined first value; in response to a successful insertion of the dummy data type or incrementation of the counter value of the immediately preceding dummy data type, performing at least one read operation on the found object directly or via a callback function; decrementing the already set or incremented counter value by the predetermined first value upon exiting the at least one read operation; and deleting the successfully inserted dummy data type when its counter value falls below the predetermined first value.

In an implementation form of the sixth aspect, the at least one processor is further configured to perform the access operation by performing a delete operation comprising: performing a search for an object in the implemented lock-free data structure; and in response to finding the object with no dummy data type immediately preceding it, performing a lock-free delete; or in response to finding the object with at least one dummy data type immediately preceding it, ending the search.

In an implementation form of the sixth aspect, the at least one processor is further configured to perform the access operation by performing an update operation comprising: performing a search for an object in the implemented lock-free data structure; and in response to finding the object with no dummy data type immediately preceding it, performing a lock-free update; or in response to finding the object with at least one dummy data type immediately preceding it, ending the search.

Many of the attendant features will be more readily appreciated as they become better understood by reference to the following detailed description considered in connection with the accompanying drawings.

DESCRIPTION OF THE DRAWINGS

In the following, embodiments of the invention are described in more detail with reference to the attached figures and drawings, in which: Fig. 1 A is a diagram illustrating a computer-implemented lock-free data structure according to an embodiment;

Fig. 1 B is a diagram illustrating a computer-implemented lock-free data structure according to another embodiment; Fig. 1 C is a diagram illustrating a computer-implemented lock-free data structure according to yet another embodiment;

Fig. 2 is a block diagram illustrating an apparatus according to an embodiment;

Fig. 3A is a flow diagram illustrating a method for performing a search operation on a computer-implemented lock-free data structure according to an embodiment; Fig. 3B is a flow diagram illustrating a method for performing a search operation on a computer-implemented lock-free data structure according to another embodiment;

Fig. 3C is a flow diagram illustrating a method for performing a delete operation according to an embodiment;

Fig. 3D is a flow diagram illustrating a method of performing an update operation according to an embodiment;

Fig. 4A is a diagram illustrating inserting a dummy data type in a lock-free manner;

Fig. 4B is a diagram further illustrating inserting the dummy data type in the lock-free manner;

Fig. 4C is a diagram illustrating deleting a dummy data type in a lock-free manner; and Fig. 4D is a diagram further illustrating deleting the dummy data type in the lock-free manner.

In the following, identical reference signs refer to identical or at least functionally equivalent features.

DETAILED DESCRIPTION

In the following description, reference is made to the accompanying drawings, which form part of the disclosure, and in which are shown, by way of illustration, specific aspects in which the invention may be placed. It is understood that other aspects may be utilized and structural or logical changes may be made without departing from the scope of the invention. The following detailed description, therefore, is not to be taken in a limiting sense, as the scope of the invention is defined in the appended claims.

For instance, it is understood that a disclosure in connection with a described method may also hold true for a corresponding device or system configured to perform the method and vice versa. For example, if a specific method step is described, a corresponding device may include a unit to perform the described method step, even if such unit is not explicitly described or illustrated in the figures. On the other hand, for example, if a specific apparatus is described based on functional units, a corresponding method may include a step performing the described functionality, even if such step is not explicitly described or illustrated in the figures. Further, it is understood that the features of the various example aspects described herein may be combined with each other, unless specifically noted otherwise.

The invention allows an improved lock-free data structure with strong consistency reads and safe memory reclamation. Using tagged memory pointers allows using memory that has already been allocated in the data structure, and it allows avoiding introduction of a new data type to the structure. The invention can be applied e.g. in data structures used in embedded software which may be constrained in resources like memory. The invention may be implemented e.g. for lock-free pointer-based linked-lists and binary search trees.

In the following, example embodiments of a computer-implemented lock-free data structures 120, 130, 140 are described based on Figs. 1 A to 1 C. Some of the features of the described data structure are optional features which provide further advantages.

Fig. 1 A is a diagram that illustrates an example of a computer-implemented lock-free data structure 120. Herein, “lock-free” is synonymous with “non-blocking”. In the example of Fig. 1 A, the computer-implemented lock-free data structure 120 comprises a linked list. A linked list is a linear collection of data elements/types, whose order is not given by their physical placement in memory. Instead, each element/type points to the next list entry. Lock-free pointer-based linked-lists may be used to implement more complex lock-free data structures, such as hash tables via e.g. chained hashing and skip lists. The computer-implemented lock-free data structure 120 comprises one or more data types. Herein,“data type” and“data element” are used interchangeably. Some of the data types may be native data types and some of them may be dummy data types. In the example of Fig. 1 A, the computer-implemented lock-free data structure 120 comprises four native data types 121 A-121 D and three dummy data types 123A-123C (represented by black circles in Fig. 1 A).

Herein, the term“dummy data type” (or“crumb”) is used to refer to a special kind of data type in the data structure the purpose of which is to signal that a thread/client is accessing a specific native data type of the data structure. In other words, a dummy data type protects the other data types (i.e.“native” or“regular” data types) of the data structure against writes.

The computer-implemented lock-free data structure 120 further comprises a memory pointer 122A-122H per each of the at least one data type. Each memory pointer points to one of the at least one data type. Furthermore, each memory pointer comprises a tag that indicates whether the pointed data type is a native data type 121 A-121 D or a dummy data type 123A-123C.

In the example of Fig. 1 A, memory pointer 122A points to native data type 121 A and comprises a tag that indicates that the pointed data type 121 A is a native data type, memory pointer 122B points to native data type 121 B and comprises a tag that indicates that the pointed data type 121 B is a native data type, memory pointer 122C points to dummy data type 123A and comprises a tag that indicates that the pointed data type 123A is a dummy data type, memory pointer 122D points to dummy data type 123B and comprises a tag that indicates that the pointed data type 123B is a dummy data type, memory pointer 122E points to dummy data type 123C and comprises a tag that indicates that the pointed data type 123C is a dummy data type, memory pointer 122F points to native data type 121 C and comprises a tag that indicates that the pointed data type 121 C is a native data type, memory pointer 122G points to native data type 121 D and comprises a tag that indicates that the pointed data type 121 D is a native data type.

The presence of a dummy data type in the computer-implemented lock-free data structure 120 indicates that a native data type first following the dummy data type is protected against writes. In the example of Fig. 1 A, the presence of the dummy data type 123C in the computer-implemented lock-free data structure 120 indicates that the native data type 121 C first following the dummy data type 123C is protected against writes.

In other words, the dummy data types are implemented by using tagged pointers, i.e. native computer (memory) pointers with a tag. This tag signals whether the data type pointed to by the tagged pointer is a data type containing data of the data structure, or whether it is a dummy data type. Advantages of using tagged pointers include e.g. the following: it allows using memory that has already been allocated in the data structure, and it allows avoiding introduction of a new data type to the structure.

In an embodiment, the computer-implemented lock-free data structure 120 may further comprise two or more dummy data types before a native data type. In such a case, each of the two or more dummy data types has been inserted by a different party and each of the two or more dummy data types protects the same native data type against writes. Herein, a party may comprise e.g. a thread or a client. In the example of Fig. 1 A, the computer-implemented lock-free data structure 120 comprises three dummy data types 123A-123C before the native data type 121 C, such that dummy data type 123A has been inserted by a first thread/client, dummy data type 123B has been inserted by a second thread/client, and dummy data type 123C has been inserted by a third thread/client. All three dummy data types 123A-123C protect the same native data type 121 C against writes.

In other words, when accessing native data types (e.g. in a lock-free linked list or binary search tree), every accessing thread/client places a dummy data type before (in the native order of the data structure in question) the accessed native data type to protect it against writes, thus providing strong consistency reads and safe memory reclamation. Thus, a chain of consecutive dummy data types indicates that more than one thread/client is accessing the protected data type of the data structure in question. When needed, this chain of dummy data types can be made longer by adding a new dummy data type before the first encountered dummy data type having a key matching the key of the protected native data type.

At least one native data type may comprise a key. In the example of Fig. 1 A, native data type 121 A comprises key 121A1 (“15”), native data type 121 B comprises key 121 B1 (“37”), native data type 121 C comprises key 121 C1 (“101”), and native data type 121 D comprises key 121 D1 (“157”). In an embodiment, each dummy data type protecting a native data type against writes may comprise a copy of the key of the protected native data type or a pointer to the key of the protected native data type. In the example of Fig. 1A, native data type 121 C comprising key 121 C1 (“101”) is the protected one. Thus, dummy data type 123A comprises key copy 123A1 (“101”), dummy data type 123B comprises key copy 123B1 (“101”), and dummy data type 123C comprises key copy 123C1 (“101”).

In other words, in the example of Fig. 1 A, three threads/clients are currently reading from native data type 121 C whose key is“101” and thus native data type 121 C is protected against writes. Dummy data types 123A-123C have the same key as the native data type 121 C they protect (in this case“101”). Other native data types 121 A, 121 B, 121 D (with keys“15”,“37”, and“157”, respectively) are unprotected against writes.

In an embodiment, insertions of native data types in lock-free (concurrent) linked lists and binary search trees may be performed without breaking chains of consecutive dummy data types and without splitting an object from its protecting chain of dummy data types (if any). That is, for insertions, a chain of dummy data types and its protected object may appear as a single entity.

Fig. 1 B is a diagram that illustrates an example of a computer-implemented lock-free data structure 130. In the example of Fig. 1 B, the computer-implemented lock-free data structure 130 comprises a linked list.

The computer-implemented lock-free data structure 130 comprises one or more data types. Some of the data types may be native data types and some of them may be dummy data types. In the example of Fig. 1 B, the computer-implemented lock-free data structure 130 comprises four native data types 131 A-131 D and one dummy data type 133A (represented by a black circle in Fig. 1 B).

The computer-implemented lock-free data structure 130 further comprises a memory pointer 132A-132F per each of the at least one data type. Each memory pointer points to one of the at least one data type. Furthermore, each memory pointer comprises a tag that indicates whether the pointed data type is a native data type 131 A-131 D or a dummy data type 133A. In the example of Fig. 1 B, memory pointer 132A points to native data type 131 A and comprises a tag that indicates that the pointed data type 131 A is a native data type, memory pointer 132B points to native data type 131 B and comprises a tag that indicates that the pointed data type 131 B is a native data type, memory pointer 132C points to dummy data type 133A and comprises a tag that indicates that the pointed data type 133A is a dummy data type, memory pointer 132D points to native data type 131 C and comprises a tag that indicates that the pointed data type 131 C is a native data type, and memory pointer 132E points to native data type 131 D and comprises a tag that indicates that the pointed data type 131 D is a native data type.

Again, the presence of a dummy data type in the computer-implemented lock-free data structure 130 indicates that a native data type first following the dummy data type is protected against writes. In the example of Fig. 1 B, the presence of the dummy data type 133A in the computer-implemented lock-free data structure 130 indicates that the native data type 131 C first following the dummy data type 133A is protected against writes.

Rather than the multiple consecutive dummy data type employed in the embodiment of Fig. 1 A, in the embodiment of Fig. 1 B the computer-implemented lock-free data structure 130 may comprise a single dummy data type before a native data type protecting the native data type against writes, such that the single dummy data type comprises a counter value indicating the number of different parties accessing the native data type. In the example of Fig. 1 B, the computer-implemented lock-free data structure 130 comprises the single dummy data type 133A before the native data type 131 C protecting the native data type 131 C against writes. The single dummy data type 133A comprises a counter value 133A2 indicating the number of different parties accessing the native data type 131 C. In the example of Fig. 1 B, the counter value 133A2 is“3” indicating that three different parties are currently accessing the native data type 131 C.

In other words, the embodiment of Fig. 1 B implements“pluggable” reference counters. That is, a single dummy data type large enough to contain a counter may be placed before (in the native order of the data structure 130) the data type to be protected. The dummy data type can then be used as a reference counter, but when not needed it may be removed from the data structure 130. At least one native data type may comprise a key. In the example of Fig. 1 B, native data type 131 A comprises key 131 A1 (“15”), native data type 131 B comprises key 131 B1 (“37”), native data type 131 C comprises key 131 C1 (“101”), and native data type 131 D comprises key 131 D1 (“157”). In an embodiment, each dummy data type protecting a native data type against writes may comprise a copy of the key of the protected native data type or a pointer to the key of the protected native data type. In the example of Fig. 1 B, native data type 131 C comprising key 131 C1 (“101”) is the protected one. Thus, dummy data type 133A comprises key copy 133A1 (“101”).

Further features of the computer-implemented lock-free data structure 130 of Fig. 1 B directly result from the functionalities and parameters of the computer-implemented lock-free data structure 120 of Fig. 1 A and thus are not repeated here.

Fig. 1 C is a diagram that illustrates an example of a computer-implemented lock-free data structure 140. In the example of Fig. 1 C, the computer-implemented lock-free data structure 140 comprises a binary search tree (also known as an ordered binary tree or a sorted binary tree). A binary search tree keeps its keys in a sorted order so that lookup and other operations can use the principle of binary search: when looking for a key in a tree (or a place to insert a new key), they traverse the tree from root to leaf, making comparisons to keys stored in the nodes of the tree and deciding, on the basis of the comparison, to continue searching in the left or right subtrees.

The computer-implemented lock-free data structure 140 comprises one or more data types. Some of the data types may be native data types and some of them may be dummy data types. In the example of Fig. 1 C, the computer-implemented lock-free data structure 140 comprises five native data types 141 A-141 E and three dummy data types 143A-143C (represented by black circles in Fig. 1 C).

The computer-implemented lock-free data structure 140 further comprises a memory pointer 142A-142K per each of the at least one data type. Each memory pointer points to one of the at least one data type. Furthermore, each memory pointer comprises a tag that indicates whether the pointed data type is a native data type 141 A-141 E or a dummy data type 143A-143C.

In the example of Fig. 1 C, memory pointer 142A points to native data type 141 B and comprises a tag that indicates that the pointed data type 141 B is a native data type, memory pointer 142B points to native data type 141 C and comprises a tag that indicates that the pointed data type 141 C is a native data type, memory pointer 142E points to native data type 141 D and comprises a tag that indicates that the pointed data type 141 D is a native data type, memory pointer 142F points to dummy data type 143A and comprises a tag that indicates that the pointed data type 143A is a dummy data type, memory pointer 142G points to dummy data type 143B and comprises a tag that indicates that the pointed data type 143B is a dummy data type, memory pointer 142H points to dummy data type 143C and comprises a tag that indicates that the pointed data type 143C is a dummy data type, and memory pointer 1421 points to native data type 141 E and comprises a tag that indicates that the pointed data type 141 E is a native data type.

The presence of a dummy data type in the computer-implemented lock-free data structure 140 indicates that a native data type first following the dummy data type is protected against writes. In the example of Fig. 1 C, the presence of the dummy data type 143C in the computer-implemented lock-free data structure 140 indicates that the native data type 141 E first following the dummy data type 143C is protected against writes.

In an embodiment, the computer-implemented lock-free data structure 140 may further comprise two or more dummy data types before a native data type. In such a case, each of the two or more dummy data types has been inserted by a different party and each of the two or more dummy data types protects the same native data type against writes. Herein, a party may comprise e.g. a thread or a client. In the example of Fig. 1 C, the computer-implemented lock-free data structure 140 comprises three dummy data types 143A-143C before the native data type 141 E, such that dummy data type 143A has been inserted by a first thread/client, dummy data type 143B has been inserted by a second thread/client, and dummy data type 143C has been inserted by a third thread/client. All three dummy data types 143A-143C protect the same native data type 141 E against writes.

In other words, the native data type 141 E with key“399” is being protected by three dummy data types 143A-143C which means that three threads/clients are currently accessing the native data type 141 E and thus can neither be overwritten nor deleted. Rebalancing operations (rotations) of the binary search tree 140 are not affected by dummy data types, since the chains of dummy data types along with their protected native data type(s) are not to be broken and instead move as a whole. At least one native data type may comprise a key. In the example of Fig. 1 C, native data type 141 A comprises key 141 A1 (“250”), native data type 141 B comprises key 141 B1 (“70”), native data type 141 C comprises key 141 C1 (“301”), native data type 141 D comprises key 141 D1 (“287”), and native data type 141 E comprises key 141 E1 (“399”). In an embodiment, each dummy data type protecting a native data type against writes may comprise a copy of the key of the protected native data type or a pointer to the key of the protected native data type. In the example of Fig. 1 C, native data type 141 E comprising key 141 E1 (“399”) is the protected one. Thus, dummy data type 143A comprises key copy 143A1 (“399”), dummy data type 143B comprises key copy 143B1 (“399”), and dummy data type 143C comprises key copy 143C1 (“399”).

In other words, in the example of Fig. 1 C, three threads/clients are currently reading from native data type 141 E whose key is“399” and thus native data type 141 E is protected against writes. Dummy data types 143A-143C have the same key as the native data type 141 E they protect (in this case“399”). Other native data types 141 A, 141 B, 141 C, 141 D (with keys “250”, “70”, “301”, and “287”, respectively) are unprotected against writes.

Further features of the computer-implemented lock-free data structure 140 of Fig. 1 C directly result from the functionalities and parameters of the computer-implemented lock-free data structure 120 of Fig. 1 A and thus are not repeated here.

In the following, example embodiments of an apparatus 200 are described based on Fig. 2. Some of the features of the described device are optional features which provide further advantages.

Fig. 2 is a block diagram that illustrates the apparatus 200. In an embodiment, the apparatus 200 may comprise a client device that may be any of various types of devices used directly by an end user entity and capable of communication in a wireless network, such as a user equipment (UE). Such devices include but are not limited to smartphones, tablet computers, smart watches, laptop computers, Internet-of-Things (loT) devices, etc. In an embodiment, the apparatus 200 may comprise a device with embedded software.

The apparatus 200 comprises at least one processor or a processing unit 201 and optionally a memory 202 coupled to the at least one processor 201 , which may be used to implement the functionalities described later in more detail. The at least one processor 201 may include e.g. one or more of various processing devices, such as a co-processor, a microprocessor, a controller, a digital signal processor (DSP), a processing circuitry with or without an accompanying DSP, or various other processing devices including integrated circuits such as, for example, an application specific integrated circuit (ASIC), a field programmable gate array (FPGA), a microcontroller unit (MCU), a hardware accelerator, a special-purpose computer chip, or the like.

The memory 202 may be configured to store e.g. computer programs and the like. The memory 202 may include one or more volatile memory devices, one or more non volatile memory devices, and/or a combination of one or more volatile memory devices and non-volatile memory devices. For example, the memory 202 may be embodied as magnetic storage devices (such as hard disk drives, floppy disks, magnetic tapes, etc.), optical magnetic storage devices, and semiconductor memories (such as mask ROM, PROM (programmable ROM), EPROM (erasable PROM), flash ROM, RAM (random access memory), etc.).

As a person skilled in the art can appreciate, when the apparatus 200 is configured to implement a functionality, a component or components of the apparatus 200, such as the at least one processor 201 and/or the memory 202, may be configured to implement this functionality. Furthermore, when the at least one processor 201 is configured to implement a functionality, this functionality may be implemented using program code comprised, for example, in the memory 202.

The at least one processor 201 is configured to implement a lock-free data structure 120, 130, 140 that comprises at least one data type 121 A-121 D, 123A-123C, 131 A- 131 D, 133A, 141 A- 141 E, 143A-143C; and a memory pointer 122A-122H, 132A-132F, 142A-142K per each of the at least one data type, each memory pointer pointing to one of the at least one data type and each memory pointer comprising a tag indicating whether the pointed data type is a native data type 121 A-121 D, 131 A-131 D, 141 A- 141 E or a dummy data type 123A-123C, 133A, 143A-143C, wherein the presence of a dummy data type 123A-123C, 133A, 143A-143C in the computer-implemented lock- free data structure 120, 130, 140 indicates that a native data type 121 A-121 D, 131 A- 131 D, 141 A-141 E first following the dummy data type 123A-123C, 133A, 143A-143C is protected against writes. Further features of the computer-implemented lock-free data structure 120, 130, 140 implemented by the at least one processor 201 of the apparatus 200 directly result from the functionalities and parameters of the computer-implemented lock-free data structure 120, 130, 140 of Figs. 1 A to 1 C and thus are not repeated here.

The at least one processor 201 is further configured to perform an access operation on the implemented lock-free data structure 120, 130, 140.

In an embodiment, the at least one processor 201 may be configured to perform the access operation by performing a search operation, such that the search operation comprises:

starting a search for an object in the implemented lock-free data structure;

in response to finding the object with no dummy data type immediately preceding it, inserting a predetermined first positive number of linked dummy data types immediately before the found data type; or

in response to finding the object with at least one dummy data type immediately preceding it, inserting the first positive number of linked dummy data types immediately before the first of the at least one dummy data type preceding the found data type;

in response to a successful insertion of the first positive number of linked dummy data types, performing at least one read operation on the found object directly or via a callback function; and

deleting the successfully inserted first positive number of linked dummy data types upon exiting said at least one read operation.

In another embodiment, each dummy data type may comprise a counter value indicating the number of different parties accessing its protected native data type, and the at least one processor 201 may be configured to perform the access operation by performing a search operation, such that the search operation comprises: starting a search for an object in the implemented lock-free data structure;

in response to finding the object with no dummy data type immediately preceding it, inserting a dummy data type immediately before the found data type and setting the counter value of the inserted dummy data type to a predetermined first value; or in response to finding the object with a dummy data type immediately preceding it, incrementing the counter value of the immediately preceding dummy data type by the predetermined first value;

in response to a successful insertion of the dummy data type or incrementation of the counter value of the immediately preceding dummy data type, performing at least one read operation on the found object directly or via a callback function;

decrementing the already set or incremented counter value by the predetermined first value upon exiting said at least one read operation; and

deleting the successfully inserted dummy data type when its counter value falls below the predetermined first value.

In an embodiment, the at least one processor 201 may be configured to perform the access operation by performing a delete operation, such that the delete operation comprises:

performing a search for an object in the implemented lock-free data structure; and

in response to finding the object with no dummy data type immediately preceding it, performing a lock-free delete; or

in response to finding the object with at least one dummy data type immediately preceding it, ending the search.

In an embodiment, the at least one processor 201 may be configured to perform the access operation by performing an update operation, such that the update operation comprises:

performing a search for an object in the implemented lock-free data structure; and

in response to finding the object with no dummy data type immediately preceding it, performing a lock-free update; or

in response to finding the object with at least one dummy data type immediately preceding it, ending the search.

Fig. 3A is a flow diagram illustrating a method 310 of performing a search operation according to an embodiment.

At step 31 1 , a processor starts a search for an object in a computer-implemented lock- free data structure comprising at least one data type, and a memory pointer per each of the at least one data type, each memory pointer pointing to one of the at least one data type and each memory pointer comprising a tag indicating whether the pointed data type is a native data type or a dummy data type, wherein the presence of a dummy data type in the computer-implemented lock-free data structure indicates that a native data type first following the dummy data type is protected against writes.

At step 312, the processor allocates a dummy data type.

At step 313, the processor performs the search for the object.

If the object is not found, step 314, the processor deletes the unused allocated dummy data type, step 315. Then, the search ends, step 320.

If the object is found, step 314, and no dummy data type immediately precedes it the processor inserts a predetermined first positive number of linked dummy data types immediately before the found data type/object, step 316.

If the object is found, step 314, and at least one dummy data type immediately precedes it the processor inserts the first positive number of linked dummy data types immediately before the first of the at least one dummy data type preceding the found data type/object, step 316.

If the insertion of the first positive number of linked dummy data types is not successful, step 317, the method returns to step 313.

If the insertion of the first positive number of linked dummy data types is successful, step 317, the processor performs at least one read operation on the found object directly or via a callback function, step 318.

At step 319, the processor deletes the successfully inserted first positive number of linked dummy data types upon exiting the at least one read operation. Then, the search ends, step 320.

The method 310 may be performed by the apparatus 200. The steps 31 1 -320 can, for example, be performed by the at least one processor 201 and the memory 202. Further features of the method 310 directly result from the functionalities of the the apparatus 200 and the computer-implemented lock-free data structure 120, 130, 140. The method 310 can be performed by a computer program product. Fig. 3B is a flow diagram illustrating a method 330 of performing a search operation according to another embodiment.

At step 331 , a processor starts a search for an object in a computer-implemented lock- free data structure comprising at least one data type, and a memory pointer per each of the at least one data type, each memory pointer pointing to one of the at least one data type and each memory pointer comprising a tag indicating whether the pointed data type is a native data type or a dummy data type, wherein the presence of a dummy data type in the computer-implemented lock-free data structure indicates that a native data type first following the dummy data type is protected against writes, each dummy data type comprising a counter value indicating the number of different parties accessing its protected native data type.

At step 332, the processor allocates a dummy data type and initializes its’ counter value to A units where A ³ 1.

At step 333, the processor performs the search for the object.

If the object is not found, step 334, the processor deletes the allocated dummy data type if unused, step 335. Then, the search ends, step 336.

If the object is found, step 334, and no dummy data type immediately precedes it, the processor inserts a dummy data type immediately before the found data type/object and sets the counter value of the inserted dummy data type to a predetermined first value (A units), step 337.

If the object is found, step 334, and a dummy data type immediately precedes it, the processor increments the counter value of the immediately preceding dummy data type by the predetermined first value (A units), step 337.

If the insertion of the dummy data type or incrementation of the counter value of the immediately preceding dummy data type is not successful, step 338, the method returns to step 333.

If the insertion of the dummy data type or incrementation of the counter value of the immediately preceding dummy data type is successful, step 338, the processor performs at least one read operation on the found object directly or via a callback function, step 339. At step 340, the processor decrements the already set or incremented counter value by the predetermined first value (A units) upon exiting the at least one read operation.

At step 341 , the processor determines whether the counter value falls below the predetermined first value (A units). If not, the method proceeds to step 335 described above. If yes, the processor deletes the successfully inserted dummy data type, step 342. Then, the method proceeds to step 335 described above.

The method 330 may be performed by the apparatus 200. The steps 331 -342 can, for example, be performed by the at least one processor 201 and the memory 202. Further features of the method 330 directly result from the functionalities of the the apparatus 200 and the computer-implemented lock-free data structure 120, 130, 140. The method 330 can be performed by a computer program product.

Fig. 3C is a flow diagram illustrating a method 350 of performing a delete operation according to an embodiment.

The method starts at step 351 .

At step 352, a processor starts a search for an object in a computer-implemented lock- free data structure comprising at least one data type, and a memory pointer per each of the at least one data type, each memory pointer pointing to one of the at least one data type and each memory pointer comprising a tag indicating whether the pointed data type is a native data type or a dummy data type, wherein the presence of a dummy data type in the computer-implemented lock-free data structure indicates that a native data type first following the dummy data type is protected against writes.

If the object is found and at least one dummy data type immediately precedes it, step 353, the method proceeds to step 356 and ends.

If the object is found and no dummy data type immediately precedes it, step 353, the processor performs a lock-free delete, step 354.

If the delete is not successful, step 355, the method returns to step 352.

If the delete is successful, step 355, the method proceeds to step 356 and ends. The method 350 may be performed by the apparatus 200. The steps 351 -356 can, for example, be performed by the at least one processor 201 and the memory 202. Further features of the method 350 directly result from the functionalities of the the apparatus 200 and the computer-implemented lock-free data structure 120, 130, 140. The method 350 can be performed by a computer program product.

Fig. 3D is a flow diagram illustrating a method 370 of performing an update operation according to an embodiment.

The method starts at step 371 .

At step 372, a processor starts a search for an object in a computer-implemented lock- free data structure comprising at least one data type, and a memory pointer per each of the at least one data type, each memory pointer pointing to one of the at least one data type and each memory pointer comprising a tag indicating whether the pointed data type is a native data type or a dummy data type, wherein the presence of a dummy data type in the computer-implemented lock-free data structure indicates that a native data type first following the dummy data type is protected against writes.

If the object is found and at least one dummy data type immediately precedes it, step 373, the method proceeds to step 376 and ends.

If the object is found and no dummy data type immediately precedes it, step 373, the processor performs a lock-free update, step 374.

If the update is not successful, step 375, the method returns to step 372.

If the update is successful, step 375, the method proceeds to step 376 and ends.

The method 370 may be performed by the apparatus 200. The steps 371 -376 can, for example, be performed by the at least one processor 201 and the memory 202. Further features of the method 370 directly result from the functionalities of the the apparatus 200 and the computer-implemented lock-free data structure 120, 130, 140. The method 370 can be performed by a computer program product.

Fig. 4A is a diagram illustrating inserting a dummy data type in a lock-free manner. As shown in Fig. 4A, after the search has successfully stopped at an entry (regular object), the dummy data type may be made to point to the object found in the search (non-CAS (compare-and-swap) operation). Fig. 4B is a diagram further illustrating inserting the dummy data type in the lock-free manner. As shown in Fig. 4B, the dummy data type may be inserted by doing a CAS operation at the object the search stopped at (the one before the sought object or the first dummy data type protecting it).

Fig. 4C is a diagram illustrating deleting a dummy data type in a lock-free manner. For deleting one dummy data type, a search for the object may be performed and stopped before the first dummy data type protecting it (since dummy data types could have accumulated while a read from the object was being performed). As shown in Fig. 4C, the dummy data type may be unlinked via one CAS operation on the element the search stopped at. Fig. 4D is a diagram further illustrating deleting the dummy data type in the lock-free manner. As shown in Fig. 4D, the dummy data type is de allocated.

The functionality described herein can be performed, at least in part, by one or more computer program product components such as software components. According to an embodiment, the network device 100 comprises at least one processor configured by the program code when executed to execute the embodiments of the operations and functionality described. Alternatively, or in addition, the functionality described herein can be performed, at least in part, by one or more hardware logic components. For example, and without limitation, illustrative types of hardware logic components that can be used include Field-programmable Gate Arrays (FPGAs), Program-specific Integrated Circuits (ASICs), Program-specific Standard Products (ASSPs), System- on-a-chip systems (SOCs), Complex Programmable Logic Devices (CPLDs), and Graphics Processing Units (GPUs).

Any range or device value given herein may be extended or altered without losing the effect sought. Also any embodiment may be combined with another embodiment unless explicitly disallowed.

Although the subject matter has been described in language specific to structural features and/or acts, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the specific features or acts described above. Rather, the specific features and acts described above are disclosed as examples of implementing the claims and other equivalent features and acts are intended to be within the scope of the claims.

It will be understood that the benefits and advantages described above may relate to one embodiment or may relate to several embodiments. The embodiments are not limited to those that solve any or all of the stated problems or those that have any or all of the stated benefits and advantages. It will further be understood that reference to 'an' item may refer to one or more of those items.

The steps of the methods described herein may be carried out in any suitable order, or simultaneously where appropriate. Additionally, individual blocks may be deleted from any of the methods without departing from the spirit and scope of the subject matter described herein. Aspects of any of the embodiments described above may be combined with aspects of any of the other embodiments described to form further embodiments without losing the effect sought.

The term 'comprising' is used herein to mean including the method, blocks or elements identified, but that such blocks or elements do not comprise an exclusive list and a method or apparatus may contain additional blocks or elements.

It will be understood that the above description is given by way of example only and that various modifications may be made by those skilled in the art. The above specification, examples and data provide a complete description of the structure and use of exemplary embodiments. Although various embodiments have been described above with a certain degree of particularity, or with reference to one or more individual embodiments, those skilled in the art could make numerous alterations to the disclosed embodiments without departing from the spirit or scope of this specification.