view release on metacpan or  search on metacpan

Permute.xs  view on Meta::CPAN

/* 
   Permute.xs

   Copyright (c) 1999 - 2008  Edwin Pratomo

   You may distribute under the terms of either the GNU General Public
   License or the Artistic License, as specified in the Perl README file,
   with the exception that it cannot be placed on a CD-ROM or similar media
   for commercial distribution without the prior approval of the author.

*/

#ifdef __cplusplus
extern "C" {
#endif
#include "EXTERN.h"
#include "perl.h"
#include "XSUB.h"
#include <stdio.h>
#include "coollex.h"
#include "multicall.h"
#include "ppport.h"
#ifdef __cplusplus
}
#endif

/* (Robin) This hack is stolen from Graham Barr's Scalar-List-Utils package.
   The comment therein runs:

   Some platforms have strict exports. And before 5.7.3 cxinc (or Perl_cxinc)
   was not exported. Therefore platforms like win32, VMS etc have problems
   so we redefine it here -- GMB

   With any luck, it will enable us to build under ActiveState Perl.
*/
#if PERL_VERSION < 7/* Not in 5.6.1. */
#  ifdef cxinc
#    undef cxinc
#  endif
#  define cxinc() my_cxinc(aTHX)
static I32
my_cxinc(pTHX)
{
    cxstack_max = cxstack_max * 3 / 2;
    Renew(cxstack, cxstack_max + 1, struct context);      /* XXX should fix CXINC macro */
    return cxstack_ix + 1;
}
#endif

/* (Robin) Assigning to AvARRAY(array) expands to an assignment which has a typecast on the left-hand side.
 * So it was technically illegal, but GCC is decent enough to accept it
 * anyway. Unfortunately other compilers are not usually so forgiving...
 */
#if PERL_VERSION >= 9
#  define AvARRAY_set(av, val) ((av)->sv_u.svu_array) = val
#else
#  define AvARRAY_set(av, val) ((XPVAV*) SvANY(av))->xav_array = (char*) val
#endif

typedef unsigned int  UINT;
typedef unsigned long ULONG;

#ifdef USE_LINKEDLIST
typedef struct record {
   int info;
   struct record *link;
} listrecord;
#endif

typedef struct {
    bool is_done;
    SV **items;
    SV* aryref;
    UV num;
#ifdef USE_LINKEDLIST
    listrecord *ptr_head, **ptr, **pred;
#else
    UINT *loc; /* location of n in p[] */
    UINT *p;
#endif
    COMBINATION *c;
} Permute;

/* private _next */
#ifdef USE_LINKEDLIST
static bool _next(UV n, listrecord *ptr_head, listrecord **ptr, listrecord **pred)
#else
static bool _next(UV n, UINT *p, UINT *loc)
#endif
{
#ifndef USE_LINKEDLIST
    int i;
#endif
    bool is_done = FALSE;

    if (n <= 1) /* termination condition */
        return TRUE;

#ifdef USE_LINKEDLIST
    /* less arithmetic */
    if (ptr[n]->link != NULL) {
        pred[n]->link = ptr[n]->link;
        pred[n] = pred[n]->link;
        ptr[n]->link = pred[n]->link;
        pred[n]->link = ptr[n];
    } else {
        pred[n]->link = NULL;
        is_done = _next(n - 1, ptr_head, ptr, pred);
        ptr[n]->link = ptr_head->link;
        ptr_head->link = ptr[n]; /* change head of list */