/*

 * Copyright (C) 2010, Google Inc.

 * and other copyright owners as documented in JGit's IP log.

 *

 * This program and the accompanying materials are made available

 * under the terms of the Eclipse Distribution License v1.0 which

 * accompanies this distribution, is reproduced below, and is

 * available at http://www.eclipse.org/org/documents/edl-v10.php

 *

 * All rights reserved.

 *

 * Redistribution and use in source and binary forms, with or

 * without modification, are permitted provided that the following

 * conditions are met:

 *

 * - Redistributions of source code must retain the above copyright

 *   notice, this list of conditions and the following disclaimer.

 *

 * - Redistributions in binary form must reproduce the above

 *   copyright notice, this list of conditions and the following

 *   disclaimer in the documentation and/or other materials provided

 *   with the distribution.

 *

 * - Neither the name of the Eclipse Foundation, Inc. nor the

 *   names of its contributors may be used to endorse or promote

 *   products derived from this software without specific prior

 *   written permission.

 *

 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND

 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,

 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES

 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR

 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT

 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;

 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER

 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,

 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)

 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF

 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

 */

#include "xinclude.h"

#define MAX_PTR UINT_MAX

#define MAX_CNT UINT_MAX

#define LINE_END(n) (line##n + count##n - 1)

#define LINE_END_PTR(n) (*line##n + *count##n - 1)

struct histindex {

  struct record {

    unsigned int ptr, cnt;

    struct record *next;

  } **records, /* an occurrence */

    **line_map; /* map of line to record chain */

  chastore_t rcha;

  unsigned int *next_ptrs;

  unsigned int table_bits,

         records_size,

         line_map_size;

  unsigned int max_chain_length,

         key_shift,

         ptr_shift;

  unsigned int cnt,

         has_common;

  xdfenv_t *env;

  xpparam_t const *xpp;

};

struct region {

  unsigned int begin1, end1;

  unsigned int begin2, end2;

};

#define LINE_MAP(i, a) (i->line_map[(a) - i->ptr_shift])

#define NEXT_PTR(index, ptr) \

  (index->next_ptrs[(ptr) - index->ptr_shift])

#define CNT(index, ptr) \

  ((LINE_MAP(index, ptr))->cnt)

#define REC(env, s, l) \

  (env->xdf##s.recs[l - 1])

static int cmp_recs(xrecord_t *r1, xrecord_t *r2)

{

  return r1->ha == r2->ha;

}

#define CMP(i, s1, l1, s2, l2) \

  (cmp_recs(REC(i->env, s1, l1), REC(i->env, s2, l2)))

#define TABLE_HASH(index, side, line) \

  XDL_HASHLONG((REC(index->env, side, line))->ha, index->table_bits)

static int scanA(struct histindex *index, int line1, int count1)

{

  unsigned int ptr, tbl_idx;

  unsigned int chain_len;

  struct record **rec_chain, *rec;

  for (ptr = LINE_END(1); line1 <= ptr; ptr--) {

    tbl_idx = TABLE_HASH(index, 1, ptr);

    rec_chain = index->records + tbl_idx;

    rec = *rec_chain;

    chain_len = 0;

    while (rec) {

      if (CMP(index, 1, rec->ptr, 1, ptr)) {

        /*

         * ptr is identical to another element. Insert

         * it onto the front of the existing element

         * chain.

         */

        NEXT_PTR(index, ptr) = rec->ptr;

        rec->ptr = ptr;

        /* cap rec->cnt at MAX_CNT */

        rec->cnt = XDL_MIN(MAX_CNT, rec->cnt + 1);

        LINE_MAP(index, ptr) = rec;

        goto continue_scan;

      }

      rec = rec->next;

      chain_len++;

    }

    if (chain_len == index->max_chain_length)

      return -1;

    /*

     * This is the first time we have ever seen this particular

     * element in the sequence. Construct a new chain for it.

     */

    if (!(rec = xdl_cha_alloc(&index->rcha)))

      return -1;

    rec->ptr = ptr;

    rec->cnt = 1;

    rec->next = *rec_chain;

    *rec_chain = rec;

    LINE_MAP(index, ptr) = rec;

continue_scan:

    ; /* no op */

  }

  return 0;

}

static int try_lcs(struct histindex *index, struct region *lcs, int b_ptr,

  int line1, int count1, int line2, int count2)

{

  unsigned int b_next = b_ptr + 1;

  struct record *rec = index->records[TABLE_HASH(index, 2, b_ptr)];

  unsigned int as, ae, bs, be, np, rc;

  int should_break;

  for (; rec; rec = rec->next) {

    if (rec->cnt > index->cnt) {

      if (!index->has_common)

        index->has_common = CMP(index, 1, rec->ptr, 2, b_ptr);

      continue;

    }

    as = rec->ptr;

    if (!CMP(index, 1, as, 2, b_ptr))

      continue;

    index->has_common = 1;

    for (;;) {

      should_break = 0;

      np = NEXT_PTR(index, as);

      bs = b_ptr;

      ae = as;

      be = bs;

      rc = rec->cnt;

      while (line1 < as && line2 < bs

        && CMP(index, 1, as - 1, 2, bs - 1)) {

        as--;

        bs--;

        if (1 < rc)

          rc = XDL_MIN(rc, CNT(index, as));

      }

      while (ae < LINE_END(1) && be < LINE_END(2)

        && CMP(index, 1, ae + 1, 2, be + 1)) {

        ae++;

        be++;

        if (1 < rc)

          rc = XDL_MIN(rc, CNT(index, ae));

      }

      if (b_next <= be)

        b_next = be + 1;

      if (lcs->end1 - lcs->begin1 < ae - as || rc < index->cnt) {

        lcs->begin1 = as;

        lcs->begin2 = bs;

        lcs->end1 = ae;

        lcs->end2 = be;

        index->cnt = rc;

      }

      if (np == 0)

        break;

      while (np <= ae) {

        np = NEXT_PTR(index, np);

        if (np == 0) {

          should_break = 1;

          break;

        }

      }

      if (should_break)

        break;

      as = np;

    }

  }

  return b_next;

}

static int fall_back_to_classic_diff(xpparam_t const *xpp, xdfenv_t *env,

    int line1, int count1, int line2, int count2)

{

  xpparam_t xpparam;

  memset(&xpparam, 0, sizeof(xpparam));

  xpparam.flags = xpp->flags & ~XDF_DIFF_ALGORITHM_MASK;

  return xdl_fall_back_diff(env, &xpparam,

          line1, count1, line2, count2);

}

static inline void free_index(struct histindex *index)

{

  xdl_free(index->records);

  xdl_free(index->line_map);

  xdl_free(index->next_ptrs);

  xdl_cha_free(&index->rcha);

}

static int find_lcs(xpparam_t const *xpp, xdfenv_t *env,

        struct region *lcs,

        int line1, int count1, int line2, int count2)

{

  int b_ptr;

  int ret = -1;

  struct histindex index;

  memset(&index, 0, sizeof(index));

  index.env = env;

  index.xpp = xpp;

  index.records = NULL;

  index.line_map = NULL;

  /* in case of early xdl_cha_free() */

  index.rcha.head = NULL;

  index.table_bits = xdl_hashbits(count1);

  index.records_size = 1 << index.table_bits;

  if (!XDL_CALLOC_ARRAY(index.records, index.records_size))

    goto cleanup;

  index.line_map_size = count1;

  if (!XDL_CALLOC_ARRAY(index.line_map, index.line_map_size))

    goto cleanup;

  if (!XDL_CALLOC_ARRAY(index.next_ptrs, index.line_map_size))

    goto cleanup;

  /* lines / 4 + 1 comes from xprepare.c:xdl_prepare_ctx() */

  if (xdl_cha_init(&index.rcha, sizeof(struct record), count1 / 4 + 1) < 0)

    goto cleanup;

  index.ptr_shift = line1;

  index.max_chain_length = 64;

  if (scanA(&index, line1, count1))

    goto cleanup;

  index.cnt = index.max_chain_length + 1;

  for (b_ptr = line2; b_ptr <= LINE_END(2); )

    b_ptr = try_lcs(&index, lcs, b_ptr, line1, count1, line2, count2);

  if (index.has_common && index.max_chain_length < index.cnt)

    ret = 1;

  else

    ret = 0;

cleanup:

  free_index(&index);

  return ret;

}

static int histogram_diff(xpparam_t const *xpp, xdfenv_t *env,

  int line1, int count1, int line2, int count2)

{

  struct region lcs;

  int lcs_found;

  int result;

redo:

  result = -1;

  if (count1 <= 0 && count2 <= 0)

    return 0;

  if (LINE_END(1) >= MAX_PTR)

    return -1;

  if (!count1) {

    while(count2--)

      env->xdf2.rchg[line2++ - 1] = 1;

    return 0;

  } else if (!count2) {

    while(count1--)

      env->xdf1.rchg[line1++ - 1] = 1;

    return 0;

  }

  memset(&lcs, 0, sizeof(lcs));

  lcs_found = find_lcs(xpp, env, &lcs, line1, count1, line2, count2);

  if (lcs_found < 0)

    goto out;

  else if (lcs_found)

    result = fall_back_to_classic_diff(xpp, env, line1, count1, line2, count2);

  else {

    if (lcs.begin1 == 0 && lcs.begin2 == 0) {

      while (count1--)

        env->xdf1.rchg[line1++ - 1] = 1;

      while (count2--)

        env->xdf2.rchg[line2++ - 1] = 1;

      result = 0;

    } else {

      result = histogram_diff(xpp, env,

            line1, lcs.begin1 - line1,

            line2, lcs.begin2 - line2);

      if (result)

        goto out;

      /*

       * result = histogram_diff(xpp, env,

       *            lcs.end1 + 1, LINE_END(1) - lcs.end1,

       *            lcs.end2 + 1, LINE_END(2) - lcs.end2);

       * but let's optimize tail recursion ourself:

      */

      count1 = LINE_END(1) - lcs.end1;

      line1 = lcs.end1 + 1;

      count2 = LINE_END(2) - lcs.end2;

      line2 = lcs.end2 + 1;

      goto redo;

    }

  }

out:

  return result;

}

int xdl_do_histogram_diff(xpparam_t const *xpp, xdfenv_t *env)

{

  return histogram_diff(xpp, env,

    env->xdf1.dstart + 1, env->xdf1.dend - env->xdf1.dstart + 1,

    env->xdf2.dstart + 1, env->xdf2.dend - env->xdf2.dstart + 1);

}