DOORS DXL Skip List

DOORS DXL Skip List

In this series of articles, we are going to explain to you IBM DOORS DXL scripting from scratch. So, if you are a beginner in DXL scripting, hopefully, this article will help you.

So, if you are looking for a starting point to learn DOORS DXL scripting, you are on the right page! I know, we have the DXL reference manual and it’s a bit concise and difficult to grasp for beginners, especially if you do not have any previous experience in other programming languages.

In this article, we will mainly discuss the DOORS DXL Skip List.

What is Skip List in DXL?

Skip lists are an efficient dictionary-like data structure. Many DXL programs use skip lists as a building block for creating complex data structures. It is an associative array of elements sorted by lexicographic order by key. A system of unique keys is enforced. Keys may be of any type and data can be of any type.

DXL does not have garbage collection. Therefore, it is important to delete skip lists that are no longer required in the program. The type name Skip begins with an upper-case letter.

It is also the programmer’s responsibility to make sure that the key and data are consistently used when storing and retrieving from a skip list. For example, if you insert data in the skip list as a string and then retrieve it as an integer variable and attempt to print will cause the program failure. When deleting a skip list, the programmer should also set the skip list to null.

Create Skip List with an Integer type Key

Here is an example of creating a Skip List with an integer type key.

// www.TheCloudStrap.Com 

/************************************************************************
* $FILENAME: sk1.dxl
* $DESCRIPTION: Skip List example code.
*
* NOTICE: Copyright www.TheCloudStrap.Com. All rights reserved.
* Software comes without any warranties and guarantees, is provided 
* as is and is not supported. Use this software at your own risk. 
* Authors resume no liabilities.
* 
* Contact: admin {at} TheCloudStrap.com
************************************************************************/

// Creating Skip List
Skip sk = create()   

// Insert data into Skip List
put(sk, 1, "New York")
put(sk, 2, "London")
put(sk, 3, "Los Angeles")
put(sk, 4, "Paris")
put(sk, 5, "Houston")
put(sk, 6, "Tokyo")
put(sk, 7, "Delhi")
put(sk, 8, "Geneva")

// Print Skip List
string each_val = null
int each_key = null
for each_val in sk do {
    each_key = (int key(sk))
    print("{" each_key ": " each_val "}\n")
}

// Delete Skip List to free dynamically allocated memory
delete(sk)

The output of the above sample program –

Create Skip List with a string type key

We can also create a skip list where the key is declared as string data type –

Here is the sample program to create such data structure using DXL –

// www.TheCloudStrap.Com 

/************************************************************************
* $FILENAME: sk2.dxl
* $DESCRIPTION: Skip List example code.
*
* NOTICE: Copyright www.TheCloudStrap.Com. All rights reserved.
* Software comes without any warranties and guarantees, is provided 
* as is and is not supported. Use this software at your own risk. 
* Authors resume no liabilities.
* 
* Contact: admin {at} TheCloudStrap.com
************************************************************************/

// Creating Skip List with string key
Skip sk = createString()   

// Insert data into Skip List
put(sk, "NY",	"New York")
put(sk, "LND",	"London")
put(sk, "LA",	"Los Angeles")
put(sk, "PRS",	"Paris")
put(sk, "HST",	"Houston")
put(sk, "TK",	"Tokyo")
put(sk, "DL",	"Delhi")
put(sk, "GNV",	"Geneva")

// Print Skip List
string each_val = null
string each_key = null
for each_val in sk do {
    each_key = (string key(sk))
    print("{" each_key ": " each_val "}\n")
}

// Delete Skip List to free dynamically allocated memory
delete(sk)

Here is the output of the above program –

Create Skip List and Delete it

A skip list in DXL can be created using create() or createString() function and it can be deleted using the delete() function.

It is generally a good practice to delete a skip list or any other data structure when it is no longer needed in a program. This is because failing to delete an unused data structure can lead to memory leaks, where the memory used by the data structure is not released back to the operating system and becomes unavailable for other parts of the program.

Memory leaks can cause a variety of problems, such as slowing down the program, causing crashes or freezing, and even leading to security vulnerabilities if an attacker is able to exploit the memory leak.

In DOORS DXL, you can use the delete function to release the memory used by a skip list or other data structure when it is no longer needed.

DXL does not have garbage collection. Therefore, it is important to delete skip lists that are no longer required in the program. You can use the following function to delete the skip list – void delete (Skip sk)

However, the variables that have been given as keys or data are not affected. The user also should set the skip list to null after deletion. In both the previous example, we deleted the skip list at the end of the program.

Creating huge skip lists and then not deleting them could cause the DOORS to get slow significantly. Therefore, extra care needs to be taken when dealing with dynamic data types in DOORS.

How DXL Skip List is stored in memory?

In IBM Rational DOORS, a skip list is stored in memory as a linked data structure consisting of nodes that contain pointers to other nodes in the list. Each node in the skip list contains a key-value pair, where the key is used to order the elements in the list and the value is the actual data associated with the key.

The nodes in the skip list are arranged in levels, with each level representing a subset of the nodes in the list. The top level contains all the nodes in the list, while each subsequent level contains a smaller subset of the nodes. The nodes in each level are linked together horizontally, while the nodes in each column (i.e., those with the same key value) are linked together vertically.

To speed up searches and insertion operations, each node in the skip list also contains pointers to nodes in the level above and below it. These pointers are used to “skip” over nodes during searches or when inserting a new node into the list.

When a new node is inserted into the skip list, the algorithm randomly determines the number of levels it should occupy. This is done to ensure that the skip list remains balanced and that the search and insertion operations remain efficient.

Overall, the use of a skip list data structure in DOORS allows for faster searching and sorting of data, particularly for large datasets, by reducing the number of comparisons required to find a particular element.

Why Skip List is an important data structure in DXL?

Skip lists are an important data structure in DOORS DXL because they provide an efficient way to store, search, and sort large amounts of data. Skip lists are particularly useful for managing sets of data that need to be ordered by a key value, such as requirements or test cases in a requirements management system.

Here are a few reasons why skip lists are important in DOORS DXL:

1. Fast search: Skip lists provide a fast way to search for data by key value, with an average search time of O(log n) where n is the number of elements in the list. This is much faster than a linear search, which would have an average search time of O(n) in a list of n elements.
2. Efficient memory usage: Skip lists can use memory efficiently by storing only a small number of pointers to other nodes, rather than storing pointers to all nodes in the list. This can be important when managing large datasets that might otherwise require a significant amount of memory.
3. Dynamic resizing: Skip lists can be dynamically resized as data is added or removed, allowing them to adapt to changing data requirements. This can be useful in requirements management systems where new requirements or test cases are added over time.
4. Balancing: Skip lists are self-balancing, which means that they maintain a balanced structure even as data is added or removed. This ensures that search times remain efficient even as the size of the list grows.

Overall, skip lists are an important data structure in DOORS DXL because they provide an efficient and scalable way to manage large sets of data, allowing for fast searching, efficient memory usage, and dynamic resizing.

Find an element in the Skip List

The find() function can be used to find an element in the Skip List. Here is an example to find the element in the given Skip List with the key as ‘3’ –

// www.TheCloudStrap.Com 

/************************************************************************
* $FILENAME: sk3.dxl
* $DESCRIPTION: Skip List example code.
*
* NOTICE: Copyright www.TheCloudStrap.Com. All rights reserved.
* Software comes without any warranties and guarantees, is provided 
* as is and is not supported. Use this software at your own risk. 
* Authors resume no liabilities.
* 
* Contact: admin {at} TheCloudStrap.com
************************************************************************/

// Creating Skip List
Skip sk = create()   

// Insert data into Skip List
put(sk, 1, "New York")
put(sk, 2, "London")
put(sk, 3, "Los Angeles")
put(sk, 4, "Paris")
put(sk, 5, "Houston")
put(sk, 6, "Tokyo")
put(sk, 7, "Delhi")
put(sk, 8, "Geneva")

// Print Skip List
string each_val = null
int each_key = null
for each_val in sk do {
    each_key = (int key(sk))
    print("{" each_key ": " each_val "}\n")
}

// Find the value of a given key
string str = null
if (find(sk, 3, str))
	print ("Found: " str "\n")

// Delete Skip List to free dynamically allocated memory
delete(sk)

Here is the output –

Here is another example where we will find out the data value from a given Skip List with the key ‘LA’ –

// www.TheCloudStrap.Com 

/************************************************************************
* $FILENAME: sk4.dxl
* $DESCRIPTION: Skip List example code.
*
* NOTICE: Copyright www.TheCloudStrap.Com. All rights reserved.
* Software comes without any warranties and guarantees, is provided 
* as is and is not supported. Use this software at your own risk. 
* Authors resume no liabilities.
* 
* Contact: admin {at} TheCloudStrap.com
************************************************************************/

// Creating Skip List with string key
Skip sk = createString()   

// Insert data into Skip List
put(sk, "NY",	"New York")
put(sk, "LND",	"London")
put(sk, "LA",	"Los Angeles")
put(sk, "PRS",	"Paris")
put(sk, "HST",	"Houston")
put(sk, "TK",	"Tokyo")
put(sk, "DL",	"Delhi")
put(sk, "GNV",	"Geneva")

// Print Skip List
string each_val = null
string each_key = null
for each_val in sk do {
    each_key = (string key(sk))
    print("{" each_key ": " each_val "}\n")
}

// Find the value of a given key
string str = null
if (find(sk, "LA", str))
	print ("Found: " str "\n")
	
// Delete Skip List to free dynamically allocated memory
delete(sk)

Here is the output –

Size Of a Skip List

There is no in-built function in DXL to provide the size of the skip list. However, we can create our custom function to re-use when needed in larger programs –

// www.TheCloudStrap.Com 

/************************************************************************
* $FILENAME: sk5.dxl
* $DESCRIPTION: Skip List example code.
*
* NOTICE: Copyright www.TheCloudStrap.Com. All rights reserved.
* Software comes without any warranties and guarantees, is provided 
* as is and is not supported. Use this software at your own risk. 
* Authors resume no liabilities.
* 
* Contact: admin {at} TheCloudStrap.com
************************************************************************/

int sizeOfSkip(Skip s) {
	int i = 0
	string val = null
	for val in s do i++
	return i

}

// Creating Skip List
Skip sk = create()   

// Insert data into Skip List
put(sk, 1, "New York")
put(sk, 2, "London")
put(sk, 3, "Los Angeles")
put(sk, 4, "Paris")
put(sk, 5, "Houston")
put(sk, 6, "Tokyo")
put(sk, 7, "Delhi")
put(sk, 8, "Geneva")

// Print Skip List
string each_val = null
int each_key = null
for each_val in sk do {
    each_key = (int key(sk))
    print("{" each_key ": " each_val "}\n")
}

// size of the Skip List
int iSize = sizeOfSkip(sk)
print "Size = " iSize "\n"

// Delete Skip List to free dynamically allocated memory
delete(sk)

Here is the output –

Delete an entry from Skip List

In the following example, we will delete several entries with the key 1,2,3,4,5,6 from the given Skip List –

// www.TheCloudStrap.Com 

/************************************************************************
* $FILENAME: sk6.dxl
* $DESCRIPTION: Skip List example code.
*
* NOTICE: Copyright www.TheCloudStrap.Com. All rights reserved.
* Software comes without any warranties and guarantees, is provided 
* as is and is not supported. Use this software at your own risk. 
* Authors resume no liabilities.
* 
* Contact: admin {at} TheCloudStrap.com
************************************************************************/

// Creating Skip List
Skip sk = create()   

// Insert data into Skip List
put(sk, 1, "New York")
put(sk, 2, "London")
put(sk, 3, "Los Angeles")
put(sk, 4, "Paris")
put(sk, 5, "Houston")
put(sk, 6, "Tokyo")
put(sk, 7, "Delhi")
put(sk, 8, "Geneva")

// Print Skip List
string each_val = null
int each_key = null
for each_val in sk do {
    each_key = (int key(sk))
    print("{" each_key ": " each_val "}\n")
}

// Delete an entry of the Skip List
if (delete (sk, 1))
	print "Deleted entry with key 1 \n"
if (delete (sk, 2))
	print "Deleted entry with key 2 \n"
if (delete (sk, 3))
	print "Deleted entry with key 3 \n"
if (delete (sk, 4))
	print "Deleted entry with key 4 \n"
if (delete (sk, 5))
	print "Deleted entry with key 5 \n"
if (delete (sk, 6))
	print "Deleted entry with key 6 \n"
	
// Print Skip List after deleting entries
print "Skip List after deleting entries - \n" 
each_val = null
each_key = null
for each_val in sk do {
    each_key = (int key(sk))
    print("{" each_key ": " each_val "}\n")
}
	
// Delete Skip List to free dynamically allocated memory
delete(sk)

Here is the output –

Make Skip List Empty

We can also remove all the elements from the Skip List and make sure it is empty. The following example demonstrates how to delete all entries from the Skip List –

// www.TheCloudStrap.Com 

/************************************************************************
* $FILENAME: sk7.dxl
* $DESCRIPTION: Skip List example code.
*
* NOTICE: Copyright www.TheCloudStrap.Com. All rights reserved.
* Software comes without any warranties and guarantees, is provided 
* as is and is not supported. Use this software at your own risk. 
* Authors resume no liabilities.
* 
* Contact: admin {at} TheCloudStrap.com
************************************************************************/

void emptySkip(Skip sk) {
	string s = null
	for s in sk do { 
		int k = (int key sk)
		delete (sk, k)
	}
}

// Creating Skip List
Skip sk = create()   

// Insert data into Skip List
put(sk, 1, "New York")
put(sk, 2, "London")
put(sk, 3, "Los Angeles")
put(sk, 4, "Paris")
put(sk, 5, "Houston")
put(sk, 6, "Tokyo")
put(sk, 7, "Delhi")
put(sk, 8, "Geneva")

// Print Skip List
string each_val = null
int each_key = null
for each_val in sk do {
    each_key = (int key(sk))
    print("{" each_key ": " each_val "}\n")
}

// Empty Skip List
emptySkip(sk)
print "All entries from the skip list has been deleted \n"
	
// Print Skip List after deleting entries
print "Skip List after deleting entries - \n" 
each_val = null
each_key = null
for each_val in sk do {
    each_key = (int key(sk))
    print("{" each_key ": " each_val "}\n")
}
	
// Delete Skip List to free dynamically allocated memory
delete(sk)

Here is the output that shows the Skip List was empty after deleting all entries –

Replace entry in Skip List

There is no built-in function in DXL to replace an item in Skip List. Here is an example program that replaces an item in the given Skip List –

// www.TheCloudStrap.Com 

/************************************************************************
* $FILENAME: sk8.dxl
* $DESCRIPTION: Skip List example code.
*
* NOTICE: Copyright www.TheCloudStrap.Com. All rights reserved.
* Software comes without any warranties and guarantees, is provided 
* as is and is not supported. Use this software at your own risk. 
* Authors resume no liabilities.
* 
* Contact: admin {at} TheCloudStrap.com
************************************************************************/

void addOrReplaceEntry(Skip sk, int key, string data_new) {
	if (find(sk, key))
		delete (sk, key)
	put (sk, key, data_new)
}

void printSkip (Skip sk) { 
	// KEY: Integer; DATA: String
	string val = null
	for val in sk do { 
		int key = (int key sk)
		if (null val)
			val = "NULL"
		print "{ Key = " key "\t Value = " val " }\n"
		
	}
}

// Creating Skip List
Skip sk = create()   

// Insert data into Skip List
put(sk, 1, "New York")
put(sk, 2, "London")
put(sk, 3, "Los Angeles")
put(sk, 4, "Paris")
put(sk, 5, "Houston")
put(sk, 6, "Tokyo")
put(sk, 7, "Delhi")
put(sk, 8, "Geneva")

// Print Skip List
printSkip(sk)

// Replace entry
addOrReplaceEntry(sk, 7, "Replaced_Data")
addOrReplaceEntry(sk, 8, "Replaced_Data")
addOrReplaceEntry(sk, 111, "Replaced_Data") // add new entry


// Print Skip List after replacing entries
print "Skip List after replacing entries - \n" 
// Print Skip List
printSkip(sk)

// Delete Skip List to free dynamically allocated memory
delete(sk)

Here is the output –

In this case, we have replaced the data values for key-7, key-8. The entry for key-111 was added newly in the Skip List as this was missing in the Skip List.

Conclusion

In this article, we have discussed DOORS DXL Skip List. We have explained how to declare and define a DXL Skip List, and how to print all the elements of the DXL Skip List, We hope this was a helpful article. However, if you have any questions about DOORS DXL Skip List, please feel free to comment below.