--- a/telepathygabble/src/gintset.c Tue Feb 02 01:10:06 2010 +0200
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,450 +0,0 @@
-/* gintset.c - Source for a Glib-link set of integers
- * Copyright (C) 2006 Collabora Ltd.
- *
- * This library is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public License
- * as published by the Free Software Foundation; either version 2.1 of
- * the License, or (at your option) any later version.
- *
- * This library 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
- * Lesser General Public License for more details.
- *
- * You should have received a copy of the GNU Lesser General Public
- * License along with this library; if not, write to the Free Software
- * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
- * 02110-1301 USA
- *
- */
-
-#include <string.h>
-#include <glib.h>
-#include "gintset.h"
-
-#define DEFAULT_SIZE 16
-#define DEFAULT_INCREMENT 8
-#define DEFAULT_INCREMENT_LOG2 3
-
-struct _GIntSet
-{
- guint32 *bits;
- guint size;
-};
-
-static GIntSet *
-_g_intset_new_with_size (guint size)
-{
- GIntSet *set = g_new (GIntSet, 1);
- set->size = MAX (size, DEFAULT_SIZE);
- set->bits = g_new0 (guint32, set->size);
- return set;
-}
-
-
-GIntSet *
-g_intset_new ()
-{
- return _g_intset_new_with_size (DEFAULT_SIZE);
-}
-
-/**
- * g_intset_destroy:
- * @set: set
- *
- * delete the set
- */
-
-void
-g_intset_destroy (GIntSet *set)
-{
- g_return_if_fail (set != NULL);
-
- g_free (set->bits);
- g_free (set);
-}
-
-/**
- * g_intset_clear:
- * @set : set
- *
- * Unset every integer in the set.
- */
-void
-g_intset_clear (GIntSet *set)
-{
- g_return_if_fail (set != NULL);
-
- memset (set->bits, 0, set->size * sizeof (guint32));
-}
-
-/**
- * g_intset_add:
- * @set: set
- * @element: integer to add
- *
- * Add an integer into a GIntSet
- */
-
-void
-g_intset_add (GIntSet *set, guint element)
-{
- guint offset;
- guint newsize;
-
- g_return_if_fail (set != NULL);
-
- offset = element >> 5;
-
- if (offset >= set->size)
- {
- newsize = ((offset>>DEFAULT_INCREMENT_LOG2) +1 ) << DEFAULT_INCREMENT_LOG2;
- set->bits = g_renew(guint32, set->bits, newsize);
- memset (set->bits + set->size, 0, sizeof(guint32) * (newsize - set->size));
- set->size = newsize;
- g_assert(offset<newsize);
- }
- set->bits[offset] = set->bits[offset] | (1<<(element & 0x1f));
-}
-
-/**
- * g_intset_remove:
- * @set: set
- * @element: integer to add
- *
- * Remove an integer from a GIntSet
- * Returns: TRUE if element was in set
- */
-
-gboolean
-g_intset_remove (GIntSet *set, guint element)
-{
- guint offset;
- guint mask;
-
- g_return_val_if_fail (set != NULL, FALSE);
-
- offset = element >> 5;
- mask = 1 << (element & 0x1f);
- if (offset >= set->size)
- return FALSE;
- else if (!(set->bits[offset] & mask))
- return FALSE;
- else
- {
- set->bits[offset] &= ~mask;
- return TRUE;
- }
-}
-
-/**
- * g_intset_is_member:
- * @set: set
- * @element: integer to test
- *
- * Tests if @element is a member of @set
- * Returns: TRUE if element was in set
- */
-
-gboolean
-g_intset_is_member (const GIntSet *set, guint element)
-{
- guint offset;
-
- g_return_val_if_fail (set != NULL, FALSE);
-
- offset = element >> 5;
- if (offset >= set->size)
- return FALSE;
- else
- return (set->bits[offset] & (1 << (element & 0x1f)));
-}
-
-/**
- * g_intset_foreach:
- * @set: set
- * @func: @GIntFunc to use to iterate the set
- * @userdata: user data to pass to each call of @func
- *
- * Iterates every member of the set calling @func
- */
-
-void
-g_intset_foreach (const GIntSet *set, GIntFunc func, gpointer userdata)
-{
- guint i, j;
-
- g_return_if_fail (set != NULL);
- g_return_if_fail (func != NULL);
-
- for (i = 0; i < set->size; i++)
- {
- if (set->bits[i])
- for (j = 0; j < 32; j++)
- {
- if (set->bits[i] & 1 << j)
- func (i * 32 + j, userdata);
- }
- }
-}
-
-
-static void
-addint (guint32 i, gpointer data)
-{
- GArray *array = (GArray *) data;
- g_array_append_val (array, i);
-}
-
-/**
- * g_intset_to_array:
- * @set: set to convert
- * Convert a gintset to an array, allocates the array for you, hence you
- * must free it after use.
- */
-
-GArray *
-g_intset_to_array (GIntSet *set)
-{
- GArray *array;
-
- g_return_val_if_fail (set != NULL, NULL);
-
- array = g_array_new (FALSE, TRUE, sizeof (guint32));
-
- g_intset_foreach (set, addint, array);
-
- return array;
-}
-
-
-GIntSet *
-g_intset_from_array (GArray *array)
-{
- GIntSet *set;
- guint32 max, i;
-
- g_return_val_if_fail (array != NULL, NULL);
-
- /* look at the 1st, last and middle values in the array to get an
- * approximation of the largest */
- max = 0;
- if (array->len > 0)
- max = g_array_index (array, guint32, 0);
- if (array->len > 1)
- max = MAX (max, g_array_index (array, guint32, array->len - 1));
- if (array->len > 2)
- max = MAX (max, g_array_index (array, guint32, (array->len - 1) >> 1));
- set = _g_intset_new_with_size (1 + (max >> 5));
-
- for (i = 0; i < array->len; i++)
- {
- g_intset_add (set, g_array_index (array, guint32, i));
- }
-
- return set;
-}
-
-
-guint
-g_intset_size (const GIntSet *set)
-{
- guint i, count = 0;
- guint32 n;
-
- g_return_val_if_fail (set != NULL, 0);
-
- for (i = 0; i < set->size; i++)
- {
- n = set->bits[i];
- n = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
- count += ((n + (n >> 3)) & 030707070707) % 63;
- }
-
- return count;
-}
-
-
-gboolean
-g_intset_is_equal (const GIntSet *left, const GIntSet *right)
-{
- const GIntSet *large, *small;
- guint i;
-
- g_return_val_if_fail (left != NULL, FALSE);
- g_return_val_if_fail (right != NULL, FALSE);
-
- if (left->size > right->size)
- {
- large = left;
- small = right;
- }
- else
- {
- large = right;
- small = left;
- }
-
- for (i = 0; i < small->size; i++)
- {
- if (large->bits[i] != small->bits[i])
- return FALSE;
- }
-
- for (i = small->size; i < large->size; i++)
- {
- if (large->bits[i] != 0)
- return FALSE;
- }
-
- return TRUE;
-}
-
-GIntSet *
-g_intset_copy (const GIntSet *orig)
-{
- GIntSet *ret;
-
- g_return_val_if_fail (orig != NULL, NULL);
-
- ret = _g_intset_new_with_size (orig->size);
- memcpy (ret->bits, orig->bits, (ret->size * sizeof (guint32)));
-
- return ret;
-}
-
-
-GIntSet *
-g_intset_intersection (const GIntSet *left, const GIntSet *right)
-{
- const GIntSet *large, *small;
- GIntSet *ret;
- guint i;
-
- g_return_val_if_fail (left != NULL, NULL);
- g_return_val_if_fail (right != NULL, NULL);
-
- if (left->size > right->size)
- {
- large = left;
- small = right;
- }
- else
- {
- large = right;
- small = left;
- }
-
- ret = g_intset_copy (small);
-
- for (i = 0; i < ret->size; i++)
- {
- ret->bits[i] &= large->bits[i];
- }
-
- return ret;
-}
-
-
-GIntSet *
-g_intset_union (const GIntSet *left, const GIntSet *right)
-{
- const GIntSet *large, *small;
- GIntSet *ret;
- guint i;
-
- g_return_val_if_fail (left != NULL, NULL);
- g_return_val_if_fail (right != NULL, NULL);
-
- if (left->size > right->size)
- {
- large = left;
- small = right;
- }
- else
- {
- large = right;
- small = left;
- }
-
- ret = g_intset_copy (large);
-
- for (i = 0; i < small->size; i++)
- {
- ret->bits[i] |= small->bits[i];
- }
-
- return ret;
-}
-
-
-GIntSet *
-g_intset_difference (const GIntSet *left, const GIntSet *right)
-{
- GIntSet *ret;
- guint i;
-
- g_return_val_if_fail (left != NULL, NULL);
- g_return_val_if_fail (right != NULL, NULL);
-
- ret = g_intset_copy (left);
-
- for (i = 0; i < MIN (right->size, left->size); i++)
- {
- ret->bits[i] &= ~right->bits[i];
- }
-
- return ret;
-}
-
-
-GIntSet *
-g_intset_symmetric_difference (const GIntSet *left, const GIntSet *right)
-{
- const GIntSet *large, *small;
- GIntSet *ret;
- guint i;
-
- g_return_val_if_fail (left != NULL, NULL);
- g_return_val_if_fail (right != NULL, NULL);
-
- if (left->size > right->size)
- {
- large = left;
- small = right;
- }
- else
- {
- large = right;
- small = left;
- }
-
- ret = g_intset_copy (large);
-
- for (i = 0; i < small->size; i++)
- {
- ret->bits[i] ^= small->bits[i];
- }
-
- return ret;
-}
-
-static void
-_dump_foreach (guint i, gpointer data)
-{
- GString *tmp = (GString *) data;
-
- if (tmp->len == 0)
- g_string_append_printf (tmp, "%d", i);
- else
- g_string_append_printf (tmp, " %d", i);
-}
-
-gchar *
-g_intset_dump (const GIntSet *set)
-{
- GString *tmp = g_string_new ("");
-
- g_intset_foreach (set, _dump_foreach, tmp);
- return g_string_free (tmp, FALSE);
-}