Matrices asociativas en C

8 minutos de lectura

avatar de usuario
expreso

Estoy implementando una forma de transferir un conjunto de datos a un dongle programable. El dongle se basa en una tecnología de tarjeta inteligente y puede ejecutar un código arbitrario en su interior. Los datos de entrada y salida se pasan como bloques binarios a los que se puede acceder a través de punteros de entrada y salida.

Me gustaría usar una matriz asociativa para simplificar el código de procesamiento de datos. Todo debería funcionar de esta manera:

Primero la aplicación host:

// Host application in C++
in_data["method"] = "calc_r";
in_data["id"] = 12;
in_data["loc_a"] = 56.19;
in_data["loc_l"] = 44.02;
processor->send(in_data);

A continuación, el código dentro del dongle:

// Some dongle function in C
char* method_name = assoc_get_string(in_data, "method");
int id = assoc_get_int(in_data, "id");
float loc_a = assoc_get_float(in_data, "loc_a");
float loc_l = assoc_get_float(in_data, "loc_l");

Entonces mi pregunta es sobre la funcionalidad de la parte del dongle. ¿Hay código C o biblioteca para implementar un comportamiento de matriz asociativa como la anterior?

  • Hay una implementación de matrices asociativas en el libro de David R Hanson Interfaces e implementaciones de C (1996). Es muy profesional, pero no del todo trivial. Se llaman ‘tablas’ en el libro.

    –Jonathan Leffler

    28 oct 2018 a las 14:10

avatar de usuario
manuel salvador

Tabla hash de Glib. implementa una interfaz de mapa o (matriz asociativa). Y es muy probable que sea la implementación de tabla hash más utilizada para C.

GHashTable *table=g_hash_table_new(g_str_hash, g_str_equal);

/* put */
g_hash_table_insert(table,"SOME_KEY","SOME_VALUE");

/* get */
gchar *value = (gchar *) g_hash_table_lookup(table,"SOME_KEY");

avatar de usuario
marca wilkins

Mi sospecha es que tendrías que escribir el tuyo propio. Si entiendo la arquitectura que está describiendo, entonces deberá enviar toda la porción de datos en una sola pieza. Si es así, la mayoría de las bibliotecas no funcionarán para eso porque lo más probable es que asignen múltiples piezas de memoria, lo que requeriría múltiples transferencias (y una comprensión interna de la estructura). Sería similar a tratar de usar una función hash de biblioteca y luego enviar su contenido a través de la red en un socket simplemente pasando el puntero raíz al send función.

Sería posible escribir algunas utilidades propias que administren una matriz asociativa (o hash) muy simple en un solo bloque de memoria. Si la cantidad de datos es pequeña, podría usar una búsqueda lineal simple para las entradas y sería un fragmento de código bastante compacto.

  • Sí, tiene usted razón. La función de procesamiento de datos en dongle se ocupa de una sola pieza de datos. ¡Realmente siento que necesito implementar una matriz asociativa simple con índices de longitud de 8 caracteres y un algoritmo de búsqueda de índice lineal! Solo pensé en no reinventar la rueda y preguntar si alguien ya lo ha implementado.

    – expreso

    1 de febrero de 2011 a las 18:25

  • Definitivamente estoy de acuerdo con no reinventar la rueda. Y ciertamente parece probable que alguien ya haya hecho esto… pero encontrarlo podría resultar difícil ya que es bastante especializado.

    –Mark Wilkins

    1 de febrero de 2011 a las 18:39

avatar de usuario
Hasturkun

Tratar utashuna biblioteca de encabezado que implementa una tabla hash en C. Es pequeña y bastante fácil de usar.

Este es un hilo antiguo, pero pensé que aún podría ser útil para cualquiera que busque una implementación. No requiere demasiado código; Hice el mío en ~100 líneas sin ninguna biblioteca adicional. Lo llamé diccionario ya que es paralelo (más o menos) al tipo de datos de python. Aquí está mi código:

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>

typedef struct hollow_list hollow_list;

struct hollow_list{
    unsigned int size;
    void *value;
    bool *written;
    hollow_list *children;
};

//Creates a hollow list and allocates all of the needed memory
hollow_list hollow_list_create(unsigned int size){
    hollow_list output;
    output = (hollow_list) {.size = size, .value = (void *) 0, .written = calloc(size, sizeof(bool)), .children = calloc(size, sizeof(hollow_list))};
    return output;
}

//Frees all memory of associated with a hollow list and its children
void hollow_list_free(hollow_list *l, bool free_values){
    int i;
    for(i = 0; i < l->size; i++){
        hollow_list_free(l->children + i, free_values);
    }
    if(free_values){
        free(l->value);
    }
    free(l);
}

//Reads from the hollow list and returns a pointer to the item's data
void *hollow_list_read(hollow_list *l, unsigned int index){
    if(index == 0){
        return l->value;
    }
    unsigned int bit_checker;
    bit_checker = 1<<(l->size - 1);
    int i;
    for(i = 0; i < l->size; i++){
        if(bit_checker & index){
            if(l->written[i] == true){
                return hollow_list_read(l->children + i, bit_checker ^ index);
            } else {
                return (void *) 0;
            }
        }
        bit_checker >>= 1;
    }
}

//Writes to the hollow list, allocating memory only as it needs
void hollow_list_write(hollow_list *l, unsigned int index, void *value){
    if(index == 0){
        l->value = value;
    } else {
        unsigned int bit_checker;
        bit_checker = 1<<(l->size - 1);
        int i;
        for(i = 0; i < l->size; i++){
            if(bit_checker & index){
                if(!l->written[i]){
                    l->children[i] = hollow_list_create(l->size - i - 1);
                    l->written[i] = true;
                }
                hollow_list_write(l->children + i, bit_checker ^ index, value);
                break;
            }
            bit_checker >>= 1;
        }
    }
}

typedef struct dictionary dictionary;

struct dictionary{
    void *value;
    hollow_list *child;
};

dictionary dictionary_create(){
    dictionary output;
    output.child = malloc(sizeof(hollow_list));
    *output.child = hollow_list_create(8);
    output.value = (void *) 0;
    return output;
}

void dictionary_write(dictionary *dict, char *index, unsigned int strlen, void *value){
    void *hollow_list_value;
    dictionary *new_dict;
    int i;
    for(i = 0; i < strlen; i++){
        hollow_list_value = hollow_list_read(dict->child, (int) index[i]);
        if(hollow_list_value == (void *) 0){
            new_dict = malloc(sizeof(dictionary));
            *new_dict = dictionary_create();
            hollow_list_write(dict->child, (int) index[i], new_dict);
            dict = new_dict;
        } else {
            dict = (dictionary *) hollow_list_value;
        }
    }
    dict->value = value;
}

void *dictionary_read(dictionary *dict, char *index, unsigned int strlen){
    void *hollow_list_value;
    dictionary *new_dict;
    int i;
    for(i = 0; i < strlen; i++){
        hollow_list_value = hollow_list_read(dict->child, (int) index[i]);
        if(hollow_list_value == (void *) 0){
            return hollow_list_value;
        } else {
            dict = (dictionary *) hollow_list_value;
        }
    }
    return dict->value;
}

int main(){
    char index0[] = "hello, this is a test";
    char index1[] = "hello, this is also a test";
    char index2[] = "hello world";
    char index3[] = "hi there!";
    char index4[] = "this is something";
    char index5[] = "hi there";

    int item0 = 0;
    int item1 = 1;
    int item2 = 2;
    int item3 = 3;
    int item4 = 4;

    dictionary d;
    d = dictionary_create();
    dictionary_write(&d, index0, 21, &item0);
    dictionary_write(&d, index1, 26, &item1);
    dictionary_write(&d, index2, 11, &item2);
    dictionary_write(&d, index3, 13, &item3);
    dictionary_write(&d, index4, 17, &item4);

    printf("%d\n", *((int *) dictionary_read(&d, index0, 21)));
    printf("%d\n", *((int *) dictionary_read(&d, index1, 26)));
    printf("%d\n", *((int *) dictionary_read(&d, index2, 11)));
    printf("%d\n", *((int *) dictionary_read(&d, index3, 13)));
    printf("%d\n", *((int *) dictionary_read(&d, index4, 17)));
    printf("%d\n", ((int) dictionary_read(&d, index5, 8)));
}

Desafortunadamente no puedes replicar la lista.[x] sintaxis, pero esta es la mejor alternativa que se me ha ocurrido.

Sí, pero no funcionará de la forma especificada. En su lugar, utilizará un struct para almacenar los datos y las funciones que operan en esa estructura, brindándole el resultado que desea. Ver Una biblioteca de matriz asociativa simple en C. Ejemplo de uso:

struct map_t *test;

test=map_create();
map_set(test,"One","Won");
map_set(test,"Two","Too");
map_set(test,"Four","Fore");

avatar de usuario
carpintero mate

de GLib tablas hash y Árboles binarios balanceados podría ser lo que buscas.

avatar de usuario
Remo.D

Mark Wilkins te dio la respuesta correcta. Si desea enviar los datos como un solo fragmento, debe comprender cómo se representan los mapas de C++ en su arquitectura y escribir las funciones de acceso.

De todos modos, si decides recrear el mapa en el dongle, he escrito una pequeña biblioteca C donde puedes escribir cosas como:

tbl_t in_data=NULL;

tblSetSS(in_data,"method","calc_r");
tblSetSN(in_data,"id",12);
tblSetSF(in_data,"loc_a",56.19);
tblSetSF(in_data,"loc_l",44.02);

y luego:

char  *method_name = tblGetP(in_data, "method");
int    id          = tblGetN(in_data, "id");
float  loc_a       = tblGetF(in_data, "loc_a");
float  loc_l       = tblGetF(in_data, "loc_l");

El hashtable es una variación del hash Hopscotch, que es bastante bueno en promedio, y puede tener cualquier combinación de tipo para claves y datos (es decir, puede usar una tabla completa como clave).

El enfoque de esas funciones estaba en facilitar la programación en lugar de la velocidad pura y el código no se ha probado a fondo, pero si le gusta la idea y quiere ampliarla, puede echarle un vistazo al código en googlecode.

(Hay otras cosas como cadenas de longitud variable y una función de coincidencia de patrón de cadena rápida, pero es posible que no sean de interés en este caso).

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad