This is dlstutil.c in view mode; [Download] [Up]
/* dlist v1.0.0 Dynamic list library
* Copyright (c) 1994 Bill Bereza
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Library General Public
* License as published by the Free Software Foundation; either
* version 2 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
* Library General Public License for more details.
*
* You should have received a copy of the GNU Library General Public
* License along with this library; if not, write to the Free
* Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*
*
* To reach the author
*
* email:
* berezaw@river.it.gvsu.edu ac368@leo.nmc.edu
*
* $Log: dlstutil.c,v $
* Revision 1.6 94/12/22 02:48:12 berezaw
* more qsort fiddling
*
* Revision 1.5 94/12/20 23:07:34 berezaw
* more qsort fiddling
*
* Revision 1.4 94/12/20 22:53:21 berezaw
* did some fiddling with qsort
*
* Revision 1.3 94/12/19 22:19:18 berezaw
* *** empty log message ***
*
* Revision 1.2 94/12/19 21:17:36 berezaw
* finished quick sort function
*
* Revision 1.1 94/12/19 13:05:26 berezaw
* Initial revision
*
*
* $Header: /Users/berezaw/src/dlist/RCS/dlstutil.c,v 1.6 94/12/22 02:48:12 berezaw Exp $
*/
#include "dlist.h"
void *arrdlist(DLIST *ostr)
{
void *index;
register size_t i=0;
void **charray;
if(ostr==NULL)
return NULL;
if((charray=calloc(dlistels(ostr)+1, sizeof(index))) != NULL) {
index=ostr->_first;
while(index != NULL) {
charray[i++]=((_DEL *)index)->_element;
index=((_DEL *)index)->_next;
}
charray[i]=NULL;
}
return charray;
}
DLIST *__dlistcat(DLIST *ostr, DLIST *addstr)
{
void *pchar;
if(!ostr || !addstr)
return NULL;
if(!delsize(ostr) && !delsize(addstr))
for(pchar=addstr->_first;pchar;pchar=((_DEL *)pchar)->_next)
daddelv(ostr, ((_DEL *)pchar)->_element, ((_DELV *)pchar)->_elvsize);
else
for(pchar=addstr->_first;pchar;pchar=((_DEL *)pchar)->_next)
daddel(ostr, ((_DEL *)pchar)->_element);
return ostr;
}
DLIST *dlstinsertsort(DLIST *tosort, int (*elcmp)(__DELCMPARGS))
{
_DEL *j, *p;
void *tmp;
_DELV *jv, *pv;
size_t tmpv;
if(dlistsize(tosort)<2)
return NULL;
if(delsize(tosort)) {
for(p=((_DEL *)tosort->_first)->_next;p;p=p->_next) {
tmp=p->_element;
for(j=p;j->_prev ? ((*elcmp)(tmp,j->_prev->_element)<0) : 0;j=j->_prev)
j->_element=j->_prev->_element;
j->_element=tmp;
}
}
else {
for(pv=((_DELV *)tosort->_first)->_next;pv;pv=pv->_next) {
tmp=pv->_element; tmpv=pv->_elvsize;
for(jv=pv;jv->_prev ? ((*elcmp)(tmp,jv->_prev->_element)<0) : 0;jv=jv->_prev) {
jv->_element=jv->_prev->_element;
jv->_elvsize=jv->_prev->_elvsize;
}
jv->_element=tmp;
jv->_elvsize=tmpv;
}
}
return tosort;
}
#define __QSCUT 10
#define __DELSWAP(a,b,t)\
(t)=(a)->_element;\
(a)->_element=(b)->_element;\
(b)->_element=(t)
#define __DELVSWAP(a,b,t,st)\
(t)=(a)->_element;\
(st)=(a)->_elvsize;\
(a)->_element=(b)->_element;\
(a)->_elvsize=(b)->_elvsize;\
(b)->_element=(t);\
(b)->_elvsize=(st)
void __dlstqsort(_DEL *first, _DEL *last, size_t left, size_t right,\
int (*elcmp)(__DELCMPARGS))
{
_DEL *i, *j, *pivot;
size_t in, jn;
void *tmp;
if((left+__QSCUT)>right)
return;
/* median of 3 */
pivot=first->_next->_next->_next->_next;
if((*elcmp)(first->_element, pivot->_element)>0) {
__DELSWAP(first,pivot,tmp);
}
if((*elcmp)(first->_element, last->_element)>0) {
__DELSWAP(first,last,tmp);
}
if((*elcmp)(pivot->_element, last->_element)>0) {
__DELSWAP(pivot,last,tmp);
}
__DELSWAP(pivot,last->_prev,tmp);
in=left; jn=right-1;
i=first; j=last->_prev;
do {
do { in++; i=i->_next; } while((*elcmp)(i->_element,pivot->_element)<0);
do { jn--; j=j->_prev; } while((*elcmp)(j->_element,pivot->_element)>0);
__DELSWAP(i,j,tmp);
} while(jn>in);
__DELSWAP(i,j,tmp);
__DELSWAP(i,last->_prev,tmp);
__dlstqsort(first,i->_prev,left, in-1, elcmp);
__dlstqsort(i->_next,last,in+1,right, elcmp);
}
void __dlstqsortv(_DELV *first, _DELV *last, size_t left, size_t right,\
int (*elcmp)(__DELCMPARGS))
{
_DELV *i, *j, *pivot;
size_t in, jn, ts;
void *tmp;
if((left+__QSCUT)>right)
return;
/* median of 3 */
pivot=first->_next->_next->_next->_next;
if((*elcmp)(first->_element, pivot->_element)>0) {
__DELVSWAP(first,pivot,tmp,ts);
}
if((*elcmp)(first->_element, last->_element)>0) {
__DELVSWAP(first,last,tmp,ts);
}
if((*elcmp)(pivot->_element, last->_element)>0) {
__DELVSWAP(pivot,last,tmp,ts);
}
__DELVSWAP(pivot,last->_prev,tmp,ts);
in=left; jn=right-1;
i=first; j=last->_prev;
do {
do { in++; i=i->_next; } while((*elcmp)(i->_element,pivot->_element)<0);
do { jn--; j=j->_prev; } while((*elcmp)(j->_element,pivot->_element)>0);
__DELVSWAP(i,j,tmp,ts);
} while(jn>in);
__DELVSWAP(i,j,tmp,ts);
__DELVSWAP(i,last->_prev,tmp,ts);
__dlstqsortv(first,i->_prev,left, in-1, elcmp);
__dlstqsortv(i->_next,last,in+1,right, elcmp);
}
DLIST *dlstsort(DLIST *tosort, int (*elcmp)(__DELCMPARGS))
{
if(delsize(tosort))
__dlstqsort(tosort->_first, tosort->_last, 1, dlistsize(tosort), elcmp);
else
__dlstqsortv(tosort->_first, tosort->_last,1, dlistsize(tosort), elcmp);
(void)dlstinsertsort(tosort, elcmp);
return tosort;
}
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.