Logo Search packages:      
Sourcecode: galeon version File versions

galeon-autocompletion.c

/*
 *  Copyright (C) 2002  Ricardo Fernández Pascual
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2, or (at your option)
 *  any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include "galeon-autocompletion.h"
#include "galeon-marshal.h"
#include "galeon-debug.h"
#include <string.h>
#include <stdlib.h>

/**
 * Private data
 */

typedef enum {
      GAS_NEEDS_REFINE,
      GAS_NEEDS_FULL_UPDATE,
      GAS_UPDATED
} GaleonAutocompletionStatus;

typedef struct {
      GaleonAutocompletionMatch *array;
      guint num_matches;
      guint array_size;
} ACMatchArray;

#define ACMA_BASE_SIZE 10240

#define GALEON_AUTOCOMPLETION_GET_PRIVATE(object) (G_TYPE_INSTANCE_GET_PRIVATE ((object), \
                               GALEON_TYPE_AUTOCOMPLETION, GaleonAutocompletionPrivate))


struct _GaleonAutocompletionPrivate {
      GSList *sources;
      
      guint nkeys;
      gchar **keys;
      guint *key_lengths;
      gchar **prefixes;
      guint *prefix_lengths;

      gchar *common_prefix;
      ACMatchArray matches;
      GaleonAutocompletionStatus status;
      gboolean sorted;

      gboolean sort_alpha;
};

/**
 * Private functions, only availble from this file
 */
static void       galeon_autocompletion_finalize_impl       (GObject *o);
static void       galeon_autocompletion_reset               (GaleonAutocompletion *ac);
static void       galeon_autocompletion_update_matches            (GaleonAutocompletion *ac);
static void       galeon_autocompletion_update_matches_full (GaleonAutocompletion *ac);
static void       galeon_autocompletion_refine_matches            (GaleonAutocompletion *ac);
static void       galeon_autocompletion_sort_by_score       (GaleonAutocompletion *ac);
static void             galeon_autocompletion_data_changed_cb           (GaleonAutocompletionSource *s, 
                                                       GaleonAutocompletion *ac);

static void       acma_init                           (ACMatchArray *a);
static void       acma_destroy                              (ACMatchArray *a);
static inline void      acma_append                         (ACMatchArray *a, 
                                                       GaleonAutocompletionMatch *m);
static void       acma_grow                           (ACMatchArray *a);



/**
 * Signals enums and ids
 */
enum GaleonAutocompletionSignalsEnum {
      GALEON_AUTOCOMPLETION_SOURCES_CHANGED,
      GALEON_AUTOCOMPLETION_LAST_SIGNAL
};
static gint GaleonAutocompletionSignals[GALEON_AUTOCOMPLETION_LAST_SIGNAL];

/**
 * Autocompletion object
 */

G_DEFINE_TYPE (GaleonAutocompletion, galeon_autocompletion, G_TYPE_OBJECT);

static void
galeon_autocompletion_class_init (GaleonAutocompletionClass *klass)
{
      G_OBJECT_CLASS (klass)->finalize = galeon_autocompletion_finalize_impl;

      GaleonAutocompletionSignals[GALEON_AUTOCOMPLETION_SOURCES_CHANGED] = g_signal_new (
            "sources-changed", G_OBJECT_CLASS_TYPE (klass),  
            G_SIGNAL_RUN_FIRST | G_SIGNAL_RUN_LAST | G_SIGNAL_RUN_CLEANUP,
                G_STRUCT_OFFSET (GaleonAutocompletionClass, sources_changed), 
            NULL, NULL, 
            galeon_marshal_VOID__VOID,
            G_TYPE_NONE, 0);

      g_type_class_add_private (klass, sizeof (GaleonAutocompletionPrivate));
}

static void 
galeon_autocompletion_init (GaleonAutocompletion *ac)
{
      GaleonAutocompletionPrivate *p = GALEON_AUTOCOMPLETION_GET_PRIVATE (ac);
      ac->priv = p;
      p->sources = NULL;
      p->common_prefix = NULL;
      acma_init (&p->matches);
      p->status = GAS_NEEDS_FULL_UPDATE;
      
      p->nkeys = 1;

      p->keys = g_new0 (gchar *, 2);
      p->keys[0] = g_strdup ("");
      p->key_lengths = g_new0 (guint, 2);
      p->key_lengths[0] = 0;

      p->prefixes = g_new0 (gchar *, 2);
      p->prefixes[0] = g_strdup ("");
      p->prefix_lengths = g_new0 (guint, 2);
      p->prefix_lengths[0] = 0;
            
      p->sort_alpha = TRUE;
}

static void
galeon_autocompletion_finalize_impl (GObject *o)
{
      GaleonAutocompletion *ac = GALEON_AUTOCOMPLETION (o);
      GaleonAutocompletionPrivate *p = ac->priv;
      GSList *li;

      galeon_autocompletion_reset (ac);

      for (li = p->sources; li; li = li->next)
      {
            g_signal_handlers_disconnect_by_func (li->data, 
                                          galeon_autocompletion_data_changed_cb, ac);
            g_object_unref (li->data);
      }

      g_slist_free (p->sources);

      g_strfreev (p->keys);
      g_free (p->key_lengths);
      g_strfreev (p->prefixes);
      g_free (p->prefix_lengths);

      G_OBJECT_CLASS (galeon_autocompletion_parent_class)->finalize (o);

}

static void
galeon_autocompletion_reset (GaleonAutocompletion *ac)
{
      GaleonAutocompletionPrivate *p = ac->priv;

      START_PROFILER ("Resetting");

      acma_destroy (&p->matches);
      g_free (p->common_prefix);
      p->common_prefix = NULL;
      p->status = GAS_NEEDS_FULL_UPDATE;

      STOP_PROFILER ("Resetting");
}

GaleonAutocompletion *
galeon_autocompletion_new (void)
{
      GaleonAutocompletion *ret = g_object_new (GALEON_TYPE_AUTOCOMPLETION, NULL);
      return ret;
}
void
galeon_autocompletion_add_source (GaleonAutocompletion *ac,
                          GaleonAutocompletionSource *s)
{
      GaleonAutocompletionPrivate *p = ac->priv;
      g_object_ref (G_OBJECT (s));
      p->sources = g_slist_prepend (p->sources, s);
      galeon_autocompletion_reset (ac);
      g_signal_connect (s, "data-changed", G_CALLBACK (galeon_autocompletion_data_changed_cb), ac);

      g_signal_emit (ac, GaleonAutocompletionSignals[GALEON_AUTOCOMPLETION_SOURCES_CHANGED], 0);
}

void
galeon_autocompletion_set_key (GaleonAutocompletion *ac, 
                         const gchar *key)
{
      GaleonAutocompletionPrivate *p = ac->priv;
      guint i;
      guint keylen = strlen (key);

      if (strcmp (key, p->keys[0]))
      {
            GSList *li;
            for (li = p->sources; li; li = li->next)
            {
                  galeon_autocompletion_source_set_basic_key
                        (GALEON_AUTOCOMPLETION_SOURCE (li->data), key);
            }
      }

      if (keylen >= p->key_lengths[0]
          && !strncmp (p->keys[0], key, p->key_lengths[0]))
      {
            if (!strcmp (key, p->keys[0]))
            {
                  return;
            }
            if (p->status != GAS_NEEDS_FULL_UPDATE)
            {
                  p->status = GAS_NEEDS_REFINE;
            }
            if (p->common_prefix)
            {
                  if (strncmp (p->common_prefix, key, keylen))
                  {
                        g_free (p->common_prefix);
                        p->common_prefix = NULL;
                  }
            }
      }
      else
      {
            p->status = GAS_NEEDS_FULL_UPDATE;
            g_free (p->common_prefix);
            p->common_prefix = NULL;
      }

      for (i = 0; p->prefixes[i]; ++i)
      {
            g_free (p->keys[i]);
            p->keys[i] = g_strconcat (p->prefixes[i], key, NULL);
            p->key_lengths[i] = keylen + p->prefix_lengths[i];
      }

}

gchar *
galeon_autocompletion_get_common_prefix   (GaleonAutocompletion *ac)
{
      GaleonAutocompletionPrivate *p = ac->priv;
      galeon_autocompletion_update_matches (ac);
      if (!p->common_prefix)
      {
            guint common_length = 0;
            guint i;

            START_PROFILER ("Calculate common prefix");

            for (i = 0; i < p->matches.num_matches; i++)
            {
                  GaleonAutocompletionMatch *mi = &p->matches.array[i];
                  const gchar *realmatch = mi->match + mi->offset;
                  if (!p->common_prefix)
                  {
                        p->common_prefix = g_strdup (realmatch);
                        common_length = strlen (p->common_prefix);
                        continue;
                  }
                  else if (!strncmp (realmatch, p->common_prefix, common_length))
                  {
                        continue;
                  }
                  else
                  {
                        common_length = 0;
                        while (realmatch[common_length] 
                               && realmatch[common_length] == p->common_prefix[common_length])
                        {
                              ++common_length;
                        }
                        g_free (p->common_prefix);
                        p->common_prefix = g_strndup (realmatch, common_length);
                  }
            }

            STOP_PROFILER ("Calculate common prefix");
      }
      return g_strdup (p->common_prefix);
}

const GaleonAutocompletionMatch *
galeon_autocompletion_get_matches (GaleonAutocompletion *ac)
{
      galeon_autocompletion_update_matches (ac);
      return ac->priv->matches.array;
}

const GaleonAutocompletionMatch *
galeon_autocompletion_get_matches_sorted_by_score (GaleonAutocompletion *ac)
{
      galeon_autocompletion_sort_by_score (ac);
      return ac->priv->matches.array;
}

guint
galeon_autocompletion_get_num_matches (GaleonAutocompletion *ac)
{
      galeon_autocompletion_update_matches (ac);
      return ac->priv->matches.num_matches;
}

static void
galeon_autocompletion_update_matches (GaleonAutocompletion *ac)
{
      GaleonAutocompletionPrivate *p = ac->priv;
      if (p->status == GAS_UPDATED)
      {
            return;
      }
      if (p->status == GAS_NEEDS_FULL_UPDATE)
      {
            galeon_autocompletion_update_matches_full (ac);
      }
      if (p->status == GAS_NEEDS_REFINE)
      {
            galeon_autocompletion_refine_matches (ac);
      }

      g_free (p->common_prefix);
      p->common_prefix = NULL;
      p->status = GAS_UPDATED;
}

static void
galeon_autocompletion_update_matches_full_item (GaleonAutocompletionSource *source, 
                                    gchar *item, gchar *title, guint32 score,
                                    GaleonAutocompletionPrivate *p)
{
      guint i;
      for (i = 0; p->keys[i]; ++i)
      {
            if (!strncmp (item, p->keys[i], p->key_lengths[i]))
            {
                  GaleonAutocompletionMatch m;
                  m.match = item;
                  m.title = title;
                  m.offset = p->prefix_lengths[i];
                  m.score = score;
                  acma_append (&p->matches, &m);
            }
      }
}

static void
galeon_autocompletion_update_matches_full (GaleonAutocompletion *ac)
{
      GaleonAutocompletionPrivate *p = ac->priv;
      GSList *li;

      LOG ("AC: fully updating");
      galeon_autocompletion_reset (ac);

      START_PROFILER ("Fully updating");

      for (li = p->sources; li; li = li->next)
      {
            GaleonAutocompletionSource *s = GALEON_AUTOCOMPLETION_SOURCE (li->data);
            g_assert (s);
            galeon_autocompletion_source_foreach (s, p->keys[0],
                                          (GaleonAutocompletionSourceForeachFunc)
                                          galeon_autocompletion_update_matches_full_item, 
                                          p);
      }

      STOP_PROFILER ("Fully updating");

      p->sorted = FALSE;

      LOG ("AC: %d matches, fully updated", p->matches.num_matches);
}

static gint
galeon_autocompletion_compare_scores (GaleonAutocompletionMatch *a, GaleonAutocompletionMatch *b)
{
      /* higher scores first */
      return b->score - a->score;
}

static gint
galeon_autocompletion_compare_scores_and_alpha (GaleonAutocompletionMatch *a, GaleonAutocompletionMatch *b)
{
      if (a->score == b->score)
      {
            return strcmp (a->match, b->match);
      }
      else
      {
            /* higher scores first */
            return b->score - a->score;
      }
}

static void
galeon_autocompletion_sort_by_score (GaleonAutocompletion *ac)
{
      GaleonAutocompletionPrivate *p = ac->priv;

      gint (*comparer) (GaleonAutocompletionMatch *m1, GaleonAutocompletionMatch *m2);

      if (p->sort_alpha)
      {
            comparer = galeon_autocompletion_compare_scores_and_alpha;
      }
      else
      {
            comparer = galeon_autocompletion_compare_scores;
      }

      galeon_autocompletion_update_matches (ac);
      if (p->sorted == TRUE) return;

      LOG ("AC: sorting");

      START_PROFILER ("Sorting by score");

      if (p->matches.num_matches > 0)
      {
            qsort (p->matches.array, p->matches.num_matches, 
                   sizeof (GaleonAutocompletionMatch), 
                   (void *) comparer);
      }

      p->sorted = TRUE;

      STOP_PROFILER ("Sorting by score");
}

static void
galeon_autocompletion_refine_matches (GaleonAutocompletion *ac)
{
      GaleonAutocompletionPrivate *p = ac->priv;
      ACMatchArray oldmatches = p->matches;
      ACMatchArray newmatches;
      guint i;
      gchar *key0 = p->keys[0];
      guint key0l = p->key_lengths[0];

      LOG ("AC: refining");

      START_PROFILER ("Refining");
      acma_init (&newmatches);

      for (i = 0; i < oldmatches.num_matches; i++)
      {
            GaleonAutocompletionMatch *mi = &oldmatches.array[i];
            if (!strncmp (key0, mi->match + mi->offset, key0l))
            {
                  acma_append (&newmatches, mi);
            }
      }

      acma_destroy (&oldmatches);
      p->matches = newmatches;
      
      STOP_PROFILER ("Refining");
      LOG ("AC: %d matches", p->matches.num_matches);
}

static void
galeon_autocompletion_data_changed_cb (GaleonAutocompletionSource *s, 
                               GaleonAutocompletion *ac)
{
      LOG ("AC: data changed, reseting");
      galeon_autocompletion_reset (ac);

      g_signal_emit (ac, GaleonAutocompletionSignals[GALEON_AUTOCOMPLETION_SOURCES_CHANGED], 0);
}

void
galeon_autocompletion_set_prefixes (GaleonAutocompletion *ac,
                            const gchar **prefixes)
{
      GaleonAutocompletionPrivate *p = ac->priv;
      guint nprefixes = 0;
      gchar *oldkey = g_strdup (p->keys[0]);
      guint i;

      /* count prefixes */
      while (prefixes[nprefixes])
      {
            ++nprefixes;
      }

      nprefixes--;
      
      g_strfreev (p->keys);
      g_free (p->key_lengths);
      g_strfreev (p->prefixes);
      g_free (p->prefix_lengths);
      
      p->prefixes = g_new0 (gchar *, nprefixes + 2);
      p->prefix_lengths = g_new0 (guint, nprefixes + 2);
      p->keys = g_new0 (gchar *, nprefixes + 2);
      p->key_lengths = g_new0 (guint, nprefixes + 2);

      p->prefixes[0] = g_strdup ("");
      p->prefix_lengths[0] = 0;
      p->keys[0] = oldkey;
      p->key_lengths[0] = strlen (p->keys[0]);

      for (i = 0; i < nprefixes; ++i)
      {
            p->prefixes[i + 1] = g_strdup (prefixes[i]);
            p->prefix_lengths[i + 1] = strlen (prefixes[i]);
            p->keys[i + 1] = g_strconcat (p->prefixes[i + 1], p->keys[0], NULL);
            p->key_lengths[i + 1] = p->prefix_lengths[i + 1] + p->key_lengths[0];
      }

      p->nkeys = nprefixes;
}


/* ACMatchArray */

static void
acma_init (ACMatchArray *a)
{
      a->array = NULL;
      a->array_size = 0;
      a->num_matches = 0;
}

/**
 * Does not free the struct itself, only its contents
 */
static void
acma_destroy (ACMatchArray *a)
{
      g_free (a->array);
      a->array = NULL;
      a->array_size = 0;
      a->num_matches = 0;
}

static inline void
acma_append (ACMatchArray *a, 
           GaleonAutocompletionMatch *m)
{
      if (a->array_size == a->num_matches)
      {
            acma_grow (a);
      }

      a->array[a->num_matches] = *m;
      a->num_matches++;
}

static void
acma_grow (ACMatchArray *a)
{
      gint new_size;
      GaleonAutocompletionMatch *new_array;

      new_size = a->array_size + ACMA_BASE_SIZE;
      new_array = g_renew (GaleonAutocompletionMatch, a->array, new_size);

      a->array_size = new_size;
      a->array = new_array;
}



Generated by  Doxygen 1.6.0   Back to index