===========================================================================
 BBS: The Abacus * HST/DS * Potterville MI
Date: 03-22-93 (14:23)             Number: 182
From: QUINN TYLER JACKSON          Refer#: NONE
  To: CORIDON HENSHAW               Recvd: NO  
Subj: Hashed NODELIST       1/       Conf: (35) Quick Basi
---------------------------------------------------------------------------
Here is a version of NODELIST.BAS that uses hashing.  It "sorts" the
index on the fly.  Also, notice that it points to the original
NODELIST.nnn with offsets, and uses a backsearch to grab node entries,
that can then be quickly turned into phone numbers.

This way, the compiled index is 243k for 15000 nodes, and the nodelist
need not be duplicated in compiled form!  Just suppy a (VALID) address,
and it returns the information on the system.  Note that POINTLISTS can
be 'spliced' into the index with a little modification.  For instance,
the index could add anothe field, called "LIST AS STRING * 12" that
tells which list the offset applies to.  If the list for a given entry
were "POINTLIST.001", then the offset would be assumed to apply to that
file, not NODELIST.nnn.  This system allows additional points to be
added to the index AT ANY TIME, without the need to rehash the entire
NODELIST.  You see, the way hashing works, it can be dynamically added
to without a trouble!  Thanks to Charles Graham for funFirstPrime.

Take a look at it and see what we can do with it!  I counted 22
collisions with 773 items, which isn't bad.  With hashing, if the table
is 30% greater than the maximum number of entries, there is an average
of 6 or so collisions.  But remember, it is STILL faster than creating
an unsorted index, and then sorting it, and then using binary searches!
All one needs to do to find an item in a hashed list is use the
fqjHashGet routine with the reconstructed key that is based on the
address.  There could be another index for system names, or sysop names,
but addresses seem to me to be enough?

Try it out!

Let me know!

Quinn
___---
________O_/________________________| SNIP |______________________\_O_______
        O \                        | HERE |                      / O
'This file created by PostIt! v4.0.
'>>> Start of page 1.

' HASNODE.BAS
'
' Hashes nodelist
'
' A fairly fast alternative, and it's sorted.  The index
' points to the original NODELIST, so only 234k is added to the
' disk space required by what the NODELIST normally hogs anyway!


DECLARE SUB sqjHashPut (Idx AS ANY)
DECLARE SUB sqjOpenHash (FileName$)
DECLARE FUNCTION fqjAdd2Kee$ (Zone%, Net%, Node%, Pnt%)
DECLARE FUNCTION BreakString% (OutArray() AS STRING * 50, InString AS_
 STRING)
DECLARE SUB ParseNodelist (NodeListFile AS STRING, ParsedListFile AS_
 STRING)
DECLARE FUNCTION fqjHashGet% (Idx AS ANY)
DECLARE FUNCTION frgHashIdent% (Idx AS ANY, Offset%)
DECLARE FUNCTION funFirstPrime% (threshold%)
DECLARE FUNCTION Add2Kee$ (Zone%, Net%, Node%, Pnt%)
DEFINT A-Z

CONST TRUE = -1
CONST FALSE = NOT TRUE

TYPE HashIdxType
    Kee AS STRING * 8
    Offset AS LONG
END TYPE

TYPE IdxType
    Zone AS INTEGER
    Region AS INTEGER
    Net AS INTEGER
    Node AS INTEGER
    Point AS INTEGER
END TYPE

TYPE NodelistType
        System          AS STRING * 36
        Location        AS STRING * 36
        Sysop           AS STRING * 36
        Phone           AS STRING * 20
        BPS             AS INTEGER
        Flags           AS STRING * 50
END TYPE

DIM SHARED MaxHash
DIM SHARED HashHandle
DIM SHARED Buffer AS HashIdxType

DIM Idx AS HashIdxType

MaxHash = funFirstPrime(15000)
DIM Temp AS HashIdxType

CLS
ParseNodelist "D:\NODELIST.022", "D:\NODELIST.DBF"
INPUT "Address to find: ", Zone, Net, Node, Pnt
Temp.Kee = fqjAdd2Kee(Zone, Net, Node, Pnt)
nul = fqjHashGet(Temp)

Test = FREEFILE
OPEN "D:\NODELIST.022" FOR BINARY AS Test
Ptr = Temp.Offset - 3
D$ = SPACE$(1)

IF Ptr > 100 THEN
DO                              ' Since SEEK() returns the NEXT place to
    SEEK #Test, Ptr             ' be read, we must scan BACKWARDS to the
    GET #Test, Ptr, D$          ' previous carriage return to get the
    Ptr = Ptr - 1               ' PREVIOUS line, and then grab it!
LOOP UNTIL D$ = CHR$(13)        '
ELSE
        PRINT "Bad node!"
END IF

D$ = SPACE$(Temp.Offset - Ptr)
GET #Test, Ptr, D$
PRINT D$

END

FUNCTION BreakString% (OutArray() AS STRING * 50, InString AS STRING)

ON LOCAL ERROR GOTO HandleError

Ptr = 1

FOR OutArrayPtr = 0 TO 1
SELECT CASE OutArrayPtr
    CASE 7
        OutArray(7) = MID$(InString, Ptr)
    CASE ELSE
        Comma = INSTR(Ptr, InString, ",")
        OutArray(OutArrayPtr) = MID$(InString, Ptr, (Comma - Ptr))
        Ptr = Comma + 1
END SELECT
NEXT

BreakString = OutArrayPtr
EXIT FUNCTION

HandleError:
RESUME ExitFunction:
>>> Continued to next message

 * OLX 2.1 TD * The plural of programmer is insomnia....

--- Maximus/2 2.01wb
 * Origin: The Nibble's Roost, Richmond BC Canada 604-244-8009 (1:153/918)