Niedawno zacząłem porządkować swoje projekty i zdecydowałem, że chcę utworzyć osobiste repozytorium przydatnych fragmentów kodu. Znalazłem ten kod bitmapowy między nimi i mocno go zredagowałem i byłbym wdzięczny, gdyby ktoś mógł go przejrzeć, ponieważ nie jestem taki przyzwyczajony do operacji bitowych i tym podobnych. Czy kod jest wystarczająco przenośny, czy powinny nastąpić zmiany?
bitmap.h
#ifndef BITMAP__ #define BITMAP__ #define BIT (8*sizeof(byte)) #define BITMAP_NOTFOUND -1 typedef enum{false=0, true} bool; typedef unsigned char byte; bool bitmapGet (byte *, int); void bitmapSet (byte *, int); void bitmapReset (byte *, int); int bitmapSearch(byte *, bool, int, int); #endif bitmap.c
#include "bitmap.h" static bool get (byte, byte); static void set (byte *, byte); static void reset(byte *, byte); /* CAREFUL WITH pos AND BITMAP SIZE! */ bool bitmapGet(byte *bitmap, int pos) { /* gets the value of the bit at pos */ return get(bitmap[pos/BIT], pos%BIT); } void bitmapSet(byte *bitmap, int pos) { /* sets bit at pos to 1 */ set(&bitmap[pos/BIT], pos%BIT); } void bitmapReset(byte *bitmap, int pos) { /* sets bit at pos to 0 */ reset(&bitmap[pos/BIT], pos%BIT); } int bitmapSearch(byte *bitmap, bool n, int size, int start) { /* Finds the first n value in bitmap after start */ /* size is the Bitmap size in bytes */ int i; /* size is now the Bitmap size in bits */ for(i = start+1, size *= BIT; i < size; i++) if(bitmapGet(bitmap,i) == n) return i; return BITMAP_NOTFOUND; } static bool get(byte a, byte pos) { /* pos is something from 0 to 7*/ return (a >> pos) & 1; } static void set(byte *a, byte pos) { /* pos is something from 0 to 7*/ /* sets bit to 1 */ *a |= 1 << pos; } static void reset(byte *a, byte pos) { /* pos is something from 0 to 7*/ /* sets bit to 0 */ *a &= ~(1 << pos); } Komentarze
- Dla każdego, kto nadal śledzi ten post, przekazałem kod na github tutaj . Dodałem również wszystkie twoje komentarze jako problemy. Dziękuję za komentarze i zacznę je wdrażać.
Odpowiedź
Jeśli spodziewasz się, że Twój kod kiedykolwiek będzie używane z C ++ (którym jest dużo kodu C), nie powinieneś używać żadnych identyfikatorów z podwójnym podkreśleniem.
#ifndef BITMAP__ // ^^ May cause problems in C++ Ponieważ jest to zarezerwowane dla implementacji w C ++. Również termin BITMAP jest bardzo ogólny i jest bardzo prawdopodobne, że będziesz kolidować z innymi bibliotekami, próbując uczynić go bardziej unikalnym dla swojego projektu.
Zakładasz, że znak ma 8 bitów.
#define BIT (8*sizeof(byte)) Norma tego nie mówi (ma co najmniej 8 bitów), ale w rzeczywistości jest zdefiniowana przez makro CHAR_BITS, więc powinieneś użyć:
#define BIT (CHAR_BITS*sizeof(byte)) Większość ludzi po raz pierwszy zobaczy Twój kod w pliku nagłówkowym i spróbuje zrozumieć, jak go używać. Dlatego umieszczenie nazw parametrów w pliku nagłówkowym jest prawdopodobnie dobrym pomysłem, ponieważ pomaga udokumentować ich użycie.
bool bitmapGet (byte *, int); void bitmapSet (byte *, int); void bitmapReset (byte *, int); int bitmapSearch(byte *, bool, int, int); Dodatkowo działanie bitmapSearch nie jest oczywiste, więc komentarz na temat jego użycia w nagłówku byłby prawdopodobnie dobrym pomysłem. Właściwie krótka notka o tym, jak pierwszy parametr może być tablicą, prawdopodobnie byłaby dobrym pomysłem (ponieważ nie jest to oczywiste bez czytania kodu).
Uważaj na komentarze:
/* pos is something from 0 to 7*/ Jest to prawdą tylko wtedy, gdy przyjmujesz założenia (A: ten rozmiar (bajt) == 1 B: mnożymy to przez 8). Komentarz powinien wyglądać następująco:
/* pos is a value between [0, BIT) */ Zwróć uwagę na użycie „[” po lewej i „)” po prawej. Jest to notacja matematyczna wskazująca, że 0 jest włącznie, a BIT nie jest uwzględniony w zakresie (jest to powszechne w dokumentacji C / C ++).
Odpowiedź
-
Twoje typy są niepotrzebne – po prostu użyj unsigned char i int, tak jak zrobiłaby to biblioteka standardowa.
-
W tym samym temacie, twoje wyliczenie bool jest niepotrzebne, ponieważ w C niezerowe oznacza stan rzeczywisty. Potwierdzasz to samodzielnie, ponieważ metoda get () zakłada, że wartość 1 jest prawdziwa. Każdy to zakłada, więc typ jest zbędny. Co więcej, jest to również błędne, ponieważ jeśli zmienię twoje wyliczenie na
typedef enum{true=0, false} bool;, twoja funkcja zawodzi, nawet jeśli jest to logicznie rozsądne.
Jeśli chcesz użyć takiej wartości bool, powinieneś wyraźnie zwrócić jedną z jej wartości:
return ((a >> pos) & 1) ? true : false;, ale naprawdę nie ma to sensu. Po prostu zwróć int, tak jak by to zrobiła biblioteka standardowa.
-
bitmapGet () zwracanie wartości bool wydaje mi się błędnie nazwane. Bity bitmapy mają wartości 1 i 0, a nie prawda i fałsz (nawet jeśli są obecnie takie same). Nazwanie go bitmapIsSet () byłoby bardziej logiczne.
-
sizeof (char) jest z definicji 1, więc BIT można zastąpić CHAR_BIT
-
Nawiasy otwierające dla funkcji zwykle znajdują się w kolumnie 0
-
Kolejność parametrów dla funkcji bitmapSearch byłaby bardziej logiczna, gdyby rozmiar występował po tym, do czego się odnosi (bitmapa).
-
Parametr początkowy dla bitmapSearch jest nieprawidłowy. Aby określić wyszukiwanie zaczynające się od bitu 0 (na pewno najczęściej), wywołujący musi przekazać -1 !!
-
Po co przekazywać parametr „pos” jako „bajt”? Zdefiniowałeś „bajt” do reprezentowania bajtów mapy bitowej, a „pos” z pewnością nie jest jednym z nich. Otrzymasz ostrzeżenia kompilatora, jeśli są włączone (powinny być) dotyczące przekazywania argumentów o różnych szerokościach z powodu prototypów. Ograniczenie „pos” do bajtu może dodać dodatkową instrukcję maszynową (spójrz na asembler), a nic nie daje. Gdybyś mógł zdefiniować typ pos_t z zakresem 0..7, który wydaje się pożądany, możesz argumentować, że był w jakiś sposób poprawny, ale ponieważ nie możesz tego zrobić w C i wyraźnie wartość bajtu ma zakres 0 .. 255, nie jest to lepsze niż użycie int.
Odpowiedź
Czy nie zapytać o wydajność, ale możesz przyspieszyć bitmapSearch w przypadku rzadkich bitmap, patrząc najpierw po jednym bajcie. Jeśli szukasz 1, możesz pominąć bajty o wartości 0x00 i jeśli szukając 0, możesz pominąć bajty o wartości 0xFF, a następnie przeskanować bity następnego bajtu lub użyć na nim tabeli przeglądowej.
Jeśli chodzi o API, możesz dodać
byte * bitmapAlloc(int sizeInBits); void bitmapFree(byte * bitmap); , aby klient nie musiał się martwić o to, ile bajtów ma alokować.
I / lub podać makro, które pomoże przy alokacjach. Makro zamiast funkcji, jeśli chcesz, aby pojawiło się w alokacjach tablic.
#define BITMAP_BYTE_COUNT_FOR(n) ((n)+BIT-1)/BIT) I „d również bitmapSearch przyjmuje rozmiar jako liczbę bitów zamiast liczby bajtów. Następnie, jeśli klient dba tylko o, powiedzmy, 26 bitów na litery, nie musi martwić się wyszukiwaniem zwracającym 27, ponieważ bitmapa naprawdę zawiera 32 bity.