Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!npeer01.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!border3.nntp.dca.giganews.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!nntp.earthlink.com!news.earthlink.com.POSTED!not-for-mail
NNTP-Posting-Date: Sat, 09 Jun 2012 22:49:20 -0500
Message-ID: <4FD41941.2DB0@mindspring.com>
Date: Sat, 09 Jun 2012 23:49:21 -0400
From: pete <pfiland@mindspring.com>
Reply-To: pfiland@mindspring.com
Organization: PF
X-Mailer: Mozilla 3.04Gold (WinNT; I)
MIME-Version: 1.0
Newsgroups: comp.lang.c
Subject: Re: Breakthrough
References: <jqi6o4$gqf$1@speranza.aioe.org> <4FCD273B.5095@mindspring.com> <4fcdb0ef$0$6481$426a74cc@news.free.fr> <4FCEDA85.66BA@mindspring.com> <d2pts7lcahumia00egio0lh881b1trn9nc@4ax.com> <4FCF56CD.962@mindspring.com> <98pus75mg8q054gcv696u78gvg7gs6h1nk@4ax.com> <4FCFEC9A.C74@mindspring.com> <jqrdv0$p9f$1@speranza.aioe.org>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Lines: 644
X-Usenet-Provider: http://www.giganews.com
NNTP-Posting-Host: 4.156.228.219
X-Trace: sv3-Mm08Yr6bfmmVUJSIpTrF9KIFbRtzLCnlytiWfcwQoP9a35p34artBFRWGWC9LcWij7b3c0qv1Hd1sNP!0rhnrhgMKHYrFkNMr+rvkNM21nmNi0+cNRjoHYfo5kWJsGmYV/KaNxRC3z2XNDbvMvLS1e5YoBxL!Orvi1HCkJDg=
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 20931
X-Received-Bytes: 21074
Xref: csiph.com comp.lang.c:22085

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