Recentemente, comecei a limpar meus projetos e decidi que quero criar um repositório pessoal de bits úteis de código. Eu encontrei esse código de bitmap entre eles e o editei pesadamente e agradeceria se alguém pudesse revisá-lo, porque não estou acostumado a operações bit a bit e tal. O código é portátil o suficiente ou deve haver mudanças?
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); } Comentários
- Para qualquer pessoa que ainda esteja seguindo esta postagem, enviei o código ao github aqui . Também adicionei todos os seus comentários como problemas. Obrigado por seus comentários e começarei a implementá-los.
Resposta
Se você espera que seu código algum dia será usado a partir de C ++ (que é muito código C), então você não deve usar nenhum identificador com um sublinhado duplo.
#ifndef BITMAP__ // ^^ May cause problems in C++ Como isso é reservado para a implementação em C ++. Além disso, o termo BITMAP é muito genérico e é muito provável que você entre em conflito com outras bibliotecas, tente torná-lo mais exclusivo para o seu projeto.
Você está assumindo que um caractere tem 8 bits.
#define BIT (8*sizeof(byte)) O padrão não diz isso (são pelo menos 8 bits), mas na verdade é definido por meio da macro CHAR_BITS, então você deve usar:
#define BIT (CHAR_BITS*sizeof(byte)) Seu arquivo de cabeçalho é como a maioria das pessoas verá primeiro o seu código e tentará entender como usá-lo. Portanto, colocar os nomes dos parâmetros no arquivo de cabeçalho é provavelmente uma boa ideia, pois ajuda a documentar seu uso.
bool bitmapGet (byte *, int); void bitmapSet (byte *, int); void bitmapReset (byte *, int); int bitmapSearch(byte *, bool, int, int); Adicional a ação de bitmapSearch não é óbvio, portanto, um comentário sobre seu uso no cabeçalho provavelmente seria uma boa ideia. Na verdade, uma pequena descrição sobre como o primeiro parâmetro pode ser um array provavelmente seria uma boa ideia (já que não é óbvio sem ler o código).
Tenha cuidado com os comentários:
/* pos is something from 0 to 7*/ Isso só é verdade se você fizer suposições (A: esse sizeof (byte) == 1 B: você multiplica isso por 8). O comentário deveria ter sido:
/* pos is a value between [0, BIT) */ Observe o uso de “[” à esquerda e “)” à direita. É uma notação matemática que indica que 0 é inclusivo e BIT não está incluído no intervalo (é comum na documentação C / C ++).
Resposta
-
Seus tipos são desnecessários – apenas use unsigned char e int como a biblioteca padrão faria.
-
No mesmo tópico, seu enum bool é desnecessário porque em C diferente de zero indica o verdadeiro estado. Você confirma isso porque get () assume que o valor 1 é verdadeiro. Todos assumem isso e, portanto, o tipo é redundante. Além disso, também está errado porque se eu mudar seu enum para
typedef enum{true=0, false} bool;sua função falhará, mesmo que seja logicamente uma coisa razoável a se fazer.
Se você quiser usar um bool como esse, você deve retornar um de seus valores explicitamente:
return ((a >> pos) & 1) ? true : false;mas realmente não há sentido nisso. Apenas retorne um int, como faria a biblioteca padrão.
-
bitmapGet () retornando um bool me parece errado. Os bits de bitmap têm valores 1 e 0, não verdadeiro e falso (embora eles sejam atualmente os mesmos). Chamar de bitmapIsSet () seria mais lógico.
-
sizeof (char) é 1 por definição, então BIT pode ser substituído por CHAR_BIT
-
Os colchetes de abertura para funções normalmente estão na coluna 0
-
A ordem dos parâmetros para bitmapSearch seria mais lógica se o tamanho fosse seguido pelo que ele se refere (bitmap).
-
O parâmetro inicial para bitmapSearch está errado. Para especificar uma pesquisa a partir do bit 0 (certamente o mais comum), o chamador deve passar -1 !!
-
Por que passar o parâmetro “pos” como um “byte”? Você definiu “byte” para representar os bytes do bitmap e “pos” certamente não é um deles. Você receberá avisos do compilador se eles estiverem habilitados (deveriam estar) sobre a passagem de argumentos com larguras diferentes devido a protótipos. E restringir “pos” a um byte pode adicionar uma instrução de máquina extra (olhe para o montador) enquanto não consegue nada. Se você pudesse definir um tipo pos_t com o intervalo 0..7 que você parece querer, então você poderia argumentar que era de alguma forma correto, mas como você não pode fazer isso em C e claramente o valor do byte tem o intervalo 0 .. 255, não é melhor do que usar um int.
Resposta
Não didn “t pergunte sobre o desempenho, mas você pode acelerar bitmapSearch para bitmaps esparsos olhando primeiro um byte de cada vez. Se estiver procurando por 1, você pode pular bytes que são 0x00, e se procurando um 0, você pode pular os bytes que são 0xFF. Depois disso, você pode varrer os bits no próximo byte ou usar uma tabela de consulta sobre ele.
No que diz respeito à API, você pode adicionar
byte * bitmapAlloc(int sizeInBits); void bitmapFree(byte * bitmap); para que o cliente não precise se preocupar com quantos bytes alocar.
E / ou fornecer uma macro para ajudar nas alocações. Uma macro em vez de uma função se quiser que apareça em alocações de matriz.
#define BITMAP_BYTE_COUNT_FOR(n) ((n)+BIT-1)/BIT) Também bitmapSearch consideraria seu tamanho como uma contagem de bits em vez de uma contagem de bytes. Então, se o cliente só se preocupa com, digamos, 26 bits para letras, ele não precisa se preocupar se uma pesquisa retornar 27 porque o bitmap realmente contém 32 bits.