Wer suchet, der findet...
Das Suchen einer Zeichenkette im RAM-Speicher erweise sich als nicht besonders kompliziert, dachte ich zuerst. Mein Suchalgorithmus gewann dann allerdings mit der Zeit doch an Umfang und Features. Lesen Sie im folgenden etwas über eben diesen Algorithmus.
Textverarbeitungen und Editoren aller Art sind ein beliebter Tummelplatz für Funktionen, die Zeichenketten (im folgenden Strings genannt) aus bestimmten Daten mengen heraussuchen. Mit dem Suchen an sich ist es allerdings auch noch nicht getan, denn eine Suchfunktion birgt meist - zumindest in besseren Programmen - noch einige Features. Die Möglichkeit, vorwärts und rückwärts zu suchen, ist da schon fast eine Selbstverständlichkeit. Meist bietet sich dann auch noch die Möglichkeit, mit der Option Groß-/Kleinschreibung ignorieren zu suchen. In diesem Fall wird nicht auf die Groß- und Kleinschreibung geachtet, es wird also das Wort ‘HalLO’ ebenso gefunden wie ‘hALIo’. Eine weitere zusätzliche Suchoption ist die Möglichkeit, als ganzes Wort zu suchen. Hierbei wird der zu suchende String nur dann gefunden, wenn das Zeichen vor und hinter dem gefundenen Wort alphanumerisch ist, das heißt, ein Zeichen zwischen A und Z oder eine Ziffer zwischen 0 und 9 ist, oder der zu durchsuchende Bereich (hier der RAM-Speicher) genau mit dem gefunden Wort endet oder direkt mit selbigem Wort beginnt. All diese Features sind in meiner Suchfunktion integriert, so daß Sie in eigenen Anwendungen problemlos alle diese Möglichkeiten bereitstellen können.
Call me...
Der Aufruf der Suchroutine gestaltet sich denkbar einfach. Es müssen einzig und allein folgende Parameter zur Verfügung gestellt werden. Als erstes übergibt man die Adresse, ab der die Suche beginnen soll, darauf folgt ein Zeiger auf den zu suchenden String. Hiernach werden von DoRamSearch bloß noch drei Boolean-Werte erwartet. Der erste gibt die Suchrichtung an. Wird TRUE übergeben, wird vorwärts, ansonsten rückwärts gesucht. Der zweite Parameter ‘whole-word’ bestimmt, ob als ganzes Wort gesucht werden soll. In diesem Fall ist TRUE zu übergeben, ansonsten FALSE. Der letzte Parameter schließlich legt fest, ob eine Überprüfung der Groß-/Kleinschreibung stattfinden soll. Dies geschieht, wenn der Wert TRUE übergeben wird. Wird FALSE übergeben, wird die Groß-/Kleinschreibung ignoriert. Als Rückgabewert erhält man einen LONG-Wert, der bei fehlerfreier Ausführung die Adresse beinhaltet, an der etwas gefunden wurde, oder im Fehlerfall den Wert -1. Mehr braucht man nicht zu tun, um das Suchen in Gang zu setzen.
Es geht ums Prinzip
Der Algorithmus basiert auf einem Zwei-Pointer-Prinzip. Es handelt sich hierbei um einen Pointer auf den zu suchenden String (im folgenden strptr genannt) und um einen in den Speicher, den ich ab jetzt ptr nenne. Der Inhalt dieser beiden Pointer wird verglichen. Stimmt er nicht überein, wird ptr um Eins erhöht oder erniedrigt je nach Suchrichtung, und es findet wieder ein Vergleich statt. Das wiederholt sich so lange, bis der Inhalt beider Pointer übereinstimmt, das erste Zeichen des Such-Strings, auf den strptr zeigt, also dem Zeichen im Speicher entspricht, auf das ptr zeigt.
Hierbei tritt allerdings noch ein Problem auf. Sollte diese Routine auf einem TT mit Fast-RAM betrieben werden, muß man darauf achten, den Sprung, der sich zwischen herkömmlichem ST-RAM und dem Fast-RAM auftut, zu überwinden, da der Speicher in diesem Fall nicht komplett linear adressierbar ist. Auch dem wird in dem Algorithmus Rechnung getragen. DoRamSearch findet sogar eine Zeichenkette, die im ST-RAM beginnt und im Fast-RAM endet (wobei ich bezweifeln möchte, daß dieser Fall allzu oft eintritt).
Hab’ dich
Wurde nun tatsächlich das erste Zeichen gefunden, wird ab dem zweiten Zeichen weiter verglichen. Dazu wird strptr benötigt, der in einer Schleife mit ptr verglichen wird. Hier wird aber nicht nur ‘ptr’ erhöht bzw. erniedrigt, sondern auch strptr, allerdings nur, solange der Inhalt beider Pointer übereinstimmt und natürlich nur, solange man sich noch im Speicher des Computers befindet und nicht aus ihm hinauszeigt. Sollte der Inhalt der Pointer mal nicht übereinstimmen und der Such-String auch noch nicht komplett verglichen worden sein, wird strptr wieder auf den Begin des Such-Strings gesetzt und in der äußeren Schleife solange mit ptr verglichen, bis ptr und strptr wieder übereinstimmen, also wieder das erste Zeichen des Such-Strings gefunden wurde. Darauf folgt die Überprüfung der weiteren Zeichen des Such-Strings und so weiter. Wenn in der inneren Schleife, in der sowohl ptr als auch strptr erhöht bzw. erniedrigt werden, die Pointer-Inhalte beider Pointer solange übereinstimmen, bis der Such-String komplett durchlaufen wurde, wurde das Wort gefunden.
Und nun?
Jetzt hat man also den Such-String im Speicher lokalisiert. Nun wird, dirigiert durch die der Funktion übergebenen Parameter, noch eine Überprüfung eingeleitet, die evtl, feststellt, ob der Such-String als ganzes Wort gefunden wurde oder nicht. Ansonsten gilt die Adresse als Rückgabewert für den gefundenen Such-String.
Alles hat ein Ende...
Der beschriebene Algorithmus ist in der Routine DoRam-Search gleich viermal ausgeführt. Das hat folgenden Grund. Um das Ignorieren der Groß- und Kleinschreibung zu ermöglichen, muß vor einem Vergleich die Funktion toupper, die Klein- in Großbuchstaben umwandelt, angewendet werden. Hieraus entstehen also schon mal zwei Suchzweige. Weiterhin ist die Suchrichtung auch noch zu beachten, so daß die genannten zwei Fälle sowohl für das Vorwärts- als auch das Rückwärtssuchen existent sein müssen. Daraus resultieren die vier Varianten des Suchalgorithmus’. Unter Einsatz eigenen geistigen Potentials dürfte es möglich sein, diese Funktion auch für das Suchen in bestimmten Speicherbereichen umzubauen. Ich selber arbeite schon an einer Version für diese Zwecke, die evtl, auch an dieser Stelle erscheinen könnte. Das Prinzip des Algorithmus’ ist relativ einfach. Es dürfte bis auf eventuell auftretende Verständnisfragen keine Probleme bereiten, diese Routine in andere Sprachen zu übersetzen. Voraussetzung hierfür ist nur die Möglichkeit, den Supervisormodus an- und ausschalten zu können und dadurch uneingeschränkten Zugriff auf den gesamten Speicher zu haben. Das sollten auch meine letzten Worte dazu sein. Ich wünsche allen, die sich die Arbeit machen, das Listing abzutippen, viel Spaß mit dieser Routine.
/* (c) 1992 MAXON Computer */
#include <aes.h>
#include <ctype.h>
#include <string.h>
#include <tos.h>
long DoRamSearch( long adr, char *string,
int forward, int wholeword,
int checkuplow )
{
int do, i;
char *ptr, *strptr, *maxptr,
*minptr, *str, *lastch, *contptr,
prevch, nextch;
long sttop, tttop, oldspst, len;
/* Variablen initialisieren */
len = strlen( string );
_do = 1;
ptr = (char*)adr + (forward ? 1L : -1L);
oldspst = Super ( (void*)lL )
? 0L : Super( (void*)0L );
sttop = * (long*) 1070L;
tttop = * (long*) 1444L;
if( oldspst )
Super( (void*)adr );
str = Malloc( len + 1L );
if( !str )
return( -1L );
strcpy( str, string );
if( !checkuplow )
for( i = 0; i < len; i++ )
str[i] = toupper( str[i] );
strptr = str;
if( (long)ptr >= sttop && (long)ptr < 0x1000000L && tttop )
(long)ptr = (long)ptr - sttop + 0x1000000L;
maxptr =
(char*)( (( (long)ptr >= 0x1000000L && tttop )
? tttop : sttop) - 1L );
minptr =
(cbar*)( (( (long)ptr >= 0x1000000L && tttop )
? 0x1000000L : 0L) );
lastch = &str[len-1];
if( ptr > maxptr || ptr < minptr )
return( -1L );
graf_mouse( HOURGLASS, 0L );
oldspst = Super( (void*)1L ) ? 0L : Super( (void*)0L );
/**********************************/
/* Vorwärts suchen mit */
/* Groß-/Kleinschreibung beachten */
/**********************************/
if( forward && checkuplow )
do
{
/* Erstes Zeichen suchen */
while((*ptr != *strptr)&&(ptr < maxptr))
++ptr;
/* Erstes Zeichen gefunden */
if ( *ptr == *strptr )
/* Beim zweiten Zeichen weiter vergleichen */
while( (ptr < maxptr) && (*ptr == *strptr) && (strptr != lastch) )
{
++ptr;
++strptr;
}
/* String komplett gefunden */
if( strptr == lastch && *ptr == *strptr )
{
/* Als ganzes Wort suchen */
if( wholeword && ptr < maxptr )
{
if( (long)ptr-len < 0x1000000L && (long)ptr >= 0x1000000L )
prevch = *(char*)(sttop - ( 0x1000000L - ((long)ptr - len)) );
else
prevch = ptr[-len];
nextch = ptr[1];
if( !isalnum( prevch ) && !isalnum( nextch ) )
_do = 0;
else
strptr = str;
}
else
_do = 0;
}
else
{
if( *ptr != *strptr )
strptr = str;
else
++strptr;
}
}
if( ptr == maxptr && strptr != lastch )
{
/* Evtl. im TT-Ram weitersuchen */
if( tttop && (flong)ptr < 0x1000000L))
{
ptr = (char*)0x1000000L;
maxptr = (char*)(tttop - 1L);
}
else
_do = 0;
}
}
while( _do );
/**********************************/
/* Vorwärts suchen ohne */
/* Groß-/Kleinschreibung beachten */
/**********************************/
if( forward && (checkuplow )
do
{
/* Erstes Zeichen suchen */
while( (toupper(*ptr) != *strptr) && (ptr < maxptr) )
++ptr;
/* Erstes Zeichen gefunden */
if( toupper(*ptr) == *strptr )
{
/* Beim zweiten Zeichen weiter vergleichen */
while( (ptr < maxptr) &&
(toupper(*ptr) == *strptr) &&
(strptr != lastch) )
{
++ptr;
++strptr;
}
/* String komplett gefunden */
if( strptr == lastch && toupper(*ptr) == *strptr )
{
/* Als ganzes Wort suchen */
if( wholeword && ptr < maxptr )
{
if( (long)ptr
- len < 0x1000000L &&
(long)ptr >= 0x1000000L )
prevch = *(char*)(sttop - ( 0x1000000L - ((long)ptr - len)) );
else
prevch = ptr[-len];
nextch = ptr[1];
if( !isalnum( prevch ) && !isalnum( nextch ) )
_do = 0;
else
strptr = str;
}
else
_do = 0;
}
else
if( *ptr != *strptr )
strptr = str;
else
++strptr;
}
if( ptr == maxptr && strptr != lastch )
{
/* Evtl. im TT-Ram weitersuchen */
if(tttop && ((long)ptr < 0x1000000L))
{
ptr = (char*)0x1000000L;
maxptr = (char*)(tttop - 1L);
}
else
_do = 0;
}
}
while( _do );
/**********************************/
/* Rückwärts suchen mit */
/* Groß-/Kleinschreibung beachten */
/**********************************/
if( !forward && checkuplow )
do
{
/* Erstes Zeichen suchen */
while( (*ptr != *strptr)&&(ptr > minptr))
--ptr;
/* Erstes Zeichen gefunden */
if( *ptr == *strptr )
{
contptr = ptr > minptr ? ptr - 1L : minptr;
/* Beim zweiten Zeichen weiter vergleichen */
while ( (*ptr == *strptr) && (strptr != lastch) )
{
++ptr;
if( (long)ptr == sttop )
(long)ptr = 0x1000000L;
++strptr;
}
/* String komplett gefunden */
if( strptr == lastch && *ptr == *strptr)
{
/* Als ganzes Wort suchen */
if( wholeword && ptr < maxptr )
{
if( (long)ptr - len < 0x1000000L && (long)ptr >= 0x1000000L )
prevch = *(char*)(sttop - 0x1000000L - ((long)ptr - len)) );
else
prevch = ptr[-len];
nextch = ptr[1];
if( !isalnum( prevch ) && !isalnum( nextch ) )
_do = 0;
else
{
strptr = str;
ptr = contptr;
}
}
else
_do = 0;
}
else
{
if( *ptr != *strptr )
{
strptr = str;
ptr = contptr;
}
else
++strptr;
}
}
if( ptr == minptr && strptr != lastch )
{
/* Evtl. im ST-Ram weitersuchen */
if( minptr )
{
ptr = (char*)(sttop - 1L);
minptr = 0L;
maxptr = ptr;
}
else
_do = 0;
}
}
while( _do );
/**********************************/
/* Rückwärts suchen ohne */
/* Groß~/Kleinschreibung beachten */
/**********************************/
if( [forward && !checkuplow )
do
{
/* Erstes Zeichen suchen */
while( (toupper(*ptr) != *strptr) && (ptr > minptr) )
--ptr;
/* Erstes Zeichen gefunden */
if( toupper(*ptr) == *strptr )
{
contptr = ptr > minptr ? ptr - 1L : minptr;
/* Beim zweiten Zeichen weiter vergleichen */
while( (toupper(*ptr) == *strptr) && (strptr != lastch) )
{
++ptr;
if( (long)ptr == sttop )
(long)ptr = 0x1000000L;
++strptr;
}
/* String komplett gefunden */
if( strptr == lastch &&
toupper(*ptr) == *strptr )
{
/* Als ganzes Wort suchen */
if( wholeword && ptr < maxptr )
{
if( (long)ptr - len < 0x1000000L && (long)ptr >= 0x1000000L )
prevch = *(char*)(sttop - ( 0x1000000L - ((long)ptr - len)) );
else
prevch = ptr[-len];
nextch = ptr[1];
if( !isalnum( prevch ) && !isalnum( nextch ) )
_do = 0;
else
{
strptr = str;
ptr = contptr;
}
}
else
_do = 0;
}
else
{
if( *ptr != »strptr )
{
strptr = str;
ptr = contptr;
}
else
++strptr;
}
}
if( ptr == minptr && strptr != lastch )
{
/* Evtl, im ST-Ram weitersuchen */
if( minptr )
{
ptr = (char*)(sttop - 1L);
minptr = 0L;
maxptr = ptr;
}
else
_do = 0;
}
}
while( _do );
if( oldspst )
Super ( (void*)adr );
graf_mouse( ARROW, 0L );
/* Den Rückgabewert erzeugen */
if( (ptr == maxptr || ptr == minptr) && strptr != lastch )
ptr = (char*)-1L;
else
{
ptr -= len - 1;
if( (long)ptr >= sttop && (long)ptr < 0x1000000L )
(long)ptr = sttop - (0x1000000L -(long)ptr);
}
/* Speicher freigeben */
Mfree{ str );
return( (long)ptr );
}
Marc René Gardeya