HashMap mit search.h

Question

Ich habe eine XML-Datei mit Koordinaten (lon, lat) und einer ID. Das Problem ist, ich möchte diese Informationen in einem HashMap speichern, aber ich weiß nicht die Größe Max meiner Datei. Ich sah einige Beispiel in internet:

#define _GNU_SOURCE 

#include <search.h> // hcreate_r() hdestroy_r() struct hsearch_data 
#include <string.h> // memset() 
#include <stdio.h> // perror() 
#include <stdlib.h> //exit() 

#define TAB 4 

... 

struct hsearch_data hash; 
size_t max_element = 42; // of elements in search table 

... 

char *food[] = { "Apple", 
       "Banana", 
       "Lemon", 
       "Carrot" 
}; 
char *color[] = { "red", 
        "yellow", 
        "yellow", 
        "orange" 
}; 

// we create the hash 
memset(&hash, 0, sizeof(hash)); 
if (hcreate_r(max_element, &hash) == 0) { 
    perror("hcreate_r"); 
    exit(1); 
} 

/* 
    adding some elements 
*/ 

// we destroy the hash 
hdestroy_r(&hash); 

max_element ist weiß nicht, in meinem Fall, und ich weiß nicht, wie das beheben, hier mein Code:

#include <stdlib.h> 
#include <stdio.h> 
#include <string.h> 
#include <libxml/tree.h> 
#include <libxml/parser.h> 

#define MAX_REF_LEN 10 

static char der_ref[MAX_REF_LEN + 1]; 
static xmlChar *der_intitule = NULL; 

void debut_document(void *user_data) { 
    *der_ref = '\0'; 
    der_intitule = NULL; 
} 

void debut_element(void *user_data, const xmlChar *name, const xmlChar **attrs) { 
    if (xmlStrEqual(name, BAD_CAST "node")) { 
     if (NULL != attrs) { 
      int i; 
      for (i = 0; attrs[i] != NULL; i += 2) { 
       if (xmlStrEqual(attrs[i], BAD_CAST "lat")) { 
        strncpy(der_ref, (char *)attrs[i + 1], MAX_REF_LEN); 
        printf("lat %s\n", der_ref); 
       } else 
       if (xmlStrEqual(attrs[i], BAD_CAST "lon")) { 
        strncpy(der_ref, (char *)attrs[i + 1], MAX_REF_LEN); 
        printf("lon %s\n", der_ref); 
       } 
      } 
     } 
    } 
} 

int main() { 

    xmlSAXHandler sh = { 0 }; 

    sh.startDocument = debut_document; 
    sh.startElement = debut_element; 

    if (xmlSAXUserParseFile(&sh, NULL, "map.osm") != 0) { 
     fprintf(stderr, "Une erreur est survenue lors du parsing\n"); 
     return EXIT_FAILURE; 
    } 
    return EXIT_SUCCESS; 
} 

ich nicht das umgesetzt haben Bibliothek suchen, aber ich möchte meine HashMap in meiner debut_element Funktion erstellen.

"map.osm" ist meine XML-Datei, aber die Größe ist nicht fix.

Answer 1

Die Hashtabellenimplementierung in <search.h> unterliegt mehreren Einschränkungen: Sie müssen die Größe im Voraus kennen und können keine Elemente entfernen.

In Ihrem Fall können Sie es immer noch verwenden, vorausgesetzt Ihre Liste der Elemente ändert sich nicht, nachdem Sie es gelesen haben. Lesen Sie zuerst alle Elemente in ein danymisches Array. Nachdem alle Standorte gelesen wurden, erstellen Sie die Hashtabelle mit der gewünschten Dimension und fügen Sie alle Standorte hinzu.

Die Werte sind Zeiger auf die Elemente im Array, der Schlüssel muss eine Zeichenfolge sein. Daher sollten Sie eine Zeichenfolgedarstellung der ID mit dem Speicherort beibehalten.

Hier ist eine Beispielimplementierung. Anstatt die Speicherorte aus der Datei zu lesen, werden einige zufällige Werte erstellt.

#include <stdio.h> 
#include <stdlib.h> 
#include <search.h> 
#include <math.h> 
#include <time.h> 

struct loc { 
    int id; 
    char label[12]; 
    double lat, lon; 
}; 

struct map { 
    size_t size; 
    size_t count; 
    struct loc *loc; 
    struct hsearch_data hash; 
}; 

double urand(void) 
{ 
    return rand()/(1.0 + RAND_MAX); 
} 

void loc_print(struct loc *loc) 
{ 
    printf("%s: (%g%c, %g%c)\n", loc->label, 
     fabs(loc->lon), loc->lon > 0 ? 'E' : 'W', 
     fabs(loc->lat), loc->lat > 0 ? 'N' : 'S'); 
} 

void map_destroy(struct map *map) 
{ 
    free(map->loc); 
    hdestroy_r(&map->hash); 
    free(map); 
} 

struct map *map_create(void) 
{ 
    struct map *map = calloc(1, sizeof(*map)); 
    size_t i; 

    while (0.005 * map->count < urand()) { 
     struct loc *p; 

     if (map->count == map->size) { 
      map->size *= 2; 
      if (map->size == 0) map->size = 1024; 

      p = realloc(map->loc, map->size * sizeof(*p)); 
      if (p == NULL) { 
       map_destroy(map); 
       exit(1); 
      } 
      map->loc = p; 
     } 

     p = &map->loc[map->count]; 
     p->lon = 360.0 * urand() - 180.0; 
     p->lat = 180.0 * urand() - 90.0; 
     p->id = map->count + 1; 
     snprintf(p->label, sizeof(p->label), "%d", p->id); 
     map->count++; 

     loc_print(p); 
    } 

    hcreate_r(3 * map->count/2, &map->hash); 

    for (i = 0; i < map->count; i++) { 
     struct loc *p = &map->loc[i];   
     ENTRY e, *res = NULL; 

     e.key = p->label; 
     e.data = p; 
     hsearch_r(e, ENTER, &res, &map->hash); 
    } 

    return map; 
} 

struct loc *map_find(struct map *map, int id) 
{ 
    char label[12]; 
    ENTRY e, *res; 

    snprintf(label, sizeof(label), "%d", id); 
    e.key = label; 
    hsearch_r(e, FIND, &res, &map->hash); 

    if (res) return res->data; 
    return NULL; 
} 

int main() 
{ 
    struct map *map; 
    int i; 

    srand(time(NULL)); 

    puts("Creating map"); 
    map = map_create(); 

    puts("Looking up values"); 
    for (i = 5; i < 80; i += 5) { 
     struct loc *loc = map_find(map, i); 

     if (loc) { 
      loc_print(loc); 
     } else { 
      printf("%d not found.\n", i); 
     } 
    } 

    map_destroy(map); 

    return 0; 
} 

Sie auch diese Technik, wenn Sie Ihre Liste der Standorte später Gows auf verwenden: Nur die alte Hash-Tabelle zerstören, wenn ein bestimmte Schwellenwert ist, 75% der Hashtabellengröße sagen, erreicht ist, und schafft es mit einem neuen größere Größe. Dies sollte funktionieren, da die Hash-Tabelle nur eine Hilfsdarstellung vorhandener Daten darstellt, die eine schnelle Suche ermöglichen.