BBSysco development log

RB Tree update

Mike King — Sat, 25 Aug 2007 02:30:33 +0000

We’ve been spending some time creating a generic RB tree routine for use within MSB for Global variables, Memory files, and likely a number of other items as time goes by. During the coding we were using the general BSD tree.h module as a prototype (with appropriate copyright credit), however we did notice what appears to be a performance issue in the generally released RB tree logic.

We have contacted the original author and will be trying our performance enhancement in the MSB release. It should give us one of the best RB tree implementations in terms of performance.

Change to file naming convention

Mike King — Fri, 17 Aug 2007 02:32:32 +0000

Up to now I have been trying to decide the best way to name the various modules that comprise MSB. While the original code generally used the first character or two as to what part of the system the ‘C’ module played in the system, it has been a bit hard to always figure out where what in.

I have tried a few combinations on file naming for the modules we have written so far, but in general I have not been happy with the results. I think I have decided to change the module names to the form:

xx_yyyy.c

Where ‘xx’ will indicate the section of the system the module relates to such as:

nf - Numeric function
sf - String function
nv - Numeric variable
sv - String variable
io - Generic IO

This is only a partial list. As we go forward we will see what other breakdowns we require to ultimately come up with a complete list of module sections.

CSE function added

Mike King — Fri, 17 Aug 2007 02:26:50 +0000

The CSE function was added to the system. In adding the function we had the opportunity to look at the compare logic in the system. With the design of the compare routine and the built in stacking logic, the CSE function took only a few hours to implement. This bodes well for future enhancements.

Tomorrow we will look at enhancing the TBL function.

Trig and Math functions added

Mike King — Fri, 17 Aug 2007 01:27:16 +0000

We added the COS, SIN, TAN, ACS, ASN, ATN trigonometric functions along with the LOG, EXP and SQR math functions to the system. In order to simplify the coding we placed all these functions in a common module called nf_trig.c rather than separate modules for each function which seemed a waste given each function was basically identical and only a few lines long.

New System variables

Mike King — Thu, 16 Aug 2007 02:02:47 +0000

We added the system string variables

DLM - Directory delimiter
NID - Network/workstation name
UID - User-id
WHO - User-id (same as UID but for compatibility)

During the addition we also moved the SEP system variable out of the variable stack and assigned it a fixed position. Since MicroShare was at one time a multi-user/multi-tasking system many of the system variables were kept in the task stack. While this made for easy task switching it is not required nor optimal for the system to keep locating the values within the stack.

Since multi-tasking is now an OS issue and multi-threading would require a different approach than having task stacks, we can optimize the performance of MicroShare by moving these off the stack.

Added +=, -=, *=, and /=

Mike King — Wed, 15 Aug 2007 18:35:59 +0000

Finalized the coding for the specialized assignment options for the LET directive. While we did the array assignment with this change we did not include the string template variables for the assignments since this will need to looked at longer term.

During the coding we reviewed the current array assignment functions in the system. MSB only supports assignments on full arrays — not ranges. I will need to come back to this logic later to add in range assignments.

ENV function

Mike King — Mon, 13 Aug 2007 20:17:05 +0000

When adding the ENV function to the system we have added an additional option of ENV(-1). This will return ‘all’ ENV entries to the application as a single string delimited using the system field separator.

Memory Files

Mike King — Mon, 13 Aug 2007 15:41:32 +0000

Have spent some time designing the internal layouts of a memory file equivalent for MSB. Historically I have implemented these as binary searches on a sorted list of records. While this provides for fast look-ups, WRITE require the list to be shuffled in order to add/remove entries from the list and this can be a fairly large overhead for large memory files.

What I think I’m going to do for MSB is implement the memory files as “symmetric binary trees” using the generic red-black algorithm which should provide for optimum access time while reducing the insertion/removal overhead. I had considered a splay tree algorithm which works well if the data is being recalled often as it sorts the tree based on most recent access — however I think the red-black algorithm will be better.

I also will likely use this for ”string” based array sub-scripting that I am considering adding to MSB. Although in this case a Splay tree might be better.

Researching -= and +=

Mike King — Tue, 07 Aug 2007 04:05:31 +0000

We spent some time today working out the implementation of the -= and += logic. These (and ultimately the *=, /=, ++ and –) all pose some issues for the syntax parser. Currently when a symbol is detected (non-alphanumeric) the logic looks at the first character and from that determines what the internal code should be. We need to change the logic slightly to handle these multi-character codes. To do this we will basically steal the logic around the : ( which is used for input validation.

We also spent some time looking into MySql and in particular Berkley DB. While this is now be owned by Oracle, the Berkley DB interface looks like it could be easily adapted to handle a Business Basic style file system. The records are dynamic is size and key segments values are defined by the caller. This might be a way to bring Database technology to MicroShare while avoiding the need to generate SQL which itself causes quite a bit of overhead. Still are anticipating a MySql interface — but a direct Berkley DB may be a interesting offering.

SUB function added

Mike King — Thu, 02 Aug 2007 13:28:00 +0000

Completed adding a SUB function to the system which gave us a chance to play with a bit of the stack manipulation routines within the MSB source. With the addition of the SUB function we are getting closer to be able to run our Apache CGI interface within the MSB code. We will still need to add an ENV function in order to access the environment variables along with += and -=.