Raised This Month: $51 Target: $400
 12% 

The advantages of a trie over an array for strings storage


Post New Thread Reply   
 
Thread Tools Display Modes
Dores
Veteran Member
Join Date: Jun 2008
Location: You really don't wanna k
Old 04-16-2009 , 15:12   Re: The advantages of a trie over an array for strings storage
Reply With Quote #31

263 is incomparable to other plugins' downloads, especially since my plugin is out for such a long time, but I'm getting off-topic here.
__________________
O o
/Ż________________________
| IMMA FIRIN' MAH LAZOR!!!
\_ŻŻŻ
Dores is offline
Mlk27
Veteran Member
Join Date: May 2008
Old 04-17-2009 , 00:03   Re: The advantages of a trie over an array for strings storage
Reply With Quote #32

Hey Joaq (hope you don' mind I call you this since your name is too long lol)

OK so I've just finish reading this tutorial but I can't figure out how to convert 2 array which entries position are correspond to entries in both arrays into trie

like

Code:
array: steamid array:owner(name) steam_01222:_bla bla    joaq steam_0666:_bla bla    james

Code:
        static szName[32], szAuth[35], szBuffer[128] //         while(!feof(hFile))         {             fgets(hFile, szBuffer, charsmax(szBuffer))             trim(szBuffer)             if(!szBuffer[0] || szBuffer[0] == ';' || (szBuffer[0] == '/' && szBuffer[1] == '/' ))                 continue             parse(szBuffer, szAuth, charsmax(szAuth), szName, charsmax(szName))             if(szName[0] && szAuth[0])             {                 ArrayPushString(g_hNameArray, szName)                 ArrayPushString(g_hAuthArray, szAuth)             }         }

Code:
CheckName(iClient, szName[], szAuth[]) {     new iSize = min(ArraySize(g_hNameArray), ArraySize(g_hAuthArray))     static szTempName[32], szTempAuth[35] //     for(new i=0; i < iSize; i++)     {         ArrayGetString(g_hNameArray, i, szTempName, charsmax(szTempName))         ArrayGetString(g_hAuthArray, i, szTempAuth, charsmax(szTempAuth))         if(equali(szTempName, szName))         {             if(equali(szTempAuth, szAuth)) g_iRegistered[iClient] = 1             return equali(szTempAuth, szAuth)         }     }     g_iRegistered[iClient] = 0     return true }


Check the ampaste link I sent you for full codes

Last edited by Mlk27; 04-17-2009 at 00:07.
Mlk27 is offline
Old 04-17-2009, 00:21
joaquimandrade
This message has been deleted by joaquimandrade.
Old 04-17-2009, 00:59
joaquimandrade
This message has been deleted by joaquimandrade. Reason: Forget this. I'm working on it
ConnorMcLeod
Veteran Member
Join Date: Jul 2006
Location: France (95)
Old 04-17-2009 , 01:05   Re: The advantages of a trie over an array for strings storage
Reply With Quote #33

Seems to check if a specific name is registered, and in that case if it's the same steamid of the actual player, seems to be a name reservation.
__________________
- tired and retired -

- my plugins -
ConnorMcLeod is offline
joaquimandrade
Veteran Member
Join Date: Dec 2008
Location: Portugal
Old 04-17-2009 , 01:11   Re: The advantages of a trie over an array for strings storage
Reply With Quote #34

Quote:
Originally Posted by ConnorMcLeod View Post
Seems to check if a specific name is registered, and in that case if it's the same steamid of the actual player, seems to be a name reservation.
Yes. It checks if a reserved name belongs to a specified player.
__________________
joaquimandrade is offline
joaquimandrade
Veteran Member
Join Date: Dec 2008
Location: Portugal
Old 04-17-2009 , 01:41   Re: The advantages of a trie over an array for strings storage
Reply With Quote #35

Here it goes the code. I didn't test it and i will not since you have to do it by yourself to understand.
(read first the explanation below)

PHP Code:
#include <amxmodx>
#include <amxmisc>

enum _:AuthField
{
    
AuthField_Names,
    
AuthField_NamesCount
}

new 
Trie:AuthsData
new Trie:AllNames

new g_szSteamFile[64]
new 
cvNameChangeKick
new cvConnectKick
new cvRenameTries

new g_iChangeName[33]
new 
g_iRegistered[33]


public 
plugin_cfg()
{
    
AuthsData TrieCreate();
    
AllNames TrieCreate();
}

public 
plugin_natives()
{
    
register_native("is_user_registered""native_is_user_registered")
}

public 
plugin_init()
{
    
get_configsdir(g_szSteamFilecharsmax(g_szSteamFile))
    
add(g_szSteamFilecharsmax(g_szSteamFile), "/steamidname.txt")

    
LoadNames(true)

    
register_concmd("nr_reload""cmd_ReloadName"ADMIN_RCON)
    
register_clcmd("nr_check""cmd_CheckRegister")

    
cvNameChangeKick register_cvar("nr_change_kick""1")
    
cvConnectKick register_cvar("nr_connect_kick""1")
    
cvRenameTries register_cvar("nr_rename_tries""5")
}

public 
cmd_ReloadName(idlevelcid)
{
    if(
cmd_access(idlevelcid1))
    {
        
console_print(id"[AMXX] %d name reservations loaded"LoadNames())

        
// Recheck all players' names
        
static iPlayers[32], iNum //
        
get_players(iPlayersiNum)

        for(new 
i=0iNum;i++)
            
client_putinserver(iPlayers[i])
    }

    return 
PLUGIN_HANDLED
}

public 
cmd_CheckRegister(id)
{
    new 
szAuth[35]
    
get_user_authid(idszAuthcharsmax(szAuth))

    
client_print(idprint_console"Registered name(s) under this SteamID")
    
client_print(idprint_console"SteamID: %s"szAuth)
    
client_print(idprint_console"================================================")

    new 
iCount
    
    
new Array:authData
                
    
if(TrieGetCell(AuthsData,szAuth,authData))
    {
        
iCount ArrayGetCell(authData,AuthField_NamesCount);
    }

    
client_print(idprint_console"================================================")
    
client_print(idprint_console"Total registered name(s): %i"iCount)
    
client_print(idprint_console"================================================")


    return 
PLUGIN_HANDLED
}

public 
client_connect(id)
{
    
g_iChangeName[id] = 0
}

public 
client_disconnect(id)
{
    
g_iChangeName[id] = 0

    g_iRegistered
[id] = 0
}

public 
client_putinserver(id)
{
    
g_iChangeName[id] = 1

    
static szName[32], szAuth[35//
    
get_user_name(idszNamecharsmax(szName))
    
get_user_authid(idszAuthcharsmax(szAuth))

    if(!
CheckName(idszNameszAuth))
    {
        switch(
get_pcvar_num(cvConnectKick))
        {
            case 
0:
            {
                static 
szUsedName[32], szTempName[32]
                
copy(szUsedName28szName)

                new 
iMaxTries min(get_pcvar_num(cvRenameTries), 9)

                for(new 
i=1<= iMaxTriesi++)
                {
                    
formatex(szTempNamecharsmax(szTempName), "%s(%d)"szUsedNamei)

                    if(!
find_player("a"szTempName) && CheckName(idszTempNameszAuth))
                    {
                        
set_user_info(id"name"szTempName)
                        
client_print(idprint_chat"[AMXX] Your name was changed, because it was already registered to another SteamID.")

                        return
                    }
                }
            }
            case 
1:
            {
                
server_cmd("kick #%d This name is registered to someone else's SteamID!"get_user_userid(id))
            }
        }

        
log_to_file("steamidfail.txt""On Join: [SteamID] %s [Name] %s"szAuthszName)
    }
}

public 
client_infochanged(id)
{
    new 
szNewName[32], szOldName[32], szAuth[35]

    
get_user_info(id"name"szNewNamecharsmax(szNewName))
    
get_user_name(idszOldNamecharsmax(szOldName))
    
get_user_authid(idszAuthcharsmax(szAuth))

    if(!
equali(szNewNameszOldName) && !CheckName(idszNewNameszAuth) && g_iChangeName[id])
    {
        switch(
get_pcvar_num(cvNameChangeKick))
        {
            case 
0:
            {
                
set_user_info(id"name"szOldName)
                
client_print(idprint_chat"Your new name is reserved to another SteamID. Name change cancelled")
            }
            case 
1:
            {
                
server_cmd("kick #%d This name is registered to someone else's SteamID!"get_user_userid(id))
            }
        }

        
log_to_file("steamidfail.txt""Name Change: [SteamID] %s [OldName] %s [NewName] %s"szAuthszOldNameszNewName)
    }
}

public 
native_is_user_registered(iPluginIDiParamsNum)
{
    new 
id get_param(1)
    return 
is_user_connected(id) ? g_iRegistered[id] : 0
}

LoadNames(iFatal false)
{
    
TrieClear(AuthsData);
    
TrieClear(AllNames);
    
    new 
namesCount

    
new hFile fopen(g_szSteamFile"r")
    if(!
hFile)
        
hFile fopen(g_szSteamFile"w+")

    if(!
hFile)
    {
        if(
iFatal)
        {
            new 
szFailMsg[64]
            
formatex(szFailMsgcharsmax(szFailMsg), "Can't open/create file %s"g_szSteamFile)

            
set_fail_state(szFailMsg)
        }
    }
    else
    {
        static 
szName[32], szAuth[35], szBuffer[128//
        
while(!feof(hFile))
        {
            
fgets(hFileszBuffercharsmax(szBuffer))

            
trim(szBuffer)

            if(!
szBuffer[0] || szBuffer[0] == ';' || (szBuffer[0] == '/' && szBuffer[1] == '/' ))
                continue

            
parse(szBufferszAuthcharsmax(szAuth), szNamecharsmax(szName))

            if(
szName[0] && szAuth[0])
            {
                new Array:
authData
                
                
if(!TrieGetCell(AuthsData,szAuth,authData))
                {
                    
authData ArrayCreate(1,AuthField);
                    
                    
ArraySetCell(authData,AuthField_Names,TrieCreate());
                    
ArraySetCell(authData,AuthField_NamesCount,0);
                    
                    
TrieSetCell(AuthsData,szAuth,authData);
                }
                
                new 
Trie:authNames ArrayGetCell(authData,AuthField_Names)
                new 
namesNumber ArrayGetCell(authData,AuthField_NamesCount);
                
                
TrieSetCell(authNames,szName,true);
                
ArraySetCell(authData,AuthField_NamesCount,++namesNumber);
                
                
TrieSetCell(AllNames,szName,true);
                
                
namesCount++;
            }
        }

        
fclose(hFile)
    }

    return 
namesCount;
}


CheckName(iClientszName[], szAuth[])
{
    
g_iRegistered[iClient] = 0;
    
    if(
TrieKeyExists(AllNames,szName))
    {
        new Array:
authData
                
        
if(TrieGetCell(AuthsData,szAuth,authData))
        {
            new 
Trie:authNames ArrayGetCell(authData,AuthField_Names);
            
g_iRegistered[iClient] = TrieKeyExists(authNames,szName);
        }
        
        return 
g_iRegistered[iClient];
    }

    return 
true;

You cannot retrieve the number of entries of a trie, and
Quote:
TrieSetArray and TrieGetArray are broken
so i have to mix
tries with cellarrays.

So you can understand it better this is the structure i used to handle the steamIds and names in your code with a fictitious situation:
Code:
STEAM ID | NAMES

STEAM:1  | joaquim , andrade
STEAM:2  | connor
STEAM:3  | Mlk27
___

Trie:AllNames 
{
  joaquim,
  andrade,
  connor,
  Mlk27
}

Trie:AuthsData
{

   STEAM:1 ->  Cellarray
                      {
                       Trie:AuthField_Names
                        {
                           joaquim,
                           andrade
                        }
                        AuthField_NamesCount = 2
                    }

   STEAM:2 ->  Cellarray
                      {
                       Trie:AuthField_Names
                        {
                           connor
                        }
                        AuthField_NamesCount = 1
                    }

   STEAM:3 ->  Cellarray
                      {
                       Trie:AuthField_Names
                        {
                           Mlk27
                        }
                        AuthField_NamesCount = 1
                    }

}
With the structure above, CheckName(iClient, szName[], szAuth[]) will work like:

Check if szName is registered by trying to find it in the trie Allnames.

If it is registered, go get the Cellarray associated with with szAuth in AuthsData.
Check if szName is associated to szAuth by searching if it is in the trie of names belonging to szAuth.
If it is associated return true. If it isn't return false.
If it isn't registered return true.
__________________

Last edited by joaquimandrade; 04-17-2009 at 02:05.
joaquimandrade is offline
PartialCloning
Senior Member
Join Date: Dec 2015
Old 12-18-2015 , 00:54   Re: The advantages of a trie over an array for strings storage
Reply With Quote #36

Taking the 1.8.3 changes into account, does the first post still hold any truth? Should I be using tries if I'm going to look up a lot of strings? Most of the time knowing the index but sometimes just to check if the string exists.
PartialCloning is offline
fysiks
Veteran Member
Join Date: Sep 2007
Location: Flatland, USA
Old 12-18-2015 , 19:00   Re: The advantages of a trie over an array for strings storage
Reply With Quote #37

Nothing in 1.8.3-dev changes the difference between string arrays and tries. So, yes, it's still valid.
__________________
fysiks is offline
PartialCloning
Senior Member
Join Date: Dec 2015
Old 12-18-2015 , 23:52   Re: The advantages of a trie over an array for strings storage
Reply With Quote #38

Quote:
Originally Posted by Arkshine View Post
Some thoughts:
If I don't say bullshits, in dev build, it's now heterogeneous. Same as Trie. Both internal libraries have been completely replaced by the libraries from SourceMod.
The rest of his post mentions a few changes as well.
PartialCloning is offline
Arkshine
AMX Mod X Plugin Approver
Join Date: Oct 2005
Old 12-19-2015 , 03:49   Re: The advantages of a trie over an array for strings storage
Reply With Quote #39

API is still the same. It is still working the same way regardless how internally things are handled.
__________________
Arkshine is offline
Reply



Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT -4. The time now is 00:57.


Powered by vBulletin®
Copyright ©2000 - 2024, vBulletin Solutions, Inc.
Theme made by Freecode