Author Topic: Implementation of dynamic structs  (Read 4720 times)

Marcus

  • Guest
Implementation of dynamic structs
« on: October 14, 2011, 04:28:36 PM »
Just before releasing version 5 of NaaLaa I added records/structs. I chosed to make them dynamic, as it's perfect for game objects when there's no classes and subclassing.

Code: [Select]
rem Player object.
player?.x = 100
player.y = 100
player.width = 64
player.height = 64
...

rem An enemy object.
enemy?.x = 200
enemy.y = 100
enemy.width = 128
enemy.height = 64
...

rem Function that operates on two objects with x, y, width and height fields.
functions ObjectsCollide(&objA?, &objB?)
  if objA.x + objA.width > objB.x and ...
  ...
endfunc

I didn't have the time to make any speed tests on this implementation before the release. So now I'm very interested in comparing it with interpreted languages that use hash tables for dynamic structs. I use a tree structure to access struct elements. I chosed this approach because I had alredy implemented a class for this (used as a symbol table by the compiler). I was lazy. But the more I think of it, the more I believe it was a smart choice.
   So does anyone here know of a language that uses hash table based structs?  

Offline John

  • Forum Support / SB Dev
  • Posts: 3005
    • ScriptBasic Open Source Project
Re: Implementation of dynamic structs
« Reply #1 on: October 14, 2011, 04:37:53 PM »
You may want to take a look at the SB HASH extenson module.

Code: [Select]
typedef struct _hashe {
  VARIABLE Key,Value;
  struct _hashe *small_son, *big_son;
  struct _hashe *next,*prev;
  } tHashE, *ptHashE;

typedef struct _hash {
  ptHashE Table[PRIME];
  ptHashE FirstElement,
          LastElement,
          ThisElement;
  } tHash,*ptHash;
typedef struct _myOBJECT {
  void *HandleArray;
  } myOBJECT, *pmyOBJECT;

Marcus

  • Guest
Re: Implementation of dynamic structs
« Reply #2 on: October 14, 2011, 05:01:27 PM »
Thanks!

I'll see if I can figure the code out and compare it with what I'm doing (I hope I'm doing something good, else I'll have to reimplement the whole thing). I'm glad script basic is open source - else I'd be lost with this piece of code.

Good night!

Offline John

  • Forum Support / SB Dev
  • Posts: 3005
    • ScriptBasic Open Source Project
Re: Implementation of dynamic structs
« Reply #3 on: October 14, 2011, 05:10:01 PM »
This routine comes from page 436 of the dragon book.

The dragon book:
Aho-Sethi-Ulman : Compilers Principles, techniques, and Tools
Addison-Wesley Publishing Company 1986

Good night and don't let the Basic bugs bite.  ;D

Marcus

  • Guest
Re: Implementation of dynamic structs
« Reply #4 on: October 14, 2011, 11:58:56 PM »
I've got that book. I did start studying compiler construction at the university, hence the book. But I was thrown out by the professor because of snoring. It was such a boring boring subject compared to computer graphics algorithms. Sorry, off topic babbling, I'll have a look in the book.

Offline John

  • Forum Support / SB Dev
  • Posts: 3005
    • ScriptBasic Open Source Project
Re: Implementation of dynamic structs
« Reply #5 on: October 15, 2011, 09:56:24 AM »
I would like to see the HASH extension module in SB have the ability to access the hash list in sorted key order. It could be used as a key based access to a file of fixed length records. Having sorted and partial key (used for positioning) access would take this to another level.


Offline John

  • Forum Support / SB Dev
  • Posts: 3005
    • ScriptBasic Open Source Project
Re: Implementation of dynamic structs
« Reply #6 on: October 16, 2011, 10:12:43 AM »
Marcus,

How are things going with your HASH adventure?

Are you able to recover what you already have written or is the SB/dragon method more attractive?

John

Marcus

  • Guest
Re: Implementation of dynamic structs
« Reply #7 on: October 16, 2011, 10:36:58 AM »
I got a little busy writing game tutorials this weekend. But I'll compare the hash table from DB with my approach any night when I've managed to put the kids to sleep early.

I'm sure any hash table will beat my tree structure approach under normal circumstanses. But the thing is that naalaa uses linked lists for strings (from start I had some great plans for string manipulation, but I sort of forgot what those plans were when I started working on the graphics part). So even if I was to use a hash for struct fields I'd still have to parse the field name (string). With the tree structure I use for structs, I can parse the tree the same time as I parse the name of the field. So at the time when I would be able to create a hash value from the field name I've already found the memory location for the data.
« Last Edit: October 16, 2011, 10:39:17 AM by Marcus »

Offline John

  • Forum Support / SB Dev
  • Posts: 3005
    • ScriptBasic Open Source Project
Re: Implementation of dynamic structs
« Reply #8 on: October 16, 2011, 12:47:16 PM »
Peter Verhas wrote a thread aware memory manger (used in SB) that is OUTSTANDING!!!

MyAlloc

SB MyAlloc Docs

Keep us in the loop as you unravel your options.
« Last Edit: October 16, 2011, 12:52:23 PM by JRS »