在幾個字段索引的Hashtable

Question

我目前正在編程一個OCaml模塊，它定義了一個與CPU寄存器相對應的類型。這個模塊的接口如下：

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

只有三個單獨的哈希表？

Answer 2

而不是使用哈希表從寄存器的一個部分表示到另一個，你有沒有想過強迫自己總是隻操作指針來完成描述，以便你可以訪問你喜歡的任何方面（索引，字符串表示，...）只有一個指針解引用？

您可以使用表示（您的類型regdescr）作爲的註冊表。

您需要多長時間模式匹配類型寄存器的值？

如果你永遠不會這樣做，你甚至可以完全消除reg字段。

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 

注意：您可以使整個事情更容易閱讀使用文件register.ml和register.mli定義Register模塊。

如果有時需要模式匹配，可以保持構造字段，以便它可以寫出漂亮的圖案匹配數：

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

但強迫自己只寫接受功能（並通過他們的callees）全部Register.t。

編輯：索引，先寫下面的泛型函數：

let all_registers = [ r0 ; at ] 

    let index projection = 
    let htbl = Hashtbl.create 32 in 
    let f r = 
     let key = projection r in 
     Hashtbl.add htbl key r 
    in 
    List.iter f all_registers ; 
    Hashtbl.find htbl 

然後通過它，你需要的所有預測：

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

Answer 3

看起來像一個完美的結合爲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