Subversion Repositories Kolibri OS

Rev

Rev 3584 | Blame | Last modification | View Log | RSS feed

  1. /*
  2.  * Copyright 2004 John M Bell <jmb202@ecs.soton.ac.uk>
  3.  *
  4.  * This file is part of NetSurf, http://www.netsurf-browser.org/
  5.  *
  6.  * NetSurf is free software; you can redistribute it and/or modify
  7.  * it under the terms of the GNU General Public License as published by
  8.  * the Free Software Foundation; version 2 of the License.
  9.  *
  10.  * NetSurf is distributed in the hope that it will be useful,
  11.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13.  * GNU General Public License for more details.
  14.  *
  15.  * You should have received a copy of the GNU General Public License
  16.  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17.  */
  18.  
  19. /*
  20.  * Much of this shamelessly copied from utils/messages.c
  21.  */
  22.  
  23. #include <assert.h>
  24. #include <stdbool.h>
  25. #include <string.h>
  26. #include <strings.h>
  27.  
  28. #include <dom/dom.h>
  29.  
  30. #include "content/content_protected.h"
  31. #include "content/hlcache.h"
  32. #include "render/box.h"
  33. #include "render/html_internal.h"
  34. #include "render/imagemap.h"
  35. #include "utils/corestrings.h"
  36. #include "utils/log.h"
  37. #include "utils/utils.h"
  38.  
  39. #define HASH_SIZE 31 /* fixed size hash table */
  40.  
  41. typedef enum {
  42.         IMAGEMAP_DEFAULT,
  43.         IMAGEMAP_RECT,
  44.         IMAGEMAP_CIRCLE,
  45.         IMAGEMAP_POLY
  46. } imagemap_entry_type;
  47.  
  48. struct mapentry {
  49.         imagemap_entry_type type;       /**< type of shape */
  50.         nsurl *url;                     /**< absolute url to go to */
  51.         char *target;                   /**< target frame (if any) */
  52.         union {
  53.                 struct {
  54.                         int x;          /**< x coordinate of centre */
  55.                         int y;          /**< y coordinate of center */
  56.                         int r;          /**< radius of circle */
  57.                 } circle;
  58.                 struct {
  59.                         int x0;         /**< left hand edge */
  60.                         int y0;         /**< top edge */
  61.                         int x1;         /**< right hand edge */
  62.                         int y1;         /**< bottom edge */
  63.                 } rect;
  64.                 struct {
  65.                         int num;        /**< number of points */
  66.                         float *xcoords; /**< x coordinates */
  67.                         float *ycoords; /**< y coordinates */
  68.                 } poly;
  69.         } bounds;
  70.         struct mapentry *next;          /**< next entry in list */
  71. };
  72.  
  73. struct imagemap {
  74.         char *key;              /**< key for this entry */
  75.         struct mapentry *list;  /**< pointer to linked list of entries */
  76.         struct imagemap *next;  /**< next entry in this hash chain */
  77. };
  78.  
  79. static bool imagemap_add(html_content *c, dom_string *key,
  80.                 struct mapentry *list);
  81. static bool imagemap_create(html_content *c);
  82. static bool imagemap_extract_map(dom_node *node, html_content *c,
  83.                 struct mapentry **entry);
  84. static bool imagemap_addtolist(dom_node *n, nsurl *base_url,
  85.                 struct mapentry **entry, dom_string *tagtype);
  86. static void imagemap_freelist(struct mapentry *list);
  87. static unsigned int imagemap_hash(const char *key);
  88. static int imagemap_point_in_poly(int num, float *xpt, float *ypt,
  89.                 unsigned long x, unsigned long y, unsigned long click_x,
  90.                 unsigned long click_y);
  91.  
  92. /**
  93.  * Add an imagemap to the hashtable, creating it if it doesn't exist
  94.  *
  95.  * \param c The containing content
  96.  * \param key The name of the imagemap
  97.  * \param list List of map regions
  98.  * \return true on succes, false otherwise
  99.  */
  100. bool imagemap_add(html_content *c, dom_string *key, struct mapentry *list)
  101. {
  102.         struct imagemap *map;
  103.         unsigned int slot;
  104.  
  105.         assert(c != NULL);
  106.         assert(key != NULL);
  107.         assert(list != NULL);
  108.  
  109.         if (imagemap_create(c) == false)
  110.                 return false;
  111.  
  112.         map = calloc(1, sizeof(*map));
  113.         if (map == NULL)
  114.                 return false;
  115.        
  116.         /* \todo Stop relying on NULL termination of dom_string */
  117.         map->key = strdup(dom_string_data(key));
  118.         if (map->key == NULL) {
  119.                 free(map);
  120.                 return false;
  121.         }
  122.  
  123.         map->list = list;
  124.  
  125.         slot = imagemap_hash(map->key);
  126.  
  127.         map->next = c->imagemaps[slot];
  128.         c->imagemaps[slot] = map;
  129.  
  130.         return true;
  131. }
  132.  
  133. /**
  134.  * Create hashtable of imagemaps
  135.  *
  136.  * \param c The containing content
  137.  * \return true on success, false otherwise
  138.  */
  139. bool imagemap_create(html_content *c)
  140. {
  141.         assert(c != NULL);
  142.  
  143.         if (c->imagemaps == NULL) {
  144.                 c->imagemaps = calloc(HASH_SIZE, sizeof(struct imagemap));
  145.                 if (c->imagemaps == NULL) {
  146.                         return false;
  147.                 }
  148.         }
  149.  
  150.         return true;
  151. }
  152.  
  153. /**
  154.  * Destroy hashtable of imagemaps
  155.  *
  156.  * \param c The containing content
  157.  */
  158. void imagemap_destroy(html_content *c)
  159. {
  160.         unsigned int i;
  161.  
  162.         assert(c != NULL);
  163.  
  164.         /* no imagemaps -> return */
  165.         if (c->imagemaps == NULL)
  166.                 return;
  167.  
  168.         for (i = 0; i != HASH_SIZE; i++) {
  169.                 struct imagemap *map, *next;
  170.  
  171.                 map = c->imagemaps[i];
  172.                 while (map != NULL) {
  173.                         next = map->next;
  174.                         imagemap_freelist(map->list);
  175.                         free(map->key);
  176.                         free(map);
  177.                         map = next;
  178.                 }
  179.         }
  180.  
  181.         free(c->imagemaps);
  182. }
  183.  
  184. /**
  185.  * Dump imagemap data to the log
  186.  *
  187.  * \param c The containing content
  188.  */
  189. void imagemap_dump(html_content *c)
  190. {
  191.         unsigned int i;
  192.  
  193.         int j;
  194.  
  195.         assert(c != NULL);
  196.  
  197.         if (c->imagemaps == NULL)
  198.                 return;
  199.  
  200.         for (i = 0; i != HASH_SIZE; i++) {
  201.                 struct imagemap *map;
  202.                 struct mapentry *entry;
  203.  
  204.                 map = c->imagemaps[i];
  205.                 while (map != NULL) {
  206.                         LOG(("Imagemap: %s", map->key));
  207.  
  208.                         for (entry = map->list; entry; entry = entry->next) {
  209.                                 switch (entry->type) {
  210.                                 case IMAGEMAP_DEFAULT:
  211.                                         LOG(("\tDefault: %s", nsurl_access(
  212.                                                         entry->url)));
  213.                                         break;
  214.                                 case IMAGEMAP_RECT:
  215.                                         LOG(("\tRectangle: %s: [(%d,%d),(%d,%d)]",
  216.                                                 nsurl_access(entry->url),
  217.                                                 entry->bounds.rect.x0,
  218.                                                 entry->bounds.rect.y0,
  219.                                                 entry->bounds.rect.x1,
  220.                                                 entry->bounds.rect.y1));
  221.                                         break;
  222.                                 case IMAGEMAP_CIRCLE:
  223.                                         LOG(("\tCircle: %s: [(%d,%d),%d]",
  224.                                                 nsurl_access(entry->url),
  225.                                                 entry->bounds.circle.x,
  226.                                                 entry->bounds.circle.y,
  227.                                                 entry->bounds.circle.r));
  228.                                         break;
  229.                                 case IMAGEMAP_POLY:
  230.                                         LOG(("\tPolygon: %s:", nsurl_access(
  231.                                                         entry->url)));
  232.                                         for (j = 0; j != entry->bounds.poly.num;
  233.                                                         j++) {
  234.                                                 fprintf(stderr, "(%d,%d) ",
  235.                                                         (int)entry->bounds.poly.xcoords[j],
  236.                                                         (int)entry->bounds.poly.ycoords[j]);
  237.                                         }
  238.                                         fprintf(stderr,"\n");
  239.                                         break;
  240.                                 }
  241.                         }
  242.                         map = map->next;
  243.                 }
  244.         }
  245. }
  246.  
  247. /**
  248.  * Extract all imagemaps from a document tree
  249.  *
  250.  * \param c The content
  251.  * \param map_str A dom_string which is "map"
  252.  * \return false on memory exhaustion, true otherwise
  253.  */
  254. nserror
  255. imagemap_extract(html_content *c)
  256. {
  257.         dom_nodelist *nlist;
  258.         dom_exception exc;
  259.         unsigned long mapnr;
  260.         uint32_t maybe_maps;
  261.         nserror ret = NSERROR_OK;
  262.  
  263.         exc = dom_document_get_elements_by_tag_name(c->document,
  264.                                                     corestring_dom_map,
  265.                                                     &nlist);
  266.         if (exc != DOM_NO_ERR) {
  267.                 return NSERROR_DOM;
  268.         }
  269.        
  270.         exc = dom_nodelist_get_length(nlist, &maybe_maps);
  271.         if (exc != DOM_NO_ERR) {
  272.                 ret = NSERROR_DOM;
  273.                 goto out_nlist;
  274.         }
  275.        
  276.         for (mapnr = 0; mapnr < maybe_maps; ++mapnr) {
  277.                 dom_node *node;
  278.                 dom_string *name;
  279.                 exc = dom_nodelist_item(nlist, mapnr, &node);
  280.                 if (exc != DOM_NO_ERR) {
  281.                         ret = NSERROR_DOM;
  282.                         goto out_nlist;
  283.                 }
  284.                
  285.                 exc = dom_element_get_attribute(node, corestring_dom_id,
  286.                                                 &name);
  287.                 if (exc != DOM_NO_ERR) {
  288.                         dom_node_unref(node);
  289.                         ret = NSERROR_DOM;
  290.                         goto out_nlist;
  291.                 }
  292.                
  293.                 if (name == NULL) {
  294.                         exc = dom_element_get_attribute(node,
  295.                                                         corestring_dom_name,
  296.                                                         &name);
  297.                         if (exc != DOM_NO_ERR) {
  298.                                 dom_node_unref(node);
  299.                                 ret = NSERROR_DOM;
  300.                                 goto out_nlist;
  301.                         }
  302.                 }
  303.                
  304.                 if (name != NULL) {
  305.                         struct mapentry *entry = NULL;
  306.                         if (imagemap_extract_map(node, c, &entry) == false) {
  307.                                 dom_string_unref(name);
  308.                                 dom_node_unref(node);
  309.                                 ret = NSERROR_NOMEM; /** @todo check this */
  310.                                 goto out_nlist;
  311.                         }
  312.                        
  313.                         /* imagemap_extract_map may not extract anything,
  314.                          * so entry can still be NULL here. This isn't an
  315.                          * error as it just means that we've encountered
  316.                          * an incorrectly defined <map>...</map> block
  317.                          */
  318.                         if ((entry != NULL) &&
  319.                             (imagemap_add(c, name, entry) == false)) {
  320.                                 dom_string_unref(name);
  321.                                 dom_node_unref(node);
  322.                                 ret = NSERROR_NOMEM; /** @todo check this */
  323.                                 goto out_nlist;
  324.                         }
  325.                 }
  326.                
  327.                 dom_string_unref(name);
  328.                 dom_node_unref(node);
  329.         }
  330.        
  331.        
  332. out_nlist:
  333.        
  334.         dom_nodelist_unref(nlist);
  335.  
  336.         return ret;
  337. }
  338.  
  339. /**
  340.  * Extract an imagemap from html source
  341.  *
  342.  * \param node  XML node containing map
  343.  * \param c     Content containing document
  344.  * \param entry List of map entries
  345.  * \param tname The sub-tags to consider on this pass
  346.  * \return false on memory exhaustion, true otherwise
  347.  */
  348. static bool
  349. imagemap_extract_map_entries(dom_node *node, html_content *c,
  350.                              struct mapentry **entry, dom_string *tname)
  351. {
  352.         dom_nodelist *nlist;
  353.         dom_exception exc;
  354.         unsigned long ent;
  355.         uint32_t tag_count;
  356.        
  357.         exc = dom_element_get_elements_by_tag_name(node, tname, &nlist);
  358.         if (exc != DOM_NO_ERR) {
  359.                 return false;
  360.         }
  361.        
  362.         exc = dom_nodelist_get_length(nlist, &tag_count);
  363.         if (exc != DOM_NO_ERR) {
  364.                 dom_nodelist_unref(nlist);
  365.                 return false;
  366.         }
  367.        
  368.         for (ent = 0; ent < tag_count; ++ent) {
  369.                 dom_node *subnode;
  370.                
  371.                 exc = dom_nodelist_item(nlist, ent, &subnode);
  372.                 if (exc != DOM_NO_ERR) {
  373.                         dom_nodelist_unref(nlist);
  374.                         return false;
  375.                 }
  376.                 if (imagemap_addtolist(subnode, c->base_url,
  377.                                        entry, tname) == false) {
  378.                         dom_node_unref(subnode);
  379.                         dom_nodelist_unref(nlist);
  380.                         return false;
  381.                 }
  382.                 dom_node_unref(subnode);
  383.         }
  384.        
  385.         dom_nodelist_unref(nlist);
  386.        
  387.         return true;
  388. }
  389.  
  390. /**
  391.  * Extract an imagemap from html source
  392.  *
  393.  * \param node  XML node containing map
  394.  * \param c     Content containing document
  395.  * \param entry List of map entries
  396.  * \return false on memory exhaustion, true otherwise
  397.  */
  398. bool imagemap_extract_map(dom_node *node, html_content *c,
  399.                 struct mapentry **entry)
  400. {
  401.         if (imagemap_extract_map_entries(node, c, entry,
  402.                         corestring_dom_area) == false)
  403.                 return false;
  404.         return imagemap_extract_map_entries(node, c, entry,
  405.                         corestring_dom_a);
  406. }
  407. /**
  408.  * Adds an imagemap entry to the list
  409.  *
  410.  * \param n     The xmlNode representing the entry to add
  411.  * \param base_url  Base URL for resolving relative URLs
  412.  * \param entry Pointer to list of entries
  413.  * \return false on memory exhaustion, true otherwise
  414.  */
  415. bool
  416. imagemap_addtolist(dom_node *n, nsurl *base_url,
  417.                    struct mapentry **entry, dom_string *tagtype)
  418. {
  419.         dom_exception exc;
  420.         dom_string *href = NULL, *target = NULL, *shape = NULL;
  421.         dom_string *coords = NULL;
  422.         struct mapentry *new_map, *temp;
  423.         bool ret = true;
  424.        
  425.         if (dom_string_caseless_isequal(tagtype, corestring_dom_area)) {
  426.                 bool nohref = false;
  427.                 exc = dom_element_has_attribute(n,
  428.                                 corestring_dom_nohref, &nohref);
  429.                 if ((exc != DOM_NO_ERR) || nohref)
  430.                         /* Skip <area nohref="anything" /> */
  431.                         goto ok_out;
  432.         }
  433.        
  434.         exc = dom_element_get_attribute(n, corestring_dom_href, &href);
  435.         if (exc != DOM_NO_ERR || href == NULL) {
  436.                 /* No href="" attribute, skip this element */
  437.                 goto ok_out;
  438.         }
  439.        
  440.         exc = dom_element_get_attribute(n, corestring_dom_target, &target);
  441.         if (exc != DOM_NO_ERR) {
  442.                 goto ok_out;
  443.         }
  444.        
  445.         exc = dom_element_get_attribute(n, corestring_dom_shape, &shape);
  446.         if (exc != DOM_NO_ERR) {
  447.                 goto ok_out;
  448.         }
  449.        
  450.         /* If there's no shape, we default to rectangles */
  451.         if (shape == NULL)
  452.                 shape = dom_string_ref(corestring_dom_rect);
  453.        
  454.         if (!dom_string_caseless_lwc_isequal(shape, corestring_lwc_default)) {
  455.                 /* If not 'default' and there's no 'coords' give up */
  456.                 exc = dom_element_get_attribute(n, corestring_dom_coords,
  457.                                                 &coords);
  458.                 if (exc != DOM_NO_ERR || coords == NULL) {
  459.                         goto ok_out;
  460.                 }
  461.         }
  462.        
  463.         new_map = calloc(1, sizeof(*new_map));
  464.         if (new_map == NULL) {
  465.                 goto bad_out;
  466.         }
  467.        
  468.         if (dom_string_caseless_lwc_isequal(shape, corestring_lwc_rect) ||
  469.             dom_string_caseless_lwc_isequal(shape, corestring_lwc_rectangle))
  470.                 new_map->type = IMAGEMAP_RECT;
  471.         else if (dom_string_caseless_lwc_isequal(shape, corestring_lwc_circle))
  472.                 new_map->type = IMAGEMAP_CIRCLE;
  473.         else if (dom_string_caseless_lwc_isequal(shape, corestring_lwc_poly) ||
  474.                  dom_string_caseless_lwc_isequal(shape, corestring_lwc_polygon))
  475.                 new_map->type = IMAGEMAP_POLY;
  476.         else if (dom_string_caseless_lwc_isequal(shape, corestring_lwc_default))
  477.                 new_map->type = IMAGEMAP_DEFAULT;
  478.         else
  479.                 goto bad_out;
  480.        
  481.         if (box_extract_link(dom_string_data(href),
  482.                              base_url, &new_map->url) == false)
  483.                 goto bad_out;
  484.        
  485.         if (new_map->url == NULL) {
  486.                 /* non-fatal error -> ignore this */
  487.                 goto ok_free_map_out;
  488.         }
  489.        
  490.         if (target != NULL) {
  491.                 /* Copy target into the map */
  492.                 new_map->target = malloc(dom_string_byte_length(target) + 1);
  493.                 if (new_map->target == NULL)
  494.                         goto bad_out;
  495.                 /* Safe, but relies on dom_strings being NULL terminated */
  496.                 /* \todo Do this better */
  497.                 strcpy(new_map->target, dom_string_data(target));
  498.         }
  499.        
  500.         if (new_map->type != IMAGEMAP_DEFAULT) {
  501.                 int x, y;
  502.                 float *xcoords, *ycoords;
  503.                 /* coordinates are a comma-separated list of values */
  504.                 char *val = strtok((char *)dom_string_data(coords), ",");
  505.                 int num = 1;
  506.  
  507.                 switch (new_map->type) {
  508.                 case IMAGEMAP_RECT:
  509.                         /* (left, top, right, bottom) */
  510.                         while (val != NULL && num <= 4) {
  511.                                 switch (num) {
  512.                                 case 1:
  513.                                         new_map->bounds.rect.x0 = atoi(val);
  514.                                         break;
  515.                                 case 2:
  516.                                         new_map->bounds.rect.y0 = atoi(val);
  517.                                         break;
  518.                                 case 3:
  519.                                         new_map->bounds.rect.x1 = atoi(val);
  520.                                         break;
  521.                                 case 4:
  522.                                         new_map->bounds.rect.y1 = atoi(val);
  523.                                         break;
  524.                                 }
  525.  
  526.                                 num++;
  527.                                 val = strtok('\0', ",");
  528.                         }
  529.                         break;
  530.                 case IMAGEMAP_CIRCLE:
  531.                         /* (x, y, radius ) */
  532.                         while (val != NULL && num <= 3) {
  533.                                 switch (num) {
  534.                                 case 1:
  535.                                         new_map->bounds.circle.x = atoi(val);
  536.                                         break;
  537.                                 case 2:
  538.                                         new_map->bounds.circle.y = atoi(val);
  539.                                         break;
  540.                                 case 3:
  541.                                         new_map->bounds.circle.r = atoi(val);
  542.                                         break;
  543.                                 }
  544.  
  545.                                 num++;
  546.                                 val = strtok('\0', ",");
  547.                         }
  548.                         break;
  549.                 case IMAGEMAP_POLY:
  550.                         new_map->bounds.poly.xcoords = NULL;
  551.                         new_map->bounds.poly.ycoords = NULL;
  552.  
  553.                         while (val != NULL) {
  554.                                 x = atoi(val);
  555.  
  556.                                 val = strtok('\0', ",");
  557.                                 if (val == NULL)
  558.                                         break;
  559.  
  560.                                 y = atoi(val);
  561.  
  562.                                 xcoords = realloc(new_map->bounds.poly.xcoords,
  563.                                                 num * sizeof(float));
  564.                                 if (xcoords == NULL) {
  565.                                         goto bad_out;
  566.                                 }
  567.  
  568.                                 ycoords = realloc(new_map->bounds.poly.ycoords,
  569.                                         num * sizeof(float));
  570.                                 if (ycoords == NULL) {
  571.                                         goto bad_out;
  572.                                 }
  573.  
  574.                                 new_map->bounds.poly.xcoords = xcoords;
  575.                                 new_map->bounds.poly.ycoords = ycoords;
  576.  
  577.                                 new_map->bounds.poly.xcoords[num - 1] = x;
  578.                                 new_map->bounds.poly.ycoords[num - 1] = y;
  579.  
  580.                                 num++;
  581.                                 val = strtok('\0', ",");
  582.                         }
  583.  
  584.                         new_map->bounds.poly.num = num - 1;
  585.  
  586.                         break;
  587.                 default:
  588.                         break;
  589.                 }
  590.         }
  591.        
  592.         new_map->next = NULL;
  593.  
  594.         if (entry && *entry) {
  595.                 /* add to END of list */
  596.                 for (temp = (*entry); temp->next != NULL; temp = temp->next)
  597.                         ;
  598.                 temp->next = new_map;
  599.         }
  600.         else {
  601.                 (*entry) = new_map;
  602.         }
  603.        
  604.         /* All good, linked in, let's clean up */
  605.         goto ok_out;
  606.        
  607. bad_out:
  608.         ret = false;
  609. ok_free_map_out:
  610.         if (new_map->url != NULL)
  611.                 nsurl_unref(new_map->url);
  612.         if (new_map->type == IMAGEMAP_POLY &&
  613.             new_map->bounds.poly.ycoords != NULL)
  614.                 free(new_map->bounds.poly.ycoords);
  615.         if (new_map->type == IMAGEMAP_POLY &&
  616.             new_map->bounds.poly.xcoords != NULL)
  617.                 free(new_map->bounds.poly.xcoords);
  618.         if (new_map->target != NULL)
  619.                 free(new_map->target);
  620.         if (new_map != NULL)
  621.                 free(new_map);
  622. ok_out:
  623.         if (href != NULL)
  624.                 dom_string_unref(href);
  625.         if (target != NULL)
  626.                 dom_string_unref(target);
  627.         if (shape != NULL)
  628.                 dom_string_unref(shape);
  629.         if (coords != NULL)
  630.                 dom_string_unref(coords);
  631.        
  632.         return ret;
  633. }
  634.  
  635. /**
  636.  * Free list of imagemap entries
  637.  *
  638.  * \param list Pointer to head of list
  639.  */
  640. void imagemap_freelist(struct mapentry *list)
  641. {
  642.         struct mapentry *entry, *prev;
  643.  
  644.         assert(list != NULL);
  645.  
  646.         entry = list;
  647.  
  648.         while (entry != NULL) {
  649.                 prev = entry;
  650.  
  651.                 nsurl_unref(entry->url);
  652.  
  653.                 if (entry->target)
  654.                         free(entry->target);
  655.  
  656.                 if (entry->type == IMAGEMAP_POLY) {
  657.                         free(entry->bounds.poly.xcoords);
  658.                         free(entry->bounds.poly.ycoords);
  659.                 }
  660.  
  661.                 entry = entry->next;
  662.                 free(prev);
  663.         }
  664. }
  665.  
  666. /**
  667.  * Retrieve url associated with imagemap entry
  668.  *
  669.  * \param h        The containing content
  670.  * \param key      The map name to search for
  671.  * \param x        The left edge of the containing box
  672.  * \param y        The top edge of the containing box
  673.  * \param click_x  The horizontal location of the click
  674.  * \param click_y  The vertical location of the click
  675.  * \param target   Pointer to location to receive target pointer (if any)
  676.  * \return The url associated with this area, or NULL if not found
  677.  */
  678. nsurl *imagemap_get(struct html_content *c, const char *key,
  679.                 unsigned long x, unsigned long y,
  680.                 unsigned long click_x, unsigned long click_y,
  681.                 const char **target)
  682. {
  683.         unsigned int slot = 0;
  684.         struct imagemap *map;
  685.         struct mapentry *entry;
  686.         unsigned long cx, cy;
  687.  
  688.         assert(c != NULL);
  689.  
  690.         if (key == NULL)
  691.                 return NULL;
  692.  
  693.         if (c->imagemaps == NULL)
  694.                 return NULL;
  695.  
  696.         slot = imagemap_hash(key);
  697.  
  698.         for (map = c->imagemaps[slot]; map != NULL; map = map->next) {
  699.                 if (map->key != NULL && strcasecmp(map->key, key) == 0)
  700.                         break;
  701.         }
  702.  
  703.         if (map == NULL || map->list == NULL)
  704.                 return NULL;
  705.  
  706.         for (entry = map->list; entry; entry = entry->next) {
  707.                 switch (entry->type) {
  708.                 case IMAGEMAP_DEFAULT:
  709.                         /* just return the URL. no checks required */
  710.                         if (target)
  711.                                 *target = entry->target;
  712.                         return entry->url;
  713.                         break;
  714.                 case IMAGEMAP_RECT:
  715.                         if (click_x >= x + entry->bounds.rect.x0 &&
  716.                                     click_x <= x + entry->bounds.rect.x1 &&
  717.                                     click_y >= y + entry->bounds.rect.y0 &&
  718.                                     click_y <= y + entry->bounds.rect.y1) {
  719.                                 if (target)
  720.                                         *target = entry->target;
  721.                                 return entry->url;
  722.                         }
  723.                         break;
  724.                 case IMAGEMAP_CIRCLE:
  725.                         cx = x + entry->bounds.circle.x - click_x;
  726.                         cy = y + entry->bounds.circle.y - click_y;
  727.                         if ((cx * cx + cy * cy) <=
  728.                                 (unsigned long) (entry->bounds.circle.r *
  729.                                         entry->bounds.circle.r)) {
  730.                                 if (target)
  731.                                         *target = entry->target;
  732.                                 return entry->url;
  733.                         }
  734.                         break;
  735.                 case IMAGEMAP_POLY:
  736.                         if (imagemap_point_in_poly(entry->bounds.poly.num,
  737.                                         entry->bounds.poly.xcoords,
  738.                                         entry->bounds.poly.ycoords, x, y,
  739.                                         click_x, click_y)) {
  740.                                 if (target)
  741.                                         *target = entry->target;
  742.                                 return entry->url;
  743.                         }
  744.                         break;
  745.                 }
  746.         }
  747.  
  748.         if (target)
  749.                 *target = NULL;
  750.  
  751.         return NULL;
  752. }
  753.  
  754. /**
  755.  * Hash function
  756.  *
  757.  * \param key The key to hash
  758.  * \return The hashed value
  759.  */
  760. unsigned int imagemap_hash(const char *key)
  761. {
  762.         unsigned int z = 0;
  763.  
  764.         if (key == 0) return 0;
  765.  
  766.         for (; *key != 0; key++) {
  767.                 z += *key & 0x1f;
  768.         }
  769.  
  770.         return (z % (HASH_SIZE - 1)) + 1;
  771. }
  772.  
  773. /**
  774.  * Test if a point lies within an arbitrary polygon
  775.  * Modified from comp.graphics.algorithms FAQ 2.03
  776.  *
  777.  * \param num Number of vertices
  778.  * \param xpt Array of x coordinates
  779.  * \param ypt Array of y coordinates
  780.  * \param x Left hand edge of containing box
  781.  * \param y Top edge of containing box
  782.  * \param click_x X coordinate of click
  783.  * \param click_y Y coordinate of click
  784.  * \return 1 if point is in polygon, 0 if outside. 0 or 1 if on boundary
  785.  */
  786. int imagemap_point_in_poly(int num, float *xpt, float *ypt, unsigned long x,
  787.                 unsigned long y, unsigned long click_x,
  788.                 unsigned long click_y)
  789. {
  790.         int i, j, c = 0;
  791.  
  792.         assert(xpt != NULL);
  793.         assert(ypt != NULL);
  794.  
  795.         for (i = 0, j = num - 1; i < num; j = i++) {
  796.                 if ((((ypt[i] + y <= click_y) && (click_y < ypt[j] + y)) ||
  797.                      ((ypt[j] + y <= click_y) && (click_y < ypt[i] + y))) &&
  798.                      (click_x < (xpt[j] - xpt[i]) *
  799.                      (click_y - (ypt[i] + y)) / (ypt[j] - ypt[i]) + xpt[i] + x))
  800.                         c = !c;
  801.         }
  802.  
  803.         return c;
  804. }
  805.