Strong type checking is good, but... 
Author Message
 Strong type checking is good, but...

Hi folks!

Today I tried to write a "dynamic"-BTree in Oberon 2. The source is based on the
file "FileDir.Mod" from N. Wirth.
My idea was, to create a index file, which I can tell at creation time (of the
index file), how long the index-value will be. In NW's source, the length of the
index-value was fixed (filename-length = 32 characters).

N. Wirth implemented a very efficient mechanism to read one sector from the hard
disk and to associate a data-structure (the DirPage) to this sector.

Here comes the original code (only the important part)

  CONST
      FnLength*    = 32;
      ...
      SectorSize*   = 1024;
      IndexSize*   = SectorSize DIV 4;
      ...
      DirRootAdr*  = 29;
      DirPgSize*   = 24;
      N = DirPgSize DIV 2;
      ...
      FillerSize = 52;

  TYPE

    DiskAdr      = LONGINT;
    FileName*       = ARRAY FnLength OF CHAR;
    ....

    DirEntry* =  (*B-tree node*)
      RECORD
        name*: FileName;
        adr*:  DiskAdr; (*sec no of file header*)
        p*:    DiskAdr  (*sec no of descendant in directory*)
      END ;

    DirPage*  =
      RECORD (Kernel.Sector)
        mark*:  LONGINT;
        m*:     INTEGER;
        p0*:    DiskAdr;  (*sec no of left descendant in directory*)
        fill:  ARRAY FillerSize OF CHAR;
        e*:  ARRAY DirPgSize OF DirEntry
      END ;

...
  PROCEDURE ...
  VAR
      dadr: DiskAdr;
      a: DirPage;
  BEGIN
    dadr := DirRootAdr;
    Kernel.GetSector(dadr, a);

That's all! Kernel.GetSector reads the sector with address "dadr" from the hard
disk and put the contents in a array of byte (where "a" points to). Fortunately
"a" is also our DirPage and with a.e[2].name we get the name from the 2. node in
that sector.

Ok. It's not so type-safe, but we are here on system programming level. The
solution is very efficient and fast.

Now I'm looking for a mechanism to read pages (sectors) with a variable length
of the index value (that implies also a dynamic number of nodes in the page).
Variable length means, that the length of the index value will be established
once at the creation of the index file. Every index value in the index file has
the same length (the length established at creation time of the file).
Unfortunately that implies, that the index value-length isn't known at compile
time :-(

I tried different solutions, but I didn't found any solution that is as same
efficient as the solution from NW. One solution I tried was a data structure,
that contains 2 open array's (or two pointers to open array's).
Here is the code:

    IndexData* =
      RECORD
        adr*:  RowAdr; (* Address of the data record*)
        p*:    SectAdr;  (*sector nr. of descendant*)
        (* the index value will be in a separate array eValue*)
      END;

    IndexValue* = POINTER TO ARRAY OF CHAR;

    IndexPage*  =
      RECORD
        m*:  INTEGER;
        p0*:  SectAdr;  (*sector nr. of left descendant in directory*)
        eData*:  POINTER TO ARRAY OF IndexData;
        eValue*:  POINTER TO ARRAY OF IndexValue;
      END ;

Here some problems:
- You can't redirect pointers like in C (eData, eValue to point to a memory
location where the data are). (I know, it is good that redirection is not
allowed, because otherwise the garbage collector wouldn't work and we would get
all the problems from C)

- You can't allocate (with new) a data structure that contains two open array's
(number of nodes, length of index value) in a matter to get a continuous memory
area. The continuous memory area is necessary to read the page into memory
without moving bytes from one area to another.

For a solution of the problem I have to allocate the data structure. Then I have
to read the page into memory (array of bytes) and then I have to move the
corresponding bytes to the memory location where the data structure points to.

Is there anybody outside, who knows a solution for reading dynamic data
structures from disk without moving bytes from one memory location to another?

You know a better way to read/save dynamic BTree's from/to disk?

Is there allready a solution (source code)???

Is this "inefficiency" (moving bytes in memory) the price I have to pay for type
safety?  ;-)

Thanks in advance!

Sorry for my english!!!

Greetings from germany
--
Jens Gericke
Heidelberg



Sun, 14 May 2000 03:00:00 GMT  
 Strong type checking is good, but...


Quote:

> - You can't redirect pointers like in C (eData, eValue to point to a memory
> location where the data are). (I know, it is good that redirection is not
> allowed, because otherwise the garbage collector wouldn't work and we
would get
> all the problems from C)

This is not something I would do when programming an application, but it
is ok when writing low level code. You *can* redirect pointers by using
the compiler function SYSTEM.VAL in this way:

   TYPE Ptr = POINTER TO ARRAY OF CHAR;
   VAR p: Ptr;

   ...

   p:=SYSTEM.VAL(Ptr, someAddr)

This is how the headers of TCP/IP packets are extracted from an ARRAY OF
BYTE: by casting the start address of the header to some pointer to a
record defining the header format.

Regards,
--Roberto Brega



Mon, 15 May 2000 03:00:00 GMT  
 Strong type checking is good, but...

Hi!

Here is a respose I've got from Aubrey via eMail:


Date: Thu, 27 Nov 1997 09:42:52 -0600


Quote:

>Hi folks!

>Today I tried to write a "dynamic"-BTree in Oberon 2. The source is based on
the
>file "FileDir.Mod" from N. Wirth.

Jens --
Please post this for me if it is not in the newsgroup, my connectivity seems
to be erratic.

I faced this same problem about 2 years ago when I wanted to build an engine
that would allow me to index/retrieve email.  The solution that I used was
to change the small portion of the node description, to rename that module to
have the same name as the relation it was modeling, and to compile it.  This
could all be done automatically with a source generator, if one prefered.

There should be source to "Alfred.Cod" on the net.  I use this routinely.  I
have passed perhaps 30,000 email messages through the resulting code, and
delegated the maintenance of this to my staff.  The code has been essentially
stable for 2 years.

Recently, my web page broke.  I have not checked if it is back up.  This
should be posted at http://ccwf.cc.utexas.edu/~mcintosh/Oberon/Alfred.Cod when
things are repaired.

--
A prudent parent neither ignores nor disturbs suprisingly quiet children.
1-512-374-0144 (d) -0145 (v) / isdn:Guest / BitSurfr
8/23 Loaded Rev 1L firmware.  Try PPP.

--
Jens Gericke
Heidelberg




Mon, 15 May 2000 03:00:00 GMT  
 
 [ 3 post ] 

 Relevant Pages 

1. Strong type checking...

2. Strong type checking ... (not really)

3. Strong type checking + Heterogenous con

4. Flying With Python (Strong versus Weak Typing) [actually, Static vs Dynamic typing]

5. Strong static typing does not work

6. Strong typed variables

7. Strong typing header needed

8. Strong Typing

9. Strong/Weak typing

10. Escape from strong typing (was: swap(x,y))

11. Strong vs. weak-typing in OO design/languagges

12. Adding Strong Typing without adding to the Language

 

 
Powered by phpBB® Forum Software