Algorithm-RectanglesContainingDot_XS
view release on metacpan or search on metacpan
ck_eval|||
ck_exec|||
ck_exists|||
ck_exit|||
ck_ftst|||
ck_fun|||
ck_glob|||
ck_grep|||
ck_index|||
ck_join|||
ck_lengthconst|||
ck_lfun|||
ck_listiob|||
ck_match|||
ck_method|||
ck_null|||
ck_open|||
ck_repeat|||
ck_require|||
ck_retarget|||
ck_return|||
mess_nocontext|||vn
mess||5.006000|v
method_common|||
mfree||5.007002|n
mg_clear|||
mg_copy|||
mg_dup|||
mg_find|||
mg_free|||
mg_get|||
mg_length||5.005000|
mg_localize|||
mg_magical|||
mg_set|||
mg_size||5.005000|
mini_mktime||5.007002|
missingterm|||
mode_from_discipline|||
modkids|||
mod|||
moreswitches|||
unshare_hek_or_pvn|||
unshare_hek|||
unsharepvn||5.004000|
unwind_handler_stack|||
upg_version||5.009000|
usage|||
utf16_to_utf8_reversed||5.006001|
utf16_to_utf8||5.006001|
utf8_distance||5.006000|
utf8_hop||5.006000|
utf8_length||5.007001|
utf8_mg_pos_init|||
utf8_mg_pos|||
utf8_to_bytes||5.006001|
utf8_to_uvchr||5.007001|
utf8_to_uvuni||5.007001|
utf8n_to_uvchr|||
utf8n_to_uvuni||5.007001|
utilize|||
uvchr_to_utf8_flags||5.007003|
uvchr_to_utf8|||
yyerror|||
yylex|||
yyparse|||
yywarn|||
);
if (exists $opt{'list-unsupported'}) {
my $f;
for $f (sort { lc $a cmp lc $b } keys %API) {
next unless $API{$f}{todo};
print "$f ", '.'x(40-length($f)), " ", format_version($API{$f}{todo}), "\n";
}
exit 0;
}
# Scan for possible replacement candidates
my(%replace, %need, %hints, %depends);
my $replace = 0;
my $hint = '';
#ifndef ERRSV
# define ERRSV get_sv("@",FALSE)
#endif
#ifndef newSVpvn
# define newSVpvn(data,len) ((data) \
? ((len) ? newSVpv((data), (len)) : newSVpv("", 0)) \
: newSV(0))
#endif
/* Hint: gv_stashpvn
* This function's backport doesn't support the length parameter, but
* rather ignores it. Portability can only be ensured if the length
* parameter is used for speed reasons, but the length can always be
* correctly computed from the string argument.
*/
#ifndef gv_stashpvn
# define gv_stashpvn(str,len,create) gv_stashpv(str,create)
#endif
/* Replace: 1 */
#ifndef get_cv
# define get_cv perl_get_cv
#endif
** In random input, N in a row low should only happen with
** probability 2^(1-N), so we can risk that we are dealing
** with orderly input without paying much when we aren't.
*/
#define RTHRESH (6)
/*
** Overview of algorithm and variables.
** The array of elements at list1 will be organized into runs of length 2,
** or runs of length >= 2 * PTHRESH. We only try to form long runs when
** PTHRESH adjacent pairs compare in the same way, suggesting overall order.
**
** Unless otherwise specified, pair pointers address the first of two elements.
**
** b and b+1 are a pair that compare with sense ``sense''.
** b is the ``bottom'' of adjacent pairs that might form a longer run.
**
** p2 parallels b in the list2 array, where runs are defined by
** a pointer chain.
**
** we start q at r and try to push it further towards t.
** If b through r is NOT a run, we detect the wrong order at (p-1,p).
** In any event, after the check (if any), we have two main cases.
**
** 1) Short run. b <= q < p <= r <= t.
** b through q is a run (perhaps trivial)
** q through p are uninteresting pairs
** p through r is a run
**
** 2) Long run. b < r <= q < t.
** b through q is a run (of length >= 2 * PTHRESH)
**
** Note that degenerate cases are not only possible, but likely.
** For example, if the pair following b compares with opposite sense,
** then b == q < p == r == t.
*/
static IV
dynprep(pTHX_ SV **list1, SV **list2, size_t nmemb, SVCOMPARE_t cmp)
{
* on others. The most likely explanation was platform-specific
* differences in cache sizes and relative speeds.
*
* The quicksort divide-and-conquer algorithm guarantees that, as the
* problem is subdivided into smaller and smaller parts, the parts
* fit into smaller (and faster) caches. So it doesn't matter how
* many levels of cache exist, quicksort will "find" them, and,
* as long as smaller is faster, take advanatge of them.
*
* By contrast, consider how the original mergesort algorithm worked.
* Suppose we have five runs (each typically of length 2 after dynprep).
*
* pass base aux
* 0 1 2 3 4 5
* 1 12 34 5
* 2 1234 5
* 3 12345
* 4 12345
*
* Adjacent pairs are merged in "grand sweeps" through the input.
* This means, on pass 1, the records in runs 1 and 2 aren't revisited until
* Note that we merge runs 1 and 2 immediately after copying them,
* while they are still likely to be in fast cache. Similarly,
* run 3 is merged with run 12 while it still may be lingering in cache.
* This implementation should therefore enjoy much of the cache-friendly
* behavior that quicksort does. In addition, it does less copying
* than the original mergesort implementation (only runs 1 and 2 are copied)
* and the "balancing" of merges is better (merged runs comprise more nearly
* equal numbers of original runs).
*
* The actual cache-friendly implementation will use a pseudo-stack
* to avoid recursion, and will unroll processing of runs of length 2,
* but it is otherwise similar to the recursive implementation.
*/
typedef struct {
IV offset; /* offset of 1st of 2 runs at this level */
IV runs; /* how many runs must be combined into 1 */
} off_runs; /* pseudo-stack element */
static void
sortsv(pTHX_ SV **base, size_t nmemb, SVCOMPARE_t cmp)
( run in 0.628 second using v1.01-cache-2.11-cpan-65fba6d93b7 )