/* heap sort, based on Matt Mackall's linux kernel version */
static void sort(void *base0, size_t num, size_t size, struct fdisk_context *cxt,
		 int (*cmp_func)(struct fdisk_context *, const void *, const void *))
{
	/* pre-scale counters for performance */
	int i = (num/2 - 1) * size;
	size_t n = num * size, c, r;
	char *base = base0;

	/* heapify */
	for ( ; i >= 0; i -= size) {
		for (r = i; r * 2 + size < n; r  = c) {
			c = r * 2 + size;
			if (c < n - size &&
			    cmp_func(cxt, base + c, base + c + size) < 0)
				c += size;
			if (cmp_func(cxt, base + r, base + c) >= 0)
				break;
			generic_swap(base + r, base + c, size);
		}
	}

	/* sort */
	for (i = n - size; i > 0; i -= size) {
		generic_swap(base, base + i, size);
		for (r = 0; r * 2 + size < (size_t) i; r = c) {
			c = r * 2 + size;
			if (c < i - size &&
			    cmp_func(cxt, base + c, base + c + size) < 0)
				c += size;
			if (cmp_func(cxt, base + r, base + c) >= 0)
				break;
			generic_swap(base + r, base + c, size);
		}
	}
}

static const BoundSeg *
find_segment_with_func (const BoundSeg **segs,
                        gint             num_segs,
                        const BoundSeg  *search_seg,
                        GCompareFunc     cmp_func)
{
    const BoundSeg **seg;
    const BoundSeg *found_seg = NULL;

    seg = bsearch (&search_seg, segs, num_segs, sizeof (BoundSeg *), cmp_func);

    if (seg != NULL)
    {
        /* find first matching segment */
        while (seg > segs && cmp_func (seg - 1, &search_seg) == 0)
            seg--;

        /* find first non-visited segment */
        while (seg != segs + num_segs && cmp_func (seg, &search_seg) == 0)
            if (!(*seg)->visited)
            {
                found_seg = *seg;
                break;
            }
            else
                seg++;
    }

    return found_seg;
}

static int
check_values(Heap *h,int idx,int depth)
{
    HeapElement *he_l = NULL;
    HeapElement *he_r = NULL;
    HeapElement *he_p = NULL;
    HeapInternCmp cmp_func;

    if (idx < 0 || idx >= HSIZE(h))
	return 0;

    if (h->hpMode == HEAP_MINIMIZE)
	cmp_func = heap_larger;
    else 
	cmp_func = heap_smaller;

    he_p = HARRAY(h,idx);

    if (HLEFT(idx) >= HSIZE(h))	/* No left child */
    	return 0;

    if (HRIGHT(idx) < HSIZE(h))	/* Has right child */
	he_r = HARRAY(h,HRIGHT(idx));
	
    he_l = HARRAY(h,HLEFT(idx));

    if ( cmp_func(h,he_p,he_l))
    {
	printf("*** Heap violates parent-lchild property.\n");
	printf("*** Left child (%d) is %s than parent (%d)\n",
		HLEFT(idx),
		h->hpMode == HEAP_MINIMIZE ? "smaller" : "larger",
		idx);
	printf("*** Depth %d\n",depth);
	printf("%.8f - %.8f = %.8f\n",Key2Double(he_l),Key2Double(he_p),
		Key2Double(he_l) - Key2Double(he_p));

	return -1;
    }

    if (he_r &&  cmp_func(h,he_p,he_r))
    {
	printf("*** Heap violates parent-rchild property.\n");
	printf("*** Right child (%d) is %s than parent (%d)\n",
		HRIGHT(idx),h->hpMode == HEAP_MINIMIZE ? "smaller" : "larger",
		idx);
	printf("*** Depth %d\n",depth);
	printf("%.8f - %.8f = %.8f\n",Key2Double(he_r),Key2Double(he_p),
		Key2Double(he_r) - Key2Double(he_p));

	return -1;
    }

    if (check_values(h,HLEFT(idx),depth+1))
	return -1;

    if (he_r)
	return check_values(h,HRIGHT(idx),depth+1);
    return 0;
}

static int
heap_heapify(Heap *h,int idx)
{
    int 		l,r,largest;
    HeapInternCmp 	cmp_func;
    DBG(debug("heap_heapify(h=%p,idx=%d)\n",h,idx));

    l = HLEFT(idx);
    r = HRIGHT(idx);

    LLOG(l); LLOG(r);

    if (h->hpMode == HEAP_MAXIMIZE)
	cmp_func = heap_larger;
    else 
    	cmp_func = heap_smaller;

    if (l <= HSIZE(h) && cmp_func(h,HARRAY(h,l),HARRAY(h,idx)))
	largest = l; 
    else 
	largest = idx;

    if (r <= HSIZE(h) && cmp_func(h,HARRAY(h,r),HARRAY(h,largest)))
	largest = r;

    if (largest != idx)
    {
	heap_swap(h,idx,largest);
	return heap_heapify(h,largest);
    }

    return 0;
}

void sort(void *base, size_t num, size_t size,
	int (*cmp_func)(const void *, const void *),
	void (*swap_func)(void *, void *, int size))
{
	int i = (num/2 - 1) * size, n = num * size, c, r;

	if (!swap_func)
		swap_func = (size == 4 ? u32_swap : generic_swap);

	for ( ; i >= 0; i -= size) {
		for (r = i; r * 2 + size < n; r = c) {
			c = r * 2 + size;
			if (c < n - size && cmp_func(base + c, base + c + size) < 0)
				c += size;
			if (cmp_func(base + r, base + c) >= 0)
				break;
			swap_func(base + r, base + c, size);
		}
	}

	for (i = n - size; i > 0; i -= size) {
		swap_func(base, base + i, size);
		for (r = 0; r * 2 + size < i; r = c) {
			c = r * 2 + size;
			if (c < i - size && cmp_func(base + c, base + c + size) < 0)
				c += size;
			if (cmp_func(base + r, base + c) >= 0)
				break;
			swap_func(base + r, base + c, size);
		}
	}
}

void sort(void *base, size_t num, size_t size,
	  int (*cmp_func)(const void *, const void *),
	  void (*swap_func)(void *, void *, int size))
{
	/* pre-scale counters for performance */
	int i = (num/2 - 1) * size, n = num * size, c, r;

	if (!swap_func)
		swap_func = (size == 4 ? u32_swap : generic_swap);

	/* heapify */
	for ( ; i >= 0; i -= size) {
		for (r = i; r * 2 + size < n; r  = c) {
			c = r * 2 + size;
			if (c < n - size && cmp_func(base + c, base + c + size) < 0)
				c += size;
			if (cmp_func(base + r, base + c) >= 0)
				break;
			swap_func(base + r, base + c, size);
		}
	}

	/* sort */
	for (i = n - size; i >= 0; i -= size) {
		swap_func(base, base + i, size);
		for (r = 0; r * 2 + size < i; r = c) {
			c = r * 2 + size;
			if (c < i - size && cmp_func(base + c, base + c + size) < 0)
				c += size;
			if (cmp_func(base + r, base + c) >= 0)
				break;
			swap_func(base + r, base + c, size);
		}
	}
}

/*
 * find_in_list: This looks up the given name in the given list.  List and
 * name are as described above.  If wild is true, each name in the list is
 * used as a wild card expression to match name... otherwise, normal matching
 * is done
 */
List	* BX_find_in_list_ext(register List **list, char *name, int wild, int (*cmp_func)(List *, char *))
{
    register List	*tmp;
    int	best_match,
        current_match;

    if (!cmp_func)
        cmp_func = wild ? list_match : list_stricmp;
    best_match = 0;

    if (wild)
    {
        register List	*match = NULL;

        for (tmp = *list; tmp; tmp = tmp->next)
        {
            if ((current_match = cmp_func(tmp, name)) > best_match)
            {
                match = tmp;
                best_match = current_match;
            }
        }
        return (match);
    }
    else
    {
        for (tmp = *list; tmp; tmp = tmp->next)
            if (cmp_func(tmp, name) == 0)
                return (tmp);
    }
    return NULL;
}

/*
 * t_array_filter_with_data
 * Filter a given target element for ordered arrays using binary search method.
 */
TArray *
t_array_filter_with_data (TArray * array, tpointer target,
                          TCompDataFunc cmp_func, tpointer user_data)
{
    TArray *ret = t_array_new ();
    tpointer elem;
    int mid;
    TBoolean found;

    mid = t_array_binary_lookup_index_with_data (array, target, cmp_func,
            user_data, &found);

    if (found) {
        int i = mid - 1, j = mid + 1;

        elem = array->vector[mid];
        t_array_append (ret, elem);
        elem = t_array_index (array, i);
        while ((i >= 0) && (cmp_func (elem, target, user_data) == 0)) {
            t_array_append (ret, elem);
            i--;
            elem = t_array_index (array, i);
        }

        elem = t_array_index (array, j);
        while ((j <= t_array_length (array) - 1) &&
                (cmp_func (elem, target, user_data) == 0)) {
            t_array_append (ret, elem);
            j++;
            elem = t_array_index (array, j);
        }
    }
    return ret;
}

/*
 * find_in_list: This looks up the given name in the given list.  List and
 * name are as described above.  If wild is true, each name in the list is
 * used as a wild card expression to match name... otherwise, normal matching
 * is done 
 */
List	*find_in_list (List **list, const char *name, int wild)
{
	List	*tmp;
	int	best_match = 0,
		current_match;
	int	(*cmp_func) (List *, const char *);

	cmp_func = wild ? list_match : list_strcmp;

	if (wild)
	{
		List	*match = (List *) 0;

		for (tmp = *list; tmp; tmp = tmp->next)
			if ((current_match = cmp_func(tmp, name)) > best_match)
				match = tmp, best_match = current_match;

		return (match);
	}
	else
	{
		for (tmp = *list; tmp; tmp = tmp->next)
			if (cmp_func(tmp, name) == 0)
				return (tmp);
	}

	return ((List *) 0);
}

/// A return value of true means all is well (even if no replacements were performed), false
/// indicates an unrecoverable error.
bool literal_replacer_t::replace_matches(const wchar_t *arg) {
    wcstring result;
    bool replacement_occurred = false;

    if (patlen == 0) {
        replacement_occurred = true;
        result = arg;
    } else {
        auto &cmp_func = opts.ignore_case ? wcsncasecmp : wcsncmp;
        const wchar_t *cur = arg;
        while (*cur != L'\0') {
            if ((opts.all || !replacement_occurred) && cmp_func(cur, pattern, patlen) == 0) {
                result += replacement;
                cur += patlen;
                replacement_occurred = true;
                total_replaced++;
            } else {
                result += *cur;
                cur++;
            }
        }
    }

    if (!opts.quiet && (!opts.filter || replacement_occurred)) {
        streams.out.append(result);
        streams.out.append(L'\n');
    }

    return true;
}

void merge( void* a1, size_t n1, void* a2, size_t n2, size_t size_elements, int (*cmp_func)(const void*, const void*)) {

    uint8_t* new_array = (uint8_t*)malloc((n1+n2)*size_elements);
    int i1 = 0;
    int i2 = 0;
    int si = 0;
    while( i1 < n1 && i2 < n2 ) {
        if( cmp_func((uint8_t*)a1+i1*size_elements,(uint8_t*)a2+i2*size_elements)) {
            memcpy(new_array+si*size_elements,(uint8_t*)a1+i1*size_elements, size_elements);
            i1++;
        } else {
            memcpy(new_array+si*size_elements,(uint8_t*)a2+i2*size_elements, size_elements);
            i2++;
        }
        si++;
    }
    while( i1 < n1 ) {
            memcpy(new_array+si*size_elements,(uint8_t*)a1+i1*size_elements, size_elements);
            si++; i1++;
    }
    while( i2 < n2 ) {
            memcpy(new_array+si*size_elements,(uint8_t*)a2+i2*size_elements, size_elements);
            si++; i2++;
    }
    memcpy(a1, new_array,(n1+n2)*size_elements);
    free(new_array);
}

/*
 * return:
 * _SHASH_NOT_FOUND  not found
 * _SHASH_FOUND      found
 * _SHASH_SYS_ERROR  system error
 */
int SHash::sh_next(void **find, const void *key, void **value)
{
    if (*find == NULL)
        return sh_find(key, value, find);

    if (sh_get_next(*find) == 0)
        return _SHASH_NOT_FOUND;

    struct shm_hash_head *head = sh_get_head();

    void *rec = sh_get_rec(head);

    *find = sh_get_pos(rec, sh_get_next(*find));

    for (;;) {
        if (sh_record_is_used(*find) && cmp_func(func_type, sh_get_key(*find), key, key_len) == 0) {
            if (value)
                *value = sh_get_value(*find);
            return _SHASH_FOUND;
        }
        if (sh_get_next(*find) == 0)
            break;
        *find = sh_get_pos(rec, sh_get_next(*find));
    }

    return _SHASH_NOT_FOUND;
}

/*
 * flag = 0 : delete 1
 * flag = 1 : delete all
 */
int SHash::sh_sys_delete(const void *key, int flag)
{
    void *value, *used, *find;
    int total = 0, n = 0;
    unsigned int crc32;
    struct shm_hash_head *head = sh_get_head();

    void *rec = sh_get_rec(head);

    if ((n = sh_sys_find(key, &value, &crc32, &used, &find)) == _SHASH_SYS_ERROR)
        return -1;

    if (n == _SHASH_NOT_FOUND || n == _SHASH_NOT_FOUND_NEXT) {
        return 0;
    }

    for (;;) {
        if (sh_record_is_used(find) && cmp_func(func_type, sh_get_key(find), key, key_len) == 0) {
            memset(sh_get_key(find), 0, key_len);
            if (value_len > 0)
                memset(sh_get_value(find), 0, value_len);
            sh_delete_a_record(find);
            head->hash_total--;
            total++;
            if (flag == 0)
                break;
        }
        if (sh_get_next(find) == 0)
            break;
        find = sh_get_pos(rec, sh_get_next(find));
    }

    return total;
}

static TArray *
_timsort_merge (TArray * a, TArray * b,TCompDataFunc cmp_func, tpointer cmp_data)
{
    int i, j, k, first_end, second_end;
    TArray *result;
    result = t_array_new();

    i = 0;
    j = 0;
    first_end = a->len;
    second_end = b->len;
    while ((i < first_end) && (j < second_end))
        if (cmp_func (a->vector[i], b->vector[j], cmp_data) > 0)
            t_array_append(result ,b->vector[j++]);
        else
            t_array_append(result ,a->vector[i++]);

    if (i >= first_end)
        for (k = j; k < second_end; k++)
            t_array_append(result ,b->vector[k]);

    if (j >= second_end)
        for (k = i; k < first_end ; k++)
            t_array_append(result ,a->vector[k]);

    return result;
}

const DOTCONFDocumentNode * DOTCONFDocument::findNode(const char * nodeName, const DOTCONFDocumentNode * parentNode, const DOTCONFDocumentNode * startNode) const
{


    std::list<DOTCONFDocumentNode*>::const_iterator i = nodeTree.begin();

    if(startNode == NULL)
        startNode = parentNode;

    if(startNode != NULL){
        while( i != nodeTree.end() && (*i) != startNode ){
            ++i;
        }
        if( i != nodeTree.end() ) ++i;
    }

    for(; i!=nodeTree.end(); ++i){

    if((*i)->parentNode != parentNode){
            continue;
        }
        if(!cmp_func(nodeName, (*i)->name)){
            return *i;
        }
    }
    return NULL;
}

char * DOTCONFDocument::getSubstitution(char * macro, int lineNum)
{
    char * buf = NULL;
    char * variable = macro+2;

    char * endBr = strchr(macro, '}');

    if(!endBr){
        error(lineNum, fileName, "unterminated '{'");
        return NULL;
    }
    *endBr = 0;

    char * defaultValue = strchr(variable, ':');

    if(defaultValue){
        *defaultValue++ = 0;
        if(*defaultValue != '-'){
            error(lineNum, fileName, "incorrect macro substitution syntax");
            return NULL;
        }
        ++defaultValue;
        if(*defaultValue == '"' || *defaultValue == '\''){
            ++defaultValue;
            defaultValue[strlen(defaultValue)-1] = 0;
        }
    } else {
        defaultValue = NULL;
    }

    char * subs = getenv(variable);
    if( subs ){
        buf = mempool->strdup(subs);
    } else {
        std::list<DOTCONFDocumentNode*>::iterator i = nodeTree.begin();
        DOTCONFDocumentNode * tagNode = NULL;
        for(; i!=nodeTree.end(); i++){
            tagNode = *i;
            if(!cmp_func(tagNode->name, variable)){
                if(tagNode->valuesCount != 0){
                    buf = mempool->strdup(tagNode->values[0]);
                    break;
                }
            }
        }
        if( i == nodeTree.end() ){
            if( defaultValue ){
                buf = mempool->strdup(defaultValue);
            } else {
                error(lineNum, fileName, "substitution not found and default value not given");
                return NULL;
            }
        }
    }
    return buf;
}

/* ----------------------------------------------------------------------------*/
int vector_contains(vector vec, void *elt,int (*cmp_func)(void*,void*)) {
	int i;
	if (vec != NULL) {
		for (i = 0; i < vec->cur; i++) {
			
			if (cmp_func(vector_get_element_at(vec,i),elt))
				return 1;
		}
	}
	return 0;
}

saim_list_node * saim_list_find(saim_list * list, const void * data, bool (*cmp_func)(const void*, const void*))
{
	saim_list_node * node;
	node = list->head;
	while (node != NULL)
	{
		if (cmp_func(data, node->data))
			return node;
		node = node->next;
	}
	return NULL;
}

/* list_find()
 *
 * Find element in list containing data using compare function *cmp_func
 */
list_t *list_find(list_t *head, void *data, int (*cmp_func)(void*, void*))
{
    list_t *l;
    
    for (l = head->next; l != NULL; l = l->next)
    {
        if (cmp_func(data, l->data) == 0)
            return l;
    }

    return NULL;
}

size_t DictList::predict(const char16 last_hzs[], uint16 hzs_len,
                         NPredictItem *npre_items, size_t npre_max,
                         size_t b4_used) {
  assert(hzs_len <= kMaxPredictSize && hzs_len > 0);

  // 1. Prepare work
  int (*cmp_func)(const void *, const void *) = cmp_func_[hzs_len - 1];

  NGram& ngram = NGram::get_instance();

  size_t item_num = 0;

  // 2. Do prediction
  for (uint16 pre_len = 1; pre_len <= kMaxPredictSize + 1 - hzs_len;
       pre_len++) {
    uint16 word_len = hzs_len + pre_len;
    char16 *w_buf = find_pos_startedbyhzs(last_hzs, word_len, cmp_func);
    if (NULL == w_buf)
      continue;
    while (w_buf < buf_ + start_pos_[word_len] &&
           cmp_func(w_buf, last_hzs) == 0 &&
           item_num < npre_max) {
      memset(npre_items + item_num, 0, sizeof(NPredictItem));
      utf16_strncpy(npre_items[item_num].pre_hzs, w_buf + hzs_len, pre_len);
      npre_items[item_num].psb =
        ngram.get_uni_psb((size_t)(w_buf - buf_ - start_pos_[word_len - 1])
                          / word_len + start_id_[word_len - 1]);
      npre_items[item_num].his_len = hzs_len;
      item_num++;
      w_buf += word_len;
    }
  }

  size_t new_num = 0;
  for (size_t i = 0; i < item_num; i++) {
    // Try to find it in the existing items
    size_t e_pos;
    for (e_pos = 1; e_pos <= b4_used; e_pos++) {
      if (utf16_strncmp((*(npre_items - e_pos)).pre_hzs, npre_items[i].pre_hzs,
                        kMaxPredictSize) == 0)
        break;
    }
    if (e_pos <= b4_used)
      continue;

    // If not found, append it to the buffer
    npre_items[new_num] = npre_items[i];
    new_num++;
  }

  return new_num;
}