代码之家 › 专栏 › 技术社区 › Pierre Bourdon

在多个字段上索引的哈希表

ocaml functional-programming data-structures

Pierre Bourdon · 技术社区 · 15 年前

我目前正在编程一个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

但是,我希望实现速度快且不太重复。例如,我可以这样编写函数的代码:

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

但是,在这种情况下,我必须选择要哈希的字段。在这种情况下,是否还有比使用三个不同的哈希表更好的解决方案?也许我不知道的数据结构能够散列三个字段,并对其中三个字段执行搜索。

很抱歉问了这么长一个问题,答案可能微不足道:)。

3 回复 | 直到 15 年前

newacct 15 年前

只有三个单独的哈希表?

ygrek 15 年前

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

Pascal Cuoq 15 年前

不是使用哈希表从一个寄存器的一部分表示转换到另一部分表示,您是否考虑过强迫自己总是只操作指向完整描述的指针,以便只使用指针取消引用就可以访问您喜欢的任何方面(索引、字符串表示等)?

您可以使用表示(您的类型 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 模块。

如果有时需要模式匹配,可以保留constructor字段,以便编写好的模式匹配:

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

但是强迫自己只写接受(并传递其被调用方)完整 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)