|
build "static" hash table? |
Thomas Fjellstrom
Member #476
June 2000
|
Ok.. I'm looking to do a bit of cheating here I'm currently working on the core/opcode generator system and code for my "new" VM, and I'm thinking I'll need to store a nice list of the opcodes for my assembler to use (so it knows what ops can be used, without it being too hardcoded). Since opcodes can have the same name, and just change the types/count of thier args, and I'll want to look up the ops based on thier nemonic, I was thinking a hash table would be perfect. So here's what I was toying with:
(that won't be the exact possition of the items when "compiled", but this is good as an example) And that works, and will be "good enough" for me. But I'm not sure this is the best way to go about it. All of the execution cores and the opcodes will be generated at compile time from a couple/few deffinition files (to allow for easy customization/addition of (new) cores and opcodes, it will allow me to reduce the work/code needed to do/make for the few cores I'll start with, ie: switch,cgoto,prederef-switch,prederef-cgoto) Any gooder ideas? -- |
Oscar Giner
Member #2,207
April 2002
|
But that's not a hasg table. That's a weird thing: an array + linked list. What I guess you want is a hash table where the indexing key is a pair {opcode, num_args}. Some base code:
Another, easier, options is go with c++ and use a map. -- |
Thomas Fjellstrom
Member #476
June 2000
|
You'll notice I said that that wasn't the actual possition of the items. And yes, that is the structure of my hashtables Heres some of my actual hash code:
notice the linked list is to store multiple items in a single bucket without resizing the entire table. Quote: Another, easier, options is go with c++ and use a map. and you missed the point entirely. I want to build the table/list at compile time. -- |
ReyBrujo
Moderator
January 2001
|
I usually add a void * to point to the callback function. The callback is like typedef int (*callback_fn)(void *, void *). The first pointer gets the input and the second the output if any. When calling a function, I set the data in the first pointer (or fill a struct if the function needs more information). Lately I have been using a void *stack_fn[D_STACKSIZE];. Whenever I call a function, I push values into the stack, and pass it as first parameter. The function knows what to do with the stack. That is one of the best ways I worked with. The struct would look like:
And so on. Note that this is an example, and might not compile. Nor I am checking if the stack has NULL values in it. Since the array is sorted, I use qsort to look for the opcode (if there are gaps between opcodes) or just direct access if they are ordered. To generate things in compile time, I use a file like: [ OPCODE ] NUMBER := 0x00 NAME := NOP ARGUMENTS := 0 [ CODE ] /* takes one cycle of script time */ int nop(void *in, void *out) { cycle_count++; return (D_SUCCESS); } A perl script parses all the files (one file for all, or one file per opcode) and generates the header and source file. I used this with a card generator in a trading card game (I file per card) and worked nicely. -- |
Oscar Giner
Member #2,207
April 2002
|
I missunderstood your first code. I though you said that was the hash table, when in fact that was just one element of the hash table (which is a linked list). Quote: and you missed the point entirely. I want to build the table/list at compile time. Ok, I think I get it now. So you what you're trying to do is a program that reads the opcodes from a file and generated c code that would consist of a hast table that stores the opcodes, isn't it? Quote: Any gooder ideas? Your method looks good. Only alternative I can thing of is a binary tree. [edit] -- |
Thomas Fjellstrom
Member #476
June 2000
|
RB: My opcode defn files look something like: op ADD (int in, int in, int out) { $3 = $1 + $2; } op ADD (int in, int inout) { $2 += $1; } op ADD (int in, int in, value out) { $3->vtable->assign_int( $1 + $2 ); } op ADD (value in, value inout) { $2->vtable->add_value($1); } And the core defns... I'm not sure how they'll look at the moment, but they need to beable to define the exececution core, which can be a function with a loop+switch configuration, a cgoto config, or maybe a loop+functable config. The cgoto core will always be the fastest, but is only doable on GCC, so I Want to provide other cores for other compilers (ie: MSVC) that don't support "computed goto"s. Quote: Your method looks good. Only alternative I can thing of is a binary tree. Thats a possibility. I was only using the hash layout because I already have hashing code I dunno. edit: heres sorta what the exec cgoto core "may" look like:
-- |
ReyBrujo
Moderator
January 2001
|
I believe a stack is better than having all functions with different arguments... in a common ASM program, you can call ADD without having pushed values. That is, the one checking the arguments is the opcode itself, not the "shell". -- |
Thomas Fjellstrom
Member #476
June 2000
|
The table I am wanting to build isn't for the VM itsself, its more for the assembler to know what ops can be used, without hard codeing them And if I did make a functable dispatch method, I'd just pass the op pointer which stores the args in a little array. -- |
|