Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| Message-ID | <4FD41941.2DB0@mindspring.com> (permalink) |
|---|---|
| Date | 2012-06-09 23:49 -0400 |
| From | pete <pfiland@mindspring.com> |
| Organization | PF |
| Newsgroups | comp.lang.c |
| Subject | Re: Breakthrough |
| References | (4 earlier) <d2pts7lcahumia00egio0lh881b1trn9nc@4ax.com> <4FCF56CD.962@mindspring.com> <98pus75mg8q054gcv696u78gvg7gs6h1nk@4ax.com> <4FCFEC9A.C74@mindspring.com> <jqrdv0$p9f$1@speranza.aioe.org> |
jacob navia wrote:
> Maybe you have some spare time?
>
> I am convinced my code would benefit from your critical eye Pete.
>
> Just download it from
>
> http://code.google.com/p/ccl/
>
> and look at it.
> The file listgen.c contains the templated sort function.
/*
** On 6 September 2008, I posted pqsort.
**
** http://groups.google.com/group/comp.lang.c/msg/6a73e359f4814457
**
** This is a version of listgen.c with a new QSORT based on pqsort.
** It's an introspective quicksort.
** If you like, I can toss in a PRNG for the pivot selection.
** Try it.
*/
/* BEGIN listgen.c */
/*
* Value types generic list routines sample implementation
* ----------------------------------- ------------------
* Thisroutines handle the List container class. This is a very general
* implementation and efficiency considerations aren't yet primordial.
Lists
* can have elements of any size. This implement single linked Lists.
The
* design goals here are just correctness and showing how the
implementation
* of the proposed interface COULD be done.
*
----------------------------------------------------------------------
*/
#include "listgen.h"
#include "ccl_internal.h"
#include <assert.h>
/* Forward declarations */
static LIST_TYPE *SetVTable(LIST_TYPE *result);
static LIST_TYPE * Create(size_t elementsize);
static LIST_TYPE *CreateWithAllocator(size_t elementsize, const
ContainerAllocator * allocator);
#define CONTAINER_LIST_SMALL 2
#define CHUNK_SIZE 1000
static int DefaultListCompareFunction(const void * left, const void *
right, CompareInfo * ExtraArgs)
{
size_t siz = ((LIST_TYPE *)
ExtraArgs->ContainerLeft)->ElementSize;
return memcmp(left, right, siz);
}
/*------------------------------------------------------------------------
Procedure: Contains ID:1
Purpose: Determines if the given data is in the container
Input: The list and the data to be searched
Output: Returns 1 (true) if the data is in there, false
otherwise
Errors: The same as the function IndexOf
------------------------------------------------------------------------*/
static int Contains(const LIST_TYPE * l, const DATA_TYPE data)
{
size_t idx;
return (iList.IndexOf((List *)l, &data, NULL, &idx) < 0) ? 0 : 1;
}
static int Add(LIST_TYPE * l, const DATA_TYPE elem)
{
return iList.Add((List *)l,&elem);
}
/*------------------------------------------------------------------------
Procedure: GetElement ID:1
Purpose: Returns the data associated with a given position
Input: The list and the position
Output: A pointer to the data
Errors: NULL if error in the positgion index
------------------------------------------------------------------------*/
static DATA_TYPE GetElement(const LIST_TYPE * l, size_t position)
{
DATA_TYPE *pdata = iList.GetElement((List *)l,position);
if (pdata == NULL) return ERROR_RETURN;
return *pdata;
}
static DATA_TYPE Back(const LIST_TYPE * l)
{
DATA_TYPE *p = (DATA_TYPE *)iList.Back((List *)l);
if (p == NULL) return ERROR_RETURN;
return *p;
}
static DATA_TYPE Front(const LIST_TYPE * l)
{
DATA_TYPE *p = (DATA_TYPE *)iList.Front((List *)l);
if (p == NULL) return ERROR_RETURN;
return *p;
}
static int CopyElement(const LIST_TYPE * l, size_t position, DATA_TYPE
*outBuffer)
{
return iList.CopyElement((List *)l,position,outBuffer);
}
static int ReplaceAt(LIST_TYPE * l, size_t position, const DATA_TYPE
data)
{
return iList.ReplaceAt((List *)l,position,&data);;
}
static int PushFront(LIST_TYPE * l, const DATA_TYPE pdata)
{
return iList.PushFront((List *)l,&pdata);
}
static int PopFront(LIST_TYPE * l, DATA_TYPE *result)
{
return iList.PushFront((List *)l,result);
}
static int InsertAt(LIST_TYPE * l, size_t pos, const DATA_TYPE pdata)
{
return iList.InsertAt((List *)l,pos,&pdata);
}
static int Erase(LIST_TYPE * l, const DATA_TYPE elem)
{
return iList.Erase((List *)l, &elem);
}
static int EraseAll(LIST_TYPE * l, const DATA_TYPE elem)
{
return iList.EraseAll((List *)l, &elem);
}
static int IndexOf(const LIST_TYPE * l, const DATA_TYPE ElementToFind,
void *ExtraArgs, size_t * result)
{
return iList.IndexOf((List *)l, &ElementToFind, ExtraArgs, result);
}
static size_t Sizeof(const LIST_TYPE * l)
{
if (l == NULL) {
return sizeof(List);
}
return sizeof(LIST_TYPE) + l->ElementSize * l->count + l->count *
offsetof(LIST_ELEMENT,Data);
}
static size_t SizeofIterator(const LIST_TYPE * l)
{
return sizeof(struct ITERATOR(DATA_TYPE));
}
static LIST_TYPE *Load(FILE * stream, ReadFunction loadFn, void *arg)
{
LIST_TYPE *result = (LIST_TYPE *)iList.Load(stream,loadFn,arg);
return SetVTable(result);
}
/*
*
---------------------------------------------------------------------------
*
* Iterators
*
*
---------------------------------------------------------------------------
*/
static int ReplaceWithIterator(Iterator * it, DATA_TYPE data, int
direction)
{
struct ITERATOR(DATA_TYPE) *iter = (struct ITERATOR(DATA_TYPE) *)it;
return iter->ListReplace(it,&data,direction);
}
static Iterator *SetupIteratorVTable(struct ITERATOR(DATA_TYPE) *result)
{
if (result == NULL) return NULL;
result->ListReplace = result->it.Replace;
result->it.Replace = (int (*)(Iterator * , void * , int
))ReplaceWithIterator;
return &result->it;
}
static Iterator *NewIterator(LIST_TYPE * L)
{
return SetupIteratorVTable((struct ITERATOR(DATA_TYPE)
*)iList.NewIterator((List *)L));
}
static int InitIterator(LIST_TYPE * L, void *r)
{
iList.InitIterator((List *)L,r);
SetupIteratorVTable(r);
return 1;
}
static size_t GetElementSize(const LIST_TYPE * l)
{
return sizeof(DATA_TYPE);
}
static int Finalize(LIST_TYPE *l)
{
iList.Finalize((List *)l);
return 1;
}
static LIST_TYPE *Copy(const LIST_TYPE * l)
{
LIST_TYPE *result = (LIST_TYPE *)iList.Copy((List *)l);
return SetVTable(result);
}
static LIST_TYPE *SelectCopy(const LIST_TYPE *l,const Mask *m)
{
LIST_TYPE *result = (LIST_TYPE *)iList.SelectCopy((const List
*)l,m);
return SetVTable(result);
}
/*---------------------------------------------------------------------------*/
/* qsort() - perform a quicksort on an
array */
/*---------------------------------------------------------------------------*/
#ifndef COMPARE_EXPRESSION
#error foo
#define COMPARE_EXPRESSION(l,lo) comp(l, lo)
//COMPAR(A, B) (B > A ? -1 : B != A)
#endif
#define E_TYPE LIST_ELEMENT *e_type
#define GT(A, B) (COMPARE_EXPRESSION((A), (B)) > 0)
#define MOV(A, B) ((void)(*(A) = *(B)))
#define SMALL_PARTITION 8
#define SWAP(A, B, T) \
(MOV((T), (A)), MOV((A), (B)), MOV((B), (T)))
#define SORT_3(A, B, C, T) \
if (GT((A), (B))) { \
MOV((T), (A)); \
if (GT((C), (B))) { \
MOV((A), (B)); \
if (GT((T), (C))) { \
MOV((B), (C)); \
MOV((C), (T)); \
} else { \
MOV((B), (T)); \
} \
} else { \
MOV((A), (C)); \
MOV((C), (T)); \
} \
} else { \
if (GT((B), (C))) { \
MOV((T), (B)); \
if (GT((A), (C))) { \
MOV((B), (A)); \
MOV((A), (C)); \
} else { \
MOV((B), (C)); \
} \
MOV((C), (T)); \
} \
}
#define SIFTDOWNM(P) \
{ \
parent = (P); \
child = parent * 2; \
MOV(&temp, array + parent); \
while (nmemb - parent > parent) { \
if (GT(array + child + 1, array + child)) { \
++child; \
} \
if (GT(array + child, &temp)) { \
MOV(array + parent, array + child); \
parent = child; \
child *= 2; \
} else { \
break; \
} \
} \
if (nmemb == child && GT(array + child, &temp)) { \
MOV(array + parent, array + child); \
parent = child; \
} \
MOV(array + parent, &temp); \
}
typedef E_TYPE;
static void sisort(e_type *array, size_t nmemb)
{
e_type *base, *low, *high, temp;
if (nmemb-- > 1) {
base = array;
do {
low = array++;
if (GT(low, array)) {
high = array;
MOV(&temp, high);
do {
MOV(high, low);
if (--high == base) {
break;
}
--low;
} while (GT(low, &temp));
MOV(high, &temp);
}
} while (--nmemb != 0);
}
}
static void jnloop(e_type *array, size_t nmemb, size_t d)
{
e_type *i, *j, temp;
while (nmemb > SMALL_PARTITION) {
if (!d--) {
hsortm(array, nmemb);
return;
}
i = nmemb / 2 + array;
SWAP(array, i, &temp);
i = 1 + array;
j = --nmemb + array;
SORT_3(j, array, i, &temp);
do {
SWAP(j, i, &temp);
do {
++i;
} while (GT(array, i));
do {
--j;
} while (GT(j, array));
} while (j > i);
SWAP(array, j, &temp);
jnloop(j + 1, nmemb + array - j, d);
nmemb = j - array;
}
sisort(array, nmemb);
}
static void hsortm(e_type *array, size_t nmemb)
{
size_t p, child, parent;
e_type temp;
if (nmemb > 1) {
p = --nmemb / 2;
do {
SIFTDOWNM(p);
} while (p-- != 0);
SWAP(array, array + nmemb, &temp);
while (--nmemb != 0) {
SIFTDOWNM(0);
SWAP(array, array + nmemb, &temp);
}
}
}
static void QSORT(e_type *array, size_t nmemb)
{
size_t d, n;
assert(SMALL_PARTITION >= 4);
d = 2;
for (n = nmemb / 4; n != 0; n /= 2) {
++d;
}
jnloop(array, nmemb, 2 * d);
}
static int Sort(LIST_TYPE * l)
{
LIST_ELEMENT **tab;
size_t i;
LIST_ELEMENT *rvp;
if (l == NULL)
return iError.NullPtrError("Sort");
if (l->count < 2)
return 1;
if (l->Flags & CONTAINER_READONLY) {
l->RaiseError("iList.Sort", CONTAINER_ERROR_READONLY);
return CONTAINER_ERROR_READONLY;
}
tab = l->Allocator->malloc(l->count * sizeof(LIST_ELEMENT *));
if (tab == NULL) {
l->RaiseError("iList.Sort", CONTAINER_ERROR_NOMEMORY);
return CONTAINER_ERROR_NOMEMORY;
}
rvp = l->First;
for (i = 0; i < l->count; i++) {
tab[i] = rvp;
rvp = rvp->Next;
}
QSORT(tab, l->count );
for (i = 0; i < l->count - 1; i++) {
tab[i]->Next = tab[i + 1];
}
tab[l->count - 1]->Next = NULL;
l->Last = tab[l->count - 1];
l->First = tab[0];
l->Allocator->free(tab);
return 1;
}
static LIST_TYPE *SetVTable(LIST_TYPE *result)
{
static int Initialized;
INTERFACE(DATA_TYPE) *intface = &INTERFACE_NAME(DATA_TYPE);
result->VTable = intface;
if (Initialized) return result;
Initialized = 1;
intface->FirstElement = (LIST_ELEMENT *(*)(LIST_TYPE
*))iList.FirstElement;
intface->LastElement = (LIST_ELEMENT *(*)(LIST_TYPE
*))iList.LastElement;
intface->Clear = (int (*)(LIST_TYPE *))iList.Clear;
intface->EraseAt = (int (*)(LIST_TYPE *,size_t))iList.EraseAt;
intface->RemoveRange = (int (*)(LIST_TYPE
*,size_t,size_t))iList.RemoveRange;
intface->Select = (int (*)(LIST_TYPE *,const Mask *))iList.Select;
intface->SetFlags = (unsigned (*)(LIST_TYPE
*,unsigned))iList.SetFlags;
intface->GetFlags = (unsigned (*)(const LIST_TYPE *))iList.GetFlags;
intface->SetDestructor = (DestructorFunction (*)(LIST_TYPE *,
DestructorFunction))iList.SetDestructor;
intface->Apply = (int (*)(LIST_TYPE *, int (Applyfn) (DATA_TYPE *,
void * ), void *))iList.Apply;
intface->Reverse = (int (*)(LIST_TYPE *))iList.Reverse;
intface->SetCompareFunction = (CompareFunction (*)(LIST_TYPE *,
CompareFunction ))iList.SetCompareFunction;
intface->GetRange = (LIST_TYPE *(*)(const LIST_TYPE * , size_t,
size_t))iList.GetRange;
intface->Skip = (LIST_ELEMENT *(*)(LIST_ELEMENT *,
size_t))iList.Skip;
intface->Append = (int (*)(LIST_TYPE *, LIST_TYPE *))iList.Append;
intface->Equal = (int (*)(const LIST_TYPE *, const LIST_TYPE
*))iList.Equal;
intface->InsertIn = (int (*)(LIST_TYPE *, size_t, LIST_TYPE
*))iList.InsertIn;
intface->AddRange = (int (*)(LIST_TYPE *, size_t, const DATA_TYPE
*))iList.AddRange;
intface->SetErrorFunction = (ErrorFunction (*)(LIST_TYPE *,
ErrorFunction))iList.SetErrorFunction;
intface->SetFlags = (unsigned (*)(LIST_TYPE * l, unsigned
newval))iList.SetFlags;
intface->RemoveRange = (int (*)(LIST_TYPE *, size_t,
size_t))iList.RemoveRange;
intface->UseHeap = (int (*)(LIST_TYPE *, const ContainerAllocator
*))iList.UseHeap;
intface->RotateLeft = (int (*)(LIST_TYPE *,
size_t))iList.RotateLeft;
intface->RotateRight = (int (*)(LIST_TYPE *,
size_t))iList.RotateRight;
intface->Save = (int (*)(const LIST_TYPE *, FILE *, SaveFunction,
void *))iList.Save;
intface->Size = (size_t (*)(const LIST_TYPE *))iList.Size;
intface->deleteIterator = (int (*)(Iterator *))iList.deleteIterator;
intface->SplitAfter = (LIST_TYPE *(*)(LIST_TYPE *, LIST_ELEMENT
*))iList.SplitAfter;
return result;
}
/*------------------------------------------------------------------------
Procedure: Create ID:1
Purpose: Allocates a new list object header, initializes the
VTable field and the element size
Input: The size of the elements of the list.
Output: A pointer to the newly created list or NULL if
there is no memory.
Errors: If element size is smaller than zero an error
routine is called. If there is no memory result is
NULL.
------------------------------------------------------------------------*/
static LIST_TYPE *CreateWithAllocator(size_t elementsize, const
ContainerAllocator * allocator)
{
LIST_TYPE *result = (LIST_TYPE
*)iList.CreateWithAllocator(sizeof(DATA_TYPE), allocator);
return SetVTable(result);
}
static LIST_TYPE * Create(size_t elementsize)
{
LIST_TYPE *result = (LIST_TYPE
*)iList.CreateWithAllocator(sizeof(DATA_TYPE), CurrentAllocator);
return SetVTable(result);
}
static LIST_TYPE *InitializeWith(size_t elementSize, size_t n, const
void *Data)
{
LIST_TYPE *result = (LIST_TYPE
*)iList.InitializeWith(sizeof(DATA_TYPE),n,Data);
return SetVTable(result);
}
static LIST_TYPE *InitWithAllocator(LIST_TYPE * result, size_t
elementsize,
const ContainerAllocator * allocator)
{
iList.InitWithAllocator((List *)result,sizeof(DATA_TYPE),allocator);
return SetVTable(result);
}
static LIST_TYPE * Init(LIST_TYPE * result, size_t elementsize)
{
return InitWithAllocator(result, elementsize, CurrentAllocator);
}
static const ContainerAllocator *GetAllocator(const LIST_TYPE * l)
{
if (l == NULL)
return NULL;
return l->Allocator;
}
static LIST_ELEMENT *NextElement(LIST_ELEMENT *le)
{
if (le == NULL) return NULL;
return le->Next;
}
static DATA_TYPE ElementData(LIST_ELEMENT *le)
{
if (le == NULL) return ERROR_RETURN;
return le->Data;
}
static int SetElementData(LIST_TYPE *l,LIST_ELEMENT *le,DATA_TYPE data)
{
return iList.SetElementData((List *)l,(ListElement *)le,&data);
}
static DATA_TYPE Advance(LIST_ELEMENT **ple)
{
LIST_ELEMENT *le;
DATA_TYPE result;
if (ple == NULL) {
iError.NullPtrError("Advance");
return ERROR_RETURN;
}
le = *ple;
if (le == NULL) return ERROR_RETURN;
result = le->Data;
le = le->Next;
*ple = le;
return result;
}
INTERFACE(DATA_TYPE) INTERFACE_NAME(DATA_TYPE) = {
NULL, // Size
NULL, // GetFlags,
NULL, // SetFlags,
NULL, // Clear,
Contains,
Erase,
EraseAll,
Finalize,
NULL, // Apply
NULL, // Equal
Copy,
NULL, // SetErrorFunction,
Sizeof,
NewIterator,
InitIterator,
NULL, // deleteIterator,
SizeofIterator,
NULL, // Save,
Load,
GetElementSize,
/* end of generic part */
Add,
GetElement,
PushFront,
PopFront,
InsertAt,
NULL, // EraseAt
ReplaceAt,
IndexOf,
/* End of sequential container part */
NULL, // InsertIn,
CopyElement,
NULL, // EraseRange,
Sort,
NULL, // Reverse,
NULL, // GetRange,
NULL, // Append,
NULL, // SetCompareFunction,
DefaultListCompareFunction,
NULL, // UseHeap,
NULL, // AddRange,
Create,
CreateWithAllocator,
Init,
InitWithAllocator,
GetAllocator,
NULL, // SetDestructor
InitializeWith,
Back,
Front,
NULL, // RemoveRange,
NULL, // RotateLeft,
NULL, // RotateRight,
NULL, // Select,
SelectCopy,
NULL, // FirstElement,
NULL, // LastElement,
NextElement,
ElementData,
SetElementData,
Advance,
NULL, // Skip,
NULL, // SplitAfter,
};
/* END listgen.c */
--
pete
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 13:38 +0200
Re: Breakthrough MelissA <melis@a.com> - 2012-06-04 14:20 +0200
Re: Breakthrough Juha Nieminen <nospam@thanks.invalid> - 2012-06-04 15:32 +0000
Re: Breakthrough Ike Naar <ike@iceland.freeshell.org> - 2012-06-04 15:44 +0000
Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 18:03 +0200
Re: Breakthrough Ian Collins <ian-news@hotmail.com> - 2012-06-05 10:23 +1200
Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-05 00:31 +0200
Re: Breakthrough Luca Risolia <luca.risolia@studio.unibo.it> - 2012-06-05 01:43 +0200
Re: Breakthrough Martin Shobe <martin.shobe@yahoo.com> - 2012-06-05 00:26 +0000
Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 17:47 +0200
Re: Breakthrough Juha Nieminen <nospam@thanks.invalid> - 2012-06-05 05:36 +0000
Re: Breakthrough Paul <nospam@needed.com> - 2012-06-04 12:32 -0400
Re: Breakthrough MelissA <melis@a.com> - 2012-06-04 21:44 +0200
Re: Breakthrough MelissA <melis@a.com> - 2012-06-04 22:01 +0200
Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 22:42 +0200
Re: Breakthrough MelissA <melis@a.com> - 2012-06-05 00:16 +0200
Re: Breakthrough MelissA <melis@a.com> - 2012-06-05 00:47 +0200
Re: Breakthrough MelissA <melis@a.com> - 2012-06-05 03:34 +0200
Re: Breakthrough 88888 Dihedral <dihedral88888@googlemail.com> - 2012-06-06 17:28 -0700
Re: Breakthrough "BartC" <bc@freeuk.com> - 2012-06-04 17:30 +0100
Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 19:30 +0200
Re: Breakthrough "BartC" <bc@freeuk.com> - 2012-06-04 19:18 +0100
Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-04 20:50 +0200
Re: Breakthrough "BartC" <bc@freeuk.com> - 2012-06-05 00:31 +0100
Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-04 17:23 -0400
Re: Breakthrough Noob <root@localhost> - 2012-06-05 09:10 +0200
Re: Breakthrough Ike Naar <ike@sverige.freeshell.org> - 2012-06-05 08:03 +0000
Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-06 00:20 -0400
Re: Breakthrough Robert Wessel <robertwessel2@yahoo.com> - 2012-06-06 00:06 -0500
Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-06 09:10 -0400
Re: Breakthrough Robert Wessel <robertwessel2@yahoo.com> - 2012-06-06 09:23 -0500
Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-06 19:49 -0400
Re: Breakthrough Willem <willem@toad.stack.nl> - 2012-06-07 15:10 +0000
Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-08 01:37 +0200
Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-08 09:55 -0400
Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-08 21:26 -0400
Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-09 23:49 -0400
Re: Breakthrough 88888 Dihedral <dihedral88888@googlemail.com> - 2012-06-11 06:50 -0700
Re: Breakthrough pete <pfiland@mindspring.com> - 2012-06-11 22:36 -0400
Re: Breakthrough Ian Collins <ian-news@hotmail.com> - 2012-06-05 10:02 +1200
Re: Breakthrough jacob navia <jacob@spamsink.net> - 2012-06-05 00:26 +0200
csiph-web