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: 3570
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: 170
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: 3570
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: 170
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: 3570
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: 1452
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: 170
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: 376
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: 3570
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: 1452
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: 3570
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: 1452
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 ;-)

Return to “Tips and Tricks”

Who is online

Users browsing this forum: No registered users and 6 guests