StringBuilder în C (Revizuirea codului, C, Siruri De Caractere)

Finanțați procesul Monicăi a intrebat.
a intrebat.

O mulțime de limbaje au ceva care vă permite să construiți un șir de caractere de dimensiuni dinamice cu un minim de cheltuieli generale. C nu are, iar eu m-am trezit folosind cod care făcea asta manual în câteva locuri, așa că am împachetat-o într-o clasă. Rețineți că am implementat doar funcționalitatea pe care o folosesc.

stringbuilder.h:

#ifndef CONCATEN_STRINGBUILDER_H
#define CONCATEN_STRINGBUILDER_H

#include <stddef.h>
#include <stdbool.h>

struct stringbuilder_s;
typedef struct stringbuilder_s *stringbuilder_t;
stringbuilder_t sb_new(size_t);
bool sb_append(stringbuilder_t, char);
char *sb_as_string(stringbuilder_t);
void sb_free(stringbuilder_t);

#endif //CONCATEN_STRINGBUILDER_H

stringbuilder.c:

#include <stdlib.h>
#include <string.h>
#include "stringbuilder.h"

struct stringbuilder_s {
    char *mem;
    size_t count;
    size_t cap;
};
typedef struct stringbuilder_s *stringbuilder_t;
stringbuilder_t sb_new(size_t init_cap) {
    stringbuilder_t ret = malloc(sizeof(struct stringbuilder_s));
    if (!ret) return NULL;
    ret->mem = calloc(init_cap, sizeof(char));
    if (!ret->mem) return NULL;
    ret->cap = init_cap;
    ret->count = 0;
    return ret;
}
#define LOAD_FACTOR 2
bool sb_append(stringbuilder_t to, char c) {
    to->mem[to->count] = c;
    ++to->count;
    if (to->count == to->cap) {
        char *new_mem = realloc(to->mem, to->cap * LOAD_FACTOR);
        if (!new_mem) {
            return false;
        }
        memset(new_mem + to->cap, 0, to->cap);
        to->mem = new_mem;
        to->cap *= LOAD_FACTOR;
    }
    return true;
}
char *sb_as_string(stringbuilder_t sb) {
    return sb->mem;
}
void sb_free(stringbuilder_t sb) {
    free(sb->mem);
    free(sb);
}

Sunt interesat în mod special de:

  • Performanță. Acest cod este apelat o mult. Vreau să fie cât mai rapid posibil.
  • Siguranța memoriei. Deși sunt destul de sigur că nu există pierderi de memorie (presupunând că este folosit în mod corespunzător), nu sunt sigur și nu știu cum să verific.
  • Cazuri limită. Funcționează, din câte îmi dau seama, dar asta nu înseamnă că este lipsit de erori.

Testat aici.

Comentarii

  • Dacă cineva are idei mai bune pentru etichete, nu ezitați să le editați. Nu am mai fost aici de ceva vreme și nu le mai știu.  > Por Finanțează procesul Monicăi.
  • Aceste tag-uri arată bine pentru întrebare.-  > Por Phrancis.
  • Cred că există o potențială scurgere de memorie în sb_new: dacă ret = malloc(...) reușește, dar ret->mem = calloc(...) eșuează (returnează NULL), memoria de la ret nu este niciodată eliberată.-  > Por jcsahnwaldt Reintroduce Monica.
  • @JonaChristopherSahnwaldt Oh, da, bună observație. Mi-am schimbat semnificativ codul de când am scris asta, totuși.-  > Por Finanțează procesul Monicăi.
3 răspunsuri
JS1

Bug: Alocarea inițială nu se șterge la zero

Alocarea inițială de sb->mem utilizează malloc în loc de calloc, , astfel încât conținutul său este neinițializat. Dacă adăugați apoi câteva caractere și apelați sb_as_string(), , veți primi înapoi un șir de caractere care nu este terminat în mod corespunzător. Ar trebui să utilizați calloc în schimb.

Bug minor

În cazul în care apelul către realloc nu reușește, buffer-ul dvs. va fi incorect deoarece nu va mai fi terminat cu terminație nulă (tocmai ați adăugat un caracter la ultimul punct). Ar trebui fie să rescrieți un '' la sfârșitul tamponului dacă realloc eșuează, fie să efectuați realloc înainte de a adăuga caracterul.

Verificarea argumentelor

Atunci când creați un buffer de șiruri de caractere, trebuie să tratați cazul în care init_cap este trecut ca fiind 0. În acest caz, îl puteți seta la o valoare implicită. În momentul de față, o capacitate inițială de 0 va cauza o eroare în timp, deoarece funcția de adăugare va adăuga la un buffer de lungime zero fără a realoca niciodată.

Utilizare

Aș prefera o funcție append care să ia ca argument un șir de caractere în loc de un argument de caractere. Nu sunt sigur că aș avea vreodată nevoie să adaug câte un caracter la un moment dat.

De asemenea, ar fi bine să existe o funcție to_string care să returneze șirul de caractere, dar care să elibereze și constructorul de șiruri. În modul în care o aveți în prezent, puteți prelua șirul, dar dacă ulterior eliberați constructorul de șiruri, acesta va elibera și șirul pe care tocmai l-ați preluat. Acest lucru îngreunează utilizarea șirului, deoarece durata de viață a acestuia este legată de durata de viață a stringbuilder-ului.

Comentarii

  • Pentru prima eroare – la naiba, am observat-o în sb_append, , dar am uitat de codul similar din sb_new. Pentru ultimul lucru — așa cum am menționat, eu scriu funcțiile pe care le folosesc. Se întâmplă ca locurile în care folosesc acest lucru să dea numai caracterele unul câte unul, iar eu folosesc acest lucru pentru a stoca caracterele pe care un alt cod decide că ar trebui să fie stocate (adică extrag date dintr-o sursă caracter cu caracter). În rest, o voi rezolva acum. Mulțumesc!  > Por Finanțați procesul Monicăi.
  • @QPaysTaxes Am mai adăugat o observație de uzabilitate cu privire la posibilitatea de a extrage șirul și de a elibera în același timp stringbuilderul.-  > Por JS1.
  • Hm, asta ridică un punct de vedere bun, de fapt. Chiar acum fac o strncopy în care obțin valoarea șirului de caractere, dar ar fi mai logic fie să o copiez în sb_as_string fie să ofer o versiune care să returneze un șir copiat. Voi adăuga și asta. Mulțumesc!  > Por Finanțați procesul Monicăi.
Ramin

Pentru a fi mai cuprinzător, linia din sb_append():

memset(new_mem + to->cap, 0, to->cap);

ar trebui să devină:

memset(new_mem + to->cap, 0, (to->cap) * (LOAD_FACTOR - 1));

Asta contează când LOAD_FACTOR este setat la ceva mai mare de 2.

Vă mulțumim că ați împărtășit acest cod.

Comentarii

  • Sau, în mod echivalent, calculați new_cap = to->cap * LOAD_FACTOR, și apoi memset(new_mem + to->cap, 0, new_cap - to->cap). Bună treabă.  > Por Toby Speight.
  • Bine ați venit la Code Review!-  > Por Toby Speight.
Toby Speight

Nu cred că este necesar să insistăm ca și constructorul de șiruri de caractere să fie în stocare dinamică. Are o dimensiune fixă și ar vrea să fie în stocare automată. În mod ideal, ar fi și reutilizabil.

Acest lucru poate fi activat, prin adăugarea unor funcții ca acestea:

typedef struct stringbuilder_s stringbuilder_s;

bool sb_init(stringbuilder_s *b, const char *s)
{
    b->count = strlen(s);
    b->cap = LOAD_FACTOR * (b->count + 1);
    b->mem = malloc(b->cap);
    if (!b->mem) {
        b->count = 0;
        b->cap = 0;
        return false;
    }
    strcpy(b->mem, s);
    return true;
}

void sb_close(stringbuilder_s *b)
{
    free(b->mem);
    b->cap = 0;
    b->count = 0;
}

Apoi putem folosi astfel:

#include <stdio.h>

int main(void)
{
    stringbuilder_s builder;
    if (!sb_init(&builder, "foo")) { goto fail; }
    if (!sb_append_char(&builder, '1')) { goto fail; }
    printf("Created %s
", sb_as_string(&builder));
    sb_close(&builder);
    return 0;

 fail:
    sb_close(&builder);
    fprintf(stderr, "String creation failed");
    return 1;
}

Bug:

  • Dacă sb_new() nu reușește să aloce mem, , trebuie să eliberăm ret înainte de a returna null.

Puncte minore:

  • sizeof (char) este 1 prin definiție, iar sizeof *ret este mai clar decât sizeof (struct stringbuilder_s) atunci când se alocă pentru a atribui la ret.
  • Este o risipă să reducem la zero întreaga capacitate, când avem nevoie doar de un singur terminator pentru un șir de caractere. Noi ar putea să amâna terminarea nulă până când vom sb_as_string() este apelată, dar cred că este mai bine să păstrăm mem terminarea nulă pe parcurs. (Cheltuielile generale se reduc odată ce vom suporta sb_append_string(), , desigur).