/*

 * Copyright © 2000 Keith Packard

 *

 * Permission to use, copy, modify, distribute, and sell this software and its

 * documentation for any purpose is hereby granted without fee, provided that

 * the above copyright notice appear in all copies and that both that

 * copyright notice and this permission notice appear in supporting

 * documentation, and that the name of the author(s) not be used in

 * advertising or publicity pertaining to distribution of the software without

 * specific, written prior permission.  The authors make no

 * representations about the suitability of this software for any purpose.  It

 * is provided "as is" without express or implied warranty.

 *

 * THE AUTHOR(S) DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,

 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO

 * EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY SPECIAL, INDIRECT OR

 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,

 * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER

 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR

 * PERFORMANCE OF THIS SOFTWARE.

 */

#include "fcint.h"

#define FC_HASH_SIZE 227

typedef struct _FcHashBucket {

    struct _FcHashBucket *next;

    void                 *key;

    void                 *value;

} FcHashBucket;

struct _FcHashTable {

    FcHashBucket *buckets[FC_HASH_SIZE];

    FcHashFunc    hash_func;

    FcCompareFunc compare_func;

    FcCopyFunc    key_copy_func;

    FcCopyFunc    value_copy_func;

    FcDestroyFunc key_destroy_func;

    FcDestroyFunc value_destroy_func;

};

FcBool

FcHashStrCopy (const void *src,

               void      **dest)

{

    *dest = FcStrdup (src);

    return *dest != NULL;

}

FcHashTable *

FcHashTableCreate (FcHashFunc    hash_func,

                   FcCompareFunc compare_func,

                   FcCopyFunc    key_copy_func,

                   FcCopyFunc    value_copy_func,

                   FcDestroyFunc key_destroy_func,

                   FcDestroyFunc value_destroy_func)

{

    FcHashTable *ret = malloc (sizeof (FcHashTable));

    if (ret) {

  memset (ret->buckets, 0, sizeof (FcHashBucket *) * FC_HASH_SIZE);

  ret->hash_func = hash_func;

  ret->compare_func = compare_func;

  ret->key_copy_func = key_copy_func;

  ret->value_copy_func = value_copy_func;

  ret->key_destroy_func = key_destroy_func;

  ret->value_destroy_func = value_destroy_func;

    }

    return ret;

}

void

FcHashTableDestroy (FcHashTable *table)

{

    int i;

    for (i = 0; i < FC_HASH_SIZE; i++) {

  FcHashBucket *bucket = table->buckets[i], *prev;

  while (bucket) {

      if (table->key_destroy_func)

    table->key_destroy_func (bucket->key);

      if (table->value_destroy_func)

    table->value_destroy_func (bucket->value);

      prev = bucket;

      bucket = bucket->next;

      free (prev);

  }

  table->buckets[i] = NULL;

    }

    free (table);

}

FcBool

FcHashTableFind (FcHashTable *table,

                 const void  *key,

                 void       **value)

{

    FcHashBucket *bucket;

    FcChar32      hash = table->hash_func (key);

    for (bucket = table->buckets[hash % FC_HASH_SIZE]; bucket; bucket = bucket->next) {

  if (!table->compare_func (bucket->key, key)) {

      if (table->value_copy_func) {

    if (!table->value_copy_func (bucket->value, value))

        return FcFalse;

      } else

    *value = bucket->value;

      return FcTrue;

  }

    }

    return FcFalse;

}

static FcBool

FcHashTableAddInternal (FcHashTable *table,

                        void        *key,

                        void        *value,

                        FcBool       replace)

{

    FcHashBucket **prev, *bucket, *b;

    FcChar32       hash = table->hash_func (key);

    FcBool         ret = FcFalse;

    bucket = (FcHashBucket *)malloc (sizeof (FcHashBucket));

    if (!bucket)

  return FcFalse;

    memset (bucket, 0, sizeof (FcHashBucket));

    if (table->key_copy_func)

  ret |= !table->key_copy_func (key, &bucket->key);

    else

  bucket->key = key;

    if (table->value_copy_func)

  ret |= !table->value_copy_func (value, &bucket->value);

    else

  bucket->value = value;

    if (ret) {

    destroy:

  if (bucket->key && table->key_destroy_func)

      table->key_destroy_func (bucket->key);

  if (bucket->value && table->value_destroy_func)

      table->value_destroy_func (bucket->value);

  free (bucket);

  return !ret;

    }

retry:

    for (prev = &table->buckets[hash % FC_HASH_SIZE];

         (b = fc_atomic_ptr_get (prev)); prev = &(b->next)) {

  if (!table->compare_func (b->key, key)) {

      if (replace) {

    bucket->next = b->next;

    if (!fc_atomic_ptr_cmpexch (prev, b, bucket))

        goto retry;

    bucket = b;

      } else

    ret = FcTrue;

      goto destroy;

  }

    }

    bucket->next = NULL;

    if (!fc_atomic_ptr_cmpexch (prev, b, bucket))

  goto retry;

    return FcTrue;

}

FcBool

FcHashTableAdd (FcHashTable *table,

                void        *key,

                void        *value)

{

    return FcHashTableAddInternal (table, key, value, FcFalse);

}

FcBool

FcHashTableReplace (FcHashTable *table,

                    void        *key,

                    void        *value)

{

    return FcHashTableAddInternal (table, key, value, FcTrue);

}

FcBool

FcHashTableRemove (FcHashTable *table,

                   void        *key)

{

    FcHashBucket **prev, *bucket;

    FcChar32       hash = table->hash_func (key);

    FcBool         ret = FcFalse;

retry:

    for (prev = &table->buckets[hash % FC_HASH_SIZE];

         (bucket = fc_atomic_ptr_get (prev)); prev = &(bucket->next)) {

  if (!table->compare_func (bucket->key, key)) {

      if (!fc_atomic_ptr_cmpexch (prev, bucket, bucket->next))

    goto retry;

      if (table->key_destroy_func)

    table->key_destroy_func (bucket->key);

      if (table->value_destroy_func)

    table->value_destroy_func (bucket->value);

      free (bucket);

      ret = FcTrue;

      break;

  }

    }

    return ret;

}