Recientemente comencé a limpiar mis proyectos y decidí que quería crear un repositorio personal de bits útiles de código. Encontré este código de mapa de bits entre ellos y lo edité en gran medida, y agradecería que alguien pudiera revisarlo, porque no estoy tan acostumbrado a las operaciones bit a bit y tal. ¿Es el código lo suficientemente portátil o debería haber cambios?
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); } Comentarios
- Para cualquiera que todavía esté siguiendo esta publicación, envié el código a github aquí . También agregué todos sus comentarios como problemas. Gracias por sus comentarios y comenzaré a implementarlos.
Responda
Si espera que su código alguna vez sea usado desde C ++ (que es una gran cantidad de código C) entonces no debe usar ningún identificador con un guión bajo doble.
#ifndef BITMAP__ // ^^ May cause problems in C++ Como esto está reservado para la implementación en C ++. Además, el término BITMAP es muy genérico y es muy probable que choque con otras bibliotecas, intente hacerlo más exclusivo para su proyecto.
Está asumiendo que un carácter tiene 8 bits.
#define BIT (8*sizeof(byte)) El estándar no dice esto (tiene al menos 8 bits) pero en realidad está definido a través de la macro CHAR_BITS por lo que debe usar:
#define BIT (CHAR_BITS*sizeof(byte)) Su archivo de encabezado es la forma en que la mayoría de la gente verá primero su código y tratará de entender cómo usarlo. Por lo tanto, poner los nombres de los parámetros en el archivo de encabezado es probablemente una buena idea, ya que ayuda a documentar su uso.
bool bitmapGet (byte *, int); void bitmapSet (byte *, int); void bitmapReset (byte *, int); int bitmapSearch(byte *, bool, int, int); Adicional a la acción de bitmapSearch no es obvio, por lo que un comentario sobre su uso en el encabezado probablemente sería una buena idea. En realidad, una pequeña propaganda sobre cómo el primer parámetro puede ser una matriz probablemente sería una buena idea (ya que no es obvio sin leer el código).
Tenga cuidado con los comentarios:
/* pos is something from 0 to 7*/ Esto solo es cierto si hace suposiciones (A: ese tamaño de (byte) == 1 B: multiplica esto por 8). El comentario debería haber sido:
/* pos is a value between [0, BIT) */ Note el uso de «[» a la izquierda y «)» a la derecha. Es una notación matemática que indica que 0 es inclusivo y BIT no está incluido en el rango (es común en la documentación de C / C ++).
Respuesta
-
Sus tipos son innecesarios – simplemente use unsigned char e int como lo haría la biblioteca estándar.
-
Sobre el mismo tema, su enum bool es innecesario porque en C un valor distinto de cero indica el estado verdadero. Lo confirma usted mismo porque get () asume que el valor 1 es verdadero. Todo el mundo asume esto y, por lo tanto, el tipo es redundante. Además, también está mal porque si cambio tu enumeración a
typedef enum{true=0, false} bool;tu función falla, aunque lógicamente es algo razonable.
Si desea utilizar un bool como ese, debe devolver uno de sus valores explícitamente:
return ((a >> pos) & 1) ? true : false;pero realmente no tiene sentido esto. Simplemente devuelva un int como lo haría la biblioteca estándar.
-
bitmapGet () devolviendo un bool me parece mal llamado. Los bits del mapa de bits tienen valores 1 y 0, no verdadero ni falso (aunque estos son actualmente iguales). Llamarlo bitmapIsSet () sería más lógico.
-
sizeof (char) es 1 por definición, por lo que BIT se puede reemplazar con CHAR_BIT
-
Los corchetes de apertura para las funciones están normalmente en la columna 0
-
El orden de los parámetros para bitmapSearch sería más lógico si el tamaño seguido a lo que se refiere (mapa de bits).
-
El parámetro de inicio de bitmapSearch es incorrecto. Para especificar una búsqueda a partir del bit 0 (seguramente el más común), el llamador debe pasar -1 !!
-
¿Por qué pasar el parámetro «pos» como un «byte»? Ha definido «byte» para representar los bytes del mapa de bits y «pos» ciertamente no es uno de esos. Obtendrá advertencias del compilador si están habilitadas (deberían estarlo) sobre el paso de argumentos con diferentes anchos debido a los prototipos. Y restringir «pos» a un byte puede agregar una instrucción extra de la máquina (mire el ensamblador) sin lograr nada. Si pudiera definir un tipo pos_t con el rango 0..7 que parece querer, entonces podría argumentar que era correcto de alguna manera, pero como no puede hacer eso en C y claramente el valor del byte tiene el rango 0 .. 255, no es mejor que usar un int.
Respuesta
No lo hice preguntar sobre el rendimiento, pero puede acelerar bitmapSearch para mapas de bits dispersos si primero mira un byte a la vez. Si busca un 1, puede omitir bytes que son 0x00, y si buscando un 0, puede omitir los bytes que son 0xFF.Después de eso, puede escanear los bits en el siguiente byte o usar una tabla de búsqueda en él.
En lo que respecta a la API, puede agregar
byte * bitmapAlloc(int sizeInBits); void bitmapFree(byte * bitmap); para que el cliente no tenga que preocuparse por cuántos bytes asignar.
Y / o proporcionar una macro para ayudar con las asignaciones. Una macro en lugar de una función si desea que aparezca en las asignaciones de matriz.
#define BITMAP_BYTE_COUNT_FOR(n) ((n)+BIT-1)/BIT) También tendré que bitmapSearch tome su tamaño como un recuento de bits en lugar de un recuento de bytes. Entonces, si al cliente solo le importan, digamos, 26 bits para las letras, no tiene que preocuparse de que una búsqueda devuelva 27 porque el mapa de bits realmente tiene 32 bits.