Zajímavé úlohy pro programátory v C a C++ #3

Zkouškové období již začalo, ale (zatím) toho není tolik, abych nemohl přinést další zajímavou úlohu :). Tentokrát si vyzkoušíme tvorbu maker.

Zadání

Zadání je poměrně jednoduché: napište makro SWAP, které prohodí hodnoty dvou proměnných (l-hodnot). Uvažujte pouze prohození proměnných typu char, short, int, long, float, double a ukazatelů na tyto typy.

Pokud by se vám toto nepodařilo, tak můžete zkusit implementovat zjednodušenou verzi tohoto makra (pojmenované SWAP_INT), které prohodí hodnoty dvou předaných proměnných typu int a bude fungovat korektně za všech situací.

Málokdy se stává, že existuje pouze jedno správné řešení, takže pokud už někdo s nějakým řešením přišel před vámi, můžete zkusit vymyslet řešení nové (a třeba i lepší).

Omezení

Makro musí být implementačně nezávislé (tj nepoužívejte konstrukty s nespecifikovaným či nedefinovaným chováním). Dále musí fungovat při použití jak v programech podle standardu C99, tak C++98. Nesmíte definovat žádné vlastní funkce.

Řešení

Nejdříve se podíváme na tu jednodušší variantu.

Jednodušší varianta - SWAP_INT

První, co by vás mohlo napadnout, tak je využít známý XOR trik:
#define SWAP_INT(x, y) ((x) ^= (y) ^= (x) ^= (y))

Problém tohoto "řešení" je ten, že výsledek jeho vyhodnocení není definován - viz standard: Between the previous and next sequence point a scalar object shall have its stored value modified at most once...; otherwise the behavior is undefined.". Dochází zde totiž dvakrát k modifikaci proměnné x a tyto modifikace nejsou odděleny žádným sekvenčním bodem.

Zkusme tedy toto "řešení" rozdělit na tři části:

#define SWAP_INT(x, y) { \
    (x) ^= (y);          \
    (y) ^= (x);          \
    (x) ^= (y);          \
}

Nyní už je výsledek této operace definován, ale při testování narazíme na další z problémů - pokud zkusíme prohodit proměnnou samu se sebou, čili SWAP_INT(a, a), tak výsledkem bude 0 uložená v hodnotě a nezávisle na přechozí hodnotě této proměnné.

Řešení tohoto problému je nasnadě:

#define SWAP_INT(x, y) { \
    if (x != y) {        \
        (x) ^= (y);      \
        (y) ^= (x);      \
        (x) ^= (y);      \
    }                    \
}

Paráda, problém vyřešen. Je zde ale ještě jeden zádrhel, který není hned vidět. Ukáže se, až se pokusíte makro použít např. takto:

if (...)
    SWAP_INT(a, b);
else
    // ...

Po preprocessingu totiž dostaneme následující kód, který není syntaktický správný (nadbytečný středník před else).

if (...) {
    if (x != y) {
        (x) ^= (y);
        (y) ^= (x);
        (x) ^= (y);
    }
};
else
    // ...

Jedno z možných řešení je následující:

#define SWAP_INT(x, y) do { \
    if (x != y) { \
        (x) ^= (y); \
        (y) ^= (x); \
        (x) ^= (y); \
    } \
} while (0)

Nyní už bude fungovat i poslední konstrukce, takže toto řešení bych považoval za finální. Pokud by vás napadla situace, kdy selže, určitě napište komentář. Jediný problém, který mě ještě napadl, je vícenásobné vyhodnocení parametru makra, ale s tím (asi) už nic neudělám.

Mimochodem, možná vás napadlo některé z těchto řešení, které ale nefungují za každé situace:

• Použít sčítání, násobení, dělení apod. - místo tří XOR operací lze použít i podobnou konstrukci složenou z aritmetických operací, která ovšem nebude fungovat, pokud dojde k overflow, proto je logická operace XOR lepší.
• Použít dočasnou proměnnou - nelze zaručit, že jméno dočasné proměnné nebude kolidovat např. se jménem swapované proměnné. Pokud by vás napadlo použít k vytvoření unikátního názvu dočasné proměnné "preprocesorové lepítko" ##, tak skončíte v okamžiku, kdy se někdo pokusí prohodit dvě místa v poli, např. SWAP_INT(p[0], p[1]), protože název proměnné nemůže obsahovat znaky [ a ].

Generické makro - SWAP

Zatímco u té jednodušší varianty jsem v zadání vyžadoval řešení, která bude fungovat korektně za všech situací, tak u generického makra jsem to nevyžadoval, protože se mě samotnému (při zadávání úkolu) nepodařilo přijít na řešení, které by bylo funkční vždy. Mrkneme tedy na to, co se mě podařilo vytvořit a ke každému řešení napíšu pro a proti.

Protože se požadovalo, aby makro fungovalo i s jinými datovými typy než je int, tak řešení založené na aritmetických či logických operací by nefungovalo, takže bylo třeba najít jinou cestu.

Obě řešení sdílejí následující nevýhody...

• Využívají dočasnou proměnnou, takže nelze zaručit, že její jméno nebude kolidovat se jménem předávané proměnné (lze pouze snížit pravděpodobnost, že se tak stane použitím podtržítka před názvem této proměnné).
• Podobně jako u jednodušší varianty by mohlo být problémem vícenásobné vyhodnocení parametru makra.

...a následující výhody:

• Funkční i za situací jako je prohození proměnné sama se sebou či použitelné v tělě podmíněného příkazu před else.
• Lze prohodit dvě místa v poli, např. SWAP(p[0], p[1]).

První řešení

#define SWAP(x, y, type) do { \
    type _tmp = (x); \
    (x) = (y); \
    (y) = _tmp; \
} while (0)

Specifické nevýhody:

• Kvůli vytváření dočasné proměnné je nutné zadat typ proměnných jako třetí parametr makra.

Specifické výhody:

• Lze prohodit dvě proměnné deklarované jako registrové.
• Většina překladačů dočasnou proměnnou vyoptimalizuje, takže je prohození opravdu rychlé a bez dalších prostorových nároků.

Druhé řešení

#define SWAP(x, y) do { \
    char _tmp[sizeof(x)]; \
    memcpy(_tmp, &(x), sizeof(x)); \
    memcpy(&(x), &(y), sizeof(x)); \
    memcpy(&(y), _tmp, sizeof(x)); \
} while (0)

Specifické nevýhody:

• Nelze prohodit dvě proměnné deklarované jako registrové.
• Zřejmě pomalejší, než první řešení (kvůli trojnásobnému volání funkce memcpy) - prakticky jsem ale netestoval, takže to berte s rezervou.

Specifické výhody:

• Není třeba předávat typ proměnných jako třetí parametr makra.

Závěr

Pokud chcete prohodit hodnoty dvou proměnných, nejlepší řešení (které bude funkční za všech okolností) bude si buď na to napsat funkci (v případě C++ šablonu funkce), nebo si přímo na místě prohození vytvořit dočasnou proměnnou či v C++ použít šablonu std::swap.