resueltos - leer cadena de caracteres en c

¿Qué le sucede a la memoria después de ''/ 0'' en una cadena C? (11)

Sorprendentemente simple / estúpida / pregunta básica, pero no tengo ni idea: supongamos que quiero devolver al usuario de mi función una cadena en C, cuya longitud no sé al principio de la función. Solo puedo colocar un límite superior en la longitud desde el principio y, dependiendo del procesamiento, el tamaño puede reducirse.

La pregunta es, ¿hay algo de malo en asignar suficiente espacio de pila (el límite superior) y luego terminar la cadena muy por debajo de eso durante el procesamiento? es decir, si inserto un ''/ 0'' en el medio de la memoria asignada, ¿funciona (a.) free() correctamente, y (b.) deja de tener importancia el espacio después de ''/ 0''? Una vez que se agrega ''/ 0'', ¿la memoria acaba de ser devuelta, o está ahí ocupando espacio hasta que se llame a free() ? ¿Es generalmente un mal estilo de programación dejar este espacio colgado allí, para ahorrar un poco de tiempo de programación inicial computando el espacio necesario antes de llamar a malloc?

Para dar un poco de contexto, digamos que quiero eliminar duplicados consecutivos, como este:

entrada "Hola oOOOo !!" -> salida "Helo oOo!"

... y algunos códigos a continuación que muestran cómo estoy precomputando el tamaño resultante de mi operación, realizando de manera efectiva el procesamiento dos veces para obtener el tamaño adecuado.

char* RemoveChains(const char* str) { if (str == NULL) { return NULL; } if (strlen(str) == 0) { char* outstr = (char*)malloc(1); *outstr = ''/0''; return outstr; } const char* original = str; // for reuse char prev = *str++; // [prev][str][str+1]... unsigned int outlen = 1; // first char auto-counted // Determine length necessary by mimicking processing while (*str) { if (*str != prev) { // new char encountered ++outlen; prev = *str; // restart chain } ++str; // step pointer along input } // Declare new string to be perfect size char* outstr = (char*)malloc(outlen + 1); outstr[outlen] = ''/0''; outstr[0] = original[0]; outlen = 1; // Construct output prev = *original++; while (*original) { if (*original != prev) { outstr[outlen++] = *original; prev = *original; } ++original; } return outstr; }

Si inserto un ''/ 0'' en el medio de la memoria asignada,
(a.) free () todavía funciona correctamente, y

Sí.

(b.) ¿el espacio después del ''/ 0'' se vuelve inconsecuente? Una vez que se agrega ''/ 0'', ¿la memoria acaba de ser devuelta, o está ahí ocupando espacio hasta que se llame a free ()?

Depende A menudo, cuando asigna grandes cantidades de espacio de almacenamiento dinámico, el sistema primero asigna espacio de direcciones virtuales; a medida que escribe en las páginas se asigna una memoria física real para respaldarlo (y eso puede luego transferirse al disco cuando su sistema operativo tiene memoria virtual) apoyo). Famosamente, esta distinción entre la asignación inútil de espacio de direcciones virtuales y la memoria física / de intercambio real permite que las matrices dispersas sean razonablemente eficientes en la memoria en dichos sistemas operativos.

Ahora, la granularidad de este direccionamiento virtual y paginación está en los tamaños de página de la memoria, que pueden ser 4k, 8k, 16k ...? La mayoría de los sistemas operativos tienen una función a la que puede llamar para conocer el tamaño de la página. Por lo tanto, si realiza muchas asignaciones pequeñas, redondear el tamaño de página es un desperdicio, y si tiene un espacio de direcciones limitado en relación con la cantidad de memoria que realmente necesita usar, dependiendo del direccionamiento virtual del modo descrito anteriormente no se escalará (por ejemplo, 4 GB de RAM con direccionamiento de 32 bits). Por otro lado, si ejecuta un proceso de 64 bits con una memoria RAM de 32 GB y hace relativamente pocas asignaciones de cadenas de este tipo, tiene una enorme cantidad de espacio de direcciones virtuales para jugar y el redondeo hasta el tamaño de página ganado. t es mucho.

Pero - note la diferencia entre escribir en el búfer y luego terminarlo en algún punto anterior (en cuyo caso la memoria una vez escrita tendrá memoria de respaldo y podría terminar en intercambio) en lugar de tener un gran búfer en el que solo escriba al primer bit luego finaliza (en cuyo caso la memoria de respaldo solo se asigna para el espacio utilizado redondeado al tamaño de página).

También vale la pena señalar que en muchos sistemas operativos, la memoria dinámica puede no devolverse al sistema operativo hasta que el proceso finalice: en cambio, la biblioteca malloc / free notifica al sistema operativo cuando necesita hacer crecer el montón (por ejemplo, utilizando sbrk() en UNIX o VirtualAlloc() en Windows). En ese sentido, free() memoria free() es gratuita para que su proceso se vuelva a usar, pero no es gratuita para que otros procesos la utilicen. Algunos sistemas operativos optimizan esto, por ejemplo, usando una región de memoria independiente y liberable independientemente para asignaciones muy grandes.

¿Es generalmente un mal estilo de programación dejar este espacio colgado allí, para ahorrar un poco de tiempo de programación inicial computando el espacio necesario antes de llamar a malloc?

Nuevamente, depende de cuántas asignaciones de ese tipo estés tratando. Si hay una gran cantidad relativa a su espacio de direcciones virtuales / RAM: usted quiere dejar explícitamente a la biblioteca de memoria saber que no toda la memoria solicitada originalmente es realmente necesaria usando realloc() , o incluso podría usar strdup() para asignar un nuevo bloquear con mayor fuerza en función de las necesidades reales (y luego free() el original), dependiendo de la implementación malloc / libre de la biblioteca que funcione mejor o peor, pero muy pocas aplicaciones se verán significativamente afectadas por cualquier diferencia.

A veces su código puede estar en una biblioteca donde no puede adivinar cuántas instancias de cadena gestionará la aplicación llamante; en tales casos, es mejor proporcionar un comportamiento más lento que nunca se pone tan mal ... así que inclínese hacia la reducción de los bloques de memoria a ajuste los datos de cadena (un número determinado de operaciones adicionales, por lo que no afecta la eficacia de big-O) en lugar de desperdiciar una proporción desconocida del búfer de cadena original (en un caso patológico: cero o un carácter utilizado después de asignaciones arbitrariamente grandes). Como optimización del rendimiento, puede que solo le moleste devolver la memoria si el espacio no utilizado es> = el espacio utilizado, sintonice el gusto, o hágalo configurable por la persona que llama.

Usted comenta en otra respuesta:

Entonces, ¿se trata de juzgar si el realloc llevará más tiempo o la determinación del tamaño de preprocesamiento?

Si el rendimiento es tu principal prioridad, entonces sí, querrás hacer un perfil. Si no está vinculado a la CPU, entonces, como regla general, tome el acierto de "preprocesamiento" y realice una asignación del tamaño adecuado: hay menos fragmentación y desorden. Contrarrestando eso, si tiene que escribir un modo especial de preprocesamiento para alguna función, esa es una "superficie" adicional para los errores y el código para mantener. (Esta decisión de compensación es comúnmente necesaria al implementar su propia asprintf() desde snprintf() , pero al menos puede confiar en que snprintf() actuará como está documentado y no tendrá que mantenerla personalmente).

Una vez que se agrega ''/ 0'', ¿la memoria acaba de ser devuelta, o está ahí ocupando espacio hasta que se llame a free ()?

No hay nada mágico sobre /0 . realloc llamar a realloc si desea "reducir" la memoria asignada. De lo contrario, la memoria se quedará allí hasta que llame free .

Si inserto un ''/ 0'' en el centro de la memoria asignada, ¿funciona (a). Free () aún funciona correctamente?

Lo que sea que hagas en esa memoria free siempre funcionará correctamente si lo pasas exactamente el mismo puntero devuelto por malloc . Por supuesto, si escribe fuera, todas las apuestas están apagadas.

free() seguirá funcionando con un byte NUL en memoria
el espacio permanecerá desperdiciado hasta que se llame a free() , o a menos que posteriormente reduzca la asignación

El /0 es una convención pura para interpretar arreglos de caracteres como picaduras, es independiente de la gestión de la memoria. Es decir, si desea recuperar su dinero, debe llamar a realloc . A la cadena no le importa la memoria (lo que es una fuente de muchos problemas de seguridad).

Generalmente, la memoria es memoria es memoria. No le importa lo que escriba en él. PERO tiene una carrera, o si prefiere un sabor (malloc, nuevo, VirtualAlloc, HeapAlloc, etc.). Esto significa que la parte que asigna un trozo de memoria también debe proporcionar los medios para desasignarlo. Si su API viene en una DLL, entonces debería proporcionar una función gratuita de algún tipo. Esto, por supuesto, supone una carga para la persona que llama, ¿verdad? Entonces, ¿por qué no poner TODA la carga sobre la persona que llama? La MEJOR manera de lidiar con la memoria asignada dinámicamente es NO asignarla usted mismo. Haga que la persona que llama lo asigne y se lo transmita. Él sabe qué sabor le dio, y él es responsable de liberarlo cada vez que termina de usarlo.

¿Cómo sabe la persona que llama cuánto asignar? Al igual que muchas API de Windows, su función devuelve la cantidad requerida de bytes cuando se llama, por ejemplo, con un puntero NULL, y luego hace el trabajo cuando se proporciona con un puntero no NULL (usando IsBadWritePtr si es adecuado para su caso para verificar la accesibilidad).

Esto también puede ser mucho más eficiente. Las asignaciones de memoria COST mucho. Demasiadas asignaciones de memoria causan la fragmentación del montón y luego las asignaciones cuestan aún más. Es por eso que en el modo núcleo utilizamos las llamadas "listas de apartados". Para minimizar el número de asignaciones de memoria, reutilizamos los bloques que ya hemos asignado y "liberado", utilizando los servicios que NT Kernel proporciona a los escritores de controladores. Si le transfiere la responsabilidad de la asignación de memoria a la persona que llama, puede que le esté pasando memoria barata de la pila (_alloca), o que le pase la misma memoria una y otra vez sin ninguna asignación adicional. No le importa, por supuesto, pero permite que su interlocutor se encargue del manejo óptimo de la memoria.

Para explicar el uso del terminador NULL en C: no puede asignar una "cadena C", puede asignar una matriz char y almacenar una cadena en ella, pero malloc y libre simplemente verlo como una matriz de la longitud solicitada.

La cadena de CA no es un tipo de datos, sino una convención para usar una matriz char donde el carácter nulo ''/ 0'' se trata como el terminador de cadena. Esta es una forma de pasar cadenas sin tener que pasar un valor de longitud como un argumento separado. Algunos otros lenguajes de programación tienen tipos de cadena explícitos que almacenan una longitud junto con los datos de los caracteres para permitir pasar cadenas en un solo parámetro.

Las funciones que documentan sus argumentos como "cadenas de caracteres C" pasan matrices de tipo char, pero no tienen forma de saber qué tan grande es la matriz sin el terminador nulo, de modo que si no está allí las cosas saldrán horriblemente mal.

Notará funciones que esperan que las matrices de caracteres que no necesariamente son tratadas como cadenas requieran siempre que se pase un parámetro de longitud de la memoria intermedia. Por ejemplo, si desea procesar datos de caracteres donde un byte cero es un valor válido, no puede usar ''/ 0'' como carácter terminador.

Podría hacer lo que algunas de las API de MS Windows hacen cuando usted (el que llama) pasa un puntero y el tamaño de la memoria que asignó. Si el tamaño no es suficiente, se le indica cuántos bytes asignar. Si fue suficiente, se usa la memoria y el resultado es la cantidad de bytes utilizados.

Por lo tanto, la decisión sobre cómo usar la memoria de manera eficiente se deja a la persona que llama. Pueden asignar 255 bytes fijos (comunes cuando se trabaja con rutas en Windows) y usar el resultado de la llamada a función para saber si se necesitan más bytes (no el caso de rutas debido a que MAX_PATH es 255 sin pasar por Win32 API) o si la mayoría de los bytes se puede ignorar ... La persona que llama también podría pasar cero como el tamaño de la memoria y saber exactamente cuánto se debe asignar, no tan eficiente en cuanto al procesamiento, pero podría ser más eficiente desde el punto de vista del espacio.

Sin duda, puede preasignar a un límite superior y usar todo o algo menos. Solo asegúrate de usar realmente todo o algo menos.

Hacer dos pases también está bien.

Hiciste las preguntas correctas sobre las compensaciones.

¿Cómo decides?

Use dos pases, inicialmente, porque:

1. you''ll know you aren''t wasting memory. 2. you''re going to profile to find out where you need to optimize for speed anyway. 3. upperbounds are hard to get right before you''ve written and tested and modified and used and updated the code in response to new requirements for a while. 4. simplest thing that could possibly work.

También puedes ajustar el código un poco. Más corto es usualmente mejor. Y cuanto más se aprovecha el código de las verdades conocidas, más cómodo me siento que hace lo que dice.

char* copyWithoutDuplicateChains(const char* str) { if (str == NULL) return NULL; const char* s = str; char prev = *s; // [prev][s+1]... unsigned int outlen = 1; // first character counted // Determine length necessary by mimicking processing while (*s) { while (*++s == prev); // skip duplicates ++outlen; // new character encountered prev = *s; // restart chain } // Construct output char* outstr = (char*)malloc(outlen); s = str; *outstr++ = *s; // first character copied while (*s) { while (*++s == prev); // skip duplicates *outstr++ = *s; // copy new character } // done return outstr; }

Tan pronto como obtenga memoria de Heap llamando a malloc (), la memoria es suya para usar. Insertar / 0 es como insertar cualquier otro caracter. Esta memoria permanecerá en su posesión hasta que la libere o hasta que OS la reclame nuevamente.

malloc solo asigna un trozo de memoria. Está hasta ti para usar como quieras y llamar gratis desde la posición inicial del puntero ... Insertar ''/ 0'' en el medio no tiene ninguna consecuencia ...

Para ser específico, Malloc no sabe qué tipo de memoria quieres (devuelve un puntero vacío).

Supongamos que desea asignar 10 bytes de memoria comenzando de 0x10 a 0x19.

char * ptr = (char *)malloc(sizeof(char) * 10);

Insertar un nulo en la quinta posición (0x14) no libera la memoria 0x15 en adelante ...

Sin embargo, una versión gratuita de 0x10 libera todo el fragmento de 10 bytes.

/0 es solo un personaje más de malloc y perspectiva free , no les importa qué datos guardas en la memoria. Por lo tanto, todavía funcionará free si agrega /0 en el medio o no agrega /0 en absoluto. El espacio adicional asignado seguirá allí, no se devolverá al proceso tan pronto como agregue /0 a la memoria. Yo personalmente preferiría asignar solo la cantidad de memoria requerida en lugar de asignar un límite superior ya que eso solo desperdiciará el recurso.