/*

 *  LibXDiff by Davide Libenzi ( File Differential Library )

 *  Copyright (C) 2003  Davide Libenzi

 *

 *  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, see

 *  <http://www.gnu.org/licenses/>.

 *

 *  Davide Libenzi <davidel@xmailserver.org>

 *

 */

#include <limits.h>

#include <assert.h>

#include "xinclude.h"

int64_t xdl_bogosqrt(int64_t n) {

  int64_t i;

  /*

   * Classical integer square root approximation using shifts.

   */

  for (i = 1; n > 0; n >>= 2)

    i <<= 1;

  return i;

}

void *xdl_mmfile_first(mmfile_t *mmf, int64_t *size)

{

  *size = mmf->size;

  return mmf->ptr;

}

int64_t xdl_mmfile_size(mmfile_t *mmf)

{

  return mmf->size;

}

int xdl_cha_init(chastore_t *cha, int64_t isize, int64_t icount) {

  cha->head = cha->tail = NULL;

  cha->isize = isize;

  cha->nsize = icount * isize;

  cha->ancur = cha->sncur = NULL;

  cha->scurr = 0;

  return 0;

}

void xdl_cha_free(chastore_t *cha) {

  chanode_t *cur, *tmp;

  for (cur = cha->head; (tmp = cur) != NULL;) {

    cur = cur->next;

    xdl_free(tmp);

  }

}

void *xdl_cha_alloc(chastore_t *cha) {

  chanode_t *ancur;

  void *data;

  if (!(ancur = cha->ancur) || ancur->icurr == cha->nsize) {

    if (!(ancur = (chanode_t *) xdl_malloc(sizeof(chanode_t) + cha->nsize))) {

      return NULL;

    }

    ancur->icurr = 0;

    ancur->next = NULL;

    if (cha->tail)

      cha->tail->next = ancur;

    if (!cha->head)

      cha->head = ancur;

    cha->tail = ancur;

    cha->ancur = ancur;

  }

  data = (char *) ancur + sizeof(chanode_t) + ancur->icurr;

  ancur->icurr += cha->isize;

  return data;

}

int64_t xdl_guess_lines(mmfile_t *mf, int64_t sample) {

  int64_t nl = 0, size, tsize = 0;

  char const *data, *cur, *top;

  if ((cur = data = xdl_mmfile_first(mf, &size)) != NULL) {

    for (top = data + size; nl < sample && cur < top; ) {

      nl++;

      if (!(cur = memchr(cur, '\n', top - cur)))

        cur = top;

      else

        cur++;

    }

    tsize += (long) (cur - data);

  }

  if (nl && tsize)

    nl = xdl_mmfile_size(mf) / (tsize / nl);

  return nl + 1;

}

int xdl_recmatch(const char *l1, int64_t s1, const char *l2, int64_t s2)

{

  if (s1 == s2 && !memcmp(l1, l2, s1))

    return 1;

  return 0;

}

uint64_t xdl_hash_record(char const **data, char const *top) {

  uint64_t ha = 5381;

  char const *ptr = *data;

  for (; ptr < top && *ptr != '\n'; ptr++) {

    ha += (ha << 5);

    ha ^= (unsigned long) *ptr;

  }

  *data = ptr < top ? ptr + 1: ptr;

  return ha;

}

unsigned int xdl_hashbits(int64_t size) {

  int64_t val = 1;

  unsigned int bits = 0;

  for (; val < size && bits < (int64_t) CHAR_BIT * sizeof(unsigned int); val <<= 1, bits++);

  return bits ? bits: 1;

}