/*

 * Copyright (C) 2004 Owen Taylor

 *

 * Authors:

 *   Owen Taylor  <otaylor@redhat.com>

 *

 * Modified by the Glade developers

 * 

 * 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 of the

 * License, 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.

 *

 */

#include "config.h"

#include "glade-id-allocator.h"

#include <glib.h>

#include <string.h>

#define INITIAL_WORDS 4

struct _GladeIDAllocator

{

  guint n_words;

  guint32 *data;

};

/**

 * glade_id_allocator_new:

 *

 * Returns: a new #GladeIDAllocator

 */

GladeIDAllocator *

glade_id_allocator_new (void)

{

  GladeIDAllocator *allocator = g_slice_new (GladeIDAllocator);

  allocator->n_words = INITIAL_WORDS;

  allocator->data    = g_new (guint32, INITIAL_WORDS);

  memset (allocator->data, 0xff, INITIAL_WORDS * sizeof (guint32));

  return allocator;

}

/**

 * glade_id_allocator_destroy:

 * @allocator: a #GladeIDAllocator

 *

 * Frees @allocator and its associated memory

 */

void

glade_id_allocator_destroy (GladeIDAllocator *allocator)

{

  g_return_if_fail (allocator != NULL);

  g_free (allocator->data);

  g_slice_free (GladeIDAllocator, allocator);

}

static inline gint

first_set_bit (guint32 word)

{

  static const char table[16] = {

    4, 0, 1, 0,

    2, 0, 1, 0,

    3, 0, 1, 0,

    2, 0, 1, 0

  };

  gint result = 0;

  if ((word & 0xffff) == 0)

    {

      word >>= 16;

      result += 16;

    }

  if ((word & 0xff) == 0)

    {

      word >>= 8;

      result += 8;

    }

  if ((word & 0xf) == 0)

    {

      word >>= 4;

      result += 4;

    }

  return result + table[word & 0xf];

}

/**

 * glade_id_allocator_alloc:

 * @allocator: a #GladeIDAllocator

 *

 * TODO: write me

 * Returns:

 */

guint

glade_id_allocator_allocate (GladeIDAllocator *allocator)

{

  guint i;

  g_return_val_if_fail (allocator != NULL, 0);

  for (i = 0; i < allocator->n_words; i++)

    {

      if (allocator->data[i] != 0)

        {

          gint free_bit = first_set_bit (allocator->data[i]);

          allocator->data[i] &= ~(1 << free_bit);

          return 32 * i + free_bit + 1;

        }

    }

  {

    guint n_words = allocator->n_words;

    allocator->data = g_renew (guint32, allocator->data, n_words * 2);

    memset (&allocator->data[n_words], 0xff, n_words * sizeof (guint32));

    allocator->n_words = n_words * 2;

    allocator->data[n_words] = 0xffffffff - 1;

    return 32 * n_words + 1;

  }

}

/**

 * glade_id_allocator_release:

 * @allocator:

 * @id:

 *

 * TODO: write me

 */

void

glade_id_allocator_release (GladeIDAllocator *allocator, guint id)

{

  guint word_idx;

  g_return_if_fail (allocator != NULL);

  /* Allocated ids start with 1 */

  if (id > 0)

    {

      id = id - 1;

      word_idx = id >> 5;

      /* Tollerate releasing ids that were never allocated with the allocator 

       * or are out of range... when we load Glade files with huge numbers it happens

       * that loaded unallocated ids are out of range

       */

      if (word_idx < allocator->n_words)

	allocator->data[word_idx] |= 1 << (id & 31);

    }

}

#ifdef GLADE_ID_ALLOCATOR_TEST

int

main (int argc, char **argv)

{

  GladeIDAllocator *allocator = glade_id_allocator_new ();

  guint i;

  guint iter;

  for (i = 0; i < 1000; i++)

    {

      guint id = glade_id_allocator_allocate (allocator);

      g_assert (id == i);

    }

  for (i = 0; i < 1000; i++)

    glade_id_allocator_release (allocator, i);

  for (iter = 0; iter < 10000; iter++)

    {

      for (i = 0; i < 1000; i++)

        glade_id_allocator_alloc (allocator);

      for (i = 0; i < 1000; i++)

        glade_id_allocator_release (allocator, i);

    }

  glade_id_allocator_destroy (allocator);

  return 0;

}

#endif