Diff of /trunk/src/osm.c

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 41 by harbaum, Sun Jan 18 19:43:20 2009 UTC revision 42 by harbaum, Wed Jan 21 20:01:18 2009 UTC
# Line 17  Line 17 
17   * along with OSM2Go.  If not, see <http://www.gnu.org/licenses/>.   * along with OSM2Go.  If not, see <http://www.gnu.org/licenses/>.
18   */   */
19    
20  /* xml parsing has a performance issue */  /* these defines select one of three possible xml parsers */
21    /* this is in fact selected depending on the plattform in the Makefile */
22  // #define OSM_DOM_PARSER  // #define OSM_DOM_PARSER
23  // #define OSM_STREAM_PARSER  // #define OSM_STREAM_PARSER
24  #define OSM_QND_XML_PARSER  // #define OSM_QND_XML_PARSER
25    
26  #include <stdio.h>  #include <stdio.h>
27  #include <stdlib.h>  #include <stdlib.h>
# Line 370  static node_t *osm_parse_osm_node(osm_t Line 371  static node_t *osm_parse_osm_node(osm_t
371      xmlFree(prop);      xmlFree(prop);
372    }    }
373    
374      /* append node to end of hash table if present */
375      if(osm->node_hash) {
376        hash_item_t **item = &osm->node_hash->hash[ID2HASH(node->id)];
377        while(*item) item = &(*item)->next;
378    
379        *item = g_new0(hash_item_t, 1);
380        (*item)->data.node = node;
381      }
382    
383    /* scan for tags and attach a list of tags */    /* scan for tags and attach a list of tags */
384    tag_t **tag = &node->tag;    tag_t **tag = &node->tag;
385    for (cur_node = a_node->children; cur_node; cur_node = cur_node->next) {    for (cur_node = a_node->children; cur_node; cur_node = cur_node->next) {
# Line 481  node_chain_t *osm_parse_osm_way_nd(osm_t Line 491  node_chain_t *osm_parse_osm_way_nd(osm_t
491      node_chain_t *node_chain = g_new0(node_chain_t, 1);      node_chain_t *node_chain = g_new0(node_chain_t, 1);
492    
493      /* search matching node */      /* search matching node */
494      node_chain->node = osm->node;      node_chain->node = osm_get_node_by_id(osm, id);
     while(node_chain->node && node_chain->node->id != id)  
       node_chain->node = node_chain->node->next;  
   
495      if(!node_chain->node) printf("Node id %lu not found\n", id);      if(!node_chain->node) printf("Node id %lu not found\n", id);
496        else                  node_chain->node->ways++;
     if(node_chain->node)  
       node_chain->node->ways++;  
497    
498      xmlFree(prop);      xmlFree(prop);
499    
# Line 527  static way_t *osm_parse_osm_way(osm_t *o Line 532  static way_t *osm_parse_osm_way(osm_t *o
532      xmlFree(prop);      xmlFree(prop);
533    }    }
534    
535      /* append way to end of hash table if present */
536      if(osm->way_hash) {
537        hash_item_t **item = &osm->way_hash->hash[ID2HASH(way->id)];
538        while(*item) item = &(*item)->next;
539    
540        *item = g_new0(hash_item_t, 1);
541        (*item)->data.way = way;
542      }
543    
544    /* scan for tags/nodes and attach their lists */    /* scan for tags/nodes and attach their lists */
545    tag_t **tag = &way->tag;    tag_t **tag = &way->tag;
546    node_chain_t **node_chain = &way->node_chain;    node_chain_t **node_chain = &way->node_chain;
# Line 652  member_t *osm_parse_osm_relation_member( Line 666  member_t *osm_parse_osm_relation_member(
666    
667      case WAY:      case WAY:
668        /* search matching way */        /* search matching way */
669        member->way = osm->way;        member->way = osm_get_way_by_id(osm, id);
       while(member->way && member->way->id != id)  
         member->way = member->way->next;  
   
670        if(!member->way) {        if(!member->way) {
671          member->type = WAY_ID;          member->type = WAY_ID;
672          member->id = id;          member->id = id;
# Line 664  member_t *osm_parse_osm_relation_member( Line 675  member_t *osm_parse_osm_relation_member(
675    
676      case NODE:      case NODE:
677        /* search matching node */        /* search matching node */
678        member->node = osm->node;        member->node = osm_get_node_by_id(osm, id);
       while(member->node && member->node->id != id)  
         member->node = member->node->next;  
   
679        if(!member->node) {        if(!member->node) {
680          member->type = NODE_ID;          member->type = NODE_ID;
681          member->id = id;          member->id = id;
# Line 676  member_t *osm_parse_osm_relation_member( Line 684  member_t *osm_parse_osm_relation_member(
684    
685      case RELATION:      case RELATION:
686        /* search matching relation */        /* search matching relation */
687        member->relation = osm->relation;        member->relation = osm_get_relation_by_id(osm, id);
       while(member->relation && member->relation->id != id)  
         member->relation = member->relation->next;  
   
688        if(!member->relation) {        if(!member->relation) {
689          member->type = NODE_ID;          member->type = NODE_ID;
690          member->id = id;          member->id = id;
# Line 755  static relation_t *osm_parse_osm_relatio Line 760  static relation_t *osm_parse_osm_relatio
760    
761  /* ----------------------- generic xml handling -------------------------- */  /* ----------------------- generic xml handling -------------------------- */
762    
763  /* parse loc entry */  /* parse osm entry */
764  static void osm_parse_osm(osm_t *osm, xmlDocPtr doc, xmlNode * a_node) {  static void osm_parse_osm(osm_t *osm, xmlDocPtr doc, xmlNode * a_node) {
765    xmlNode *cur_node = NULL;    xmlNode *cur_node = NULL;
766    
# Line 837  static osm_t *osm_parse_root(xmlDocPtr d Line 842  static osm_t *osm_parse_root(xmlDocPtr d
842    
843    /* allocate memory to hold osm file description */    /* allocate memory to hold osm file description */
844    osm = g_new0(osm_t, 1);    osm = g_new0(osm_t, 1);
845      osm->node_hash = g_new0(hash_table_t, 1);
846      osm->way_hash = g_new0(hash_table_t, 1);
847    
848    for (cur_node = a_node; cur_node; cur_node = cur_node->next) {    for (cur_node = a_node; cur_node; cur_node = cur_node->next) {
849      if (cur_node->type == XML_ELEMENT_NODE) {      if (cur_node->type == XML_ELEMENT_NODE) {
# Line 874  static osm_t *osm_parse_doc(xmlDocPtr do Line 881  static osm_t *osm_parse_doc(xmlDocPtr do
881    
882  /* ------------------ osm handling ----------------- */  /* ------------------ osm handling ----------------- */
883    
884    /* the two hash tables eat over 512kBytes memory and may thus be */
885    /* freed at any time. osm2go can work without them (albeit slower) */
886    static void hash_table_free(hash_table_t *table) {
887      if(!table) return;
888    
889      int i;
890      for(i=0;i<65536;i++) {
891        hash_item_t *item = table->hash[i];
892        while(item) {
893          hash_item_t *next = item->next;
894          g_free(item);
895          item = next;
896        }
897      }
898    }
899    
900    void osm_hash_tables_free(osm_t *osm) {
901      hash_table_free(osm->node_hash);
902      osm->node_hash = NULL;
903      hash_table_free(osm->way_hash);
904      osm->way_hash = NULL;
905    }
906    
907  void osm_free(icon_t **icon, osm_t *osm) {  void osm_free(icon_t **icon, osm_t *osm) {
908    if(!osm) return;    if(!osm) return;
909    
910      osm_hash_tables_free(osm);
911    
912    if(osm->bounds)   osm_bounds_free(osm->bounds);    if(osm->bounds)   osm_bounds_free(osm->bounds);
913    if(osm->user)     osm_users_free(osm->user);    if(osm->user)     osm_users_free(osm->user);
914    if(osm->way)      osm_ways_free(osm->way);    if(osm->way)      osm_ways_free(osm->way);
# Line 1057  static node_t *process_node(xmlTextReade Line 1089  static node_t *process_node(xmlTextReade
1089    
1090    pos2lpos(osm->bounds, &node->pos, &node->lpos);    pos2lpos(osm->bounds, &node->pos, &node->lpos);
1091    
1092      /* append node to end of hash table if present */
1093      if(osm->node_hash) {
1094        hash_item_t **item = &osm->node_hash->hash[ID2HASH(node->id)];
1095        while(*item) item = &(*item)->next;
1096    
1097        *item = g_new0(hash_item_t, 1);
1098        (*item)->data.node = node;
1099      }
1100    
1101    /* just an empty element? then return the node as it is */    /* just an empty element? then return the node as it is */
1102    if(xmlTextReaderIsEmptyElement(reader))    if(xmlTextReaderIsEmptyElement(reader))
1103      return node;      return node;
# Line 1094  static node_chain_t *process_nd(xmlTextR Line 1135  static node_chain_t *process_nd(xmlTextR
1135      node_chain_t *node_chain = g_new0(node_chain_t, 1);      node_chain_t *node_chain = g_new0(node_chain_t, 1);
1136    
1137      /* search matching node */      /* search matching node */
1138      node_chain->node = osm->node;      node_chain->node = osm_get_node_by_id(osm, id);
     while(node_chain->node && node_chain->node->id != id)  
       node_chain->node = node_chain->node->next;  
   
1139      if(!node_chain->node) printf("Node id %lu not found\n", id);      if(!node_chain->node) printf("Node id %lu not found\n", id);
1140        else                  node_chain->node->ways++;
     if(node_chain->node)  
       node_chain->node->ways++;  
1141    
1142      xmlFree(prop);      xmlFree(prop);
1143    
# Line 1138  static way_t *process_way(xmlTextReaderP Line 1174  static way_t *process_way(xmlTextReaderP
1174      xmlFree(prop);      xmlFree(prop);
1175    }    }
1176    
1177      /* append way to end of hash table if present */
1178      if(osm->way_hash) {
1179        hash_item_t **item = &osm->way_hash->hash[ID2HASH(way->id)];
1180        while(*item) item = &(*item)->next;
1181    
1182        *item = g_new0(hash_item_t, 1);
1183        (*item)->data.way = way;
1184      }
1185    
1186    /* just an empty element? then return the way as it is */    /* just an empty element? then return the way as it is */
1187    /* (this should in fact never happen as this would be a way without nodes) */    /* (this should in fact never happen as this would be a way without nodes) */
1188    if(xmlTextReaderIsEmptyElement(reader))    if(xmlTextReaderIsEmptyElement(reader))
# Line 1193  static member_t *process_member(xmlTextR Line 1238  static member_t *process_member(xmlTextR
1238    
1239      case WAY:      case WAY:
1240        /* search matching way */        /* search matching way */
1241        member->way = osm->way;        member->way = osm_get_way_by_id(osm, id);
       while(member->way && member->way->id != id)  
         member->way = member->way->next;  
   
1242        if(!member->way) {        if(!member->way) {
1243          member->type = WAY_ID;          member->type = WAY_ID;
1244          member->id = id;          member->id = id;
# Line 1205  static member_t *process_member(xmlTextR Line 1247  static member_t *process_member(xmlTextR
1247    
1248      case NODE:      case NODE:
1249        /* search matching node */        /* search matching node */
1250        member->node = osm->node;        member->node = osm_get_node_by_id(osm, id);
       while(member->node && member->node->id != id)  
         member->node = member->node->next;  
   
1251        if(!member->node) {        if(!member->node) {
1252          member->type = NODE_ID;          member->type = NODE_ID;
1253          member->id = id;          member->id = id;
# Line 1217  static member_t *process_member(xmlTextR Line 1256  static member_t *process_member(xmlTextR
1256    
1257      case RELATION:      case RELATION:
1258        /* search matching relation */        /* search matching relation */
1259        member->relation = osm->relation;        member->relation = osm_get_relation_by_id(osm, id);
       while(member->relation && member->relation->id != id)  
         member->relation = member->relation->next;  
   
1260        if(!member->relation) {        if(!member->relation) {
1261          member->type = NODE_ID;          member->type = NODE_ID;
1262          member->id = id;          member->id = id;
# Line 1306  static relation_t *process_relation(xmlT Line 1342  static relation_t *process_relation(xmlT
1342  static osm_t *process_osm(xmlTextReaderPtr reader) {  static osm_t *process_osm(xmlTextReaderPtr reader) {
1343    /* alloc osm structure */    /* alloc osm structure */
1344    osm_t *osm = g_new0(osm_t, 1);    osm_t *osm = g_new0(osm_t, 1);
1345      osm->node_hash = g_new0(hash_table_t, 1);
1346      osm->way_hash = g_new0(hash_table_t, 1);
1347    
1348    node_t **node = &osm->node;    node_t **node = &osm->node;
1349    way_t **way = &osm->way;    way_t **way = &osm->way;
# Line 1500  static gboolean osm_node_cb(qnd_xml_stac Line 1538  static gboolean osm_node_cb(qnd_xml_stac
1538    /* store current tag pointer in userdata for fast access to current tag */    /* store current tag pointer in userdata for fast access to current tag */
1539    stack->userdata[1] = &node->tag;    stack->userdata[1] = &node->tag;
1540    
1541      /* append node to end of hash table if present */
1542      if(osm->node_hash) {
1543        hash_item_t **item = &osm->node_hash->hash[ID2HASH(node->id)];
1544        while(*item) item = &(*item)->next;
1545    
1546        *item = g_new0(hash_item_t, 1);
1547        (*item)->data.node = node;
1548      }
1549    
1550    return TRUE;    return TRUE;
1551  }  }
1552    
# Line 1515  static gboolean osm_way_nd_cb(qnd_xml_st Line 1562  static gboolean osm_way_nd_cb(qnd_xml_st
1562        g_new0(node_chain_t, 1);        g_new0(node_chain_t, 1);
1563    
1564      /* search matching node */      /* search matching node */
1565      node_chain->node = osm->node;      node_chain->node = osm_get_node_by_id(osm, id);
     while(node_chain->node && node_chain->node->id != id)  
       node_chain->node = node_chain->node->next;  
   
1566      if(!node_chain->node) printf("Node id %lu not found\n", id);      if(!node_chain->node) printf("Node id %lu not found\n", id);
1567        else                  node_chain->node->ways++;
     if(node_chain->node)  
       node_chain->node->ways++;  
1568    
1569      stack->prev->userdata[2] = &node_chain->next;      stack->prev->userdata[2] = &node_chain->next;
1570    }    }
# Line 1551  gboolean osm_way_cb(qnd_xml_stack_t *sta Line 1593  gboolean osm_way_cb(qnd_xml_stack_t *sta
1593    stack->userdata[1] = &way->tag;    stack->userdata[1] = &way->tag;
1594    stack->userdata[2] = &way->node_chain;    stack->userdata[2] = &way->node_chain;
1595    
1596      /* append way to end of hash table if present */
1597      if(osm->way_hash) {
1598        hash_item_t **item = &osm->way_hash->hash[ID2HASH(way->id)];
1599        while(*item) item = &(*item)->next;
1600    
1601        *item = g_new0(hash_item_t, 1);
1602        (*item)->data.way = way;
1603      }
1604    
1605    return TRUE;    return TRUE;
1606  }  }
1607    
# Line 1580  static gboolean osm_rel_member_cb(qnd_xm Line 1631  static gboolean osm_rel_member_cb(qnd_xm
1631    
1632      case WAY:      case WAY:
1633        /* search matching way */        /* search matching way */
1634        member->way = osm->way;        member->way = osm_get_way_by_id(osm, id);
       while(member->way && member->way->id != id)  
         member->way = member->way->next;  
   
1635        if(!member->way) {        if(!member->way) {
1636          member->type = WAY_ID;          member->type = WAY_ID;
1637          member->id = id;          member->id = id;
# Line 1592  static gboolean osm_rel_member_cb(qnd_xm Line 1640  static gboolean osm_rel_member_cb(qnd_xm
1640    
1641      case NODE:      case NODE:
1642        /* search matching node */        /* search matching node */
1643        member->node = osm->node;        member->node = osm_get_node_by_id(osm, id);
       while(member->node && member->node->id != id)  
         member->node = member->node->next;  
   
1644        if(!member->node) {        if(!member->node) {
1645          member->type = NODE_ID;          member->type = NODE_ID;
1646          member->id = id;          member->id = id;
# Line 1604  static gboolean osm_rel_member_cb(qnd_xm Line 1649  static gboolean osm_rel_member_cb(qnd_xm
1649    
1650      case RELATION:      case RELATION:
1651        /* search matching relation */        /* search matching relation */
1652        member->relation = osm->relation;        member->relation = osm_get_relation_by_id(osm, id);
       while(member->relation && member->relation->id != id)  
         member->relation = member->relation->next;  
   
1653        if(!member->relation) {        if(!member->relation) {
1654          member->type = NODE_ID;          member->type = NODE_ID;
1655          member->id = id;          member->id = id;
# Line 1657  gboolean osm_cb(qnd_xml_stack_t *stack, Line 1699  gboolean osm_cb(qnd_xml_stack_t *stack,
1699    osm_t *osm = stack->prev->userdata[0] =    osm_t *osm = stack->prev->userdata[0] =
1700      stack->userdata[0] = g_new0(osm_t, 1);      stack->userdata[0] = g_new0(osm_t, 1);
1701    
1702      osm->node_hash = g_new0(hash_table_t, 1);
1703      osm->way_hash = g_new0(hash_table_t, 1);
1704    
1705    /* store direct pointers for faster list access */    /* store direct pointers for faster list access */
1706    /* (otherwise we'd have to search the end of the lists for every item */    /* (otherwise we'd have to search the end of the lists for every item */
1707    /* to be attached) */    /* to be attached) */
# Line 1712  osm_t *osm_parse(char *filename) { Line 1757  osm_t *osm_parse(char *filename) {
1757    struct timeval start;    struct timeval start;
1758    gettimeofday(&start, NULL);    gettimeofday(&start, NULL);
1759    
   
1760  #ifdef OSM_STREAM_PARSER  #ifdef OSM_STREAM_PARSER
1761    LIBXML_TEST_VERSION;    LIBXML_TEST_VERSION;
1762    
# Line 2002  char *osm_generate_xml_relation(osm_t *o Line 2046  char *osm_generate_xml_relation(osm_t *o
2046    return osm_generate_xml(osm, RELATION, relation);    return osm_generate_xml(osm, RELATION, relation);
2047  }  }
2048    
2049    /* the following three functions are eating much CPU power */
2050    /* as they search the objects lists. Hashing is supposed to help */
2051  node_t *osm_get_node_by_id(osm_t *osm, item_id_t id) {  node_t *osm_get_node_by_id(osm_t *osm, item_id_t id) {
2052      if(id > 0 && osm->node_hash) {
2053        // use hash table if present
2054        hash_item_t *item = osm->node_hash->hash[ID2HASH(id)];
2055        while(item) {
2056          if(item->data.node->id == id)
2057            return item->data.node;
2058    
2059          item = item->next;
2060        }
2061      }
2062    
2063      /* use linear search if no hash tables are present or search in hash table failed */
2064    node_t *node = osm->node;    node_t *node = osm->node;
2065    while(node) {    while(node) {
2066      if(node->id == id)      if(node->id == id)
2067        return node;        return node;
2068    
2069      node = node->next;      node = node->next;
2070    }    }
2071    
2072    return NULL;    return NULL;
2073  }  }
2074    
2075  way_t *osm_get_way_by_id(osm_t *osm, item_id_t id) {  way_t *osm_get_way_by_id(osm_t *osm, item_id_t id) {
2076      if(id > 0 && osm->way_hash) {
2077        // use hash table if present
2078        hash_item_t *item = osm->way_hash->hash[ID2HASH(id)];
2079        while(item) {
2080          if(item->data.way->id == id)
2081            return item->data.way;
2082    
2083          item = item->next;
2084        }
2085      }
2086    
2087      /* use linear search if no hash tables are present or search on hash table failed */
2088    way_t *way = osm->way;    way_t *way = osm->way;
2089    while(way) {    while(way) {
2090      if(way->id == id)      if(way->id == id)
2091        return way;        return way;
2092    
2093      way = way->next;      way = way->next;
2094    }    }
2095    
2096    return NULL;    return NULL;
2097  }  }
2098    
2099  relation_t *osm_get_relation_by_id(osm_t *osm, item_id_t id) {  relation_t *osm_get_relation_by_id(osm_t *osm, item_id_t id) {
2100      // use linear search
2101    relation_t *relation = osm->relation;    relation_t *relation = osm->relation;
2102    while(relation) {    while(relation) {
2103      if(relation->id == id)      if(relation->id == id)
Legend:
Removed from v.41  
changed lines
  Added in v.42