Linked lists in PAWN -
BigETI - 19.07.2013
list.inc
Linked lists in PAWN
About
This include allows you to create linked lists, where data can be stored into almost "infinite amount" (depends on your memory) of nodes.
Those nodes also allow you to store data with different sizes into different nodes.
Why?
As I've released this plugin, which allows you to access dynamic memory, so I've thought about an actual use of this plugin by making this include.
Also it can become useful for some of you.
Documentation
Stocks
Quote:
ListIt:LIST_push_back(List:list[], value) - Description:
- Adds a node at the end of a linked list.
- Returns an address of the created node, otherwise ListIt:0.
- LIST::push_back() can be used aswell!
- Usage:
- Example:
pawn Код:
new LIST_init<my_list>; // Declare an empty list and NULL initialize it LIST_push_back(my_list, 10); // Create a node at the end
|
Quote:
ListIt:LIST_push_back_arr(List:list[], arr[], arr_size = sizeof arr) - Description:
- Adds a node at the end of a linked list.
- Returns an address of the created node, otherwise ListIt:0.
- LIST::push_back_arr() can be used aswell!
- Usage:
- Example:
pawn Код:
new LIST_init<my_list>; // Declare an empty list and NULL initialize it LIST_push_back_arr(my_list, {2, 4, 6, 8, 10}); // Create a node of an array at the end
|
Quote:
ListIt:LIST_pop_back(List:list[]) - Description:
- Removes the last created node.
- Returns the address of the new last node, otherwise ListIt:0.
- LIST::pop_back() can be used aswell!
- Usage:
- Example:
pawn Код:
new LIST_init<my_list>; // Declare an empty list and NULL initialize it LIST_push_back_arr(my_list, 10); // Create a node at the end LIST_pop_back(my_list); // Remove the last node
|
Quote:
ListIt:LIST_push_front(List:list[], value) - Description:
- Adds a node at the beginning of a linked list.
- Returns an address of the created node, otherwise ListIt:0.
- LIST::push_front() can be used aswell!
- Usage:
- Example:
pawn Код:
new LIST_init<my_list>; // Declare an empty list and NULL initialize it LIST_push_front(my_list, 10); // Create a node at the beginning
|
Quote:
ListIt:LIST_push_front_arr(List:list[], arr[], arr_size = sizeof arr) - Description:
- Adds a node at the beginning of a linked list.
- Returns an address of the created node, otherwise ListIt:0.
- LIST::push_front_arr() can be used aswell!
- Usage:
- Example:
pawn Код:
new LIST_init<my_list>; // Declare an empty list and NULL initialize it LIST_push_front_arr(my_list, {2, 4, 6, 8, 10}); // Create a node of an array at the beginning
|
Quote:
ListIt:LIST_pop_front(List:list[]) - Description:
- Removes a node at the beginning of a linked list.
- Returns the address of the new beginning, otherwise ListIt:0.
- LIST::pop_front() can be used aswell!
- Usage:
- Example:
pawn Код:
new LIST_init<my_list>; // Declare an empty list and NULL initialize it LIST_push_front(my_list, 10); // Create a node at the beginning LIST_pop_front(my_list); // Remove the node at the beginning
|
Quote:
ListIt:LIST_insert(List:list[], ListIt:node, value) - Description:
- Adds a node at a certain position, and uses the older one as the next one.
- Returns the address of the newly created node, otherwise ListIt:0.
- LIST::insert() can be used aswell!
- Usage:
- Example:
pawn Код:
new LIST_init<my_list>; // Declare an empty list and NULL initialize it new ListIt:something = LIST_push_back(my_list, 10); // Create a node at the end LIST_insert(my_list, something, 10); // Add a node at a certain position, and use the older node as the next one
|
Quote:
ListIt:LIST_insert_arr(List:list[], ListIt:node, arr[], arr_size = sizeof arr) - Description:
- Adds a node at a certain position, and uses the older one as the next one.
- Returns the address of the newly created node, otherwise ListIt:0.
- LIST::insert_arr() can be used aswell!
- Usage:
- Example:
pawn Код:
new LIST_init<my_list>; // Declare an empty list and NULL initialize it new ListIt:something = LIST_push_back(my_list, 10); // Create a node at the end LIST_insert_arr(my_list, something, {2, 4, 6, 8, 10}); // Add a node of an array at a certain position, and use the older node as the next one
|
Quote:
ListIt:LIST_erase(List:list[], ListIt:node) - Description:
- Removes a specified node.
- Returns the address of the next node, otherwise ListIt:0.
- LIST::erase() can be used aswell!
- Usage:
- Example:
pawn Код:
new LIST_init<my_list>; // Declare an empty list and NULL initialize it new ListIt:something = LIST_push_back(my_list, 10); // Create a node at the end LIST_insert(my_list, something, 10); // Add a node at a certain position, and use the older node as the next one
|
Quote:
ListIt:LIST_find(List:list[], value, index = 0, bool:reverse = false, jump = 0) - Description:
- Returns the node, where the value has been found respectively depends on index and how many times it should jump over a result, otherwise ListIt:0.
- LIST::find() can be used aswell!
- Usage:
- Example:
pawn Код:
new LIST_init<my_list>; // Declare an empty list and NULL initialize it LIST_push_back(my_list, 10); // Create a node at the end LIST_push_back(my_list, 5); // Create a node at the end LIST_push_back(my_list, 8); // Create a node at the end LIST_push_back(my_list, 20); // Create a node at the end LIST_find(my_list, 8); // Finds the node
|
Quote:
ListIt:LIST_find_arr(List:list[], arr[], arr_size = sizeof arr, index = 0, bool:reverse = false, jump = 0) - Description:
- Returns the node, where the array has been found respectively depends on index and how many times it should jump over a result, otherwise ListIt:0.
- LIST::find_arr() can be used aswell!
- Usage:
- Example:
pawn Код:
new LIST_init<my_list>; // Declare an empty list and NULL initialize it LIST_push_back_arr(my_list, {10, 2}); // Create a node at the end LIST_push_back_arr(my_list, {5, 2, 4, 8}); // Create a node at the end LIST_push_back_arr(my_list, {8, 4, 8, 6}); // Create a node at the end LIST_push_back_arr(my_list, {2, 4, 6}); // Create a node at the end LIST_find_arr(my_list, {4, 6}, _, 1); // Finds the node
|
Quote:
LIST_count_found(List:list[], value, index = 0) - Description:
- Returns the amount of found results.
- LIST::count_found() can be used aswell!
- Usage:
- Example:
pawn Код:
new LIST_init<my_list>; // Declare an empty list and NULL initialize it LIST_push_back(my_list, 2); // Create a node at the end LIST_push_back(my_list, 2); // Create a node at the end LIST_push_back(my_list, 8); // Create a node at the end LIST_push_back(my_list, 2); // Create a node at the end LIST_count_found(my_list, 2); // Returns the amount of founds
|
Quote:
LIST_count_found_arr(List:list[], value, index = 0) - Description:
- Returns the amount of found results.
- LIST::count_found_arr() can be used aswell!
- Usage:
- Example:
pawn Код:
new LIST_init<my_list>; // Declare an empty list and NULL initialize it LIST_push_back_arr(my_list, {2, 3, 4, 5}); // Create a node at the end LIST_push_back_arr(my_list, {2, 4, 4, 8}); // Create a node at the end LIST_push_back_arr(my_list, {8, 2, 5}); // Create a node at the end LIST_push_back_arr(my_list, {2, 3, 6}); // Create a node at the end LIST_count_found_arr(my_list, {2, 3}); // Returns the amount of founds
|
Quote:
LIST_sort(List:list[], bool:descending = false) - Description:
- Sorts a list in an ascending or descending order.
- LIST::sort() can be used aswell!
- Usage:
- Example:
pawn Код:
new LIST_init<my_list>; // Declare an empty list and NULL initialize it LIST_push_back_arr(my_list, {2, 3, 4, 5}); // Create a node at the end LIST_push_back_arr(my_list, {2, 4, 4, 8}); // Create a node at the end LIST_push_back_arr(my_list, {8, 2, 5}); // Create a node at the end LIST_push_back_arr(my_list, {2, 3, 6}); // Create a node at the end LIST_sort(my_list); // Sorts the list ascending
|
Quote:
LIST_count_nodes(List:list[]) - Description:
- Returns the amount of available nodes in a list.
- LIST::count_nodes() can be used aswell!
- Usage:
- Example:
pawn Код:
new LIST_init<my_list>; // Declare an empty list and NULL initialize it LIST_push_back_arr(my_list, {2, 3, 4, 5}); // Create a node at the end LIST_push_back_arr(my_list, {2, 4, 4, 8}); // Create a node at the end LIST_push_back_arr(my_list, {8, 2, 5}); // Create a node at the end LIST_push_back_arr(my_list, {2, 3, 6}); // Create a node at the end printf(" Nodes: %d", LIST_count_nodes(my_list)); // Returns the amount of available nodes
|
Quote:
LIST_get_data_cell_size(List:list[]) - Description:
- Returns the amount of cells (data only) taking space in a list.
- LIST::get_data_cell_size() can be used aswell!
- Usage:
- Example:
pawn Код:
new LIST_init<my_list>; // Declare an empty list and NULL initialize it LIST_push_back_arr(my_list, {2, 3, 4, 5}); // Create a node at the end LIST_push_back_arr(my_list, {2, 4, 4, 8}); // Create a node at the end LIST_push_back_arr(my_list, {8, 2, 5}); // Create a node at the end LIST_push_back_arr(my_list, {2, 3, 6}); // Create a node at the end printf(" Data in cells: %d", LIST_get_data_cell_size(my_list)); // Returns the amount of cells (data only)
|
Quote:
LIST_get_all_cell_size(List:list[]) - Description:
- Returns the amount of cells (data + info) taking space in a list.
- LIST::get_all_cell_size() can be used aswell!
- Usage:
- Example:
pawn Код:
new LIST_init<my_list>; // Declare an empty list and NULL initialize it LIST_push_back_arr(my_list, {2, 3, 4, 5}); // Create a node at the end LIST_push_back_arr(my_list, {2, 4, 4, 8}); // Create a node at the end LIST_push_back_arr(my_list, {8, 2, 5}); // Create a node at the end LIST_push_back_arr(my_list, {2, 3, 6}); // Create a node at the end printf(" Data in cells: %d", LIST_get_all_cell_size(my_list)); // Returns the amount of cells (data + info)
|
Quote:
LIST_clear(List:list[]) - Description:
- Clears the whole list.
- Returns nothing.
- LIST::clear() can be used aswell!
- Usage:
- Example:
pawn Код:
new LIST_init<my_list>; // Declare an empty list and NULL initialize it LIST_push_back(my_list, 10); // Create a node at the end LIST_push_back(my_list, 20); // Create a node at the end LIST_push_back(my_list, 30); // Create a node at the end LIST_push_back(my_list, 40); // Create a node at the end LIST_push_back(my_list, 50); // Create a node at the end LIST_clear(my_list); // Clear the whole list
|
Quote:
bool:LIST_copy(List:dest_list[], List:src_list[]) - Description:
- Copies a whole list.
- Returns true if successful, otherwise false.
- LIST::copy() can be used aswell!
- Usage:
- Example:
pawn Код:
new LIST_init<my_list_1>; // Declare an empty list and NULL initialize it new LIST_init<my_list_2>; // Declare an empty list and NULL initialize it LIST_push_back(my_list_1, 10); // Create a node at the end LIST_push_back(my_list_1, 20); // Create a node at the end LIST_push_back(my_list_1, 30); // Create a node at the end LIST_push_back(my_list_1, 40); // Create a node at the end LIST_push_back(my_list_1, 50); // Create a node at the end LIST_copy(my_list_2, my_list_1); // Copies a whole list
|
Quote:
bool:LIST_save(List:list[], file_name[], bool:clear = false) - Description:
- Saves a list into a file.
- Returns "true" if successful, otherwise "false".
- "clear" defines, if the list should be cleared afterwards. ("false" by default)
- LIST::save() can be used aswell!
- Usage:
- Example:
pawn Код:
new LIST_init<my_list>; // Declare an empty list and NULL initialize it LIST_push_back(my_list, 10); // Create a node at the end LIST_push_back(my_list, 20); // Create a node at the end LIST_push_back(my_list, 30); // Create a node at the end LIST_push_back(my_list, 40); // Create a node at the end LIST_push_back(my_list, 50); // Create a node at the end LIST_save(my_list, "my_list.binlist"); // Saves the list
|
Quote:
bool:LIST_load(List:list[], file_name[], bool:rewrite = true) - Description:
- Loads a list from a file.
- Returns "true" if successful, otherwise "false".
- "rewrite" defines, if the list should be cleared before loading the data. ("true" by default)
- LIST::load() can be used aswell!
- Usage:
- Example:
pawn Код:
new LIST_init<my_list>; // Declare an empty list and NULL initialize it LIST_load(my_list, "my_list.binlist"); // Loads the list
|
Constants
Quote:
LIST_file_header[] - Description:
- Returns the file header used by LIST_save() and LIST_load().
- Each cell represents 1 byte.
- LIST::file_header[] can be used aswell!
|
Macros
Quote:
LIST_init<list_name> - Description:
- Declares an empty list and NULL initializes it.
- LIST::init<> can be used aswell!
- Usage:
- Example:
pawn Код:
new LIST_init<my_list>; // Declare an empty list and NULL initialize it
|
Quote:
ListIt: LIST_begin(List:list[]) - Description:
- Returns the address of the first node.
- LIST::begin() can be used aswell!
- Usage:
- Example:
pawn Код:
new LIST_init<my_list>; // Declare an empty list and NULL initialize it LIST_push_back(my_list, 10); // Create a node at the end LIST_push_back(my_list, 20); // Create a node at the end printf(" Address: 0x%x", _:LIST_begin(list_name)); // Shows the address of the first node
|
Quote:
ListIt: LIST_end(List:list[]) - Description:
- Returns the address of the last node.
- LIST::end() can be used aswell!
- Usage:
- Example:
pawn Код:
new LIST_init<my_list>; // Declare an empty list and NULL initialize it LIST_push_back(my_list, 10); // Create a node at the end LIST_push_back(my_list, 20); // Create a node at the end printf(" Address: 0x%x", _:LIST_end(list_name)); // Shows the address of the last node
|
Quote:
bool: LIST_exist(List:list[], value, index = 0, bool:reverse = false, jump = 0) - Description:
- Checks, if found.
- LIST::exist() can be used aswell!
- Usage:
- Example:
pawn Код:
new LIST_init<my_list>; // Declare an empty list and NULL initialize it LIST_push_back(my_list, 10); // Create a node at the end LIST_push_back(my_list, 20); // Create a node at the end if(LIST_exist(my_list, 20)) // Check, if found { // ... }
|
Quote:
Pointer: LIST_IT_data_ptr(ListIt:node) - Description:
- Returns the pointer of the stored data.
- LIST_IT::data_ptr() can be used aswell!
- Usage:
- Example:
pawn Код:
new LIST_init<my_list>; // Declare an empty list and NULL initialize it LIST_push_back(my_list, 10); // Create a node at the end LIST_push_back(my_list, 20); // Create a node at the end printf(" Address: 0x%x", _:LIST_IT_data_ptr(LIST_end(list_name))); // Shows the address of the stored data at the last node
|
Quote:
LIST_IT_data_val(ListIt:node, index) - Description:
- Returns an indexed data from a node.
- LIST_IT::data_val() can be used aswell!
- Usage:
- Example:
pawn Код:
new LIST_init<my_list>; // Declare an empty list and NULL initialize it LIST_push_back(my_list, 10); // Create a node at the end LIST_push_back(my_list, 20); // Create a node at the end printf(" Value: %d", LIST_IT_data_val(LIST_end(list_name))); // Shows the stored data of the last node
|
Quote:
ListIt: LIST_IT_next(ListIt:node) - Description:
- Returns the address of the next node.
- LIST_IT::next() can be used aswell!
- Usage:
- Example:
pawn Код:
new LIST_init<my_list>; // Declare an empty list and NULL initialize it LIST_push_back(my_list, 10); // Create a node at the end LIST_push_back(my_list, 20); // Create a node at the end LIST_foreach<my_iterator>(my_list) // Loops through all nodes { new ListIt:something = LIST_IT_next(my_iterator); // Returns the address of the next node }
|
Quote:
ListIt: LIST_IT_previous(ListIt:node) - Description:
- Returns the address of the previous node.
- LIST_IT::previous() can be used aswell!
- Usage:
- Example:
pawn Код:
new LIST_init<my_list>; // Declare an empty list and NULL initialize it LIST_push_back(my_list, 10); // Create a node at the end LIST_push_back(my_list, 20); // Create a node at the end LIST_foreach<my_iterator>(my_list) // Loops through all nodes { new ListIt:something = LIST_IT_previous(my_iterator); // Returns the address of the previous node }
|
Quote:
LIST_IT_data_size(ListIt:node) - Description:
- Returns the size of the data inside a node.
- LIST_IT::data_size() can be used aswell!
- Usage:
- Example:
pawn Код:
new LIST_init<my_list>; // Declare an empty list and NULL initialize it LIST_push_back(my_list, 10); // Create a node at the end LIST_push_back(my_list, 20); // Create a node at the end LIST_foreach<my_iterator>(my_list) // Loops through all nodes { printf(" Data size: %d", LIST_IT_data_size(my_iterator)) // Returns the size of the data inside the node }
|
Quote:
LIST_foreach<ListIt:iterator>(List:list[]) - Description:
- Loops through all nodes inside a list.
- Do NOT declare "ListIt:iterator" by yourself! The macro itself will already declare it for you.
- LIST_IT::foreach<>() can be used aswell!
- Usage:
- Example:
pawn Код:
new LIST_init<my_list>; // Declare an empty list and NULL initialize it LIST_push_back_arr(my_list, {10, 20, 30}); // Create a node of an array at the end LIST_push_back_arr(my_list, {100, 200, 300}); // Create a node of an array at the end new Pointer:data_ptr; LIST_foreach<my_iterator>(my_list) // Loops through all nodes { data_ptr = LIST_IT_data_ptr(my_iterator); printf(" Values: %d | %d | %d", MEM_EX::get_val(data_ptr->0), MEM_EX::get_val(data_ptr->1), MEM_EX::get_val(data_ptr->2)) // Returns an indexed data inside the node }
|
Quote:
LIST_foreach_rev<ListIt:iterator>(List:list[]) - Description:
- Loops through all nodes inside a list (reversed).
- Do NOT declare "ListIt:iterator" by yourself! The macro itself will already declare it for you.
- LIST_IT::foreach_rev<>() can be used aswell!
- Usage:
- Example:
pawn Код:
new LIST_init<my_list>; // Declare an empty list and NULL initialize it LIST_push_back_arr(my_list, {10, 20, 30}); // Create a node of an array at the end LIST_push_back_arr(my_list, {100, 200, 300}); // Create a node of an array at the end new Pointer:data_ptr; LIST_foreach_rev<my_iterator>(my_list) // Loops through all nodes { data_ptr = LIST_IT_data_ptr(my_iterator); printf(" Values: %d | %d | %d", MEM_EX::get_val(data_ptr->0), MEM_EX::get_val(data_ptr->1), MEM_EX::get_val(data_ptr->2)) // Returns an indexed data inside the node }
|
Setup
First you need this plugin: Memory access plugin
After that just download list.inc, put it into your server includes, and put this on top of your script:
pawn Код:
// On top of your script
#include <list>
// Your code
Compile and run.
Downloads
Changelog
Quote:
- v1.2.1 -> Fixed LIST_erase() ( 18.01.2014 )
- v1.2 -> Added more functions again ( LIST_copy(), LIST_save(), and LIST_load() ) and a macro ( LIST_IT_data_val() ) (17.10.2013)
- v1.1 -> Added more functions, improved macros, fixed LIST_insert() and LIST_insert_arr() ( 21.07.2013 )
- v1.0 -> Initial release ( 19.07.2013 )
|
Credits
Quote:
- BigETI for the memory access plugin and this include
- SA:MP development team
|
Best Regards
~ BigETI
Re: Linked lists in PAWN -
RajatPawar - 19.07.2013
Yes, nice work! Finally good to see my reply was seen! This is awesome. I'll test it soon and let you know about it!
Re: Linked lists in PAWN -
SsHady - 19.07.2013
Epic
Gonna test it right away !!
Re: Linked lists in PAWN -
Richard_Gere - 19.07.2013
delete
Re: Linked lists in PAWN -
Black Wolf - 19.07.2013
Awesome bro.Good Job.
Re: Linked lists in PAWN -
Red_Dragon. - 19.07.2013
Great work!
Re: Linked lists in PAWN -
MP2 - 19.07.2013
Good work. I was actually wanting something like this about two weeks ago, and now like magic it's here.
Re: Linked lists in PAWN -
Richard_Gere - 19.07.2013
By the way would be a function
LIST::find(List:list[], value).
AW: Re: Linked lists in PAWN -
BigETI - 19.07.2013
I appreciate all of your comments.
Quote:
Originally Posted by Richard_Gere
By the way would be a function LIST::find(List:list[], value).
|
Don't worry, I'll add much more functions for this include. Just keep suggesting me more functions to add.
Re: Linked lists in PAWN -
Richard_Gere - 19.07.2013
pawn Код:
LIST::find(List:list[], value); // return address of node list[] with value
LIST::exists(List:list[], value); // If value exists in list
LIST::sort(List:list[], type = SORT_TYPE_ASCENDING/SORT_TYPE_DESCENDING); // Sorting
LIST::size(List:list[]); // Return size of list
I'm testing include with vector and got the result: (100000 iterations and 500 nodes)
pawn Код:
Vectors: 70683 ms
Lists: 11472 ms
Result very good
AW: Linked lists in PAWN -
BigETI - 21.07.2013
Updated, see main post.
Re: Linked lists in PAWN -
Bakr - 21.07.2013
Very nicely done!
Any plans for other data structures?
Re: Linked lists in PAWN -
DanielCortez - 22.07.2013
It would be very interesting to see some speed comparsions against foreach.inc by ****** (especially under JIT).
btw, nice job =)
Re: Linked lists in PAWN -
Maxips2 - 24.07.2013
Any speed comparisons against other CSTL data containers plugins?
Great release btw.
AW: Re: Linked lists in PAWN -
BigETI - 24.07.2013
Quote:
Originally Posted by Maxips2
Any speed comparisons against other CSTL data containers plugins?
Great release btw.
|
Thanks.
Can you give me links to compare this release with similar ones, which are released on this forum, please?
Re: AW: Re: Linked lists in PAWN -
Maxips2 - 24.07.2013
Quote:
Originally Posted by BigETI
Thanks.
Can you give me links to compare this release with similar ones, which are released on this forum, please?
|
The only two that I have seen are the following:
Vectoral Pawn - STL Data containers for pawn - By Rancho
https://sampforum.blast.hk/showthread.php?tid=364285
CSTL - VECTOR AND MAP FOR PAWN - By Teprey
https://sampforum.blast.hk/showthread.php?tid=238844
Re: Linked lists in PAWN -
Richard_Gere - 25.07.2013
Quote:
Originally Posted by Maxips2
Any speed comparisons against other CSTL data containers plugins?
Great release btw.
|
My tests showed that the linked lists in ~7 times faster
AW: Linked lists in PAWN -
BigETI - 17.10.2013
Updated, see main post.
Re: Linked lists in PAWN -
wups - 19.10.2013
Nice, now you could make one with stacks.
AW: Linked lists in PAWN -
BigETI - 19.10.2013
It's actually possible to created nested lists. Maybe I should write a tutorial about it... :/