En los 80 del siglo pasado, proliferaban los miroordenadores: Sinclair, Amstrad, MSX, Apple, Commodore... Cada uno de ellos llevaba un BASIC, y en general cada uno era incompatible con el resto de ordenadores. Por ejemplo, Sinclair llevaba el Basic de Nine Tiles Ltd., conocido como Sinclair Basic. Amstrad utilizaba el Locomotive Basic... pero la gran mayoría empleaba alguna adaptación de Microsoft Basic.
Y es que en Microsoft Basic, como la gran mayoría de implementaciones de Basic, empleaba p-strings (Pascal Strings)(1). Es decir, se trata del texto (String), que también es conocido como cadena de caracteres.
El nombre de Pascal proviene del lenguaje de programación Pascal, que fue desarrollado por Niklaus Wirth, e incorporaba este tipo de cadenas de caracteres.
Mientras que actualmente se utilizan C strings. o NUL-terminated strings (cadenas de caracteres con una marca de fin nulo), las p-strings mantienen ciertas ventajas.
(Es importante tener en cuenta que NUL es el carácter ASCII número 0, mientras que NULL es el puntero nulo, es decir, que no apunta a ninguna posición válida en memoria. Su valor también suele ser 0 (excepto en arquitecturas muy particulares), pero ese es otro tema.)
Las p-strings se representan en memoria como un cuarto de kilobyte: 256 caracteres, que es suficiente para una gran mayoría de casos. El primer byte se emplea como marca de longitud, de forma que a partir del segundo byte (es decir, la dirección en memoria de la cadena, más uno), es donde se almacenan los caracteres del texto.
Esto significa que las cadenas están siempre alineadas en memoria, en bloques de tamaño exacto. Además, obtener la longitud de la cadena de caracteres es una operación O(1), mientras que la misma tarea en una C-String (como, por ejemplo, la función strlen() en string.h de C), es O(n), siendo n la propia longitud de la cadena. Por supuesto el tamaño máximo de 256 bytes de bloque no es casual, pues es el mayor número representable en un solo byte (0 a 255), que también coincide con el número de caracteres máximo (255), ya que es necesario contar con el byte del tamaño. Precisamente ahí está también la mayor desventaja, y es que solo puedes utilizar esos 255 caracteres como máximo.
Hay que tener en cuenta que aquí solo estamos teniendo en cuenta el sistema ASCII, o dicho de otra forma, un carácter por cada byte. UTF-8 sería inventado muchos años más tarde. Sí que sería sencillo implementar UTF-16 sobre este sistema, a costa de limitar aún más el número de caracteres: 127.
En el repositorio de Github para PascalString se puede encontrar una implementación de p-strings. El sistema consiste en emplear una estructura simple:
#define PSTR_MAX_CHARS 254
typedef struct p_str {
/* Position 0 : holds the length of the string (0-254).
* Position 1 : It's the position 0 of the string.
* Position n : It's the (n - 1)th position of the string.
* Position length - 1: It's a 0, to be able to interact with C strings.
*/
char raw[PSTR_MAX_CHARS + 2];
} pstr;
La cuestión es que para poder interoperar con las funciones de cadenas de C, se añade un NUL al final, Por lo tanto, resulta ser un sistema híbrido, en el que se reserva un byte más para el NUL (carácter 0), de fin de cadena.
Las siguientes funciones de la API son esclarecedoras sobre cómo se manejan esos 256 bytes. Como C no dispone de la posibilidad de manejar espacios de nombres, prefijamos cada función con pstr_.
pstr * pstr_create()
{
pstr * toret = (pstr *) malloc( sizeof( pstr ) );
if ( toret != NULL ) {
toret->raw[ 0 ] = toret->raw[ 1 ] = 0;
}
return toret;
}
inline void pstr_destroy(pstr * s)
{
free( s );
}
Estas dos funciones son las encargadas de crear una p_string sin contenido, y de eliminarla, respectivamente. pstr_create() primero reserva memorua con malloc() , y en caso de obtenerla, inicializa la cadena de caracteres a sin contenido. Es decir, la longitud de la cadena (primer byte) es 0, y el primer y único elemento de la cadena de caracteres es el carácter NUL, es decir, 0, también representado como '\0'.
Utilizando la notación de corchetes queda mucho más claro (y nuestro objetivo debe ser siempre la claridad y legibilidad), pero si quieres la versión pro, es esta:
*( toret->raw ) = *( toret->raw + 1 ) = 0;
Aunque si quieres realmente ser sucio, y que tus amigos te miren extrañados, puedes hacerlo así:
*( (int *) toret ) = 0;
Primero convertimos toret, que es un puntero a la estructura pstr, es decir pstr *, a un puntero a entero, es decir, un int *. Como un entero ocupa más de 2 bytes, obtenemos el objetivo deseado, es decir, poner el conteo de caracteres a 0 y el primer carácter a NUL (que como vimos antes, en ambos casos es el entero 0).
Si de verdad desees que tus amigos o compañeros miren tu código sin entender qué está pasando, si te enorgullece ese tipo de programación, debes saber que vas por el mal camino... hasta hay un artículo en la Wikipedia sobre legibilidad del código fuente. Suelo dar una charla sobre legbilidad de código a mis alumnos.
Necesitamos una función que devuelva el primer byte como un número entero. El tipo más adecuado para estos casos es size_t, aunque jamás lleguemos a ocupar todo su tamaño.
static inline
void set_len(pstr *s, size_t len)
{
return (size_t) ( (unsigned char) s->raw[ 0 ] );
}
inline
size_t pstr_len(const pstr *s)
{
return (size_t) s->raw[ 0 ];
}
Que es lo mismo que return (size_t) *s->raw, por si te lo estabas preguntando.
La función privada set_len(), así como pstr_len(), sirven para guardar en un byte una longitud de cadena, y reinterpretar desde ese byte dicha longitud.
inline
const char * pstr_to_cstr(const pstr *s)
{
return s->raw + 1;
}
La forma de obtener la cadena de caracteres en sí es la más sencilla, solo es necesario ignorar el primer byte dedicado a la longitud.
La función pstr_to_cstr() nos permite utilizar las funciones de C en string.h, ya que obtenemos un char *, y además, la cadena de caracteres, como vimos más arriba, termina con un NUL.
inline
char pstr_get(const pstr *s, size_t pos)
{
if ( pos <= pstr_len( s ) ) {
return s->raw[ pos + 1 ];
}
return '\0';
}
Esta función, pstr_get(), nos permite acceder al contenido de la cadena de caracteres, a un byte (un caŕacter ASCII, en esta implementación), determinado. Controlamos que no sea posible direccionar más allá del final del texto, lo cual sería un error.
Es bastante común que necesitemos crear una copia de una cadena de caracteres, bien desde una p-string (función pstr_copy(const pstr *)), o desde una C String (función pstr_create_from(const char *).
pstr * pstr_copy(const pstr *s)
{
pstr * toret = pstr_create();
if ( toret != NULL ) {
size_t len = pstr_len( s );
if ( len > PSTR_MAX_CHARS ) {
len = PSTR_MAX_CHARS;
}
strncpy(
(char *) pstr_to_cstr( toret ),
pstr_to_cstr( s ),
len + 1 );
set_len( toret, len );
}
return toret;
}
Lo que hacemos en esta función es crear la cadena de caracteres, y después utilizar strncpy(), que permite como mucho copiar PSTR_MAX_CHARS, de manera que, en caso de corrupción en memoria, nunca propaguemos dicha corrupción. Le sumamos un uno para incluir el cero de fin de cadena.
Finalmente, una operación también muy típica es la concatenación, que en el caso de dos p-strings es más eficiente que tomándolas como dos C Strings.
pstr * pstr_concat(const pstr *s1, const pstr *s2)
{
pstr * toret = pstr_create_from( pstr_to_cstr( s1 ) );
if ( toret != NULL ) {
size_t len_s1 = pstr_len( s1 );
size_t len_s2 = pstr_len( s2 );
size_t space_left = PSTR_MAX_CHARS - len_s1;
if ( len_s2 > space_left ) {
len_s2 = space_left;
}
strncpy(
(char *) pstr_to_cstr( toret ) + len_s1,
pstr_to_cstr( s2 ),
len_s2 );
toret->raw[ 1 + len_s1 + len_s2 ] = '\0';
set_len( toret, len_s1 + len_s2 );
}
return toret;
}
En este caso, truncamos la segunda cadena en caso de que no haya suficiente espacio remamente en la p-string. Utilizamos strncpy() para asegurarnos de que no excedemos el tamaño máximo.
(1) En realidad, utilizaban otra de tantas variantes que consistía en mantener un puntero al texto real, incluyendo recolección de basura en el llamado heap de cadenas. Como todos los métodos, encontrar uno que sea realmente puro es en la práctica muy complicado.
Top comments (0)