Fast text search (hash table / GLib)

Post your FreeBASIC tips and tricks here. Please don’t post your code without including an explanation.
TJF
Posts: 3604
Joined: Dec 06, 2009 22:27
Location: N47°, E15°
Contact:

Fast text search (hash table / GLib)

Postby TJF » Sep 26, 2011 12:16

This example is about a hash table text search. You may find it useful if you have a users input and you need to check if the input is in a given list of textes. Due to the hash table the search will be done much faster than by searching the text list in sequentiell order, especially in long text lists.

The library GLib is used for this code. So the code can be compiled and executed under windows and LINUX.

After hash table creation the table will be filled with the keys (ZSTRING PTRs in this case). You also may add a value to each key (INTEGERs in this case). To check if a specific text is in the list of keywords use g_hash_table_lookup function. If this function finds a similar key it will return its value, otherwise it returns NULL.

You may use any kind of variable type for key and value. This gets specified by the g_hash_table_new function call. For details see the original documentation. Especially the value can be a PTR to a complex data structure.

Code: Select all

' This is file HashTable_glib.bas, an example for GLib Hash tables
' (C) 2011 by Thomas[ dot ]Freiherr[ at ]gmx{ dot }net
' License GPLv 3
'
' See for details
' http://developer.gnome.org/glib/2.28/glib-Hash-Tables.html


'#DEFINE __ORIGINAL_FB_HEADER__

#IFNDEF __ORIGINAL_FB_HEADER__
#INCLUDE "TJF/glib.bi" ' easy / einfache Loesung
#ELSE
#INCLUDE "gtk/glib.bi" ' not so easy / geht auch, mit etwas Nachhilfe
' These macros (and others) are missing in original FB header
' Diese (und andere) Makros fehlen im original FB header
#DEFINE GPOINTER_TO_INT(p) (CAST(gint, (p)))
#DEFINE GINT_TO_POINTER(i) (CAST(gpointer, (i)))
#ENDIF

' Define some keys (FB keywords) /  Definiere Keys (hier FB Befehle)
STATIC AS ZSTRING CONST PTR FBKEY(...) = { _
@"ABS",@"ACCESS",@"ACOS",@"ALIAS",@"ALLOCATE",@"ALPHA",@"AND", _
@"ANDALSO",@"ANY",@"APPEND",@"ASSERT",@"ASSERTWARN",@"ASC", _
@"ASIN",@"ASM",@"ATAN2",@"ATN", _
@"BASE",@"BEEP",@"BIN",@"BINARY",@"BIT",@"BITRESET",@"BITSET", _
@"BLOAD",@"BSAVE", _
@"CALL",@"CALLOCATE",@"CASE",@"CAST",@"CBYTE",@"CDBL",@"CDECL", _
@"CHAIN",@"CHDIR",@"CHR",@"CINT",@"CIRCLE",@"CLASS",@"CLEAR", _
@"CLNG",@"CLNGINT",@"CLOSE",@"CLS",@"COLOR",@"COM",@"CONS", _
@"COMMAND",@"COMMON",@"CONDBROADCAST",@"CONDCREATE",@"CONDDESTROY", _
@"CONDSIGNAL",@"CONDWAIT",@"CONST",@"CONSTRUCTOR",@"CONTINUE", _
@"COS",@"CPTR",@"CSHORT",@"CSIGN",@"CSNG",@"CSRLIN",@"CUBYTE", _
@"CUINT",@"CULNG",@"CULNGINT",@"CUNSG",@"CURDIR",@"CUSHORT", _
@"CUSTOM",@"CVD",@"CVI",@"CVL",@"CVLONGINT",@"CVS",@"CVSHORT", _
@"DATA",@"DATE",@"DATEADD",@"DATEDIFF",@"DATEPART",@"DATESERIAL", _
@"DATEVALUE",@"DAY",@"DEALLOCATE",@"DECLARE",@"DEFBYTE",@"DEFDBL", _
@"DEFINT",@"DEFLNG",@"DEFLNGINT",@"DEFSHORT",@"DEFSNG",@"DEFSTR", _
@"DEFUBYTE",@"DEFUINT",@"DEFULNGINT",@"DEFUSHORT",@"DELETE", _
@"DESTRUCTOR",@"DIM",@"DIR",@"DO",@"DRAW",@"DYNAMIC", _
@"DYLIBFREE",@"DYLIBLOAD",@"DYLIBSYMBOL", _
@"ELSE",@"ELSEIF",@"ENCODING",@"END",@"ENUM",@"ENVIRON",@"ESCAPE", _
@"EOF",@"EQV",@"ERASE",@"ERFN",@"ERL",@"ERMN",@"ERR",@"ERROR", _
@"EXEC",@"EXEPATH",@"EXIT",@"EXP",@"EXPLICIT",@"EXPORT",@"EXTERN", _
@"FALSE",@"FBOOLEAN",@"FIELD",@"FILEATTR",@"FILECOPY",@"FILEDATETIME", _
@"FILEEXISTS",@"FILELEN",@"FIX",@"FLIP",@"FOR",@"FORMAT",@"FRAC", _
@"FRE",@"FREEFILE",@"FUNCTION", _
@"GET",@"GETJOYSTICK",@"GETKEY",@"GETMOUSE",@"GOSUB",@"GOTO", _
@"HEX",@"HIBYTE",@"HIWORD",@"HOUR", _
@"IF",@"IIF",@"IMAGECONVERTROW",@"IMAGECREATE",@"IMAGEDESTROY",@"IMP", _
@"IMPORT",@"INKEY",@"INP",@"INPUT",@"INPUT$",@"INSTR",@"INSTRREV", _
@"INT",@"IS",@"ISDATE", _
@"KILL", _
@"LBOUND",@"LCASE",@"LEFT",@"LEN",@"LET",@"LIB",@"LPT",@"LINE", _
@"LOBYTE",@"LOC",@"LOCAL",@"LOCATE",@"LOCK",@"LOF",@"LOG", _
@"LOOP",@"LOWORD",@"LPOS",@"LPRINT",@"LSET",@"LTRIM", _
@"MID",@"MINUTE",@"MKD",@"MKDIR",@"MKI",@"MKL",@"MKLONGINT",@"MKS", _
@"MKSHORT",@"MOD",@"MONTH",@"MONTHNAME",@"MULTIKEY",@"MUTEXCREATE", _
@"MUTEXDESTROY",@"MUTEXLOCK",@"MUTEXUNLOCK", _
@"NAME",@"NAMESPACE",@"NOKEYWORD",@"NEXT",@"NEW",@"NOT",@"NOW", _
@"OCT",@"OFFSETOF",@"ON",@"ONCE",@"OPEN",@"OPTION",@"OPERATOR", _
@"OR",@"ORELSE",@"OUT",@"OUTPUT",@"OVERLOAD", _
@"PAINT",@"PALETTE",@"PASCAL",@"PCOPY",@"PEEK",@"PIPE",@"PMAP", _
@"POINT",@"POINTER",@"POKE",@"POS",@"PRESERVE",@"PRESET",@"PRINT", _
@"PRIVATE",@"PROCPTR",@"PROPERTY",@"PROTECTED",@"PSET",@"PTR", _
@"PUBLIC",@"PUT", _
@"RANDOM",@"RANDOMIZE",@"READ",@"REALLOCATE",@"REDIM",@"REM", _
@"RESET",@"RESTORE",@"RESUME",@"RETURN",@"RGB",@"RGBA",@"RIGHT", _
@"RMDIR",@"RND",@"RSET",@"RTRIM",@"RUN", _
@"SADD",@"SCOPE",@"SCRN",@"SCREEN",@"SCREENCOPY",@"SCREENCONTROL", _
@"SCREENEVENT",@"SCREENINFO",@"SCREENGLPROC",@"SCREENLIST", _
@"SCREENLOCK",@"SCREENPTR",@"SCREENRES",@"SCREENSET",@"SCREENSYNC", _
@"SCREENUNLOCK",@"SECOND",@"SEEK",@"SELECT",@"SETDATE",@"SETENVIRON", _
@"SETMOUSE",@"SETTIME",@"SGN",@"SHARED",@"SHELL",@"SIN", _
@"SIZEOF",@"SLEEP",@"SPACE",@"SPC",@"SQR",@"STATIC", _
@"STDCALL",@"STEP",@"STOP",@"STR",@"STRING",@"STRPTR",@"SUB", _
@"SWAP",@"SYSTEM",@"SHR",@"SHL", _
@"TAB",@"TAN",@"THEN",@"THIS",@"THREADCREATE",@"THREADWAIT", _
@"TIME",@"TIMESERIAL",@"TIMEVALUE",@"TIMER",@"TO",@"TRANS", _
@"TRIM",@"TRUE",@"TYPE", _
@"UBOUND",@"UCASE", _
@"UNION",@"UNLOCK",@"UNSIGNED",@"UNTIL",@"USING", _
@"VA_ARG",@"VA_FIRST",@"VA_NEXT",@"VAL",@"VALLNG",@"VALINT", _
@"VALUINT",@"VALULNG",@"VAR",@"VARPTR",@"VIEW", _
@"WAIT",@"WBIN",@"WCHR",@"WEEKDAY",@"WEEKDAYNAME",@"WEND", _
@"WHILE",@"WHEX",@"WIDTH",@"WINDOW",@"WINDOWTITLE",@"WINPUT", _
@"WITH",@"WOCT",@"WRITE",@"WSPACE",@"WSTR",@"WSTRING", _
@"XOR",@"YEAR", _
@"AS",@"BYREF",@"BYVAL", _
@"BYTE",@"UBYTE",@"SHORT",@"USHORT",@"LONG",@"ULONG", _
@"INTEGER",@"UINTEGER",@"LONGINT",@"ULONGINT", _
@"SINGLE",@"DOUBLE",@"ZSTRING"}


' Search for a key, output error message if not exist (value = 0)
' Sucht Key _K_ und meldet Fehler wenn nicht vorhanden (Value = 0)
#DEFINE check(_T_, _K_) _
  IF g_hash_table_lookup(_T_, _K_) = 0 THEN _
    ? "Error, keyword not found: "; *_K_

' Callback for output: value first, then key
' Callback zur Ausgabe: erst Value, dann Key
SUB HashOut CDECL( _
  BYVAL key AS gpointer, _
  BYVAL value AS gpointer, _
  BYVAL user_data AS gpointer)

  ? GPOINTER_TO_INT(value), *CAST(ZSTRING PTR, key)
END SUB


' ***** main / Hauptprogramm *****

' Create new hash table / Neue HashTable erstellen
VAR table = g_hash_table_new(@g_str_hash, @g_str_equal)

' Insert keys and values / Fuellen mit den Keys und Values
FOR i AS INTEGER = 0 TO UBOUND(FBKEY)
  g_hash_table_insert(table, FBKEY(i), GINT_TO_POINTER(i + 1000))
NEXT i

' Replace an existing key / Ersetzen eines vorhandenen Keys (6 x)
FOR i AS INTEGER = 0 TO 5
  g_hash_table_insert(table, @"UBYTE", GINT_TO_POINTER(i - 999999))
NEXT i

' Check if all keys are available / Pruefen ob alle Keys vorhanden
FOR i AS INTEGER = 0 TO UBOUND(FBKEY)
  check(table, FBKEY(i))
NEXT i

' Print all keys and values / Alle Keys und Values ausgeben
g_hash_table_foreach(table, @HashOut, 0)

' Search for a non existing key / Suche einen nicht vorhandenen Key
check(table, @"FreeBasic-Portal")

' Destroy table, release memory / Tabelle aufloesen, Speicher freigeben
g_hash_table_unref(table)

#IFNDEF __FB_UNIX__
SLEEP
#ENDIF


Check also this link for updates.
Makoto WATANABE
Posts: 196
Joined: Apr 10, 2010 11:41
Location: Japan
Contact:

Re: Fast text search (hash table / GLib)

Postby Makoto WATANABE » Jun 29, 2020 15:03

Hi !

I copied the "glib.bi" of "C:\Tool\FreeBASIC\inc\glib.bi" into "TJF" folder and tried to compile "HashTable_glib.bas".
The following error was displayed. Where can I get "-lgthread-2.0"?

C:\Tool\FreeBASIC\bin\win32\ld.exe: cannot find -lgthread-2.0
TJF
Posts: 3604
Joined: Dec 06, 2009 22:27
Location: N47°, E15°
Contact:

Re: Fast text search (hash table / GLib)

Postby TJF » Jun 29, 2020 16:52

Check out this post

viewtopic.php?f=14&t=26932&p=272471#p272460

When you install GTK3 it'll include all GLib stuff. And installing only GLib should also be possible.

Regards
Makoto WATANABE
Posts: 196
Joined: Apr 10, 2010 11:41
Location: Japan
Contact:

Re: Fast text search (hash table / GLib)

Postby Makoto WATANABE » Jul 03, 2020 10:53

Sorry.

This program is too difficult for me.
I was unable to compile with following errors.
C:\Tool\FreeBASIC\bin\win32\ld.exe: cannot find -lglib-2.0
C:\Tool\FreeBASIC\bin\win32\ld.exe: cannot find -lgthread-2.0

Is there anyone who compiled and ran this program in a Windows environment?
TJF
Posts: 3604
Joined: Dec 06, 2009 22:27
Location: N47°, E15°
Contact:

Re: Fast text search (hash table / GLib)

Postby TJF » Jul 03, 2020 12:07

Makoto WATANABE wrote:This program is too difficult for me.
I was unable to compile with following errors.
C:\Tool\FreeBASIC\bin\win32\ld.exe: cannot find -lglib-2.0
C:\Tool\FreeBASIC\bin\win32\ld.exe: cannot find -lgthread-2.0

Is there anyone who compiled and ran this program in a Windows environment?
Sure, I compiled and executed successfully in 2011.

It's not the code. Your trouble is related to the installation. The linker (ld.exe) cannot find some GLib binaries.

As long as you don't describe how you installed or how your installation looks like, nobody can help.
jj2007
Posts: 1726
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: Fast text search (hash table / GLib)

Postby jj2007 » Jul 03, 2020 13:37

Makoto WATANABE wrote:This program is too difficult for me
TJF wrote:FB users are a bit lazy
(more)
Makoto WATANABE
Posts: 196
Joined: Apr 10, 2010 11:41
Location: Japan
Contact:

Re: Fast text search (hash table / GLib)

Postby Makoto WATANABE » Jul 03, 2020 14:24

Dear TJF;

Thanks for your reply.

Dear jj2007;

Yes I am so lazy!

I downloaded FreeBASIC-1.07.1-win32.exe(MD5:433309afceaf34f24f2ee22e827e5c93) and I installed it.
*****************************
Microsoft Windows [Version 10.0.18363.900]
(c) 2019 Microsoft Corporation. All rights reserved.

C:\Users\e570makoto>fbc -version
FreeBASIC Compiler - Version 1.07.1 (2019-09-27), built for win32 (32bit)
Copyright (C) 2004-2019 The FreeBASIC development team.
standalone
*****************************

There are similar programs in the "examples" folder of FreeBASIC.
When I try to compile them, I get the same errors.
*****************************
C:\Tool\FreeBASIC\examples\misc\glib\g_HashTable.bas

C:\Tool\FreeBASIC\\fbc -s console "g_HashTable.bas"
C:\Tool\FreeBASIC\bin\win32\ld.exe: cannot find -lglib-2.0
C:\Tool\FreeBASIC\bin\win32\ld.exe: cannot find -lgthread-2.0
*********************************************************
C:\Tool\FreeBASIC\examples\misc\glib\g_VarArgMacros.bas

C:\Tool\FreeBASIC\\fbc -s console "g_VarArgMacros.bas"
C:\Tool\FreeBASIC\bin\win32\ld.exe: cannot find -lglib-2.0
C:\Tool\FreeBASIC\bin\win32\ld.exe: cannot find -lgthread-2.0
*****************************
Provoni
Posts: 391
Joined: Jan 05, 2014 12:33
Location: Belgium

Re: Fast text search (hash table / GLib)

Postby Provoni » Jul 03, 2020 14:33

Makoto, what is it that you actually want to do?
TJF
Posts: 3604
Joined: Dec 06, 2009 22:27
Location: N47°, E15°
Contact:

Re: Fast text search (hash table / GLib)

Postby TJF » Jul 03, 2020 16:12

@Makoto

You're trying to compile source code against a dynamic linked library (.dll). The fbc can generate an object file (.o), but afterwards the linker (ld.exe) needs to bind your object file against the .dll file. Therefore the linker needs the matching binary (.dll-file). You've to install those binaries, in order to finish the compiling process (create the final .exe).

So the binaries must be present at your harddisk ANDALSO the linker must be able to find them.

Above I already send a link describing how to get and install the binaries:
TJF wrote:Check out this post

viewtopic.php?f=14&t=26932&p=272471#p272460

When you install GTK3 it'll include all GLib stuff. And installing only GLib should also be possible.
Regards
jj2007
Posts: 1726
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: Fast text search (hash table / GLib)

Postby jj2007 » Jul 03, 2020 19:15

Makoto WATANABE wrote:Yes I am so lazy!
Not my opinion, I just quoted somebody else ;-)

This forum is crammed full of threads discussing why little proggies don't compile as they should.
TJF
Posts: 3604
Joined: Dec 06, 2009 22:27
Location: N47°, E15°
Contact:

Re: Fast text search (hash table / GLib)

Postby TJF » Jul 03, 2020 19:23

jj2007 wrote:This forum is crammed full of threads discussing why little proggies don't compile as they should.
Boy, you should learn to differentiate between compiler and linker errors.

Here're adults talking. You're welcome if you focus on the topic and try to provide solutions.
jj2007
Posts: 1726
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: Fast text search (hash table / GLib)

Postby jj2007 » Jul 03, 2020 20:00

Perhaps I should stop arguing with people who live in the Alps ;-)
Makoto WATANABE
Posts: 196
Joined: Apr 10, 2010 11:41
Location: Japan
Contact:

Re: Fast text search (hash table / GLib)

Postby Makoto WATANABE » Jul 05, 2020 3:15

Dear All !
Thanks for your advice.

Dear Provoni;
I want to implement an associative array.
I have already learned that "The Ultimate FB HashMap" can be used to implement associative arrays.
https://www.freebasic.net/forum/viewtopic.php?f=7&t=24440&p=273654#p273478

In addition to this, TJF san taught me the following.
"Instead I use GTK as cross platform GUI toolkit which includes GLIB, which provides a hash table feature."
So I'm here now.

Dear TJF;

I got "gtk3 32-bit dlls.7z" which I was told below.
https://www.freebasic.net/forum/viewtopic.php?f=2&t=28506&hilit=glib&start=60#p272178
Then I renamed and used it as follows.
libglib-2.0-0.dll -> libglib-2.0.dll, libgthread-2.0-0.dll -> libgthread-2.0.dll
Then the situation changed and the following error was displayed.
I have a difficult long way to go.

***********************
HashTable_glib.exe - Entry point not found
The procedure entry point g_mutex_unlock was not found in the dynamic link library H:\Tool\FbEdit\Projects\GTK\HashTable_glib.exe.
***********************
TJF
Posts: 3604
Joined: Dec 06, 2009 22:27
Location: N47°, E15°
Contact:

Re: Fast text search (hash table / GLib)

Postby TJF » Jul 05, 2020 9:12

Makoto WATANABE wrote:Dear TJF;

I got "gtk3 32-bit dlls.7z" which I was told below.
https://www.freebasic.net/forum/viewtopic.php?f=2&t=28506&hilit=glib&start=60#p272178
Then I renamed and used it as follows.
libglib-2.0-0.dll -> libglib-2.0.dll, libgthread-2.0-0.dll -> libgthread-2.0.dll
That's not the instructions I recommended.

Makoto WATANABE wrote:Then the situation changed and the following error was displayed.
I have a difficult long way to go.

***********************
HashTable_glib.exe - Entry point not found
The procedure entry point g_mutex_unlock was not found in the dynamic link library H:\Tool\FbEdit\Projects\GTK\HashTable_glib.exe.
***********************
The process is
  1. fbc.exe compiles the source to an object file (.o)
  2. the linker ld.exe links the object file to libraries and creates the executable (.exe)
  3. when starting the .exe the OS calls a run-time linker loading the .dll binaries and passes the entry points to your .exe
Steps 1 and 2 are OK now. Your problem in step 3: both linkers (ld.exe and run-time) do not use then same binary (.dll).
Makoto WATANABE
Posts: 196
Joined: Apr 10, 2010 11:41
Location: Japan
Contact:

Re: Fast text search (hash table / GLib)

Postby Makoto WATANABE » Jul 11, 2020 12:34

Dear TJF;

Thanks for your continued support and advice.

> Your problem in step 3: both linkers (ld.exe and run-time) do not use then same binary (.dll).

I copied the dlls extracted by "gtk2-runtime-2.24.10-2012-10-10-ash.exe" to the folder of my program source.
After that, when I uninstall the installed exe, "Entry point not found" disappeared.
I was able to compile "HashTable_glib.bas" and get the result.
Thank you very much.

By the way, I made the following program with the intention of checking for hash data collisions.

I'm not sure of the validity of this program, but it did detect data collisions.
Please let me know if there is a way to fix it.

Code: Select all

'Fast text search (hash table / GLib)
'by TJF ≫ Sep 26, 2011 12:16
'https://www.freebasic.net/forum/viewtopic.php?f=7&t=18558&p=163893&hilit=glib+hash#p163893

' See for details
' http://developer.gnome.org/glib/2.28/glib-Hash-Tables.html

#INCLUDE ONCE "glib.bi"

Dim Shared ItemID() As String     
Dim Shared As Integer Counter, i, j, k, l
Dim As Single t1,t2
Dim collisions As Integer
Dim accumulation As Integer


' ***** main / Hauptprogramm *****

' Create new hash table / Neue HashTable erstellen
' ★新しいハッシュテーブルを作成★
' g_hash_table_new (GHashFunc hash_func, GEqualFunc key_equal_func)
'                            演算子 @ (のアドレス)
' g_str_hash (gconstpointer v) 文字列をハッシュ値に変換します。
' g_str_equal (gconstpointer v1, gconstpointer v2) 2つの文字列をバイト毎に比較して、等しい場合は TRUE を返します。

VAR ArrayItemID = g_hash_table_new(@g_str_hash, @g_str_equal)

t1=Timer
Counter = 0
collisions = 0
accumulation = 0
' Insert keys and values / Fuellen mit den Keys und Values
' ★キーと値を挿入★

For i = Asc("A") To Asc("Z")

   For j = Asc("A") To Asc("Z")
      For k = Asc("A") To Asc("Z")
            Counter = Counter + 1
            ReDim Preserve ItemID(Counter + 1)
           
            ItemID(Counter) =  Chr(i) + Chr(j) + Chr(k) + Chr(l)
            IF g_hash_table_lookup(ArrayItemID, @ItemID(Counter)) = 0 Then
               accumulation = accumulation + 1
               g_hash_table_insert(ArrayItemID, @ItemID(Counter), GINT_TO_POINTER(Counter + 1000))
            Else
               'Display when duplicate keys occur
               collisions = collisions + 1
               Print g_hash_table_lookup(ArrayItemID, @ItemID(Counter)) , Counter, ItemID(Counter)
            End If
      Next k
   Next j
Next i

t2=Timer
   
Print
Print
Print "Finished. Last ItemID = "; ItemID(Counter); "      Counter = 26^3(17,576) = "; Counter
Print "collisions = ";collisions," accumulation = ";accumulation
Print
Print "Required seconds = ";t2 - t1

' Destroy table, release memory / Tabelle aufloesen, Speicher freigeben
' テーブルを破棄、メモリを解放
g_hash_table_unref(ArrayItemID)

Sleep

Return to “Tips and Tricks”

Who is online

Users browsing this forum: No registered users and 8 guests