itemarr.c

Go to the documentation of this file.

#include "itemarr.h"
#ifdef DBGALLOC
#define DMALLOC(s,f,ln)     DebugReAlloc(NULL,s,f,ln)
#define DREALLOC(p,s,f,ln)  DebugReAlloc(p,s,f,ln)
#define DFREE(p,f,ln)       DebugFree(p,f,ln)
#else
#define DMALLOC(s,f,ln)     __malloc(s)
#define DREALLOC(p,s,f,ln)  __realloc(p,s)
#define DFREE(p,f,ln)       __free(p)
#endif

#define STRTREEITEM(st,x) AddPtr(LPBYTE,(st)->strings,(st)->offsets[x])

BOOL ItemArrayInitEx(ITEMARRAY *ia, DWORD sz, DWORD init, DWORD grow){
 if(!ia)return FALSE;
 ZeroMemory(ia,sizeof(ITEMARRAY));
 ia->size=0;
 ia->length=0;
 ia->szItem=sz;
 ia->szRef=sz;
 ia->szInit=init;
 ia->szGrow=grow;
 ia->array=NULL;
 ia->bFixed=FALSE;
 ia->first=ia->last=NULL;
 return TRUE;
}

BOOL ItemArrayInitFixedEx(ITEMARRAY *ia, DWORD sz, DWORD init, DWORD grow){
 if(!ia)return FALSE;
 ZeroMemory(ia,sizeof(ITEMARRAY));
 ia->size=0;
 ia->length=0;
 ia->szItem=sz;
 ia->szRef=sizeof(LPVOID);
 ia->szInit=init;
 ia->szGrow=grow;
 ia->array=NULL;
 ia->bFixed=TRUE;
 ia->first=ia->last=NULL;
 return TRUE;
}

//Growth strategy idea from Qt documention for generic containers
static DWORD allocstrat[]={
4, 8, 12, 16, 20, 52, 
116, 244, 500, 1012, 2036, 4084
};

static DWORD ItemArrayGrow(ITEMARRAY *ia, DWORD need){
 DWORD cursize=ia->size;
 if(ia->szGrow==0){
  if(need>=4084){
   while(cursize<need)
    cursize+=2048;
  } else {
   int x;
   for(x=11;x>=0;x--){
    if(allocstrat[x]<=need)
     break;
   }
   cursize=allocstrat[x+1];
  }
  return cursize;
 } else {
  need+=(cursize)?ia->szInit:ia->szGrow;
  return need;
 }
}

static LONG ItemArrayInternalAllocDynamic(ITEMARRAY *ia, DWORD sz, LPTSTR f, DWORD ln){
 DWORD need=ia->length+sz;
 LONG ret;
 LPBYTE mem;
 LONG refsz;
 if(need>ia->size){
  need=ItemArrayGrow(ia,need);
  ia->array=DREALLOC(ia->array,ia->szRef*need,f,ln);
  ia->size=need;
 }
 ret=ia->length;
 ia->length+=sz;
 mem=AddPtr(LPBYTE,ia->array,ia->szRef*ret);
 refsz=ia->szRef*sz;
 while(--refsz>=0)
  *mem++=0;
 return ret;
}

static void AllocNewBlock(ITEMARRAY *ia, DWORD sz, LPTSTR f, DWORD ln){
 ITEMLINK *link;
 LPBYTE afterlink;
 ia->size+=sz;
 link=DMALLOC((sz*ia->szItem)+sizeof(ITEMLINK),f,ln);
 ASSERT(!IsBadReadPtr(link,(sz*ia->szItem)+sizeof(ITEMLINK)));
 link->size=sz;
 link->cur=0;
 link->next=NULL;
 if(ia->last){
  ia->last->next=link;
 } else
  ia->first=link;
 ia->last=link;
 ia->array=DREALLOC(ia->array,ia->size*ia->szRef,f,ln);
}

static DWORD PopulateAlloc(ITEMARRAY *ia, DWORD sz){
 DWORD have,i;
 DWORD mn;
 LPBYTE link;
 LPBYTE *array;
 LPBYTE linkend;
 ASSERT(ia->last);
 ASSERT(ia->array);
 link=AddPtr(LPBYTE,ia->last,sizeof(ITEMLINK));
 ASSERT(!IsBadReadPtr(link,ia->szItem*ia->last->size));
 linkend=link+ia->szItem*ia->last->size;
 link+=ia->szItem*ia->last->cur;
 ASSERT(ia->last->cur<=ia->last->size);
 have=ia->last->size-ia->last->cur;
 array=ia->array;
 mn=min(have,sz);
 ia->last->cur+=mn;
 ZeroMemory(link,mn*ia->szItem);
 for(i=0;i<mn;i++,link+=ia->szItem){
  array[ia->length++]=link;
  ASSERT(link+ia->szItem<=linkend);
 }
 return sz-mn;
}

static LONG ItemArrayInternalAllocFixed(ITEMARRAY *ia, DWORD sz, LPTSTR f, DWORD ln){
 LONG ret=ia->length;
 DWORD t;
 if(!ia->last){
  ASSERT(!ia->first);
  ia->size=0;
  AllocNewBlock(ia,sz+ia->szInit,f,ln);
  t=PopulateAlloc(ia,sz);
  ASSERT(t==0);
 } else {
  DWORD need=PopulateAlloc(ia,sz);
  if(need>0){
   AllocNewBlock(ia,need+ia->szGrow,f,ln);
   t=PopulateAlloc(ia,need);
   ASSERT(t==0);
  }
 }
 return ret;
}

#define ItemArrayInternalAlloc(ia,sz,f,ln) \
   (ia->bFixed)?ItemArrayInternalAllocFixed(ia,sz,f,ln):ItemArrayInternalAllocDynamic(ia,sz,f,ln)

LPVOID ItemArrayPtr(ITEMARRAY *ia, int i){
 LPVOID *p;
 if(i<0||i>=ia->length)return NULL;
 p=AddPtr(LPVOID,ia->array,i*ia->szRef); 
 return (ia->bFixed)?*p:p;
}
#ifndef DBGALLOC
LPVOID ItemArrayAllocOnePtr(ITEMARRAY *ia){
 LONG i=ItemArrayInternalAlloc(ia,1,NULL,0);
 return ItemArrayPtr(ia,i);
}
LONG ItemArrayAllocOne(ITEMARRAY *ia){
 return ItemArrayInternalAlloc(ia,1,NULL,0);
}
LPVOID ItemArrayAllocManyPtr(ITEMARRAY *ia, DWORD sz){
 LONG i=ItemArrayInternalAlloc(ia,sz,NULL,0);
 return ItemArrayPtr(ia,i);
}
LONG ItemArrayAllocMany(ITEMARRAY *ia, DWORD sz){
 return ItemArrayInternalAlloc(ia,sz,NULL,0);
}
void ItemArrayFree(ITEMARRAY *ia){
 ITEMLINK *p=ia->first,*n;
 DFREE(ia->array,NULL,0);
 while(p){
  n=p->next;
  DFREE(p,NULL,0);
  p=n;
 }
 ZeroMemory(ia,sizeof(ITEMARRAY));
}
#else
LPVOID _ItemArrayAllocOnePtr(ITEMARRAY *ia, LPTSTR f, DWORD ln){
 LONG i=ItemArrayInternalAlloc(ia,1,f,ln);
 return ItemArrayPtr(ia,i);
}
LONG _ItemArrayAllocOne(ITEMARRAY *ia, LPTSTR f, DWORD ln){
 return ItemArrayInternalAlloc(ia,1,f,ln);
}
LPVOID _ItemArrayAllocManyPtr(ITEMARRAY *ia, DWORD sz, LPTSTR f, DWORD ln){
 LONG i=ItemArrayInternalAlloc(ia,sz,f,ln);
 return ItemArrayPtr(ia,i);
}
LONG _ItemArrayAllocMany(ITEMARRAY *ia, DWORD sz, LPTSTR f, DWORD ln){
 return ItemArrayInternalAlloc(ia,sz,f,ln);
}
void _ItemArrayFree(ITEMARRAY *ia, LPTSTR f, DWORD ln){
 ITEMLINK *p=ia->first,*n;
 DFREE(ia->array,f,ln);
 while(p){
  n=p->next;
  DFREE(p,f,ln);
  p=n;
 }
 ZeroMemory(ia,sizeof(ITEMARRAY));
}
#endif

void ItemArraySort(
 ITEMARRAY *ia,
 int (*cmp)(LPVOID,LPVOID)
){
 if(ia->bFixed)return;
 qsort(ia->array,ia->length,ia->szRef,cmp);
}

void ItemArrayRemoveItem(ITEMARRAY *ia, LONG idx){
 if(idx<0||idx>=ia->length||ia->bFixed)
  return;
 if(idx!=ia->length-1){
  LONG startidx=idx+1;
  LONG movelen=(ia->length-startidx)*ia->szRef;
  LPVOID startpos=AddPtr(LPVOID,ia->array,ia->szRef*startidx);
  LPVOID endpos=AddPtr(LPVOID,ia->array,ia->szRef*idx);
  memmove(endpos,startpos,movelen);
 }
 ia->length--;
}

LONG ItemArraySearchIndex(ITEMARRAY *ia, LPVOID key, int (*cmp)(LPVOID,LPVOID)){
 LONG l=0,c,rcmp,r;
 if(!ia||ia->length==0)
  return -1;
 r=ia->length-1;
 while(l<=r){
  LPVOID *ppdata;
  LPVOID pdata;
  c=(l+r)/2;
  ppdata=AddPtr(LPVOID,ia->array,ia->szRef*c);
  pdata=(ia->bFixed)?*ppdata:ppdata;
  rcmp=(*cmp)(key,pdata);
  if(rcmp==0){
   return c;
  }
  else if(rcmp>0){
   l=c+1;
  } else {
   r=c-1;
  }
 }
 return -1;
}

LPVOID ItemArraySearch(
 ITEMARRAY *ia,
 LPVOID key,
 int (*cmp)(LPVOID,LPVOID)
){
 LONG idx=ItemArraySearchIndex(ia,key,cmp);
 return ItemArrayPtr(ia,idx);
}

static int StringCmp(
 LPCTSTR a,
 LPCTSTR b,
 BOOL ignoreCase
){
 if(ignoreCase)
  return lstrcmpiA(a,b);
 else
  return lstrcmpA(a,b);
}

LONG StringTreeFindString(STRINGTREE *st, LPCTSTR str){
 LONG root;
 int cmp;
 if(!st||st->length==0)
  return -1;
 root=st->root;
 while(root!=-1&&(cmp=StringCmp(str,STRTREEITEM(st,root),st->ignoreCase))!=0){
  if(cmp<0)root=st->nodes[root].left;
  else     root=st->nodes[root].right;
 }
 return root;
}
LPBYTE StringTreeGetString(STRINGTREE *st, LONG i){
 if(!st||i<0||i>=st->length)return NULL;
 return STRTREEITEM(st,i);
}
LPVOID StringTreeGetData(STRINGTREE *st, LONG i){
 if(!st||i<0||i>=st->length||!st->szItem||!st->array)return NULL;
 return AddPtr(LPVOID,st->array,i*st->szItem);
}
LPVOID StringTreeFindData(STRINGTREE *st, LPCTSTR str){
 LONG i;
 if(!st||st->length==0||!st->szItem||!st->array)return NULL;
 i=StringTreeFindString(st,str);
 if(i<0)return NULL;
 return AddPtr(LPVOID,st->array,i*st->szItem);
}
static void StringTreeInsertString(STRINGTREE *st, LPCTSTR str, LONG *root){
 STRINGTREEITEM *node;
 if(*root==-1){
  node=&st->nodes[st->length];
  node->left=-1;
  node->right=-1;
  *root=st->length;
 } else {
  int cmp=StringCmp(str,STRTREEITEM(st,*root),st->ignoreCase);
  if(cmp==0)return;//exists already
  else if(cmp<0)
   StringTreeInsertString(st,str,&st->nodes[*root].left);
  else 
   StringTreeInsertString(st,str,&st->nodes[*root].right);
 }
}

LONG StringTreeAddString(STRINGTREE *st, LPCTSTR str){
 DWORD need=st->length+1;
 LONG ret;
 LPVOID ptr;
 if(!st||!str)return -1;
 DWORD len=strlen(str)+1;
 if((ret=StringTreeFindString(st,str))!=-1)
  return ret;
 if(need>st->size){
  need+=(st->size)?st->init:st->grow;
  st->offsets=realloc(st->offsets,sizeof(DWORD)*need);
  if(st->szItem)st->array=realloc(st->array,st->szItem*need);
  st->nodes=realloc(st->nodes,sizeof(STRINGTREEITEM)*need);
  st->size=need;
 }
 need=st->lenStrings+len;
 if(need>st->szStrings){
  need+=(st->szStrings)?512:1024;
  st->strings=realloc(st->strings,need);
  st->szStrings=need;
 }
 strcpy(&st->strings[st->lenStrings],str);
 st->offsets[st->length]=st->lenStrings;
 if(st->szItem){
  ptr=AddPtr(LPVOID,st->array,st->szItem*st->length);
  ZeroMemory(st->array,st->szItem);
 }
 StringTreeInsertString(st,str,&st->root);
 st->lenStrings+=len;
 st->length++; 
 return st->length-1;
}

BOOL StringTreeInitEx(
  STRINGTREE *st,
  DWORD szItem,
  DWORD init,
  DWORD grow,
  BOOL ignoreCase
){
 ZeroMemory(st,sizeof(STRINGTREE));
 st->size=0;
 st->length=0;
 st->init=init?init:10;
 st->szItem=szItem;
 st->grow=grow;
 st->ignoreCase=ignoreCase;
 st->strings=NULL;
 st->offsets=NULL;
 st->array=NULL;
 st->nodes=NULL;
 st->root=-1;
 return TRUE;
}

BOOL StringTreeFree(STRINGTREE *st){
 if(!st)return FALSE;
 free(st->strings);
 free(st->offsets);
 free(st->nodes);
 free(st->array);
 ZeroMemory(st,sizeof(STRINGTREE));
 return TRUE;
}

LPVOID MemArrayReAlloc(ITEMARRAY *ia, LPVOID pv, DWORD sz){
 DWORD i;
 BOOL found=FALSE;
 LPVOID *pBlocks=ia->array;
// DebugOut("[pBlocks=%p,length=%d]",ia->array,ia->length);
 for(i=0;i<ia->length;i++){
  if(pBlocks[i]==pv){
   found=TRUE;
   break;
  }
 }
 if(found){
  if(pv){
   pBlocks[i]=realloc(pBlocks[i],sz);
  } else {
   pBlocks[i]=calloc(1,sz);
  }
  return pBlocks[i];
 } else {
  pBlocks=ItemArrayAllocOnePtr(ia);
  if(!pBlocks)return NULL;
  *pBlocks=malloc(sz);
  return *pBlocks;
 }
}

void MemArrayFreePtr(ITEMARRAY *ia, LPVOID pv){
 LPVOID *pBlocks;
 DWORD i;
 if(!ia||!pv)return;
 pBlocks=ia->array;
 for(i=0;i<ia->length;i++){
  if(pBlocks[i]==pv){
   free(pBlocks[i]);
   pBlocks[i]=NULL;
   return;
  }
 }
}

void MemArrayFreeAll(ITEMARRAY *ia){
 LPVOID *pBlocks;
 DWORD i;
 if(!ia)return;
 pBlocks=ia->array;
 for(i=0;i<ia->length;i++){
  if(pBlocks[i]){
   free(pBlocks[i]);
   pBlocks[i]=NULL;
  }
 }
 ia->length=0;
}

BOOL ItemStackInit(ITEMSTACK *stack, DWORD sz){
 if(!stack)return FALSE;
 ZeroMemory(stack,sizeof(ITEMSTACK));
 ItemArrayInit(&stack->ia,sizeof(LPVOID));
 stack->szRef=sz;
 return TRUE;
}

LPVOID ItemStackGet(ITEMSTACK *stack){
 if(!stack)return NULL;
 if(stack->ia.length>0){
  LPVOID p=ItemArrayPtr(&stack->ia,stack->ia.length-1);
  if(!p)
   return NULL;
  return *(LPVOID*)p;
 } else {
  return NULL;
 }
}

LPVOID ItemStackPush(ITEMSTACK *stack, LPVOID p){
 LPVOID *r; 
 if(!stack)return NULL;
 r=ItemArrayAllocOnePtr(&stack->ia);
 if(!r){
  return NULL;
 }
 *r=malloc(stack->szRef);
 if(p){
  CopyMemory(*r,p,stack->szRef);
 } else {
  ZeroMemory(*r,stack->szRef);
 }
 return *r;
}

void ItemStackPop(ITEMSTACK *stack){
 LPVOID *p;
 if(!stack)return;
 if(stack->ia.length>0){
  p=ItemArrayPtr(&stack->ia,stack->ia.length-1);
  if(p){
   p=*p;
   free(p);
  }
  stack->ia.length--;
 }
}

void ItemStackFree(ITEMSTACK *stack){
 LONG i;
 LPVOID *a=stack->ia.array;
 for(i=0;i<stack->ia.length;i++){
  free(a[i]);
 }
 ItemArrayFree(&stack->ia);
}

---