/*******************************************************************
  uLan Communication - C interface library

  ul_gsa.c	- generic sorted arrays

  (C) Copyright 2001 by Pavel Pisa - Originator

  The uLan driver is distributed under the Gnu General Public License. 
  See file COPYING for details.

  Originator reserve the right to use and publish sources
  under different conditions too. If third party contributors
  do not accept this condition, they can delete this statement
  and only GNU license will apply.
 *******************************************************************/

#include <malloc.h>
#include <string.h>
#include "ul_gsa.h"

#undef DEBUG

#define GSA_ALLOC_STEP 8
#define GSA_DEALLOC_STEP 32

void 
gsa_struct_init(gsa_array_t *array, int key_offs,
		gsa_cmp_fnc_t *cmp_fnc)
{
  array->key_offs=key_offs;
  array->cmp_fnc=cmp_fnc;
  array->count=0;
  array->alloc_count=0;
  array->items=NULL;
};

void 
gsa_delete_all(gsa_array_t *array)
{
  if(array->items) free(array->items);
  array->items=NULL;
  array->count=0;
  array->alloc_count=0;
}


int 
gsa_bsearch_indx(gsa_array_t *array, void *key, int key_offs,
	    gsa_cmp_fnc_t *cmp_fnc, int mode, unsigned *indx)
{
  unsigned a, b, c;
  int r;
  if(!array->items || !array->count || !cmp_fnc){
    *indx=0;
    if(mode==2)
      *indx=array->count;
    return 0;
  }
  key_offs=array->key_offs;
  cmp_fnc=array->cmp_fnc;
  a=0;
  b=array->count;
  while(1){
    c=(a+b)/2;
    r=cmp_fnc((char*)array->items[c]+key_offs,key);
    if(!r) break;
    if(r<0)
      a=c+1;
     else
      b=c;  
    if(a==b){
      *indx=a;
      return 0;
    }
  }
  if(mode==1){
    /* equal items can be in range a to b-1 */
    /* routine looks for first one */
    b=c;
    do{
      c=(a+b)/2;
      r=cmp_fnc((char*)array->items[c]+key_offs,key);
      if(r)
	a=c+1;
       else
	b=c;  
    }while(a!=b);
    c=b;
  } else if(mode==2) {
    /* equal items can be in range a to b-1 */
    /* return index after last one */
    a=c+1;
    while(a!=b){
      c=(a+b)/2;
      r=cmp_fnc((char*)array->items[c]+key_offs,key);
      if(r)
	b=c;
       else
	a=c+1;
    }
    c=a;
  }
  *indx=c;
  return 1;
}

void * 
gsa_find(gsa_array_t *array, void *key)
{
  unsigned indx;
  if(gsa_bsearch_indx(array,key,array->key_offs,
  		      array->cmp_fnc,0,&indx))
    return array->items[indx];
  else return NULL;
}

void * 
gsa_find_first(gsa_array_t *array, void *key)
{
  unsigned indx;
  if(gsa_bsearch_indx(array,key,array->key_offs,
  		      array->cmp_fnc,1,&indx))
    return array->items[indx];
  else return NULL;
}

void * 
gsa_find_indx(gsa_array_t *array, void *key, int *indx)
{
  if(gsa_bsearch_indx(array,key,array->key_offs,
  		      array->cmp_fnc,1,indx))
    return array->items[*indx];
  else return NULL;
}

int
gsa_insert_at(gsa_array_t *array, void *item, unsigned where)
{
  unsigned acnt=array->alloc_count;
  unsigned cnt=array->count;
  void **items, **p;
  if(where>cnt) where=cnt;
  if((cnt+1>=acnt)||!array->items)
  {
    acnt+=GSA_ALLOC_STEP;
    if(!array->items)
      items=malloc(acnt*sizeof(void*));
     else
      items=realloc(array->items,acnt*sizeof(void*));
    if(!items) return -1;
    array->alloc_count=acnt;
    array->items=items;
  }
  else items=array->items;
  p=items+where;
  memmove(p+1,p,(char*)(items+cnt)-(char*)p);
  array->count=cnt+1;
  *p=item;
  return 0;
}

int
gsa_insert(gsa_array_t *array, void *item, int mode)
{
  unsigned indx;
  int res;
  res=gsa_bsearch_indx(array,(char*)item+array->key_offs,
  		array->key_offs,array->cmp_fnc,mode,&indx);
  if(res){
    if(!mode) return -1;
  }
  if(gsa_insert_at(array,item,indx)<0)
    return -1;
  return res;
}

int
gsa_delete_at(gsa_array_t *array, unsigned indx)
{
  unsigned acnt=array->alloc_count;
  unsigned cnt=array->count;
  void **items=array->items;
  void **p;
  if(indx>=cnt) return -1;
  p=items+indx;
  array->count=--cnt;
  memmove(p,p+1,(items+cnt-p)*sizeof(void *));
  if(acnt-cnt>GSA_DEALLOC_STEP+GSA_ALLOC_STEP)
  {
    acnt-=GSA_DEALLOC_STEP;
    items=realloc(array->items,acnt*sizeof(void*));
    if(items){
      array->alloc_count=acnt;
      array->items=items;
    }
  }
  return 0;
}

int
gsa_delete(gsa_array_t *array, void *item)
{
  unsigned indx;
  int key_offs=array->key_offs;
  gsa_cmp_fnc_t *cmp_fnc=array->cmp_fnc;
  if(!gsa_bsearch_indx(array,(char*)item+key_offs,
  	key_offs,cmp_fnc,1,&indx))
    return -1;

  while(array->items[indx]!=item){
    if(++indx>=array->count) return -1;
    if(cmp_fnc){
      if(cmp_fnc((char*)(array->items[indx])+key_offs,
               (char*)item+key_offs))
        return -1;
    }
  }
  return gsa_delete_at(array,indx);
}

int
gsa_resort_buble(gsa_array_t *array, int key_offs,
	       gsa_cmp_fnc_t *cmp_fnc)
{
  char **a, **b, **p;
  char *k1, *k2;
  int m, m1;
  if(array->count<2) return 0;
  a=(char**)array->items; m=0;
  b=(char**)&array->items[array->count-1];
  do{
    /* upward run */
    p=a; m1=0;
    k1=*p+key_offs;
    do{
      k2=*(p+1)+key_offs;
      if(cmp_fnc(k1,k2)>0) {
        k2=*p;
        *p=*(p+1);
        *(p+1)=k2;
        m1=1;
      } else k1=k2;
    } while(++p!=b);
    m|=m1;
    if((a==--b)||!m1) return m;
    /* downward run */
    p=b; m1=0;
    k1=*p+key_offs;
    do{
      k2=*(p-1)+key_offs;
      if(cmp_fnc(k1,k2)<0) {
        k2=*p;
        *p=*(p-1);
        *(p-1)=k2;
        m1=1;
      } else k1=k2;
    } while(--p!=a);
    m|=m1;
    if((++a==b)||!m1) return m;
  }while(1);
}

int
gsa_setsort(gsa_array_t *array, int key_offs,
	       gsa_cmp_fnc_t *cmp_fnc)
{
  if(key_offs>=0) array->key_offs=key_offs;
  if(cmp_fnc!=NULL) array->cmp_fnc=cmp_fnc;
  return gsa_resort_buble(array,array->key_offs,array->cmp_fnc);
}

int gsa_cmp_int(const void *a, const void *b)
{
  return *(int*)a-*(int*)b;
}

int gsa_cmp_ulong(const void *a, const void *b)
{
  return *(unsigned long*)a-*(unsigned long*)b;
}