bigeti / pawn-map

Hash-map implementation in PAWN

Hash-map implementation in PAWN

Description

This is a map data structure implementation in PAWN using binary search tree. Detailed documentation can be checked out at the wiki.

Installation

Using sampctl

1. Get sampctl from https://github.com/Southclaws/sampctl
2. Install package using this command:

sampctl package install BigETI/pawn-map

3. Include library in your PAWN code

#include <map>

Manually

1. Get pawn-memory from https://github.com/BigETI/pawn-memory
2. Move or copy map.inc to your PAWN includes directory
3. Include library in your PAWN code

#include <map>

Dependencies

• https://github.com/BigETI/pawn-memory
• https://github.com/sampctl/pawn-stdlib

Documentation

You can find the documentation here: https://github.com/BigETI/pawn-map/wiki

Licence

You can find the licence here: https://github.com/BigETI/pawn-map/blob/master/LICENCE.md

How to contribute to this project?

Just create a fork out of this project, make your changes and create a pull request.

pawn-map's Issues

Add options for tree traversal

• Pre-order
• In-order
• Post-order
• Reverse pre-order
• Reverse in-order
• Reverse post-order

Fix deep-recursive function calls

Some operations, such as for example MAP_clear, MAP_remove_found, MAP_count, and MAP_iter_next, will cause runtime errors, due to deep-recursive function calls.

Reduce memory fragmentation

The current implementation causes fragmented memory allocation, causing issues, such as for example cache misses, and excessive de-reference operations, even if a value is a scalar.

Implement red-black tree to optimize search

Insertion and search takes in a worst case scenario would take from O(n) (current) to O(log n).

Implement non-hashed binary search tree back

This would allow to traverse through a tree for example in-order to get the elements in a sorted order.

Update documentation

I need to document this release according to http://forum.sa-mp.com/showthread.php?t=381784

Better function names.

About

This is just an appraisal, stumbled across this plugin and I felt like the function names isn't precise and confusing to new users (I was confused as well until I looked at test.pwn and the source code, having redundant names such as arr_arr, str_str, val_val.

Solution:

#define new_name old_name

Transition

old name -> new name
MAP_insert_val_val -> Map_InsertValue
MAP_insert_val_arr -> Map_InsertValueArray
MAP_insert_arr_val -> Map_InsertArrayValue
MAP_insert_arr_arr -> Map_InsertArray

MAP_insert_str_str -> Map_InsertString
MAP_insert_str_val -> Map_InsertStringValue
MAP_insert_val_str -> Map_InsertValueString
MAP_insert_arr_str -> Map_InsertValueArray
MAP_insert_str_arr -> Map_InsertStringArray

MAP_get_ptr_val -> Map_GetPointerValue
MAP_get_ptr_arr -> Map_GetPointerArray
MAP_get_ptr_str -> Map_GetPointerString

MAP_contains_val -> Map_ContainsValue
MAP_contains_arr -> Map_ContainsArray
MAP_contains_str -> Map_ContainsString

MAP_get_val_val -> Map_GetValue
MAP_get_val_arr -> Map_GetValueArray
MAP_get_arr_val -> Map_GetArrayValue
MAP_get_arr_arr -> Map_GetArray
MAP_get_str_val -> Map_GetStringValue
MAP_get_str_arr -> Map_GetStringArray


MAP_remove_val -> Map_RemoveValue	
MAP_remove_arr -> Map_RemoveArray
MAP_remove_str -> Map_RemoveString

MAP_count -> Map_Count
MAP_clear -> Map_Clear
MAP_iter_get -> Map_IterGet
MAP_iter_next -> Map_IterNext

Key not found after using MAP_remove_val on another key.

Hy,
first I want to thank you for this awesome plugin. I have been using it in my new SA:MP mode im working on...
I found bug in plugin, after using MAP_remove_val with some key, another key from map becomes unavaliable too...

Example:

static DoTestMap()
{
	new Map:TestMap;

	MAP_insert_val_val(TestMap, 19, 2);
	MAP_insert_val_val(TestMap, 20, 3);
	MAP_insert_val_val(TestMap, 22, 4);
	MAP_insert_val_val(TestMap, 23, 5);
	MAP_insert_val_val(TestMap, 24, 6);
	MAP_insert_val_val(TestMap, 25, 7);

	MAP_remove_val(TestMap, 22);
	printf("map contains 24 [%d]", MAP_contains_val(TestMap, 24));
	MAP_insert_val_val(TestMap, 22, 4);
	printf("map contains 24 [%d]", MAP_contains_val(TestMap, 24));
	MAP_remove_val(TestMap, 23);
        // After removing key 23, key 24 starts to become unavaliable too...
	printf("map contains 24 [%d]", MAP_contains_val(TestMap, 24));
	MAP_insert_val_val(TestMap, 23, 5);
	printf("map contains 24 [%d]", MAP_contains_val(TestMap, 24));

}

Are you still maintaining this plugin ? Im not sure if I will be able to fix this problem...