propiedad - Conjuntos asociativos en C

propiedad asociativa en la suma

Question

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 mediante punteros de entrada y salida.

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

Primero la aplicación de 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);

Siguiente 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 de dongle. ¿Hay un código C o una biblioteca para implementar un comportamiento de matriz asociativa como el anterior?

Answer 1

Este es un hilo viejo, pero pensé que esto aún podría ser útil para cualquiera que busque una implementación. No requiere demasiado código; Hice la mía en ~ 100 líneas sin ninguna biblioteca adicional. Lo llamé un diccionario porque es paralelo (tipo de) el tipo de datos 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 se puede replicar la sintaxis de la lista [x], pero esta es la mejor alternativa que se me ocurrió.

Answer 2

Los Hash Tables y los Binary Balanced Binary Trees de GLib pueden ser lo que buscas.

Answer 3

Mark Wilkins le dio la respuesta correcta. Si desea enviar los datos como un solo fragmento, debe entender 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 de C donde puedes escribir piensa 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 entonces:

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");

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

El objetivo de esas funciones era facilitar la programación en lugar de la velocidad pura y el código no se probó exhaustivamente, pero si le gusta la idea y desea expandirla, puede echarle un vistazo al código en googlecode .

(Hay otras cosas como cadenas de longitud variable y una función de emparejamiento de patrón sttring rápido, pero es posible que en este caso no interesen).

Answer 4

Mi sospecha es que tendrías que escribir la tuya. Si entiendo la arquitectura que está describiendo, tendrá que enviar toda la información en una sola pieza. Si es así, entonces la mayoría de las bibliotecas no funcionarán para eso porque lo más probable es que estén asignando varias piezas de memoria, lo que requeriría transferencias múltiples (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 a la función de send .

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.

Answer 5

Pruebe uthash , una biblioteca de cabecera que implementa una tabla hash en C. Es pequeña y bastante fácil de usar.

Answer 6

Sí, pero no funcionará de la manera que ha especificado. En su lugar, usará una struct para almacenar los datos y las funciones que operan en esa estructura, proporcionándole el resultado que desea. Consulte 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");

Answer 7

Tabla hash de Glib. implementa una interfaz de mapa o (matriz asociativa). Y es muy probable que la implementación de la 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");