 Notice. New forum software under development. It's going to miss a few functions and look a bit ugly for a while, but I'm working on it full time now as the old forum was too unstable. Couple days, all good. If you notice any issues, please contact me. |
Forum Index : Microcontroller and PC projects : [Micromite] Dictionary as a CFunction
| Author | Message | ||||
MicroBlocks Guru  Joined: 12/05/2012 Location: ThailandPosts: 2209 |
I have some source code for making a Dictionary in C (HashTable). I would like to make a CFunction version of it. Library functions can not be used, but some of those can be removed or made as a local function. The functions strcmp,strlen,strcpy are easily duplicated. The only functions that are not replaceable are (i think) malloc(), and free(). Is there a trick to solve that? [code] struct nlist { /* table entry: */ struct nlist *next; /* next entry in chain */ char *name; /* defined name */ char *defn; /* replacement text */ }; #define HASHSIZE 101 static struct nlist *hashtab[HASHSIZE]; /* pointer table */ /* hash: form hash value for string s */ unsigned hash(char *s) { unsigned hashval; for (hashval = 0; *s != ’\0’; s++) hashval = *s + 31 * hashval; return hashval % HASHSIZE; } /* lookup: look for s in hashtab */ struct nlist *lookup(char *s) { struct nlist *np; for (np = hashtab[hash(s)]; np != NULL; np = np->next) if (strcmp(s, np->name) == 0) return np; /* found */ return NULL; /* not found */ } char *strdup(char *); /* install: put (name, defn) in hashtab */ struct nlist *install(char *name, char *defn) { struct nlist *np; unsigned hashval; if ((np = lookup(name)) == NULL) { /* not found */ np = (struct nlist *) malloc(sizeof(*np)); if (np == NULL || (np->name = strdup(name)) == NULL) return NULL; hashval = hash(name); np->next = hashtab[hashval]; hashtab[hashval] = np; } else /* already there */ free((void *) np->defn); /*free previous defn */ if ((np->defn = strdup(defn)) == NULL) return NULL; return np; } char *strdup(char *s) /* make a duplicate of s */ { char *p; p = (char *) malloc(strlen(s)+1); /* +1 for ’\0’ */ if (p != NULL) strcpy(p, s); return p; } [/code] Microblocks. Build with logic. |
||||
G8JCF Guru Joined: 15/05/2014 Location: United KingdomPosts: 676 |
malloc and free are about reserving memory and releasing it. This type of operation can not be done in a CFunction. What you will probably need to do is create a var array in MMBasic and use that as the hashtab, ie pass the address of that array into the CFunction call. Any kind of var array should do since the content will never be accessed via MMBasic, ie DIMming the array is simply a way of asking MMBasic to reserve a piece of memory. I should imagine that a real 'C' expert, ie not me, could advise you in more detail. Peter The only Konstant is Change |
||||
| MicroBlocks Guru Joined: 12/05/2012 Location: ThailandPosts: 2209 |
What i was thinking is that it would be possible to have jumptables in the firmware that point to the most important library functions. Then you could use them from a CFunction too. I imagine having about 10 or so crucial library functions available it would make the CFunction very powerful. library functions like strcmp, strcpy and lots of other are easily replaced with a self written function but stuff like malloc and free can not. Microblocks. Build with logic. |
||||
| G8JCF Guru Joined: 15/05/2014 Location: United KingdomPosts: 676 |
Hi TZ I'm really against that kind of thing, and in particular for malloc - I don't know how many core dumps I've seen generated by malloc/free. The debate always becomes about what is most important and inevitably the list always expands over time. I really think that we should try our best to exploit the existing capability of CFunctions, and then after some time has passed, eg 9 months, we should then re-evaluate in the light of experience what further things could be added to MMBasic. "Peeking/Poking about" in the innards of the MMBasic interpreter is not a good thing IMHO. CFunctions are primarily there to support/ehance MMBasic, IMHO 'C' string functions for example wouldn't be of much use in that regard since MMBasic strings are completely different from 'C' strings. Although much slower in execution, have you translated the 'C' code into MMBasic code ? For us non 'C' experts, such an MMBasic translation would then serve as a guide for writing the CFunction - I know it seems daft, C->MMBasic->CFunction, but the MMBasic step is so that clarity of the algorithm becomes readily apparent, and to prove that it can be done in MMBasic, then the final CFunction stage is just about performance. Hope I'm making sense Peter The only Konstant is Change |
||||
Geoffg Guru Joined: 06/06/2011 Location: AustraliaPosts: 3282 |
Peter is right, the best way to get memory for a CFunction is to declare an array and pass that to the CFunction. I also agree with Peter that initially it is best to use CFunctions as they are. That way we can learn if they are popular and what new features are really needed. If CFunctions prove popular and if limitations (like not being able to call MMBasic functions) become critical then we could add more functionality. My fear is that no one will write CFunctions (except Peter and myself) so I do not want to keep adding features to them without some confidence that they will be used. The whole of MMBasic has evolved this way - people have used it and discovered missing functionality, that has been addressed so they use it further exposing more requirements, etc. Geoff Geoff Graham - http://geoffg.net |
||||
| micronut Newbie  Joined: 03/09/2014 Location: United StatesPosts: 37 |
You don't need to fear Geoff. I am working on a TFT project using MMBASIC and the CFunction will be perfect for the fast interface needed to make it work. |
||||
| MicroBlocks Guru Joined: 12/05/2012 Location: ThailandPosts: 2209 |
I jumped a bit on a dictionary because some members are using a WiFi module to retrieve or send info from web services/websites. Parsing then becomes a challenge. One of the things that can really help in those use cases is having a dictionary 'object'. Not difficult to implement. But that nasty malloc and free makes it impossible. Implementing it in MMBasic will be very difficult as there are no provisions to extend an arrays dimension and no boundaries can be checked. That will cause a lot of global variables for 'bookkeeping'. Something like redim or lbound/ubound would be very handy to have when working with arrays. All of that 'bookkeeping' could be done of course, but I think it gets complicated and difficult to use as a library function which is my goal. I'll try something simpler first. :) Microblocks. Build with logic. |
||||
| G8JCF Guru Joined: 15/05/2014 Location: United KingdomPosts: 676 |
Hi TZ Presumably one could create 4 arrays DIM LinkPtr(N) 'next entry in chain DIM Name$(N) Length L 'defined name - max length of L chars DIM Defn$(N) Length M 'replacement text - max length of M chars DIM Hash%(N) 'Array to hold the hash of Name To replicate struct Nlist, setting N to some value which is large enough to cope with the expected maximum number of dictionary items ? These 4 vars together with N could then be passed through to the install and lookup CFunctions IndexOfNewName=install(NewName$,NewDefn$,LinkPtr(),Name$(), Defn$(),Hash%(),N) IndexOfMyName=lookup(MyName$,LinkPtr(),Name$(),Defn$(),Hash% (),N) Also, given the limited memory space of the uMite, perhaps Hashing may be overkill, it might be just as good to simply search through the Name$ array to find a match (or not). How many dictionary items are you envisaging ? Thinking out loud here; hopefully will prompt someone, somewhere 
Peter The only Konstant is Change |
||||
| MicroBlocks Guru Joined: 12/05/2012 Location: ThailandPosts: 2209 |
I might look into the possibility of just declaring an array that i can then manipulate from C. Can i determine the length of that array in C. I read that when an array is used as a parameter then in C you will have a pointer to the first element. So i probably add a second parameter holding the length of the array, correct? I wanted to read up more about the CFunction but the link in the documentation is pointing to a non existing page. http://geoffg.net/downloads/Micromite/cfunctions.zip Microblocks. Build with logic. |
||||
| G8JCF Guru Joined: 15/05/2014 Location: United KingdomPosts: 676 |
@TZ goto http://www.g8jcf.dyndns.org/mmbasicmkii/index.html And the documentation should have been included as part of the Beta s/w package. You will need to pass the number of elements/length through to your CFunction(s) Peter The only Konstant is Change |
||||
| MicroBlocks Guru Joined: 12/05/2012 Location: ThailandPosts: 2209 |
Thanks Peter. More to study. :) Microblocks. Build with logic. |
||||
| G8JCF Guru Joined: 15/05/2014 Location: United KingdomPosts: 676 |
Hopefully it will be rewarding The only Konstant is Change |
||||
| G8JCF Guru Joined: 15/05/2014 Location: United KingdomPosts: 676 |
Hi TZ Looking at the 'C' code, if I'm understanding it correctly, the number of items seems to be limited to hashsize, ie 101, which is pretty small. Peter The only Konstant is Change |
||||
| MicroBlocks Guru Joined: 12/05/2012 Location: ThailandPosts: 2209 |
It's a starting point. 😉 with hashes, especially simple ones, you will get collisions. Each hash entry should be a bucket that can hold more than one 'key'. However, with limits in mind and easier to program only using the name is sufficient. The end goal is to parse simple xml or json and make those values available by using the property name. Microblocks. Build with logic. |
||||
 Print this page |
 |
The Back Shed's forum code is written, and hosted, in Australia. | © JAQ Software 2025 |
