Jeg startede for nylig med at rydde op i mine projekter og besluttede at jeg ville oprette et personligt lager med nyttige kodestykker. Jeg fandt denne bitmapkode imellem dem og redigerede den kraftigt, og jeg ville sætte pris på, om nogen kunne gennemgå den, fordi jeg ikke er den, der plejede at bitvise operationer og sådan. Er koden bærbar nok, eller burde der være ændringer?
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); } Kommentarer
- For alle, der stadig følger dette indlæg, tildelte jeg koden til github her . Jeg tilføjede også alle dine kommentarer som problemer. Tak for dine kommentarer, og jeg begynder at implementere dem.
Svar
Hvis du forventer, at din kode nogensinde vil være brugt fra C ++ (som en masse C-kode er), skal du ikke bruge nogen identifikatorer med dobbelt understregning.
#ifndef BITMAP__ // ^^ May cause problems in C++ Da dette er forbeholdt implementeringen i C ++. Udtrykket BITMAP er også meget generisk, og det er meget sandsynligt, at du kommer i konflikt med andre biblioteker, så prøv at gøre det mere unikt for dit projekt.
Du antager, at en char er 8 bit.
#define BIT (8*sizeof(byte)) Standarden siger ikke dette (det er mindst 8 bit), men det defineres faktisk via makroen CHAR_BITS, så du skal bruge:
#define BIT (CHAR_BITS*sizeof(byte)) Din headerfil er, hvordan de fleste først vil se din kode og prøve at forstå, hvordan du bruger den. Således er det sandsynligvis en god ide at sætte parameternavne i headerfilen, da det hjælper med at dokumentere deres brug.
bool bitmapGet (byte *, int); void bitmapSet (byte *, int); void bitmapReset (byte *, int); int bitmapSearch(byte *, bool, int, int); Yderligere handlinger af bitmapSearch er ikke indlysende, så en kommentar til dets anvendelse i overskriften ville sandsynligvis være en god idé. Faktisk ville en lille uklarhed om, hvordan den første parameter kan være en matrix, sandsynligvis være en god idé (da det ikke er indlysende uden at læse koden).
Vær forsigtig med kommentarer:
/* pos is something from 0 to 7*/ Dette er kun sandt, hvis du antager antagelser (A: størrelsen på (byte) == 1 B: multiplicerer du dette med 8). Kommentaren burde have været:
/* pos is a value between [0, BIT) */ Bemærk brugen af “[” til venstre og “)” til højre. Det er en matematisk notation, der indikerer, at 0 er inkluderende, og BIT ikke er inkluderet i området (det er almindeligt i begge C / C ++ -dokumentationer).
Svar
-
Dine typer er unødvendige – brug bare usigneret char og int som standardbiblioteket ville.
-
Om det samme emne er din enum bool unødvendig, fordi i C ikke-nul angiver den sande tilstand. Du bekræfter det selv, fordi get () antager, at værdien 1 er sand. Alle antager dette, og så er typen overflødig. Desuden er det også forkert, for hvis jeg ændrer dit enum til
typedef enum{true=0, false} bool;mislykkes din funktion, selvom det logisk set er en rimelig ting at gøre.
Hvis du vil bruge en sådan bool, skal du udtrykkeligt returnere en af dens værdier:
return ((a >> pos) & 1) ? true : false;men der er virkelig ingen mening i dette. Du skal bare returnere et int, som standardbiblioteket ville.
-
bitmapGet () at returnere en bool virker forkert navngivet for mig. Bitmapbitene har værdierne 1 og 0, ikke sandt og falsk (selvom disse i øjeblikket er de samme). At kalde det bitmapIsSet () ville være mere logisk.
-
sizeof (char) er 1 per definition, så BIT kan erstattes med CHAR_BIT
-
Åbningsbeslag for funktioner er normalt i kolonne 0
-
Parameterrækkefølgen for bitmapSearch ville være mere logisk, er størrelsen fulgt af den ting, den henviser til (bitmap).
-
Startparameteren for bitmapSearch er forkert. For at specificere en søgning startende fra bit 0 (helt sikkert den mest almindelige) skal den, der ringer, passere -1 !!
-
Hvorfor sende “pos” -parameteren som en “byte”? Du har defineret “byte” til at repræsentere bitmapbyte, og “pos” er bestemt ikke en af dem. Du får advarsler om kompiler, hvis de er aktiveret (de burde være) om at videregive argumenter med forskellige bredder på grund af prototyper. Og at begrænse “pos” til en byte kan tilføje en ekstra maskininstruktion (se på samleren) mens og uden at opnå noget. Hvis du kunne definere en type pos_t med området 0..7, som du synes at have lyst til, kan du argumentere for, at det var på en eller anden måde korrekt, men da du ikke kan gøre det i C og klart har byteværdien området 0 .. 255, det er ikke bedre end at bruge et int.
Svar
Fandt det ikke spørg om ydeevne, men du kan fremskynde bitmapSearch for sparsomme bitmaps ved først at se på en byte ad gangen. Hvis du leder efter en 1, kan du springe over byte, der er 0x00, og hvis på udkig efter en 0, kan du springe over byte, der er 0xFF. Derefter kan du scanne bitene på den næste byte eller bruge en opslagstabel på den.
Hvad APIet angår, kan du tilføje
byte * bitmapAlloc(int sizeInBits); void bitmapFree(byte * bitmap); så klienten ikke behøver at bekymre sig om, hvor mange byte der skal allokere.
Og / eller tilvejebringe en makro til at hjælpe med tildelinger. En makro i stedet for en funktion, hvis du vil have den vist i matrixallokeringer.
#define BITMAP_BYTE_COUNT_FOR(n) ((n)+BIT-1)/BIT) I “d har også bitmapSearch tage størrelsen som et bitantal i stedet for et antal byte. Så hvis klienten kun bekymrer sig om f.eks. 26 bits for bogstaver, behøver de ikke bekymre sig om en søgning, der returnerer 27, fordi bitmap virkelig har 32 bits i sig.