data-structures - 在多个字段上建立索引的哈希表

Question

我目前正在编写一个定义与 CPU 寄存器对应的类型的 OCaml 模块。该模块的界面如下:

(*
 * 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

但是，我希望实现快速且不要太重复。例如，我可以像这样编写 of_int 函数:

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

但这将是可怕且无法维护的。我不想这样做，因为它与我的编程信仰相冲突。此外，我不仅需要做一次这种脏代码，而且需要为四个函数做一次。

我发现的第一个解决方案是使用预处理器(Camlp4 或 cpp)来生成我想要的代码。我觉得这有点矫枉过正，但如果你不能帮助我解决我的第二个想法，我会使用这种方法。

经过一番思考，我想我可以做这样的事情:

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

但是，在这种情况下，我必须选择要散列的字段。在这种情况下，除了使用三个不同的哈希表之外，还有其他解决方案吗？也许我不知道的数据结构能够散列三个字段并在其中三个字段上执行搜索。

对不起，答案可能微不足道的长问题:)。

Answer 1

看起来非常适合 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)));
  ()

输出 :

0 31 24
R0 RA T8
A0 A1 A2

编译:

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