Multiple Field Hashtable Index

Question

I am currently programming an OCaml module that determines the type corresponding to the CPU register. The interface of this module is as follows:

(* * Defines a type which represents a R3000 register. *) type t = | R0 (* Always 0 *) | AT (* Assembler temporary *) | V0 | V1 (* Subroutine return values *) | A0 | A1 | A2 | A3 (* Subroutine arguments *) | T0 | T1 | T2 | T3 | T4 | T5 | T6 | T7 (* Temporary registers *) | S0 | S1 | S2 | S3 | S4 | S5 | S6 | S7 (* Register variables *) | T8 | T9 (* Temporary registers *) | K0 | K1 (* Reserved for kernels *) | GP | SP | FP (* Global/Stack/Frame pointer *) | RA (* Return address *) (* * Conversion from/to [|0, 31|]. *) val of_int : int -> t val to_int : t -> int (* * Conversion to string for display. *) val of_string : string -> t val to_string : t -> string 

However, I would like the implementation to be fast and not too repetitive. For example, I could encode the of_int function as follows:

 let of_int = function | 0 -> R0 | 1 -> AT (* ... *) 

But that would be terrible and incomprehensible. I do not want to do this because it is contrary to my religion of programming. Moreover, I will need to do this dirty code not only once, but also for four functions.

The first solution I found was to use a preprocessor (Camlp4 or cpp) to generate the code I want. I think this is too much, but will use this method if you can not help me with my second idea.

After some thought, I thought I could do something like this:

 type regdescr = { reg : t ; name : string ; index : int } let regs = let htbl = Hashtbl.create 32 in let li = [ (* regdescr defs here *) ] in List.iter (Hashtbl.add htbl) li ; htbl 

However, in this case I have to choose which field I want to use. Is there any other solution than using three different hash tables in this case? Maybe a data structure that I don’t know about is able to hash three fields and search for three of them.

Sorry for the long question for which the answer may be trivial :).

Answer 1

Do you just have three separate hash tables?

Answer 2

It seems like perfect for deriving .

 (* * Defines a type which represents a R3000 register. *) type t = | R0 (* Always 0 *) | AT (* Assembler temporary *) | V0 | V1 (* Subroutine return values *) | A0 | A1 | A2 | A3 (* Subroutine arguments *) | T0 | T1 | T2 | T3 | T4 | T5 | T6 | T7 (* Temporary registers *) | S0 | S1 | S2 | S3 | S4 | S5 | S6 | S7 (* Register variables *) | T8 | T9 (* Temporary registers *) | K0 | K1 (* Reserved for kernels *) | GP | SP | FP (* Global/Stack/Frame pointer *) | RA (* Return address *) deriving (Enum,Show) let of_int x = Enum.to_enum<t>(x) let to_int x = Enum.from_enum<t>(x) let to_string x = Show.show<t>(x) let pr = Printf.printf let () = pr "%i %i %i\n" (to_int R0) (to_int RA) (to_int T8); pr "%s %s %s\n" (to_string (of_int 0)) (to_string (of_int 31)) (to_string (of_int 24)); pr "%s %s %s\n" (to_string (Enum.pred<t>(A1))) (to_string A1) (to_string (Enum.succ<t>(A1))); () 

Exit:

 0 31 24 R0 RA T8 A0 A1 A2 

Compile with:

  ocamlc -pp deriving -I ~/work/contrib/deriving/0.1.1-3.11.1-orig/lib deriving.cma q.ml -oq 

Answer 3

Instead of using a hash table to move from one partial representation of the register to another, have you thought about forcing yourself to always manipulate only the pointers to complete the descriptions so that you can access any aspect that you like (index, string representation, ...) with pointer dereferencing?

You can use the view (your regdescr type) as a register.

How often do you need to map a pattern to a register type?

If you do not, you can completely remove the reg field.

 module Register : sig type t = private { name : string ; index : int } val r0 : t val at : t val equal : t -> t -> bool val hash : t -> int val compare : t -> t -> int end = struct type t = { name : string ; index : int } let r0 = { name = "R0" ; index = 0 } let at = { name = "AT" ; index = 1 } let equal r1 r2 = r1.index = r2.index let hash r1 = Hashtbl.hash (r1.index) let compare r1 r2 = Pervasives.compare r1.index r2.index end 

Note. You can make it all more readable by using the register.ml and register.mli files to define the Register module.

If you sometimes need pattern matching, you can save the constructor field so that you can write good pattern mappings:

 match r.reg with R0 -> ... | AT -> ... 

But force yourself to write only functions that accept (and transmit their calls) the full Register.t .

EDIT: To index, first write a generic function below:

  let all_registers = [ r0 ; at ] let index projection = let htbl = Hashtbl.create 32 in let fr = let key = projection r in Hashtbl.add htbl key r in List.iter f all_registers ; Hashtbl.find htbl 

Then pass all the forecasts you need:

 let of_int = index (fun r -> r.index) let of_name = index (fun r -> r.name)