Les tableaux associatifs en C

Question

Je suis en œuvre un moyen de transférer un ensemble de données sur une clé programmable. Le dongle est basé sur une technologie de carte à puce et peut exécuter un code arbitraire à l'intérieur. L'entrée et la sortie de données est transmis sous forme de blocs binaires qui peuvent être accessibles par l'intermédiaire des pointeurs d'entrée et de sortie.

Je voudrais utiliser un tableau associatif pour simplifier le code de traitement des données. Tout devrait fonctionner de cette façon:

D'abord l'application hôte:

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

Suivant le code de la clé:

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

Donc, ma question concerne la fonctionnalité partie de dongle. Y at-il un code C ou à la bibliothèque pour mettre en œuvre un tel comportement de tableau associatif comme ci-dessus?

Answer 1

Je soupçonne que vous devez écrire votre propre. Si je comprends bien l'architecture que vous décrivez, alors vous aurez besoin d'envoyer l'ensemble bloc de données en une seule pièce. Si oui, alors la plupart des bibliothèques ne fonctionnera pas pour cela parce qu'ils seront très allouera probablement plusieurs morceaux de mémoire, ce qui nécessiterait plusieurs transferts (et une à l'intérieur de la compréhension de la structure). Il serait similaire à essayer d'utiliser une fonction de hachage bibliothèque, puis d'envoyer son contenu sur le réseau sur une prise juste en passant le pointeur de la racine à la fonction send.

Il serait possible d'écrire quelques utilitaires de votre propre qui gèrent un tableau associatif très simple (ou hachage) dans un seul bloc de mémoire. Si la quantité de données est faible, il pourrait utiliser une simple recherche linéaire pour les entrées et serait un peu assez compact de code.

Answer 2

table de hachage Glib. Implémente une interface carte ou (tableau associatif) . Et il est très probablement la plus mise en œuvre de la table de hachage utilisée pour 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");

Answer 3

uthash , une bibliothèque d'en-tête la mise en œuvre d'une table de hachage dans les petites et assez facile à utiliser C. Il.

Answer 4

Oui, mais il ne fonctionne pas dans la façon dont vous avez spécifié. Il utilisera plutôt un struct pour stocker les données et les fonctions qui opèrent sur ce struct, vous donnant le résultat que vous voulez. Voir Un tableau simple Associatif Library En C . Exemple d'utilisation:

struct map_t *test;

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

Answer 5

tables de hachage et Balanced arbres binaires pourrait être ce que vous êtes après.

Answer 6

Mark Wilkins vous a donné la bonne réponse. Si vous voulez envoyer les données en un seul morceau, vous devez comprendre comment les cartes C ++ sont représentés dans votre architecture et écrire les fonctions d'accès.

Quoi qu'il en soit, si vous décidez de recréer la carte de la clé, j'ai écrit une petite bibliothèque C où l'on pouvait écrire pense comme:

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

et

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

Le Hashtable est une variante du hachage Hopscotch, ce qui est plutôt bon en moyenne, et vous pouvez avoir un mélange de type pour les clés et les données (à savoir, vous pouvez utiliser une table entière comme une clé).

L'accent pour que les fonctions était sur la programmation de l'assouplissement plutôt que la vitesse pure et le code ne soit pas complètement testé mais si vous aimez l'idée et que vous souhaitez développer, vous pouvez consulter le code sur googlecode .

(Il y a d'autres choses comme des chaînes de longueur variable et une fonction de correspondance de motif sttring rapide, mais ceux qui pourraient ne pas être d'intérêt dans ce cas).

Answer 7

Ceci est un vieux fil, mais je pensais que cela pourrait encore être utile pour tout le monde là-bas à la recherche d'une mise en œuvre. Il ne prend pas trop de code; J'ai fait le mien dans ~ 100 lignes de sans bibliothèque supplémentaire. Je l'ai appelé un dictionnaire car il est parallèle (sorte de) le type de données python. Voici mon code:

#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)));
}

Malheureusement, vous ne pouvez pas reproduire la liste [x] syntaxe, mais c'est la meilleure alternative que je suis venu avec.