[Include] Linked lists in PAWN
#1

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
Reply
#2

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!
Reply
#3

Epic
Gonna test it right away !!
Reply
#4

delete
Reply
#5

Awesome bro.Good Job.
Reply
#6

Great work!
Reply
#7

Good work. I was actually wanting something like this about two weeks ago, and now like magic it's here.
Reply
#8

By the way would be a function LIST::find(List:list[], value).
Reply
#9

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.
Reply
#10

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
Reply
#11

Updated, see main post.
Reply
#12

Very nicely done!

Any plans for other data structures?
Reply
#13

It would be very interesting to see some speed comparsions against foreach.inc by ****** (especially under JIT).

btw, nice job =)
Reply
#14

Any speed comparisons against other CSTL data containers plugins?
Great release btw.
Reply
#15

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?
Reply
#16

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
Reply
#17

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
Reply
#18

Updated, see main post.
Reply
#19

Nice, now you could make one with stacks.
Reply
#20

It's actually possible to created nested lists. Maybe I should write a tutorial about it... :/
Reply


Forum Jump:


Users browsing this thread: 1 Guest(s)