Na komputerze 64-bitowym wskaźniki są zazwyczaj wyrównane do granic wyrazów, które są wielokrotnością ośmiu bajtów. W rezultacie najniższe trzy bity wskaźnika będą zerowe. W konsekwencji, jeśli struktura danych potrzebuje trzech bitów informacji, może spakować je do najniższych trzech bitów wskaźnika. W ten sposób:
- Aby śledzić wskaźnik, usuń najniższe trzy bity wartości wskaźnika, a następnie usuń zaznaczenie.
- Aby odczytać którykolwiek z trzech bitów, zamaskuj pozostałe bity w wskaźniku i przeczytaj je bezpośrednio.
Takie podejście jest dość standardowe i nie traci możliwości wskazywania na adresy, ponieważ zazwyczaj ze względu na wydajność lub ze względu na sprzęt komputerowy i tak nie chciałbyś mieć wskaźników niezgodnych.
Nie jestem pewien, dlaczego nie zrobili tego w 32-bitowym przypadku, ponieważ za pomocą trzech wskazówek mogli z łatwością ukryć potrzebne bity przy użyciu tej samej sztuczki, ale z dwoma bitami na wskaźnik. Domyślam się, że chodzi o wydajność: jeśli umieścisz bity w dolnej części wskaźników, zwiększysz koszt podążania za wskaźnikiem z powodu obliczeń koniecznych do wyczyszczenia bitów. Zauważ, na przykład, że w 64-bitowym przypadku bity są spakowane do wskaźnika nadrzędnego, który jest używany tylko w rzadkich operacjach, takich jak obliczanie następców z kolejnością lub wykonywanie rotacji we wstawianiu lub usuwaniu. Dzięki temu wyszukiwanie jest szybkie. W przypadku 32-bitowym, aby ukryć 3 bity, implementacja musiałaby użyć niższych bitów dwóch wskaźników, z których jeden musiałby być lewym lub prawym wskaźnikiem. Domyślam się, że wydajność spowalniania wyszukiwań w drzewie nie była warta oszczędności miejsca, więc postanowili po prostu wziąć pamięć i przechowywać je oddzielnie. To tylko spekulacja, ponieważ absolutnie mogliby przechowywać bity w spodniach swoich wskaźników, gdyby chcieli.
Na marginesie: jeśli implementacja korzystała z drzewa czerwonego/czarnego, a nie z drzewa AVL, potrzebne byłyby tylko dwa bity informacji: odrobinę do sprawdzenia, czy węzeł jest czerwony, czy czarny, i nieco aby określić, czy węzeł jest lewym, czy prawym dzieckiem. W takim przypadku wymagane dwa bity zawsze można spakować do 32-bitowego wskaźnika. Jest to jeden z powodów, dla których czerwono-czarne drzewa są popularne.
Mam nadzieję, że to pomoże!
Zadziwiająco! Dziękuję Ci. – Igor
Należy zauważyć, że plik źródłowy znajduje się w usr/src/uts/..., który jest drzewem źródłowym jądra, a nie bibliotekami przestrzeni użytkownika, więc prawdopodobnie nie było potrzeby optymalizacji 32-bitowej implementacji w przypadkach użycia, które mieli kiedy został zaprojektowany. – alanc
sys/avl.h jest również często używany w przestrzeni użytkownika, np. sol. przez linker środowiska wykonawczego i kilka innych bibliotek. – Igor