/* Copyright (c) 2000 Shlomi Fish
 *
 * Permission is hereby granted, free of charge, to any person
 * obtaining a copy of this software and associated documentation
 * files (the "Software"), to deal in the Software without
 * restriction, including without limitation the rights to use,
 * copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following
 * conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
 * OTHER DEALINGS IN THE SOFTWARE.
 */
/*
 * check_and_add_state.c - the various possible implementations of the function
 * fc_solve_check_and_add_state().
 *
 */

#ifndef FC_SOLVE__CAAS_C
#define FC_SOLVE__CAAS_C

#define BUILDING_DLL 1

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

#include "check_and_add_state.h"

#include "fcs_dm.h"
#include "instance.h"

#ifdef INDIRECT_STACK_STATES
#include "fcs_hash.h"
#endif

#include "move_stack_compact_alloc.h"
#include "inline.h"

#include "check_limits.h"

typedef  unsigned long  int  ub4;   /* unsigned 4-byte quantities */
typedef  unsigned       char ub1;

static GCC_INLINE ub4 perl_hash_function(
    register ub1 *s_ptr,        /* the key */
    register ub4  length        /* the length of the key */
    )
{
    register ub4  hash_value_int = 0;
    register ub1 * s_end = s_ptr+length;

    while (s_ptr < s_end)
    {
        hash_value_int += (hash_value_int << 5) + *(s_ptr++);
    }
    hash_value_int += (hash_value_int>>5);

    return hash_value_int;
}

#ifdef INDIRECT_STACK_STATES

#define replace_with_cached(condition_expr) \
        if (condition_expr)     \
        {      \
            fcs_compact_alloc_release(stacks_allocator);    \
            new_state_key->stacks[a] = cached_stack;       \
        }

static void GCC_INLINE fc_solve_cache_stacks(
        fc_solve_hard_thread_t * hard_thread,
        fcs_state_t * new_state_key,
        fcs_state_extra_info_t * new_state_val
        )
{
    int a;
#if (FCS_STACK_STORAGE == FCS_STACK_STORAGE_INTERNAL_HASH)
#ifdef FCS_ENABLE_SECONDARY_HASH_VALUE
    SFO_hash_value_t hash_value_int;
#endif
#elif (FCS_STACK_STORAGE == FCS_STACK_STORAGE_JUDY)
    PWord_t * PValue;
#endif
    void * cached_stack;
    char * new_ptr;
    fc_solve_instance_t * instance = hard_thread->instance;
#ifndef HARD_CODED_NUM_STACKS
    int stacks_num = instance->stacks_num;
#endif
    fcs_cards_column_t column;
    register int col_len;
    fcs_compact_allocator_t * stacks_allocator;
    
    stacks_allocator = &(hard_thread->allocator);

    for(a=0 ; a < LOCAL_STACKS_NUM ; a++)
    {
        /*
         * If the stack is not a copy - it is already cached so skip
         * to the next stack
         * */
        if (! (new_state_val->stacks_copy_on_write_flags & (1 << a)))
        {
            continue;
        }

        column = fcs_state_get_col(*new_state_key, a);
        col_len = (fcs_col_len(column)+1);

        new_ptr = (char*)fcs_compact_alloc_ptr(stacks_allocator, col_len);
        memcpy(new_ptr, column, col_len);
        new_state_key->stacks[a] = new_ptr;

#if FCS_STACK_STORAGE == FCS_STACK_STORAGE_INTERNAL_HASH
#ifdef FCS_ENABLE_SECONDARY_HASH_VALUE
        /* Calculate the hash value for the stack */
        /* This hash function was ripped from the Perl source code.
         * (It is not derived work however). */
        {
            const char * s_ptr = (char*)(new_state_key->stacks[a]);
            const char * s_end = s_ptr+fcs_col_len(s_ptr)+1;
            hash_value_int = 0;
            while (s_ptr < s_end)
            {
                hash_value_int += (hash_value_int << 5) + *(s_ptr++);
            }
            hash_value_int += (hash_value_int >> 5);
        }

        if (hash_value_int < 0)
        {
            /*
             * This is a bit mask that nullifies the sign bit of the
             * number so it will always be positive
             * */
            hash_value_int &= (~(1<<((sizeof(hash_value_int)<<3)-1)));
        }
#endif

        {
            void * dummy;
            int verdict;

            column = fcs_state_get_col(*new_state_key, a);

            verdict = fc_solve_hash_insert(
                &(instance->stacks_hash),
                column,
                column,
                &cached_stack,
                &dummy,
                perl_hash_function(
                    (ub1 *)new_state_key->stacks[a],
                    col_len
                    )
#ifdef FCS_ENABLE_SECONDARY_HASH_VALUE
                , hash_value_int
#endif
                );

            replace_with_cached(verdict);
        }

#elif (FCS_STACK_STORAGE == FCS_STACK_STORAGE_LIBAVL2_TREE)

        cached_stack =
            fcs_libavl2_stacks_tree_insert(
                instance->stacks_tree,
                new_state_key->stacks[a]
            );

        replace_with_cached(cached_stack != NULL);

#elif (FCS_STACK_STORAGE == FCS_STACK_STORAGE_LIBREDBLACK_TREE)
        cached_stack = (void *)rbsearch(
            new_state_key->stacks[a],
            instance->stacks_tree
            );

        replace_with_cached(cached_stack != new_state_key->stacks[a]);
#elif (FCS_STACK_STORAGE == FCS_STACK_STORAGE_GLIB_TREE)
        cached_stack = g_tree_lookup(
             instance->stacks_tree,
             (gpointer)new_state_key->stacks[a]
             );

        /* replace_with_cached contains an if statement */
        replace_with_cached(cached_stack != NULL)
        else
        {
            g_tree_insert(
                instance->stacks_tree,
                (gpointer)new_state_key->stacks[a],
                (gpointer)new_state_key->stacks[a]
                );
        }
#elif (FCS_STACK_STORAGE == FCS_STACK_STORAGE_GLIB_HASH)
        cached_stack = g_hash_table_lookup(
            instance->stacks_hash,
            (gconstpointer)new_state_key->stacks[a]
            );
        replace_with_cached(cached_stack != NULL)
        else
        {
            g_hash_table_insert(
                instance->stacks_hash,
                (gpointer)new_state_key->stacks[a],
                (gpointer)new_state_key->stacks[a]
                );
        }
#elif (FCS_STACK_STORAGE == FCS_STACK_STORAGE_JUDY)
        column = fcs_state_get_col(*new_state_key, a);

        JHSI(
            PValue,
            instance->stacks_judy_array,
            column,
            (1+fcs_col_len(column))
        );
        /* later_todo : Handle out-of-memory. */
        if (*PValue == 0)
        {
            /*  A new stack */
            *PValue = (PWord_t)column;
        }
        else
        {
            cached_stack = (void *)(*PValue);
            replace_with_cached(1);
        }
#else
#error FCS_STACK_STORAGE is not set to a good value.
#endif
    }
}

#else /* #ifdef INDIRECT_STACK_STATES */

#define fc_solve_cache_stacks(hard_thread, new_state_key, new_state_val) \
    {}

#endif


#ifdef FCS_WITH_TALONS
static GCC_INLINE void fc_solve_cache_talon(
    fc_solve_instance_t * instance,
    fcs_state_t * new_state_key,
    fcs_state_extra_info_t * new_state_val
    )
{
    void * cached_talon;
    int hash_value_int;

    new_state_key->talon = realloc(new_state_key->talon, fcs_klondike_talon_len(new_state_key)+1);
    hash_value_int = *(SFO_hash_value_t*)instance->hash_value;
    if (hash_value_int < 0)
    {
        /*
         * This is a bit mask that nullifies the sign bit of the
         * number so it will always be positive
         * */
        hash_value_int &= (~(1<<((sizeof(hash_value_int)<<3)-1)));
    }

    cached_talon = (void *)fc_solve_hash_insert(
        instance->talons_hash,
        new_state_key->talon,
        hash_value_int,
        1
        );

    if (cached_talon != NULL)
    {
        free(new_state_key->talon);
        new_state_key->talon = cached_talon;
    }
}
#endif

#if (FCS_STATE_STORAGE == FCS_STATE_STORAGE_GLIB_HASH)
guint fc_solve_hash_function(gconstpointer key)
{
    guint hash_value;
    const char * s_ptr = (char*)key;
    const char * s_end = s_ptr+sizeof(fcs_state_t);
    hash_value = 0;
    while (s_ptr < s_end)
    {
        hash_value += (hash_value << 5) + *(s_ptr++);
    }
    hash_value += (hash_value >> 5);

    return hash_value;
}
#endif


/*
 * check_and_add_state() does the following things:
 *
 * 1. Check if the number of iterations exceeded its maximum, and if so
 *    return FCS_STATE_EXCEEDS_MAX_NUM_TIMES in order to terminate the
 *    solving process.
 * 2. Check if the maximal depth was reached and if so return
 *    FCS_STATE_EXCEEDS_MAX_DEPTH
 * 3. Canonize the state.
 * 4. Check if the state is already found in the collection of the states
 *    that were already checked.
 *    If it is:
 *
 *        5a. Return FCS_STATE_ALREADY_EXISTS
 *
 *    If it isn't:
 *
 *        5b. Add the new state and return FCS_STATE_DOES_NOT_EXIST
 * */

GCC_INLINE int fc_solve_check_and_add_state(
    fc_solve_soft_thread_t * soft_thread,
    fcs_state_extra_info_t * new_state_val,
    fcs_state_extra_info_t * * existing_state_val
    )
{
#if (FCS_STATE_STORAGE == FCS_STATE_STORAGE_INTERNAL_HASH)
#ifdef FCS_ENABLE_SECONDARY_HASH_VALUE
    SFO_hash_value_t hash_value_int;
#endif
#endif
#if (FCS_STATE_STORAGE == FCS_STATE_STORAGE_INDIRECT)
    fcs_standalone_state_ptrs_t * pos_ptr;
    int found;
#endif
    fc_solve_hard_thread_t * hard_thread = soft_thread->hard_thread;
    fc_solve_instance_t * instance = hard_thread->instance;
    fcs_state_t * new_state_key = new_state_val->key;

    int is_state_new;

    if (check_if_limits_exceeded())
    {
        return FCS_STATE_BEGIN_SUSPEND_PROCESS;
    }

    if ((instance->max_depth >= 0) &&
        (new_state_val->depth >= instance->max_depth))
    {
        return FCS_STATE_EXCEEDS_MAX_DEPTH;
    }


    fc_solve_cache_stacks(hard_thread, new_state_key, new_state_val);

    fc_solve_canonize_state(new_state_val,
            INSTANCE_FREECELLS_NUM,
            INSTANCE_STACKS_NUM
            );

/*
    The objective of this part of the code is:
    1. To check if new_state_key / new_state_val is already in the prev_states
       collection.
    2. If not, to add it and to set check to true.
    3. If so, to set check to false.
  */

#if (FCS_STATE_STORAGE == FCS_STATE_STORAGE_INTERNAL_HASH)
#ifdef FCS_ENABLE_SECONDARY_HASH_VALUE
    {
        const char * s_ptr = (char*)new_state_key;
        const char * s_end = s_ptr+sizeof(*new_state_key);
        hash_value_int = 0;
        while (s_ptr < s_end)
        {
            hash_value_int += (hash_value_int << 5) + *(s_ptr++);
        }
        hash_value_int += (hash_value_int>>5);
    }
    if (hash_value_int < 0)
    {
        /*
         * This is a bit mask that nullifies the sign bit of the
         * number so it will always be positive
         * */
        hash_value_int &= (~(1<<((sizeof(hash_value_int)<<3)-1)));
    }
#endif
    {
        void * existing_key_void, * existing_val_void;
    is_state_new = (fc_solve_hash_insert(
        &(instance->hash),
        new_state_key,
        new_state_val,
        &existing_key_void,
        &existing_val_void,
        perl_hash_function(
            (ub1 *)new_state_key,
            sizeof(*new_state_key)
            )
#ifdef FCS_ENABLE_SECONDARY_HASH_VALUE
        , hash_value_int
#endif
        ) == 0);
        if (! is_state_new)
        {
            *existing_state_val = existing_val_void;
        }
    }
#elif (FCS_STATE_STORAGE == FCS_STATE_STORAGE_INDIRECT)
    /* Try to see if the state is found in indirect_prev_states */
    if ((pos_ptr = (fcs_standalone_state_ptrs_t *)bsearch(&new_state_key,
                instance->indirect_prev_states,
                instance->num_indirect_prev_states,
                sizeof(instance->indirect_prev_states[0]),
                fc_solve_state_compare_indirect)) == NULL)
    {
        /* It isn't in prev_states, but maybe it's in the sort margin */
        pos_ptr = (fcs_standalone_state_ptrs_t *)fc_solve_bsearch(
            &new_state_key,
            instance->indirect_prev_states_margin,
            instance->num_prev_states_margin,
            sizeof(instance->indirect_prev_states_margin[0]),
            fc_solve_state_compare_indirect_with_context,
            NULL,
            &found);

        if (found)
        {
            is_state_new = 0;
            *existing_state_val = pos_ptr->val;
        }
        else
        {
            /* Insert the state into its corresponding place in the sort
             * margin */
            memmove((void*)(pos_ptr+1),
                    (void*)pos_ptr,
                    sizeof(*pos_ptr) *
                    (instance->num_prev_states_margin-
                      (pos_ptr-instance->indirect_prev_states_margin)
                    ));
            pos_ptr->key = new_state_key;
            pos_ptr->val = new_state_val;

            instance->num_prev_states_margin++;

            if (instance->num_prev_states_margin >= PREV_STATES_SORT_MARGIN)
            {
                /* The sort margin is full, let's combine it with the main array */

                instance->indirect_prev_states = 
                    realloc(
                        instance->indirect_prev_states,
                        sizeof(instance->indirect_prev_states[0])
                        * (instance->num_indirect_prev_states
                            + instance->num_prev_states_margin
                        )
                    );

                fc_solve_merge_large_and_small_sorted_arrays(
                    instance->indirect_prev_states,
                    instance->num_indirect_prev_states,
                    instance->indirect_prev_states_margin,
                    instance->num_prev_states_margin,
                    sizeof(instance->indirect_prev_states[0]),
                    fc_solve_state_compare_indirect_with_context,
                    NULL
                );

                instance->num_indirect_prev_states += instance->num_prev_states_margin;

                instance->num_prev_states_margin=0;
            }
            is_state_new = 1;
        }

    }
    else
    {
        *existing_state_val = pos_ptr->val;
        is_state_new = 0;
    }

#elif (FCS_STATE_STORAGE == FCS_STATE_STORAGE_LIBREDBLACK_TREE)
    *existing_state_val = (fcs_state_extra_info_t *)rbsearch(new_state_val,
            instance->tree
            );
    is_state_new = ((*existing_state_val) == new_state_val);

#elif (FCS_STATE_STORAGE == FCS_STATE_STORAGE_LIBAVL2_TREE)

    *existing_state_val = (fcs_state_extra_info_t *)
        fcs_libavl2_states_tree_insert(instance->tree, new_state_val);
    is_state_new = ((*existing_state_val) == NULL);

#elif (FCS_STATE_STORAGE == FCS_STATE_STORAGE_GLIB_TREE)
    *existing_state_val = g_tree_lookup(instance->tree, (gpointer)new_state_key);
    if (*existing_state_val == NULL)
    {
        /* The new state was not found. Let's insert it.
         * The value must be the same as the key, so g_tree_lookup()
         * will return it. */
        g_tree_insert(
            instance->tree,
            (gpointer)new_state_key,
            (gpointer)new_state_val
            );
        is_state_new = 1;
    }
    else
    {
        is_state_new = 0;
    }



#elif (FCS_STATE_STORAGE == FCS_STATE_STORAGE_GLIB_HASH)
    *existing_state_val = g_hash_table_lookup(instance->hash, 
            (gpointer)new_state_key);
    if (*existing_state_val == NULL)
    {
        /* The new state was not found. Let's insert it.
         * The value must be the same as the key, so g_tree_lookup()
         * will return it. */
        g_hash_table_insert(
            instance->hash,
            (gpointer)new_state_key,
            (gpointer)new_state_val

            );
        is_state_new = 1;
    }
    else
    {
        is_state_new = 0;
    }

#elif (FCS_STATE_STORAGE == FCS_STATE_STORAGE_DB_FILE)
    {
        DBT key, value;
        key.data = new_state;
        key.size = sizeof(*new_state);
        if (instance->db->get(
            instance->db,
            NULL,
            &key,
            &value,
            0
            ) == 0)
        {
            /* The new state was not found. Let's insert it.
             * The value must be the same as the key, so g_tree_lookup()
             * will return it. */

            value.data = key.data;
            value.size = key.size;
            instance->db->put(
                instance->db,
                NULL,
                &key,
                &value,
                0);
            is_state_new = 1;
        }
        else
        {
            is_state_new = 0;
        }
    }
#elif (FCS_STATE_STORAGE == FCS_STATE_STORAGE_JUDY)
    {
        PWord_t * PValue;

        JHSI(PValue, instance->judy_array, new_state_key, sizeof(*new_state_key));

        /* later_todo : Handle out-of-memory. */
        if (*PValue == 0)
        {
            /* A new state. */
            is_state_new = 1;
            *PValue = (PWord_t)(*existing_state_val = new_state_val);
        }
        else
        {
            /* Already exists. */
            is_state_new = 0;
            *existing_state_val = (fcs_state_extra_info_t *)(*PValue);
        }
    }
#else
#error no define
#endif
    if (is_state_new)
    {
        /* The new state was not found in the cache, and it was already inserted */
        if (new_state_val->parent_val)
        {
            new_state_val->parent_val->num_active_children++;
        }
        instance->num_states_in_collection++;

        if (new_state_val->moves_to_parent != NULL)
        {
            new_state_val->moves_to_parent =
                fc_solve_move_stack_compact_allocate(
                    hard_thread,
                    new_state_val->moves_to_parent
                    );
        }

        return FCS_STATE_DOES_NOT_EXIST;
    }
    else
    {
        return FCS_STATE_ALREADY_EXISTS;
    }
}

#endif /* #ifndef FC_SOLVE__CAAS_C */