data structures - Hashtable indexado en varios campos

data-structures functional-programming

Question

Actualmente estoy programando un módulo OCaml que define un tipo correspondiente a un registro de CPU. La interfaz de este módulo es la siguiente:

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

Sin embargo, me gustaría que la implementación sea rápida y no demasiado repetitiva. Por ejemplo, podría codificar la función of_int así:

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

Pero sería horrible e imposible de mantener. No quiero hacer esto ya que entra en conflicto con mi religión de programación. Además, necesitaría hacer este tipo de código sucio no solo una vez, sino también para las cuatro funciones.

La primera solución que encontré sería usar un preprocesador (ya sea Camlp4 o cpp) para generar el código que quiero. Encuentro que esto es excesivo, pero usaría este método si no puede ayudarme con mi segunda idea.

Después de pensarlo un poco, pensé que podría hacer algo como esto:

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

Sin embargo, en este caso, debo elegir qué campo quiero hash. ¿Hay alguna otra solución que usar tres hashtables diferentes en este caso? Tal vez una estructura de datos que no conozco es capaz de hacer hash en tres campos y realizar búsquedas en los tres.

Perdón por la larga pregunta para la cual la respuesta puede ser trivial :).

Answer 1

¿Solo tienes tres tablas hash separadas?

Answer 2

En lugar de utilizar una tabla hash para pasar de una representación parcial de un registro a otro, ¿ha pensado en obligarse a manipular siempre solo punteros para completar las descripciones, para que pueda acceder a cualquier aspecto que desee (índice, representación de cadena, ... ) con solo una desreferencia de puntero?

Puedes usar la representación (tu tipo regdescr ) como el registro.

¿Con qué frecuencia necesita ajustar el valor de un tipo de registro de patrones?

Si nunca lo haces, incluso puedes eliminar completamente el campo de 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 

Nota: puede hacer que todo sea más legible utilizando los archivos register.ml y register.mli para definir el módulo de Register .

Si a veces necesita una coincidencia de patrones, puede mantener el campo de constructor para que sea posible escribir combinaciones de patrones agradables:

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

Pero oblíguese a escribir solo las funciones que aceptan (y pasan sus calles) el Register.t completo.

EDITAR: Para indexar, primero escriba la función genérica a continuación:

  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

Luego pase todas las proyecciones que necesita:

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

Answer 3

Parece un ajuste perfecto para derivar .

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

Salida:

0 31 24
R0 RA T8
A0 A1 A2

Compilar con :

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