History

/* Copyright 1997 Acorn Computers Ltd
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
/***************************************************/
/* File   : History.c                              */
/*                                                 */
/* Purpose: Handles the browser History.           */
/*                                                 */
/* Author : A.D.Hodgkinson                         */
/*                                                 */
/* History: 07-Feb-97: Created.                    */
/*                                                 */
/*          06-Nov-97: Major revision, largely a   */
/*                     complete rewrite to make    */
/*                     the system more flexible    */
/*                     and less prone to bugs (but */
/*                     still do Back/Forward as in */
/*                     Navigator 2, rather than    */
/*                     Navigator 3).               */
/***************************************************/

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

#include "kernel.h"
#include "swis.h"
#include "flex.h"

#include "wimp.h"
#include "wimplib.h"
#include "event.h"

#include "toolbox.h"
#include "window.h"
#include "gadgets.h"
#include "menu.h"

#include "svcprint.h"
#include "Global.h"
#include "FromROSLib.h"
#include "Utils.h"

#include "Browser.h"
#include "ChoiceDefs.h"
#include "FetchPage.h"
#include "Filetypes.h"
#include "Memory.h"
#include "OpenURL.h"
#include "Save.h"
#include "Toolbars.h"
#include "URLutils.h"
#include "Windows.h"

#include "History.h"

/**************************************************************************************************/
/*                                                                                                */
/* Browser History structure                                                                      */
/* =========================                                                                      */
/*                                                                                                */
/*          prev       next            The basic History structure is as pictured to the left.    */
/* (entry) <---- ENTRY ----> (entry)   Global History takes the form of a doubly-linked list of   */
/*                 | ^                 history_entry structures, which may point to another       */
/*            users| |parent           doubly-linked list of structures recording the usage of    */
/*                 | |                 a History item by a specific browser. Within these         */
/*                 | |                 history_user records, there are doubly-linked references   */
/*                 | |(user)           to other history_user structures referring to the same     */
/*                 | |^                browser - in this way, a local visit History is held. The  */
/*                 | ||prev            history_user structures point back to the history_entry    */
/*                 | ||                structures through the 'parent' field.                     */
/*                 v ||                                                                           */
/*    (LHPU) <---- USER ----> (LHNU)   LHPU and LHNU stand for 'Local History [Prev/Next] User'.  */
/*    history_prev    | history_next                                                              */
/*                    |                All memory allocations are through malloc, since the       */
/*                    |next            blocks in use are typically small and must not move (so a  */
/*                    v                granular allocation system or a shifting heap such as      */
/*                    (user)           that provided by flexlib would be inappropriate).          */
/*                                                                                                */
/* Two records are kept in the browser_data structure which are, as far as anyone else is         */
/* concerned, magic words. They are in fact both history_user pointers cast to void *. One is     */
/* updated every time a new history_user entry is created - this is needed so that prev/next      */
/* pointers within all the items relevant to the browser's local History may be updated quickly.  */
/* The other is a pointer to a history_user struct which when non-NULL, indicates a position      */
/* within the History itself.                                                                     */
/*                                                                                                */
/* Note that one history_entry may have several history_user structs threading through it for the */
/* same browser, if a user keeps going back to the same page by following links.                  */
/*                                                                                                */
/**************************************************************************************************/

/* Internationalisation support */

#ifdef UNIFONT
  #define CHARSET_SPECIFIER "<meta http-equiv=\"Content-Type\" content=\"text/html; charset=UTF-8\">\n"
#else
  #define CHARSET_SPECIFIER "<meta http-equiv=\"Content-Type\" content=\"text/html; charset=ISO-8859-1\">\n"
#endif

/* Local definitions */

#define HistoryWrite(fn) {written = (fn); if (written < 0) goto history_save_error;}

/* Main History list structures */

struct history_entry;

/* Record usage by a specific browser */

typedef struct history_user
{
  struct history_entry * parent;

  struct history_user  * next;
  struct history_user  * prev;

  struct history_user  * history_next; /* (For the browser history, this is NOT a linked list) */
  struct history_user  * history_prev;

  browser_data         * user;
  unsigned int           last_accessed;
}
history_user;

/* Global History structure, which points to */
/* an array of usage structures (see above)  */

typedef struct history_entry
{
  struct history_entry * next;
  struct history_entry * prev;

  url_description      * url; /* (Defined in URLutils.h) */
  unsigned int           hash;
  char                 * title;

  history_user         * users;

  unsigned int           last_accessed;
}
history_entry;

/* Static variables */

static history_entry   * history_base = NULL;

static void            * history_menu = NULL;
static int               menu_entries = 0;

static history_user   ** user_array   = NULL;
static history_entry  ** entry_array  = NULL;
static int               nusers       = 0;
static int               nentries     = 0;

/* Static function prototypes */

static history_entry   * history_find_entry      (const char * url);
static history_user    * history_find_user       (browser_data * b, history_entry * entry);

static _kernel_oserror * history_add_user        (browser_data * b, history_entry * found, history_user ** created);
static void              history_remove_user     (history_user * user);
static void              history_remove_entry    (browser_data * b, history_entry * entry);

static int               history_compare_entries (const void * first, const void * second);

/*************************************************/
/* history_find_entry()                          */
/*                                               */
/* Returns a pointer to a history_entry for a    */
/* given URL.                                    */
/*                                               */
/* Parameters: Pointer to a null-terminated URL  */
/*             string to find.                   */
/*                                               */
/* Returns:    Pointer to a history_entry struct */
/*             representing the given URL, or    */
/*             NULL if no such entry is found    */
/*             in the History.                   */
/*************************************************/

static history_entry * history_find_entry(const char * url)
{
  history_entry   * find = history_base;
  url_description * url_d;
  int               hash;

  if (!url || !*url) return NULL;

  /* Get a description of the URL - makes comparissons faster */

  url_d = urlutils_return_description(url);
  if (!url_d) return NULL;

  hash = utils_return_hash(url_d->full);

  /* Search the list */

  while (find)
  {
    if (hash == find->hash && !urlutils_urlddcmp(find->url, url_d)) break;

    find = find->next;
  }

  urlutils_free_description(url_d);

  return find;
}

/*************************************************/
/* history_find_user                             */
/*                                               */
/* Returns a pointer to a history_user for a     */
/* given browser in a given History entry.       */
/*                                               */
/* Parameters: Pointer to a browser_data struct  */
/*             represented by the entry;         */
/*                                               */
/*             Pointer to a history_entry struct */
/*             to search in.                     */
/*                                               */
/* Returns:    Pointer to a history_user struct  */
/*             representing the given browser or */
/*             NULL if no such entry is found.   */
/*************************************************/

static history_user * history_find_user(browser_data * b, history_entry * entry)
{
  history_user * user;

  if (!b || !entry) return NULL;

  /* Search the list */

  user = entry->users;

  while (user)
  {
    if (user->user == b) return user;

    user = user->next;
  }

  return NULL;
}

/*************************************************/
/* history_add_user()                            */
/*                                               */
/* Add an association of a given browser with a  */
/* given History entry, updating the browser's   */
/* record of where it is in the local History to */
/* the new association (user record). This last  */
/* step is required if subsequent additions are  */
/* to be correctly linked into the local History */
/* list (history_next and history_prev fields).  */
/*                                               */
/* Parameters: Pointer to a browser_data struct  */
/*             relevant to the association;      */
/*                                               */
/*             Pointer to a history_entry struct */
/*             to associate the browser to;      */
/*                                               */
/*             Pointer to a history_user *,      */
/*             in which the address of the new   */
/*             user record will be placed.       */
/*                                               */
/* Assumes:    The history_user * pointer may    */
/*             be NULL.                          */
/*************************************************/

static _kernel_oserror * history_add_user(browser_data * b, history_entry * found, history_user ** created)
{
  history_user * newuser;

  #ifdef TRACE
    if (tl & (1u<<16)) Printf("history_add_user: Called for browser %p, entry %p\n",b,found);
  #endif

  if (created) *created = NULL;

  newuser = malloc(sizeof(history_user));

  if (!newuser)
  {
    /* Oh just great, the allocation failed. Well, rather */
    /* than scrap everything, leave the global entry      */
    /* alone - just don't create the extra reference to   */
    /* this browser.                                      */

    #ifdef TRACE
      if (tl & (1u<<16)) Printf("history_add_user: Could not allocate space for user record\n");
    #endif

    return make_no_memory_error(25);
  }

  #ifdef TRACE
    if (tl & (1u<<16)) Printf("history_add_user: New user record is %p\n", newuser);
  #endif

  /* Insert the item into the linked list of history_user */
  /* structures for this history_entry structure.         */

  newuser->parent = found;

  if (found->users) found->users->prev = newuser;

  newuser->next = found->users;
  newuser->prev = NULL;

  found->users  = newuser;

  /* Link the item into the linked list of history_user */
  /* structures forming the browser local history.      */

  newuser->history_prev = (history_user *) b->history_current;
  newuser->history_next = NULL;
  newuser->user         = b;

  /* Fill in the accessed time */

  newuser->last_accessed = found->last_accessed;

  /* If newuser->history_prev points in its history_next  */
  /* field to any other items, remove them, because we've */
  /* just branched the history at this point by adding    */
  /* the new item.                                        */

  if (newuser->history_prev && newuser->history_prev->history_next)
  {
    history_user * current = newuser->history_prev->history_next;
    history_user * next;

    #ifdef TRACE
      if (tl & (1u<<16)) Printf("history_add_user: Adding from within an existing history; removing later entries...\n");
    #endif

    while (current)
    {
      next = current->history_next;

      #ifdef TRACE
        if (tl & (1u<<16)) Printf("history_add_user: Calling history_remove_user for user record %p\n",current);
      #endif

      history_remove_user(current);

      current = next;
    }
  }

  /* Fill in the link to the new structure */

  if (newuser->history_prev) newuser->history_prev->history_next = newuser;

  b->history_current = (void *) newuser;

  #ifdef TRACE
    if (tl & (1u<<16)) Printf("history_add_user: Successful\n");
  #endif

  if (created) *created = newuser;

  return NULL;
}

/*************************************************/
/* history_record()                              */
/*                                               */
/* Records the visiting of a given URL in the    */
/* History, optionally associating this visit    */
/* with a given browser.                         */
/*                                               */
/* If there is already an entry for this URL, it */
/* will simply have its latest visit time        */
/* record updated.                               */
/*                                               */
/* Parameters: Pointer to a browser_data struct  */
/*             to associate the visit with, or   */
/*             NULL for none;                    */
/*                                               */
/*             Pointer to a null-terminated URL  */
/*             string to record.                 */
/*************************************************/

_kernel_oserror * history_record(browser_data * b, const char * url)
{
  history_entry * found   = NULL;
  history_user  * newuser = NULL;

  if (!url || !*url) return NULL;

  #ifdef TRACE
    if (tl & (1u<<16)) Printf("history_record: Called for %p and '%s'\n",b,url);
  #endif

  /* First, see if we have the URL present already */

  found = history_find_entry(url);

  /* If this is for a specific browser which is fetching */
  /* from its own local History, then we don't record    */
  /* anything (it'd corrupt the history ordering). We    */
  /* should, however, update the timestamps.             */

  if (b && b->from_history)
  {
    #ifdef TRACE
      if (tl & (1u<<16)) Printf("history_record: Browser fetching from History; updating timestamps and exitting\n");
    #endif

    if (found)
    {
      found->last_accessed = time(NULL);

      newuser = history_find_user(b, found);

      if (newuser) newuser->last_accessed = found->last_accessed;
    }

    return NULL;
  }

  /* If not fetching from the local History, proceed as normal */

  if (!found)
  {
    #ifdef TRACE
      if (tl & (1u<<16)) Printf("history_record: No existing entry, so creating a new one\n");
    #endif

    /* Need to create an entry */

    found = malloc(sizeof(history_entry));

    if (!found)
    {
      #ifdef TRACE
        if (tl & (1u<<16)) Printf("history_record: Couldn't allocate space for entry\n");
      #endif

      return make_no_memory_error(25);
    }

    /* Need to turn the URL into a more complete description, */
    /* but if we get NULL back, memory allocation must have   */
    /* failed somewhere.                                      */

    found->url = urlutils_return_description(url);

    if (!found->url)
    {
      free(found);

      #ifdef TRACE
        if (tl & (1u<<16)) Printf("history_record: Couldn't allocate space for URL description\n");
      #endif

      return make_no_memory_error(25);
    }
    else
    {
      /* Create a hash number for the string */

      found->hash = utils_return_hash(found->url->full);
    }

    /* Link in the structure */

    found->prev = NULL;
    found->next = history_base;

    if (history_base) history_base->prev = found;

    history_base = found;

    /* Fill in some other fields */

    found->title = NULL;
    found->users = NULL;

    #ifdef TRACE
      if (tl & (1u<<16)) Printf("history_record: OK, have entry %p with description block %p\n",found,found->url);
    #endif
  }

  #ifdef TRACE
    else
    {
      if (tl & (1u<<16)) Printf("history_record: Already have an entry %p\n",found);
    }
  #endif

  /* Update the last accessed time for the global record */

  found->last_accessed = time(NULL);

  /* Always add a usage record for the browser, unless the URL being     */
  /* added matches that represented by the item the browser is currently */
  /* on in terms of its visit history.                                   */

  if (
       b &&
       (
         !b->history_current ||
         (
           ((history_user *) b->history_current)->parent != found
         )
       )
     )
     RetError(history_add_user(b, found, NULL));

  #ifdef TRACE
    if (tl & (1u<<16))
    {
      Printf("history_record: Successful. History size is now %d\n", history_count());
      Printf("                Exitting through expiry functions.\n");
    }
  #endif

  if (choices.expiry_age) RetError(history_expire(NULL, time(NULL) - choices.expiry_age));
  if (choices.max_size)   RetError(history_limit(choices.max_size));

  #ifdef SINGLE_USER

    if (choices.save_history == Choices_SaveHistory_Always)
    {
      return history_save(lookup_choice("HistorySave:Browse:User.History",0,0));
    }

  #endif

  return NULL;
}

/*************************************************/
/* history_inherit()                             */
/*                                               */
/* For any association in the History of a given */
/* base (parent) browser with a URL, create a    */
/* duplicate associaton with a given child       */
/* browser with the same visit timestamps. The   */
/* child browser thus inherits the history of    */
/* the parent.                                   */
/*                                               */
/* The history_current field of the child is set */
/* to the child's equivalent of the field in the */
/* parent.                                       */
/*                                               */
/* Parameters: Pointer to a browser_data struct  */
/*             representing the parent browser;  */
/*                                               */
/*             Pointer to a browser_data struct  */
/*             representing the child browser.   */
/*                                               */
/* Assumes:    The child browser has no existing */
/*             history references. If it does,   */
/*             then this will become detached as */
/*             the new references are put in     */
/*             place.                            */
/*************************************************/

_kernel_oserror * history_inherit(browser_data * parent, browser_data * child)
{
  history_user * parent_user;
  history_user * parent_current;
  history_user * child_user;
  history_user * child_equivalent = NULL;

  if (!parent || !child) return NULL;

  parent_user    = (history_user *) parent->history_current;
  parent_current = parent_user;

  if (!parent_user) return NULL; /* Nothing to inherit */

  /* Find the first item in the local History */

  while (parent_user->history_prev) parent_user = parent_user->history_prev;

  /* Now go through adding users for the new browser */

  child->history_current = NULL;

  while (parent_user)
  {
    /* Add the user record for the child */

    RetError(history_add_user(child, parent_user->parent, &child_user));

    /* If this record is equivalent to the history_current field */
    /* of the parent, remember the new user record's address in  */
    /* 'child_equivalent'.                                       */

    if (parent_user == parent_current) child_equivalent = child_user;

    /* Go on to the next user record in the parent's History */

    parent_user = parent_user->history_next;
  }

  /* Set the child's history_current field to the equivalent */
  /* of the same field in the parent.                        */

  if (child_equivalent) child->history_current = (void *) child_equivalent;

  /* Finished */

  return NULL;
}

/*************************************************/
/* history_remove_user()                         */
/*                                               */
/* Removes a given history_user record from the  */
/* various lists in which it may lie.            */
/*                                               */
/* Parameters: Pointer to the history_user       */
/*             structure to remove.              */
/*************************************************/

static void history_remove_user(history_user * user)
{
  #ifdef TRACE
    if (tl & (1u<<16)) Printf("history_remove_user: Called for %p\n",user);
  #endif

  if (!user) return;

  /* Repoint within the linked list of items attached to a history_entry structure, */
  /* and within the local history list.                                             */

  if (user->prev) user->prev->next = user->next;
  if (user->next) user->next->prev = user->prev;

  if (user->history_prev) user->history_prev->history_next = user->history_next;
  if (user->history_next) user->history_next->history_prev = user->history_prev;

  /* If required, repoint the parent history_entry structure's 'users' field. */

  if (user == user->parent->users) user->parent->users = user->next;

  /* Does the owner browser point to this item? If so, invalidate */
  /* that pointer (set it to NULL).                               */

  if (
       is_known_browser(user->user)                 &&
       user->user->history_current == (void *) user
     )
     user->user->history_current = NULL;

  /* Finally, free the item. */

  free(user);

  #ifdef TRACE
    if (tl & (1u<<16)) Printf("history_remove_user: Successful\n");
  #endif

  return;
}

/*************************************************/
/* history_remove_entry()                        */
/*                                               */
/* Removes a given record from the History,      */
/* removes all associations with this entry,     */
/* and/or removes all associations between any   */
/* URLs in the History and a given browser. In   */
/* the latter case, URLs left with no            */
/* assocations are *not* removed; they stay as   */
/* global visit History records.                 */
/*                                               */
/* Parameters: Pointer to a browser_data struct  */
/*             to remove all associations for,   */
/*             or NULL to not do this;           */
/*                                               */
/*             Pointer to the history_entry      */
/*             struct to remove, or NULL not to  */
/*             do this;                          */
/*                                               */
/* Assumes:    Either or both pointers may be    */
/*             valid or NULL, though obviously   */
/*             there's little point calling with */
/*             both set to NULL...               */
/*************************************************/

static void history_remove_entry(browser_data * b, history_entry * entry)
{
  #ifdef TRACE
    if (tl & (1u<<16)) Printf("history_remove_entry: Called for browser %p, entry %p\n",b,entry);
  #endif

  if (entry)
  {
    history_user * user = entry->users;
    history_user * next;

    /* We've found the entry. First remove all user structures */

    #ifdef TRACE
      if (tl & (1u<<16)) Printf("history_remove_entry: Have found the entry - removing user records...\n");
    #endif

    while (user)
    {
      next = user->next;

      #ifdef TRACE
        if (tl & (1u<<16)) Printf("history_remove_entry: Calling history_remove_user for user record %p\n",user);
      #endif

      history_remove_user(user);

      user = next;
    }

    /* Point other History entries elsewhere too, and correct */
    /* the history_base pointer if required.                  */

    if (entry->prev) entry->prev->next = entry->next;
    if (entry->next) entry->next->prev = entry->prev;

    if (entry == history_base) history_base = entry->next;

    /* Free the URL description */

    #ifdef TRACE
      if (tl & (1u<<16)) Printf("history_remove_entry: Calling urlutils_free_description for URL description %p\n",entry->url);
    #endif

    urlutils_free_description(entry->url);

    /* Free the title string */

    #ifdef TRACE
      if (tl & (1u<<16)) Printf("history_remove_entry: Freeing entry title string\n");
    #endif

    free(entry->title);

    /* Free the entry */

    #ifdef TRACE
      if (tl & (1u<<16)) Printf("history_remove_entry: Freeing entry itself\n");
    #endif

    free(entry);
  }

  /* Deal with removing all associations for a given browser */

  if (b)
  {
    history_user * user;
    history_user * next;

    #ifdef TRACE
      if (tl & (1u<<16)) Printf("history_remove_entry: Removing all user records for browser %p\n",b);
    #endif

    entry = history_base;

    /* Go through all entries... */

    while (entry)
    {
      user = entry->users;

      /* ...and all users (associations) in each entry... */

      while (user)
      {
        next = user->next;

        /* ...and remove any associated with the given browser. */

        if (user->user == b)
        {
          #ifdef TRACE
            if (tl & (1u<<16)) Printf("history_remove_entry: Calling history_remove_user for user record %p\n",user);
          #endif

          history_remove_user(user);
        }

        user = next;
      }

      entry = entry->next;
    }
  }

  /* Finished */

  #ifdef TRACE
    if (tl & (1u<<16)) Printf("history_remove_entry: Successful\n");
  #endif

  return;
}

/*************************************************/
/* history_remove()                              */
/*                                               */
/* Removes a record in the History of a given    */
/* URL and all associations with this URL,       */
/* and/or removes all associations between any   */
/* URLs in the History and a given browser. In   */
/* the latter case, URLs left with no            */
/* assocations are *not* removed; they stay as   */
/* global visit History records.                 */
/*                                               */
/* Parameters: Pointer to a browser_data struct  */
/*             to remove all associations for,   */
/*             or NULL to not do this;           */
/*                                               */
/*             Pointer to a null-terminated URL  */
/*             string to remove, or NULL to not  */
/*             do this.                          */
/*                                               */
/* Assumes:    Either or both pointers may be    */
/*             valid or NULL, though obviously   */
/*             there's little point calling with */
/*             both set to NULL...               */
/*************************************************/

void history_remove(browser_data * b, const char * url)
{
  history_entry * entry = NULL;

  #ifdef TRACE
    if (tl & (1u<<16)) Printf("history_remove: Called for browser %p, URL address %p\n",b,url);
  #endif

  /* Deal with removing a specific URL */

  if (url)
  {
    #ifdef TRACE
      if (tl & (1u<<16)) Printf("history_remove: Removing entry for URL '%s'\n",url);
    #endif

    entry = history_find_entry(url);

    #ifdef TRACE
      if (tl & (1u<<16)) Printf("history_remove: Entry for this URL %p\n",entry);
    #endif
  }

  #ifdef TRACE
    if (tl & (1u<<16)) Printf("history_remove: Calling history_remove_entry\n");
  #endif

  history_remove_entry(b, entry);

  #ifdef TRACE
    if (tl & (1u<<16)) Printf("history_remove: Successful. History size is now %d\n", history_count());
  #endif
}

/*************************************************/
/* history_add_title()                           */
/*                                               */
/* Associates a given title string with a given  */
/* URL and all associations with this URL,       */
/* and/or removes all associations between any   */
/* URLs in the History and a given browser.      */
/*                                               */
/* Parameters: Pointer to a null-terminated URL  */
/*             string for which the title is to  */
/*             be associated;                    */
/*                                               */
/*             Pointer to a null-terminated      */
/*             title string to associate with    */
/*             the URL.                          */
/*************************************************/

_kernel_oserror * history_add_title(const char * url, const char * title)
{
  history_entry * entry;

  if (!url || !*url || !title || !*title) return NULL;

  #ifdef TRACE
    if (tl & (1u<<16)) Printf("history_add_title: Called for URL '%s'\n"
                              "                        and title '%s'\n",url,title);
  #endif

  /* Find the item */

  entry = history_find_entry(url);

  #ifdef TRACE
    if (tl & (1u<<16)) Printf("history_add_title: Entry returned by history_find_entry is 0x%08x\n",entry);
  #endif

  if (!entry) return NULL;

  /* Add the title */

  free(entry->title);

  entry->title = malloc(strlen(title) + 1);

  if (!entry->title)
  {
    #ifdef TRACE
      if (tl & (1u<<16)) Printf("history_add_title: Couldn't allocate space for title string\n");
    #endif

    return make_no_memory_error(26);
  }
  else strcpy(entry->title, title);

  /* Finished */

  #ifdef TRACE
    if (tl & (1u<<16)) Printf("history_add_title: Successful. History size is now %d\n", history_count());
  #endif

  return NULL;
}

/*************************************************/
/* history_return_title()                        */
/*                                               */
/* Returns a title string (if any) associated    */
/* with a given URL.                             */
/*                                               */
/* Parameters: Pointer to a null-terminated URL  */
/*             string for which a title is to be */
/*             found.                            */
/*                                               */
/* Returns:    Pointer to a null-terminated      */
/*             title string associated with the  */
/*             URL, or NULL if either the URL    */
/*             had no associated title, or the   */
/*             URL couldn't be found in the      */
/*             History at all.                   */
/*************************************************/

char * history_return_title(char * url)
{
  history_entry * entry;

  if (!url || !*url) return NULL;

  #ifdef TRACE
    if (tl & (1u<<16)) Printf("history_return_title: Called for URL '%s'\n",url);
  #endif

  entry = history_find_entry(url);

  #ifdef TRACE
    if (tl & (1u<<16)) Printf("history_return_title: Entry returned by history_find_entry is 0x%08x\n",entry);
  #endif

  if (!entry) return NULL;

  #ifdef TRACE

    if (tl & (1u<<16))
    {
      if (entry->title) Printf("history_return_title: Successful, returning '%s'\n",entry->title);
      else              Printf("history_return_title: Successful, but there is no title (returning NULL)\n");
    }

  #endif

  return entry->title;
}

/*************************************************/
/* history_expire()                              */
/*                                               */
/* Remove all associations of a URL which have   */
/* been visited before a given time (i.e. are    */
/* greater than a certain age). This may only be */
/* for associations with a specific browser.     */
/*                                               */
/* Any URL left with no associations and an      */
/* overall last visit time before that given     */
/* will be removed from the History completely.  */
/*                                               */
/* Parameters: Pointer to a browser_data struct  */
/*             for which associations are to be  */
/*             expired, or NULL if the expiry is */
/*             for all History items;            */
/*                                               */
/*             Time (in time() function format)  */
/*             which a URL must have not been    */
/*             visited on or since for expiry to */
/*             take place - so to expire 1 day   */
/*             old URLs, say, you'd pass         */
/*             time() - 60*60*24.                */
/*************************************************/

_kernel_oserror * history_expire(browser_data * b, unsigned int time)
{
  history_entry * this_entry;
  history_entry * next_entry;
  history_user  * this_user;
  history_user  * next_user;

  #ifdef TRACE
    if (tl & (1u<<16)) Printf("history_expire: Called for %p and time %d\n",b,time);
  #endif

  this_entry = history_base;

  /* Scan the main entry list */

  while (this_entry)
  {
    next_entry = this_entry->next;
    this_user  = this_entry->users;

    /* For each entry, scan the associated users */

    while (this_user)
    {
      next_user = this_user->next;

      /* If we've not been given a browser, or we have and it matches */
      /* the user for this user record, and the last accessed time is */
      /* earlier than that given (the record is older), remove it.    */

      if ((!b || this_user->user == b) && this_user->last_accessed < time)
      {
        #ifdef TRACE
          if (tl & (1u<<16)) Printf("history_expire: Calling history_remove_user for user record %p\n",this_user);
        #endif

        history_remove_user(this_user);
      }

      this_user = next_user;
    }

    /* If this item has no users [now], and the last accessed time */
    /* is earlier than that given (the entry is older), remove it. */

    if (!this_entry->users && this_entry->last_accessed < time)
    {
      #ifdef TRACE
        if (tl & (1u<<16)) Printf("history_expire: Calling history_remove_entry for entry %p\n",this_entry);
      #endif

      history_remove_entry(NULL, this_entry);
    }

    /* Next... */

    this_entry = next_entry;
  }

  openurl_update_popup();

  #ifdef TRACE
    if (tl & (1u<<16)) Printf("history_expire: Successful, exitting through toolbars_set_all_button_states\n");
  #endif

  return toolbars_set_all_button_states();
}

/*************************************************/
/* history_count()                               */
/*                                               */
/* Counts the size in memory of all strings and  */
/* structures used by the History.               */
/*                                               */
/* Returns:    Size of all strings and structs   */
/*             used by the History, in bytes.    */
/*************************************************/

int history_count(void)
{
  int             count = 0;
  history_entry * entry = history_base;
  history_user  * user;

  #ifdef TRACE
    if (tl & (1u<<16)) Printf("history_count: Called\n");
  #endif

  while (entry)
  {
    /* Work out how much the entry takes up. First */
    /* the structure itself.                       */

    count += sizeof(entry);

    /* The title string, if present */

    if (entry->title) count += strlen(entry->title) + 1;

    /* The URL description, if present (should always be!) */

    if (entry->url)
    {
      /* This has a structure itself */

      count += sizeof(url_description);

      /* Then add in all the strings it can carry */

      if (entry->url->full)     count += strlen(entry->url->full)     + 1;
      if (entry->url->protocol) count += strlen(entry->url->protocol) + 1;
      if (entry->url->host)     count += strlen(entry->url->host)     + 1;
      if (entry->url->port)     count += strlen(entry->url->port)     + 1;
      if (entry->url->user)     count += strlen(entry->url->user)     + 1;
      if (entry->url->password) count += strlen(entry->url->password) + 1;
      if (entry->url->account)  count += strlen(entry->url->account)  + 1;
      if (entry->url->path)     count += strlen(entry->url->path)     + 1;
      if (entry->url->query)    count += strlen(entry->url->query)    + 1;
      if (entry->url->fragment) count += strlen(entry->url->fragment) + 1;
    }

    /* Now deal with any user records in this entry */

    user = entry->users;

    while (user)
    {
      /* Only need to count the structure size itself here */

      count += sizeof(history_user);

      user = user->next;
    }

    /* Next entry */

    entry = entry->next;
  }

  #ifdef TRACE
    if (tl & (1u<<16)) Printf("history_count: Successful, returning %d\n", count);
  #endif

  return count;
}

/*************************************************/
/* history_limit()                               */
/*                                               */
/* Counts the history size, and will expire the  */
/* oldest item if it is over the given size.     */
/* This continues until the history falls at or  */
/* below the given size limit.                   */
/*                                               */
/* This is quite a slow process.                 */
/*                                               */
/* Parameters: Size in bytes at or below which   */
/*             the history is to fall on exit.   */
/*************************************************/

_kernel_oserror * history_limit(unsigned int size)
{
  int size_now;

  #ifdef TRACE
    if (tl & (1u<<16)) Printf("history_limit: Called with limit size %d\n",size);
  #endif

  do
  {
    size_now = history_count();

    #ifdef TRACE
      if (tl & (1u<<16)) Printf("history_limit: Current size is %d\n",size_now);
    #endif

    if (size_now > size)
    {
      history_entry * entry  = history_base;
      history_entry * old    = NULL;
      int             oldest = 0;

      /* If we're oversize, find the oldest item */

      #ifdef TRACE
        if (tl & (1u<<16)) Printf("history_limit: Need to remove entries\n");
      #endif

      while (entry)
      {
        if (!oldest || entry->last_accessed < oldest) oldest = entry->last_accessed, old = entry;

        entry = entry->next;
      }

      /* Now expire it */

      #ifdef TRACE
        if (tl & (1u<<16)) Printf("history_limit: Expiring entry %p\n", old);
      #endif

      if (old) history_remove_entry(NULL, old);
    }

    /* Continue until we fall within the required size */
  }
  while (size_now > size);

  /* Exit through a toolbar button update, as some local histories */
  /* may well have been disturbed by the loss of History entries.  */

  openurl_update_popup();

  #ifdef TRACE
    if (tl & (1u<<16)) Printf("history_limit: Successful, exitting through toolbars_set_all_button_states\n");
  #endif

  return toolbars_set_all_button_states();
}

/*************************************************/
/* history_visited()                             */
/*                                               */
/* Returns 1 if a given URL is in the History,   */
/* else 0.                                       */
/*                                               */
/* Parameters: Pointer to a null-terminated URL  */
/*             string to look for.               */
/*                                               */
/* Returns:    1 if a record of this can be      */
/*             found in the History, else 0.     */
/*************************************************/

int history_visited(const char * url)
{
  if (history_find_entry(url)) return 1;

  return 0;
}

/*************************************************/
/* history_empty()                               */
/*                                               */
/* Inquire if there are any History items        */
/* present for a given browser or the global     */
/* History.                                      */
/*                                               */
/* Parameters: Pointer to a browser_data struct  */
/*             relevant to the enquiry, or NULL  */
/*             for the global History.           */
/*                                               */
/* Returns:    1 if there are no items, else 0.  */
/*************************************************/

int history_empty(browser_data * b)
{
  if (!b) return !history_base;

  return !b->history_current;
}

/*************************************************/
/* history_can_go_backwards()                    */
/*                                               */
/* Reports whether or not there are more pages   */
/* to go back to in the local History of a       */
/* given browser.                                */
/*                                               */
/* Parameters: Pointer to a browser_data struct  */
/*             relevant to the History.          */
/*                                               */
/* Returns:    1 if there are more items in the  */
/*             local history to go back to, else */
/*             0.                                */
/*************************************************/

int history_can_go_backwards(browser_data * b)
{
  history_user * user;

  if (!b) return 0;

  user = (history_user *) b->history_current;

  if (!user || !user->history_prev) return 0;

  return 1;
}

/*************************************************/
/* history_can_go_forwards()                     */
/*                                               */
/* Reports whether or not there are more pages   */
/* to go forward to in the local History of a    */
/* given browser.                                */
/*                                               */
/* Parameters: Pointer to a browser_data struct  */
/*             relevant to the History.          */
/*                                               */
/* Returns:    1 if there are more items in the  */
/*             local history to go forwards to,  */
/*             else 0.                           */
/*************************************************/

int history_can_go_forwards(browser_data * b)
{
  history_user * user;

  if (!b) return 0;

  user = (history_user *) b->history_current;

  if (!user || !user->history_next) return 0;

  return 1;
}

/*************************************************/
/* history_fetch_backwards()                     */
/*                                               */
/* When called, will fetch the previous page in  */
/* a given browser's local History.              */
/*                                               */
/* Parameters: Pointer to a browser_data struct  */
/*             relevant to the History;          */
/*                                               */
/*             1 to open the URL in a new window */
/*             or 0 to open it in the window to  */
/*             which the browser_data struct is  */
/*             relevant.                         */
/*************************************************/

_kernel_oserror * history_fetch_backwards(browser_data * b, int new_view)
{
  history_user * user;
  const char   * url;

  #ifdef TRACE
    if (tl & (1u<<16)) Printf("history_fetch_backwards: Called for %p\n", b);
  #endif

  if (!is_known_browser(b)) return NULL;

  /* Only proceed if we're not right at the start of the history */

  user = (history_user *) b->history_current;

  if (!user || !user->history_prev)
  {
    #ifdef TRACE
      if (tl & (1u<<16)) Printf("history_fetch_backwards: Can't go back any further, exitting\n");
    #endif

    return NULL;
  }

  #ifdef TRACE
    if (tl & (1u<<16)) Printf("history_fetch_backwards: Proceeding\n");
  #endif

  /* Step backwards - even if we're going to open a new view, */
  /* when the child inherits the parent's history this needs  */
  /* to have been set up to make sure the child gains the     */
  /* right position in the inherited history list. We will    */
  /* correct the parent's history position later.             */

  b->history_current = (void *) (user->history_prev);

  /* Get a pointer to the URL */

  url = user->history_prev->parent->url->full;

  /* Flag that this will be a History based fetch */

  b->from_history = 1;

  /* Get the URL in either the same window or a new window. */

  if (!new_view)
  {
    #ifdef TRACE
      if (tl & (1u<<16)) Printf("history_fetch_backwards: Exitting through fetchpage_new\n");
    #endif

    /* Fetch the URL, flagging not to record this URL in the history */

    return (fetchpage_new(b, (char *) url, 0, 1));
  }
  else
  {
    #ifdef TRACE
      if (tl & (1u<<16)) Printf("history_fetch_backwards: Exitting through windows_create_browser and browser_inherit\n");
    #endif

    RetError(windows_create_browser((char *) url, NULL, NULL, NULL, Windows_CreateBrowser_Normal));
    RetError(browser_inherit(b, last_browser));

    /* We didn't end up moving anywhere in b, and only stepped backwards */
    /* so that the indirectly called history_inherit could work properly */
    /* - so now make sure that b's current history position has not been */
    /* altered.                                                          */

    b->history_current = (void *) (user);
  }

  return NULL;
}

/*************************************************/
/* history_fetch_forwards()                      */
/*                                               */
/* When called, will fetch the next page in a    */
/* given browser's local History.                */
/*                                               */
/* Parameters: Pointer to a browser_data struct  */
/*             relevant to the History;          */
/*                                               */
/*             1 to open the URL in a new window */
/*             or 0 to open it in the window to  */
/*             which the browser_data struct is  */
/*             relevant.                         */
/*************************************************/

_kernel_oserror * history_fetch_forwards(browser_data * b, int new_view)
{
  history_user * user;
  const char   * url;

  #ifdef TRACE
    if (tl & (1u<<16)) Printf("history_fetch_forwards: Called for %p\n", b);
  #endif

  if (!is_known_browser(b)) return NULL;

  /* Only proceed if we're not right at the start of the history */

  user = (history_user *) b->history_current;

  if (!user || !user->history_next)
  {
    #ifdef TRACE
      if (tl & (1u<<16)) Printf("history_fetch_forwards: Can't go forwards any further, exitting\n");
    #endif

   return NULL;
  }

  #ifdef TRACE
    if (tl & (1u<<16)) Printf("history_fetch_forwards: Proceeding\n");
  #endif

  /* Step forwards - even if we're going to open a new view, */
  /* when the child inherits the parent's history this needs */
  /* to have been set up to make sure the child gains the    */
  /* right position in the inherited history list. We will   */
  /* correct the parent's history position later.            */

  b->history_current = (void *) (user->history_next);

  /* Get a pointer to the URL */

  url = user->history_next->parent->url->full;

  /* Flag that this will be a History based fetch */

  b->from_history = 1;

  /* Get the URL in either the same window or a new window. */

  if (!new_view)
  {
    #ifdef TRACE
      if (tl & (1u<<16)) Printf("history_fetch_forwards: Exitting through fetchpage_new\n");
    #endif

    /* Fetch the URL, flagging not to record this URL in the history */

    return (fetchpage_new(b, (char *) url, 0, 1));
  }
  else
  {
    #ifdef TRACE
      if (tl & (1u<<16)) Printf("history_fetch_forwards: Exitting through windows_create_browser and browser_inherit\n");
    #endif

    RetError(windows_create_browser((char *) url, NULL, NULL, NULL, Windows_CreateBrowser_Normal));
    RetError(browser_inherit(b, last_browser));

    /* We didn't end up moving anywhere in b, and only stepped forwards  */
    /* so that the indirectly called history_inherit could work properly */
    /* - so now make sure that b's current history position has not been */
    /* altered.                                                          */

    b->history_current = (void *) (user);
  }

  return NULL;
}

/*************************************************/
/* history_menu_popup()                          */
/*                                               */
/* Handles clicks on a history menu popup item.  */
/*                                               */
/* Parameters: Pointer to a browser_data struct  */
/*             relevant to the history to show,  */
/*             or NULL if this is for a global   */
/*             history from an OpenURL dialogue  */
/*             box;                              */
/*                                               */
/*             Object ID of the item holding the */
/*             menu gadget;                      */
/*                                               */
/*             Component ID of the item that was */
/*             clicked on;                       */
/*                                               */
/*             1 to show the global history even */
/*             if the first parameter is not     */
/*             NULL, else 0;                     */
/*                                               */
/*             1 to show the URLs, 0 to show     */
/*             page titles where available.      */
/*************************************************/

_kernel_oserror * history_menu_popup(browser_data * b, ObjectId object, ComponentId component, int global, int show_urls)
{
  _kernel_oserror         * e;
  WimpGetWindowStateBlock   state;
  BBox                      menu;

  /* If there's already a menu open, close it */
  /* (so the action is to toggle the menu).   */

  if ((menusrc == Menu_LocalHist || menusrc == Menu_GlobalHist) && menuhdl == b)
  {
    menusrc = Menu_None;
    menuhdl = NULL;

    return wimp_create_menu((void *) -1, 0, 0);
  }

  /* Get the Wimp handle for the tool bar and get the window state */

  e = window_get_wimp_handle(0, object, &state.window_handle);
  if (e) return e;

  e = wimp_get_window_state(&state);
  if (e) return e;

  /* Get the bounding box of the popup icon that was used */

  e = gadget_get_bbox(0, object, component, &menu);
  if (e) return e;

  /* Convert that to screen coords ready for opening the menu */
  /* next to it.                                              */

  coords_box_toscreen(&menu, (WimpRedrawWindowBlock *) &state);

  if (component == URLBarHistoryMenuR || component == OpenHistory)
  {
    /* Build and show menu to right of menu icon for URLBarHistoryMenuR object */

    e = (history_build_menu(b,
                            menu.xmax - 2,
                            menu.ymax,
                            global,
                            show_urls,
                            0));
    if (e) return e;
  }
  else
  {
    /* Otherwise, show it to the left of the icon */

    e = history_build_menu(b,
                           menu.xmin - 4,
                           menu.ymin + 4,
                           global,
                           show_urls,
                           1);
    if (e) return e;
  }

  return NULL;
}

/*************************************************/
/* history_compare_entries()                     */
/*                                               */
/* A comparisson function for qsort(); compares  */
/* the last_accessed fields of two given         */
/* history_entry structures so that an array     */
/* being sorted will have highest last_accessed  */
/* field (newest) items first.                   */
/*                                               */
/* Parameters: Pointer to the first              */
/*             history_entry struct as a void *. */
/*                                               */
/*             Pointer to the second             */
/*             history_entry struct as a void *. */
/*************************************************/

static int history_compare_entries(const void * first, const void * second)
{
  history_entry * f = *((history_entry **) first);
  history_entry * s = *((history_entry **) second);

  if (f->last_accessed < s->last_accessed) return 1; /* We want the greatest last_accessed field to come first */
  if (f->last_accessed > s->last_accessed) return -1;

  return 0;
}

/*************************************************/
/* history_build_menu()                          */
/*                                               */
/* Builds a history menu for the given browser,  */
/* showing it at the specified coordinates.      */
/*                                               */
/* Parameters: Pointer to a browser_data struct  */
/*             relevant to the menu, or NULL to  */
/*             build from the global history;    */
/*                                               */
/*             x coordinate to show at;          */
/*                                               */
/*             y coordinate to show at;          */
/*                                               */
/*             1 to show the global history even */
/*             if the first parameter is not     */
/*             NULL;                             */
/*                                               */
/*             Non-0 to only show URLs, 0 to     */
/*             allow titles in the menu;         */
/*                                               */
/*             Non-0 to subtract the width of    */
/*             the menu from the given show x    */
/*             coordinate (e.g. to show to the   */
/*             left of a given position) else 0. */
/*************************************************/

_kernel_oserror * history_build_menu(browser_data * b, int x, int y, int global, int show_urls, int subtract)
{
  _kernel_oserror * e;
  wimp_menuhdr    * mhp;
  wimp_menuitem   * mip;
  char            * menudata;

  int               i;
  int               size;
  int               width, awidth, thiswidth;
  int               len;

  /* Clear out any existing menu-related data */

  free(history_menu); history_menu = NULL;
  free(entry_array);  entry_array  = NULL, nentries = 0;
  free(user_array);   user_array   = NULL, nusers   = 0;

  #ifdef TRACE
    if (tl & (1u<<16)) Printf("history_build_menu: Called with %p\n", (void *) b);
  #endif

  /* If there are no History items, flag an error. */

  if (!history_base) goto history_build_menu_empty_history;

  /* Work out the data size required for the menu structure. */
  /* Can't just point the menu to the history list as it's a */
  /* flex block, which may shift whilst the menu is open.    */

  size   = sizeof(wimp_menuhdr);
  width  = 8;
  awidth = 0;

  /* Loop round finding the string length of the longest entry */
  /* in 'width' and the OS unit width of it in 'awidth'.       */

  _swix(Hourglass_On, 0);

  #ifdef TRACE
    if (tl & (1u<<16))
    {
      Printf("\nhistory_build_menu: Widthing menu\n"
               "=================================\n\n");
    }
  #endif

  if (b && !global)
  {
    history_user  * current;

    /* Want a local (visit history).                                     */
    /*                                                                   */
    /* For this, we want to build a menu which shows where the forwards  */
    /* / backwards buttons will go, with the current position in the     */
    /* local History ticked. So we need to find the browser's current    */
    /* position, move right to the end of it, and build the menu from    */
    /* there. The build order will follow the history path by definition */
    /* so no sorting is needed afterwards.                               */

    current = (history_user *) b->history_current;

    if (!current) goto history_build_menu_empty_history;

    /* Track to the end of the local History */

    while (current->history_next) current = current->history_next;

    /* Now add in each entry */

    menu_entries = 0;

    while (current)
    {
      history_user    ** new_array;
      const char       * used;
      const char       * url;
      const char       * title = current->parent->title;
      url_description  * url_d = current->parent->url;

      /* Rremember the item in the array */

      new_array = realloc(user_array, (++nusers) * sizeof(history_user *));

      if (!new_array) /* Zoiks! The allocation failed */
      {
        goto history_build_menu_out_of_memory;
      }

      user_array             = new_array;
      user_array[nusers - 1] = current;

      menu_entries ++;

      if (url_d) url = url_d->full;
      else       url = "";

      /* (So from the above, 'url' is never NULL) */

      if (show_urls || !title || !*title) len = strlen(url),   used = url;
      else                                len = strlen(title), used = title;

      #ifdef TRACE
        if (tl & (1u<<16))
        {
          Printf("Local  - URL  : '%s'\n",   url);
          Printf("Local  - Title: '%s'\n\n", title ? title : "");
        }
      #endif

      /* Account for an appended space to stop e.g. 'Home' being taken */
      /* as a keyboard shortcut by the Wimp                            */

      len ++;

      /* Work out the space requirement for this entry and record the */
      /* widest entry in characters in 'width'.                       */

      size += len + 1 + sizeof(wimp_menuitem); /* (+1 = string terminator) */

      if (len > width) width = len;

      /* Find the width of the entry in OS units */

      RetError(utils_text_width((char *) used, &thiswidth, 0));

      /* Record the widest entry in OS units in 'awidth' */

      if (thiswidth > awidth) awidth = thiswidth;

      /* Go on to the next (or rather, given the order we want the */
      /* menu items in, previous!) item.                           */

      current = current->history_prev;
    }
  }
  else
  {
    history_entry   * entry = history_base;
    history_entry  ** new_array;
    const char      * used;
    const char      * url;
    const char      * title;
    url_description * url_d;

    /* Want a global history.                                        */
    /*                                                               */
    /* We need to go through all history_entry structures, recording */
    /* each on in the entry_array array so menu entry numbers can be */
    /* associated with history_entry structures.                     */

    menu_entries = 0;

    while (entry)
    {
      new_array = realloc(entry_array, (++nentries) * sizeof(history_user *));

      if (!new_array)
      {
        goto history_build_menu_out_of_memory;
      }

      entry_array = new_array;
      entry_array[nentries - 1] = entry;

      /* Find the maximum width in chars and OS units of the URL or title strings */

      title = entry_array[nentries - 1]->title;
      url_d = entry_array[nentries - 1]->url;

      /* From here on it's more or less identical to the local history code above */

      if (url_d) url = url_d->full;
      else       url = NULL;

      if (show_urls || !title || !*title) len = url ? strlen(url) : 0, used = url;
      else                                len = strlen(title),         used = title;

      #ifdef TRACE
        if (tl & (1u<<16))
        {
          Printf("Global - URL  : '%s'\n",   url   ? url   : "");
          Printf("Global - Title: '%s'\n\n", title ? title : "");
        }
      #endif

      len ++;
      size += len + 1 + sizeof(wimp_menuitem);

      if (len > width) width = len;

      RetError(utils_text_width((char *) used, &thiswidth, 0));

      if (thiswidth > awidth) awidth = thiswidth;

      menu_entries ++;

      /* Next item */

      entry = entry->next;
    }

    /* Sort the entries array based on the entry datestamps - */
    /* newest (highest datestamp number) first.               */

    qsort(entry_array, nentries, sizeof(history_entry *), history_compare_entries);

    #ifdef TRACE

      if (tl & (1u<<16))
      {
        history_entry * entry;

        Printf("Post-sorting, entry array looks like:\n\n");

        for (i = 0; i < nentries; i++)
        {
          entry = entry_array[i];

          Printf("Entry %04d - URL '%s'\n", i, entry->url ? entry->url->full : "");
        }

        Printf("\n");
      }

    #endif
  }

  size += 4;

  /* Deallocate any existing menu data and allocate the new required size. */

  #ifdef TRACE
    if (tl & (1u<<16))
    {
      if (history_menu) Printf("history_build_menu: Freeing existing store\n");
      else              Printf("history_build_menu: There is no existing store\n");
    }
  #endif

  free(history_menu);
  history_menu = NULL;

  #ifdef TRACE
    if (tl & (1u<<16)) Printf("history_build_menu: Attempting to malloc %d bytes\n",size);
  #endif

  history_menu = calloc(1, size);
  if (!history_menu) goto history_build_menu_out_of_memory;

  /* Point mhp to the start of the menu header, and mip  */
  /* to the first menu item (straight after the header). */

  mhp = (wimp_menuhdr  *) history_menu;
  mip = (wimp_menuitem *) (((int) mhp) + sizeof(wimp_menuhdr));

  /* Fill in the header. */

  strncpy(mhp->title, lookup_token("HistMenT:History",0,0), 12);

  mhp->tit_fcol  = 7;
  mhp->tit_bcol  = 2;
  mhp->work_fcol = 7;
  mhp->work_bcol = 0;
  mhp->width     = awidth;
  mhp->height    = 44;
  mhp->gap       = 0;

  /* Pointer arithmetic - mip + menu_entries adds menu_entries */
  /* lots of sizeof(mip) to menudata, since the cast to char * */
  /* is the last thing that happens. So menudata points past   */
  /* all the menu structure stuff to the data area.            */

  menudata = (char *) (mip + menu_entries);

  /* Fill in each menu item. */

  #ifdef TRACE
    if (tl & (1u<<16))
    {
      Printf("\nhistory_build_menu: Building menu\n"
               "=================================\n\n");
    }
  #endif

  for (i = 0; i < menu_entries; i++)
  {
    url_description * url_d;
    char            * url;
    char            * title;

    /* Find the URL or title string for this entry */

    if (b && !global)
    {
      history_user * user = user_array[i];

      url_d = user->parent->url;
      title = user->parent->title;

      url = url_d ? url_d->full : "";

      #ifdef TRACE
        if (tl & (1u<<16))
        {
          Printf("Local  - URL  : '%s'\n",   url);
          Printf("Local  - Title: '%s'\n\n", title ? title : "");
        }
      #endif
    }
    else
    {
      history_entry * entry = entry_array[i];

      url_d = entry->url;
      title = entry->title;

      url = url_d ? url_d->full : "";

      #ifdef TRACE
        if (tl & (1u<<16))
        {
          Printf("Global - URL  : '%s'\n",   url);
          Printf("Global - Title: '%s'\n\n", title ? title : "");
        }
      #endif
    }

    /* Fill in the entry header */

    mip->flags     = (
                       (i == menu_entries - 1)
                       ?
                       wimp_MLAST
                       :
                       0
                     )
                     |
                     (
                       (
                         b       &&
                         !global &&
                         user_array[i] == (history_user *) b->history_current
                       )
                       ?
                       wimp_MTICK
                       :
                       0
                     );

    mip->submenu   = (wimp_menuptr) -1;
    mip->iconflags = wimp_ITEXT    |
                     wimp_IFILLED  |
                     wimp_INDIRECT |
                     (7<<24);

    mip->data.indirecttext.validstring = NULL;
    mip->data.indirecttext.bufflen     = 0;
    mip->data.indirecttext.buffer      = menudata;

    /* Use the URL if we're told to, or the title is NULL / a null string */

    if (show_urls || !title || !*title)
    {
      /* Use the URL */

      strcpy(menudata, url);
      strcat(menudata, " "); /* To stop e.g. 'Home' at the end of an item being taken as a keyboard shortcut by the Wimp */

      len = strlen(menudata);

      /* Advance the data pointer, possibly removing any */
      /* CGI information if HIDE_CGI is defined inside   */
      /* the compiler.                                   */

      #ifdef HIDE_CGI

        toolbars_hide_cgi(menudata);

      #else

        /* If not hiding all CGI information, still don't want to  */
        /* put all the CGI stuff in the menu or it can get far too */
        /* wide. So leave an indicator to show there was CGI info. */

        toolbars_hide_cgi(menudata);

        if      (len > strlen(menudata) + 7) strcat(menudata, " (+CGI)");
        else if (len > strlen(menudata) + 4) strcat(menudata, "?...");

      #endif
    }
    else
    {
      /* Use the title */

      strcpy(menudata, title);
      strcat(menudata, " "); /* To stop e.g. 'Home' at the end of an item being taken as a keyboard shortcut by the Wimp */

      len = strlen(menudata);
    }

    /* If we've gone over the width limit on this entry,  */
    /* show the right hand portion of the item with '...' */
    /* before it.                                         */

    if (len + 4 > Limits_HistoryMenuItemSize) /* '+4' to account for the '...' we'll put in front plus terminator */
    {
      memmove(menudata + 3, menudata + len - (Limits_HistoryMenuItemSize - 3), Limits_HistoryMenuItemSize - 3);
      strncpy(menudata, "...", 3);
      menudata[Limits_HistoryMenuItemSize - 1] = '\0';
    }

    menudata += strlen(menudata) + 1;

    /* Next item... */

    mip ++;
  }

  #ifdef TRACE
    if (menudata > ((char *) history_menu) + size)
    {
      erb.errnum = 0;
      sprintf(erb.errmess,"Fatal error inside history_build_menu: Overran menu buffer! Allocated %d bytes, then used %d.",size,(int) menudata - (int) history_menu);
      show_error(&erb);
    }
  #endif

  /* Finally, open the menu */

  #ifdef TRACE
    if (tl & (1u<<16)) Printf("history_build_menu: Exitting through wimp_create_menu\n");
  #endif

  menuhdl = (void *) b;

  if (global) menusrc = Menu_GlobalHist;
  else        menusrc = Menu_LocalHist;

  e = wimp_create_menu(history_menu, x - (subtract ? (mhp->width + 64) : 0), y);

  _swix(Hourglass_Off, 0);

  return e;

  /* Forced exits... */

history_build_menu_out_of_memory:

  _swix(Hourglass_Off, 0);

  free(history_menu); history_menu = NULL;
  free(entry_array);  entry_array  = NULL, nentries = 0;
  free(user_array);   user_array   = NULL, nusers   = 0;

  /* Out of memory */

  erb.errnum = Utils_Error_Custom_Normal;

  StrNCpy0(erb.errmess,
           lookup_token("NoMemLHi:There is not enough free memory to open the history menu.",
                        0,
                        0));

  #ifdef TRACE
    if (tl & (1u<<16)) Printf("history_build_menu: Exitting (out of memory)\n");
  #endif

  return &erb;

history_build_menu_empty_history:

  _swix(Hourglass_Off, 0);

  free(history_menu); history_menu = NULL;
  free(entry_array);  entry_array  = NULL, nentries = 0;
  free(user_array);   user_array   = NULL, nusers   = 0;

  /* Empty history (nothing at all, nothing for a given */
  /* browser, or whatever)                              */

  erb.errnum = Utils_Error_Custom_Message;

  StrNCpy0(erb.errmess,
           lookup_token("EmptyHistE:The history list is empty.",
                        0,
                        0));

  #ifdef TRACE
    if (tl & (1u<<16)) Printf("history_build_menu: Exitting (history is empty)\n");
  #endif

  return &erb;
}

/*************************************************/
/* history_menu_selection()                      */
/*                                               */
/* Jumps to a URL according to the item selected */
/* in a history menu.                            */
/*                                               */
/* If Adjust is used the menu is not reopened as */
/* the fetch will occur in a new window (as with */
/* following page links) - it doesn't make sense */
/* to reopen the menu in this case.              */
/*                                               */
/* Parameters: Pointer to a browser_data struct  */
/*             relevant to the history, or NULL  */
/*             for the global history - in this  */
/*             case it is assumed that the menu  */
/*             opened from an Open URL dialogue  */
/*             and appropriate alternative       */
/*             functions will be called;         */
/*                                               */
/*             Pointer to a WimpPollBlock struct */
/*             from which the menu item that was */
/*             selected may be determined.       */
/*************************************************/

_kernel_oserror * history_menu_selection(browser_data * b, WimpPollBlock * block)
{
  int          item, adj;
  int          global;
  const char * url = NULL;

  /* What type of menu was it? */

  if (menusrc == Menu_GlobalHist || !b) global = 1;
  else                                  global = 0;

  /* Flag that there is no known menu source anymore */
  /* and fetch the new URL.                          */

  menusrc = Menu_None;

  /* What item was clicked on? */

  item = block->menu_selection[0];

  /* If the menu selection appears to be out of range, */
  /* exit quietly.                                     */

  if (
       item < 0             ||
       item >= menu_entries ||
       (
         global           &&
         item >= nentries
       )
       ||
       (
         !global        &&
         item >= nusers
       )
     )
  {
    #ifdef TRACE
      if (tl & (1u<<16)) Printf("history_menu_selection: Warning, menu selection out of range\n");
    #endif

    return NULL;
  }

  /* Otherwise find out the button that was used. */

  adj = controls.ignore_adjust ? 0 : adjust();

  /* If a new window isn't going to be opened, */
  /* need to remember that we've just dived    */
  /* into the History list so that forwards /  */
  /* backwards work correctly.                 */

  if (!adj && b && !global)
  {
    history_user * user = user_array[item];

    b->history_current = (void *) user;
  }

  /* Point to the required URL */

  if (!global)
  {
    history_user * user = user_array[item];

    if (user->parent && user->parent->url) url = user->parent->url->full;
  }
  else
  {
    history_entry * entry = entry_array[item];

    if (entry->url) url = entry->url->full;
  }

  /* If b is set, this is from a browser toolbar */

  if (b)
  {
    /* Somewhat non-standard behaviour to have an adjust-click  */
    /* open a new window instead of leaving the menu up, but    */
    /* this is more consistent with the rest of the browser UI. */

    if (!adj) return fetchpage_new(b,
                                   url,
                                   0,
                                   1);

    else return windows_create_browser((char *) url,
                                       NULL,
                                       NULL,
                                       NULL,
                                       Windows_CreateBrowser_Normal);
  }

  /* Otherwise, if b is NULL, it's from an Open URL dialogue */

  else
  {
    return openurl_fill_in_url((char *) url);
  }

  return NULL;
}

/*************************************************/
/* history_load()                                */
/*                                               */
/* Loads the global history from the given path. */
/* Will raise errors (usually, due to RISC OS    */
/* C's file I/O, the wrong ones...) if there is  */
/* a failure during loading, but not if the file */
/* refuses to open or the number of items cannot */
/* be read from it (i.e. a missing or zero       */
/* length History file).                         */
/*                                               */
/* Parameters: Pointer to the full pathname for  */
/*             the history file.                 */
/*************************************************/

_kernel_oserror * history_load(char * pathname)
{
  FILE        * file;
  char        * title      = NULL;
  char        * url        = NULL;
  static char * local_path = NULL;
  int           result;
  int           last_accessed, title_len, url_len;
  int           items, item;
  int           cc, ch;

  if (!pathname || !*pathname) return NULL;

  local_path = malloc(strlen(pathname) + 1);
  if (!local_path) return NULL;

  strcpy(local_path, pathname);

  #ifdef TRACE
    if (tl & (1u<<16)) Printf("history_load: Called\n");
  #endif

  file = fopen(local_path, "rb");

  if (!file)
  {
    free(local_path);
    return NULL; /* Fail silently - there may be no History file; this is OK */
  }

  /* Read how many items there are - again file silently, the */
  /* file may just be zero bytes long.                        */

  #ifdef TRACE
    if (tl & (1u<<16)) Printf("history_load: File opened OK\n");
  #endif

  result = fscanf(file, "%d\n", &items);

  if (result == EOF)
  {
    fclose(file);
    free(local_path);

    return NULL;
  }

  #ifdef TRACE
    if (tl & (1u<<16))
    {
      if (items > 1) Printf("history_load: There are %d items\n",items);
      else           Printf("history_load: There is 1 item\n");
    }
  #endif

  _swix(Hourglass_On, 0);

  for (item = 0; item < items; item++)
  {
    _swix(Hourglass_Percentage,
          _IN(0),

          (100 * item) / items);

    /* Read the last accessed time and required string lengths */

    result = fscanf(file, "%d,%d,%d\n", &last_accessed, &title_len, &url_len);
    if (result == EOF) goto history_load_exit;

    /* Allocate buffers for the strings */

    free(title);
    title = malloc(title_len + 1);

    if (!title)
    {
      fclose(file);

      _swix(Hourglass_Off,0);

      free(local_path);

      return make_no_memory_error(27);
    }

    free(url);
    url = malloc(url_len + 1);

    if (!url)
    {
      fclose(file);

      _swix(Hourglass_Off,0);

      free(title);
      free(local_path);

      return make_no_memory_error(27);
    }

    /* Read the title */

    for (cc = 0; cc < title_len; cc++)
    {
      int ch = fgetc(file);

      if (ch == EOF) goto history_load_exit;

      title[cc] = (char) ch;
    }

    title[title_len] = 0;

    /* Hmm, should not be needed? But it seems fscanf reads one \n extra */
    /* when there is a NULL title string. It probably thinks the line    */
    /* ending type is '\n\n' or something.                               */

    if (title_len)
    {
      /* Skip the '\n' */

      ch = fgetc(file);
      if (ch == EOF) goto history_load_exit;
    }

    /* Read the URL */

    for (cc = 0; cc < url_len; cc++)
    {
      int ch = fgetc(file);

      if (ch == EOF) goto history_load_exit;

      url[cc] = (char) ch;
    }

    url[url_len] = 0;

    /* Skip the '\n' */

    ch = fgetc(file);
    if (ch == EOF) goto history_load_exit;

    #ifdef TRACE
      if (tl & (1u<<16))
      {
        Printf("history_load: %04d Title = \0213'%s'\0217\n", item, title);
        Printf("                     URL = \0216'%s'\0217\n", url);
      }
    #endif

    /* Now make the entry */

    if (url_len)
    {
      history_entry * found = malloc(sizeof(history_entry));

      if (!found)
      {
        #ifdef TRACE
          if (tl & (1u<<16)) Printf("history_load: Couldn't allocate space for entry\n");
        #endif

        fclose(file);

        _swix(Hourglass_Off,0);

        free(url);
        free(title);
        free(local_path);

        return make_no_memory_error(25);
      }

      found->url = urlutils_return_description(url);

      /* We've now finished with the temporary URL string */

      free(url);
      url = NULL;

      if (!found->url)
      {
        free(found);

        #ifdef TRACE
          if (tl & (1u<<16)) Printf("history_load: Couldn't allocate space for URL description\n");
        #endif

        fclose(file);

        _swix(Hourglass_Off,0);

        free(url);
        free(title);
        free(local_path);

        history_remove_entry(NULL, found);

        return make_no_memory_error(25);
      }
      else
      {
        /* Create a hash number for the string */

        found->hash = utils_return_hash(found->url->full);
      }

      /* Link in the structure */

      found->prev = NULL;
      found->next = history_base;

      if (history_base) history_base->prev = found;

      history_base = found;

      /* Fill in some other fields */

      found->title         = title; /* Use the title string directly */
      found->users         = NULL;
      found->last_accessed = last_accessed;

      title = NULL;

      #ifdef TRACE
        if (tl & (1u<<16)) Printf("history_load: OK, have entry %p with description block %p\n",found,found->url);
      #endif
    }

  /* (Closure of 'for' loop) */
  }

  fclose(file);

  #ifdef TRACE
    if (tl & (1u<<16)) Printf("history_load: Successful, exitting via. expiry functions\n");
  #endif

  _swix(Hourglass_Off,0);

  free(url);
  free(title);
  free(local_path);

  if (choices.expiry_age) RetError(history_expire(NULL, time(NULL) - choices.expiry_age));

  if (choices.max_size) return history_limit(choices.max_size);
  else return NULL;

  /* Error condition exit routine */

history_load_exit:

  if (file) fclose(file);

  _swix(Hourglass_Off, 0);

  free(url);
  free(title);
  free(local_path);

  RetLastE;
}

/*************************************************/
/* history_save()                                */
/*                                               */
/* Saves the global history to the given path.   */
/*                                               */
/* Parameters: Pointer to the full pathname for  */
/*             the history file.                 */
/*************************************************/

_kernel_oserror * history_save(char * pathname)
{
  history_entry * entry      = history_base;
  FILE          * file;
  static char   * local_path = NULL;
  int             wrote;
  int             items = 0;

  if (!pathname || !*pathname) return NULL;

  /* Canonicalise the path */

  RetError(utils_canonicalise_path(pathname, &local_path));

  /* Ensure it is present */

  {
    _kernel_oserror * e = utils_build_tree(local_path);

    if (e)
    {
      free(local_path);
      return e;
    }
  }

  /* How many items are there? */

  while (entry)
  {
    items ++;
    entry = entry->next;
  }

  entry = history_base;

  /* Create the file */

  file = fopen(local_path, "wb");

  if (!file)
  {
    free(local_path);

    RetLastE;
  }

  /* Write the number of items */

  wrote = fprintf(file, "%d\n", items);

  if (wrote <= 0)
  {
    fclose(file);
    free(local_path);

    RetLastE;
  }

  /* Write the item contents */

  while (entry)
  {
    if (entry->url)
    {
      wrote = fprintf(file,

                      "%d,%d,%d\n%s\n%s\n",

                      entry->last_accessed,

                      entry->title     ? strlen(entry->title)     : 0,
                      entry->url->full ? strlen(entry->url->full) : 0,

                      entry->title     ? entry->title     : "",
                      entry->url->full ? entry->url->full : "");

      if (wrote <= 0)
      {
        fclose(file);
        free(local_path);

        RetLastE;
      }
    }

    entry = entry->next;
  }

  /* Close the file and exit */

  fclose(file);
  free(local_path);

  return NULL;
}

/*************************************************/
/* history_save_as_html()                        */
/*                                               */
/* This function saves the History as an HTML    */
/* file.                                         */
/*                                               */
/* Parameters: Pointer to the filename to save   */
/*             to (null terminated);             */
/*                                               */
/*             Pointer to a browser_data struct  */
/*             to save the History for if you    */
/*             want a local history, else NULL   */
/*             for the global history.           */
/*************************************************/

_kernel_oserror * history_save_as_html(char * pathname, browser_data * b)
{
  _kernel_oserror * e;
  static char     * local_path = NULL;
  history_entry   * entry      = history_base;
  history_user    * user;
  FILE            * fileptr;
  int               written;

  if (!pathname || !*pathname) return NULL;

  local_path = malloc(strlen(pathname) + 1);
  if (!local_path) return NULL;

  strcpy(local_path, pathname);

  /* Could take a while... */

  _swix(Hourglass_On, 0);

  /* Open the file for writng */

  fileptr = fopen(local_path, "wb");

  /* Complain if it fails */

  if (fileptr == NULL)
  {
    free(local_path);

    RetLastE;
  }

  /* Write the file header */

  HistoryWrite(fprintf(fileptr, "<html>\n"
                                "<head>\n"
                                CHARSET_SPECIFIER
                                "<title>"));

  HistoryWrite(fprintf(fileptr, lookup_token("HistoryHTMLTitle:History",0,0)));

  HistoryWrite(fprintf(fileptr, "</title>\n"
                                "</head>\n"
                                "<body>\n"
                                "<ul>\n"));

  /* Fill in the body for global histories */

  if (!b)
  {
    while (entry)
    {
      if (entry->url && entry->url->full)
      {
        HistoryWrite(fprintf(fileptr, "<li><a href=\"%s\">%s</a>\n",
                                      entry->url->full,
                                      (entry->title && *entry->title) ? entry->title : entry->url->full));
      }

      entry = entry->next;
    }
  }

  /* Fill in the body for local histories */

  else
  {
    user = (history_user *) b->history_current;

    while (user && user->history_next) user = user->history_next;

    while (user)
    {
      entry = user->parent;

      if (entry && entry->url && entry->url->full)
      {
        HistoryWrite(fprintf(fileptr, "<li><a href=\"%s\">%s</a>\n",
                                      entry->url->full,
                                      (entry->title && *entry->title) ? entry->title : ""));
      }

      user = user->history_prev;
    }
  }

  /* Write the footer and close the file */

  HistoryWrite(fprintf(fileptr, "</ul>\n"));
  HistoryWrite(fprintf(fileptr, "</body>\n"));
  HistoryWrite(fprintf(fileptr, "</html>\n"));

  fclose(fileptr);

  _swix(Hourglass_Off, 0);

  /* Set the filetype to HTML (0xfaf) */

  e = _swix(OS_File,
            _INR(0,2),

            18,
            local_path,
            FileType_HTML);

  free(local_path);

  return e;

  /* Error condition exit */

history_save_error:

  if (fileptr)
  {
    fclose(fileptr);

    _swix(Hourglass_Off, 0);
  }

  free(local_path);

  RetLastE;
}

/*************************************************/
/* history_find_match()                          */
/*                                               */
/* Takes a string from the given buffer and sees */
/* if there's something in the global History    */
/* that matches it in some way.                  */
/*                                               */
/* If it finds something, it writes it back to   */
/* the buffer and returns 1.                     */
/*                                               */
/* Parameters: Pointer to the buffer holding the */
/*             string to try and match;          */
/*                                               */
/*             Size of the buffer in bytes.      */
/*                                               */
/* Returns:    1 if the buffer is updated with a */
/*             match string, else 0 (buffer      */
/*             contents will be unaltered).      */
/*************************************************/

int history_find_match(char * buffer, int buffer_size)
{
  history_entry * entry         = history_base;
  history_entry * lowest_entry  = NULL;
  const char    * found         = NULL;
  int             lowest_offset = -1;
  int             lowest_diff   = 0;
  int             this_offset   = 0;
  int             got_one;

  if (!buffer || !*buffer) return 0;

  while (entry)
  {
    if (entry->url && entry->url->full)
    {
      got_one = 0;

      /* Match in the host, if present */

      if (entry->url->host)
      {
        /* See if we can find the string */

        found = strstr(entry->url->host, buffer);

        if (found)
        {
          /* If so, record the offset into the string where  */
          /* the match was found and mark we've got a match. */

          this_offset = found - entry->url->host;
          got_one     = 1;
        }
      }

      /* Match in the path, if nothing found in the host */

      if (!got_one && entry->url->path)
      {
        found = strstr(entry->url->path, buffer);

        if (found)
        {
          this_offset = found - entry->url->path;
          got_one     = 1;
        }
      }

      /* Match in the full URL, if all else fails */

      if (!got_one)
      {
        found = strstr(entry->url->full, buffer);

        if (found)
        {
          this_offset = found - entry->url->full;
          got_one     = 1;
        }
      }

      /* Match in the title, out of desperation! */

      if (!got_one && entry->title)
      {
        found = strstr(entry->title, buffer);

        if (found)
        {
          this_offset = found - entry->title;
          got_one     = 1;
        }
      }

      /* If found, have we not recorded an offset before, or is this offset  */
      /* lower than any previously recorded? If so, remember the entry. This */
      /* way, 'digital' will match 'www.digital.com' rather than             */
      /* 'www.altavista.digital.com' regardless of where the entry is in the */
      /* History. Matching the first one we come to would obviously rely on  */
      /* the order of appearance in the list.                                */

      if (got_one)
      {
        if (lowest_offset < 0 || this_offset <= lowest_offset)
        {
          int this_diff = strlen(entry->url->full) - strlen(buffer);

          lowest_offset = this_offset;

          /* Having found an entry that matches in the lowest part of the string */
          /* so far, we also want to choose one which has the smallest string    */
          /* length difference between itself and the given match string, which  */
          /* is non-zero. This ensures we would go 'www.acorn.com/acorn/',       */
          /* 'www.acorn.com/acorn/news/', 'www.acorn.com/acorn/news/releases/'   */
          /* again regardless of the relative position of the entries in the     */
          /* History list.                                                       */
          /*                                                                     */
          /* Of course, the whole thing is still fairly undetermined - whatever  */
          /* the next directory is after you've found a match on the root of a   */
          /* site (say) which happens to be the shortest will be the tree you    */
          /* always end up fetching. But it's a reasonable start on this anyway, */
          /* and the mists of time may well reveal that further enhancements are */
          /* not necessary in practice.                                          */

          if (this_offset < lowest_offset)
          {
            /* First thing, we've found a new lowest offset; so forget any previous */
            /* string length differences.                                           */

            lowest_diff = 0;
          }

          /* If we've not got a lowest difference yet, or we have a current difference */
          /* and it's lower than the recorded lowest, then remember the difference and */
          /* the entry that generated it.                                              */

          if (!lowest_diff || (this_diff && this_diff < lowest_diff))
          {
            lowest_diff  = this_diff;
            lowest_entry = entry;
          }
        }
      }
    }

    /* Try the next item */

    entry = entry->next;
  }

  /* Did we end up finding anything? */

  if (lowest_entry && lowest_offset >= 0)
  {
    /* Yes - copy the full URL into the buffer and return, saying */
    /* we updated the buffer contents.                            */

    strncpy(buffer, lowest_entry->url->full, buffer_size);
    buffer[buffer_size - 1] = 0;

    return 1;
  }

  /* No - exit, saying we didn't touch the buffer contents. */

  return 0;
}