Lists, Vectors, Queues and Stacks
What we are going to look at in this tutorial is lists, vectors, queues and stacks. More specifically, why the industry has ended up with them in the standard templates library. Is there a difference between these types or not? Let's take a look at them individually so we are sure we are reading from the same page!
Lists
Google defines a list as a number of connected items or names written or printed consecutively, typically one below the other. In computer terms it is probably more appropriate to say a list is a number of connected items held as a collection. For example, we could have a list of strings or a list of objects held in a collection.
Seen from an implementation perspective, lists are generally held as a set of chained objects where the chain is either a single forward pointer to the next object in the chain or two pointers used to reference the next and previous objects in the chain.
Lists are used when the objects that are contained within the container are relatively static. Inserting an object into the chain anywhere except the head or the tail of the list requires that entries are examined one by one down the chain until the insertion point is located. For very large lists this can be somewhat time consuming.
Vectors
A vector is a collection of objects where a specific object can be located via an index (anybody have a better description?). For example, a machine code instruction number is a vector into the microcode used to implement that instruction.
Vectors are extremely fast in terms of accessing a specific object but are somewhat slow in terms of insertion and/or deletion. Objects from the insertion point to the end of the vector table have to be moved either down in order to obtain a 'hole' in the vector table to be used for the inserted object. Objects from the deletion point to the end of the table have to be moved up to remove the 'hole' where the deleted object was. Without taking these actions, the integrity of the vector table would be compromised.
Vectors like lists tend to be used in situations where the overall collection remains static.
Queues
A queue is a collection of transient objects that are added and removed from either the head or tail of the collection normally implemented on a first in/first out principle.
Queues are really a specialised form of a list were one can push onto the tail of the queue and pop from the head of the queue.
Stacks
Stacks like queues are really a specialised form of a list were one can push onto the tail of the queue and pop from the tail of the queue or push onto the head of the queue and pop from the head of the queue (depending on whether the stack grows downwards or upwards).
Implementation of Lists, Vectors, Queues and Stacks Using A Common Approach
What we are going to do is to implement the list, queue and stack as a vector.
We loose no functionality in doing this as we can transverse a list using an index pointer. So the next object in the list would be the index of the current object + 1 and the previous object in the list would be the index of the current object - 1. We can insert objects into and delete objects from the vector collection at the expense of adding and removing holes in the vector table itself.
The API
The API (which just happens to be called List) consists of 6 functions:-
- CreateList
- AddItem
- InsertItem
- DeleteItem
- GetItem
- GetNumberItems
The implementation would be in a dynamic link library.
Here is the code:-
title 'List' public _DllMainCRTStartup public CreateList public AddItem public DeleteItem public GetItem public GetNumberItems public InsertItem ; ; There are two ways that you can refer to external functions in MASM ; Firstly, one could say ; ; extern __imp_VirtualAlloc: qword ; ; The alternative is using externdef as I have used below ; ; The difference between the two methods is that the first reference ; is to a qword pointer (which of course an external pointer) ; You would use the first method by loading the address into a register ; and the calling the external function with a call statement as follows ; ; mov rax, __imp_VirtualAlloc ; call qword ptr [rax] ; ; The second method is perhaps more appropriate mechanism and permits ; you to simply say ; ; call qword ptr __imp_VirtualAlloc ; externdef __imp_VirtualAlloc: proc ; ; The structure definitions used by the dynamic link library are below. ; ListHeader struc NumberObjects dq ? MaximumObjects dq ? FreeSpace dq ? ListHeader ends ListItem struc Object dq ? ListItem ends .code ; ; You need to specify a function called _DllMainCRTStartup (in 'C' is ; DllMain - called by the C runtime system). For this DLL, we are not ; interested if its a process attach, detach, or thread attach, detach ; We simply return a 1, which fundamentally says continue with the task ; _DllMainCRTStartup: mov rax, 1 ret ; ; This is the entry point for the creation of the list. The function ; simply expects the maximum number of entries that the list can ; contain. The function allocates space of the objects in the list, sets ; up the list header and returns the start of the allocation block to ; the caller. ; CreateList: push rbx push r15 sub rsp, 32 mov r15, rdx mov rax, SIZE ListItem imul rcx mov rdx, rax add rdx, SIZE ListHeader xor rcx, rcx mov r8, 1000H mov r9, 4H call qword ptr [__imp_VirtualAlloc] mov rbx, SIZE ListHeader add rbx, rax mov ListHeader.MaximumObjects[rax], r15 mov ListHeader.FreeSpace[rax], rbx add rsp, 32 pop r15 pop rbx ret ; ; This is the entry point for the addition of an item into the list. It ; is the address of the item that goes into the list, not the object ; itself. The address is always added to the end of the list. ; ; The caller supplies the pointer to the list (returned from the call to ; CreateList) and the address of the object to be added to the list. ; AddItem: push r14 mov rax, ListHeader.FreeSpace[rcx] mov r14, SIZE ListItem add r14, rax mov ListHeader.FreeSpace[rcx], r14 inc ListHeader.NumberObjects[rcx] mov ListItem.Object[rax], rdx pop r14 ret ; ; Return the number of items active in the list. The caller supplies the ; pointer to the list (returned from the call to CreateList), and the ; number of items is returned. ; GetNumberItems: mov rax, ListHeader.NumberObjects[rcx] ret ; ; Get the address of an item in the list. The caller supplies the pointer ; to the list (returned from the call to CreateList), and the item index ; of the item to retrieve. The funtion returns the address of the object ; located at the requested position in the list. If the item index is ; outside the bounds of the list, NULL is returned. ; GetItem: xor rax, rax cmp ListHeader.NumberObjects[rcx], rdx jb GetItemReturn shl rdx, 3 add rdx, SIZE ListHeader add rdx, rcx mov rax, qword ptr [rdx] GetItemReturn: ret ; ; Insert an item in the list. The caller supplies the pointer to the list ; (returned from the call to CreateList), and the item index of the item ; before which the new item will be inserted. There is no return value. ; ; The routine has to move all the items from the supplied index to the last ; item in the list (i.e. index to index + 1, index + 2 to index + 2 etc). ; The moving of items is performed backwards. ; InsertItem: push r13 push r14 xor rax, rax cmp ListHeader.NumberObjects[rcx], rdx jb InsertItemReturn mov r14, ListHeader.NumberObjects[rcx] mov r13, r14 sub r14, rdx inc r14 inc ListHeader.NumberObjects[rcx] shl r13, 3 add r13, SIZE ListHeader add r13, rcx InsertNextEntry: mov rax, qword ptr [r13] mov qword ptr 8[r13], rax sub r13, 8 dec r14 jne InsertNextEntry mov qword ptr 8[r13], r8 InsertItemReturn: pop r14 pop r13 ret ; ; Delete an item in the list. The caller supplies the pointer to the list ; (returned from the call to CreateList), and the item index of the item ; being deleted. There is no return value. ; ; The routine has to move all the items from the supplied index to the last ; item in the list (i.e. index + 1 to index, index + 2 to index + 1 etc). ; The moving of items is performed forwards. ; DeleteItem: push r13 push r14 xor rax, rax cmp ListHeader.NumberObjects[rcx], rdx jbe DeleteItemReturn mov r14, ListHeader.NumberObjects[rcx] sub r14, rdx inc r14 dec ListHeader.NumberObjects[rcx] mov r13, rdx shl r13, 3 add r13, SIZE ListHeader add r13, rcx DeleteNextEntry: mov rax, qword ptr 8[r13] mov qword ptr [r13], rax add r13, 8 dec r14 jne DeleteNextEntry DeleteItemReturn: pop r14 pop r13 ret end
Here is the linker definition (.def) file.
LIBRARY EXPORTS CreateList @1 AddItem @2 GetNumberItems @3 GetItem @4 InsertItem @5 DeleteItem @6
Here are the 'C' prototypes should you wish to compile and test the routines.
extern "C" void * __stdcall CreateList(unsigned long long count); extern "C" void __stdcall AddItem(void * list, void * item); extern "C" unsigned long __stdcall GetNumberItems(void * list); extern "C" void * __stdcall GetItem(void * list, unsigned long item); extern "C" void __stdcall InsertItem(void * list, unsigned long item, void * object); extern "C" void __stdcall DeleteItem(void * list, unsigned long item);
This post has been edited by Martyn.Rae: 22 November 2018 - 10:01 AM
MultiQuote
| 