Code-Beispiel

Schnelle Textsuche (Hash-Table / GLib)

Lizenz:	Erster Autor:	Letzte Bearbeitung:
GPLv3	TJF	26.09.2011

Dieses Beispiel betrifft die schnelle Suche von Texten mithilfe einer Hash-Table. Diese wird zunächst mit Keys (hier die Texte) aufgefüllt. Zusätzlich kann jedem Key ein Value (Wert) zugewiesen werden. Beim Anwenden wird dann mit der g_hash_table_lookup-Funktion geprüft, ob ein Text (z. B. ein Wort aus einer Benutzereingabe) einem der Keys entspricht. Dann wird ggf. dessen Value er- bzw. übermittelt, sonst liefert die Funktion NULL.

Das Beispiel verwendet die Bibliothek GLib, welche in den FreeBasic-Archiven enthalten ist. Dadurch ist das Programm unter windows und LINUX kompilier- und ausführbar.

Besonders bei einer großen Anzahl von Keys erfolgt die Suche mit einer Hash-Table erheblich schneller als das sequentielle Durchsuchen der Einzeltexte. Die Suche erfolgt case-sensitive, d. h. die Groß- und Kleinschreibung wird berücksichtigt.

Die Hash-Table in diesem Beispiel ist für Keys vom Typ ZSTRING PTR ausgelegt und enthält Values vom Typ INTEGER. Die Variablentypen für Keys und Values sind jedoch beliebig. Andere Typen können durch entsprechende Vorgabe beim Aufruf der Funktion g_hash_table_new definiert werden, vgl. Original-Dokumentation (en). Insbesondere können Values auch PTR auf komplexe Datenstrukturen enthalten.

' 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 (STRING Typ)

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

Zusätzliche Informationen und Funktionen

Das Code-Beispiel wurde am 26.09.2011 von TJF angelegt.
Die aktuellste Version wurde am 26.09.2011 von TJF gespeichert.

Bearbeiten

Versionen