[C] Regel verwijderen uit file

[BezurK]

Ik ben bezig met een soort van database, die al zijn records opslaat in een tekstfile, nu wil ik dat als er een record verwijderd word de gehele regel verwijderen, dus inclusief newline zodat de regel in de file echt verdwijnt.
Hoe doe ik dit?
Het is btw in Linux (ik neem aan dat dit niet echt uitmaakt)

[Infinitive]

Je kunt niet veel anders doen dat in de file naar de positie gaan op het punt waar de te verwijderen regel en vanaf dat punt de rest van de file vanaf dat punt wegschrijven.

Hint: fpos, fseek. Evt. nog zaken als truncate. Verder zul je natuurlijk delen van de file in geheugenbuffers moeten plaatsen.

[BezurK]

Op woensdag 03 april 2002 21:07 schreef Infinitive het volgende:
Je kunt niet veel anders doen dat in de file naar de positie gaan op het punt waar de te verwijderen regel en vanaf dat punt de rest van de file vanaf dat punt wegschrijven.

Daar was ik ook al bang voor ja, maar ik wilde het voor de zekerheid toch ff vragen, misschien dat er een leuke libc functie voor is ofzo

[ACM]

code:

while(!feof())
{
  data = fread();
  if(!verwijderen)
  {
    fwrite(data);
  }
}

1 buffer nodig van bijvoorbeeld 4096 bytes en verder een manier om te bepalen of je de betreffende regel moet verwijderen...

[Verwijderd]

Op woensdag 03 april 2002 21:36 schreef ACM het volgende:

code:

while(!feof())
{
  data = fread();
  if(!verwijderen)
  {
    fwrite(data);
  }
}

1 buffer nodig van bijvoorbeeld 4096 bytes en verder een manier om te bepalen of je de betreffende regel moet verwijderen...

Zo moet je denk ik eerst je filetje kopiëren, en van daaruit weer schrijven naar je vorige file?

[.oisyn]

hoeft niet persee, meestal kun je files openen voor zowel reading als writing (tip: fopen (file, "r+"))

[Verwijderd]

Omdat PHP aardig wat van C weg heeft met dit punt.
Hele file inlezen (Array) -> regel die weg moet onthouden -> each de file weer wegschrijven, zonder bewuste regel..

Moet de file uiteraard niet te groot zijn..

Is er anders in C geen functie die uit een array de zoveelste index verwijderd ?!?!

[Janoz]

Op woensdag 03 april 2002 23:07 schreef Tizzwat het volgende:
Omdat PHP aardig wat van C weg heeft met dit punt.
Hele file inlezen (Array) -> regel die weg moet onthouden -> each de file weer wegschrijven, zonder bewuste regel..

Moet de file uiteraard niet te groot zijn..

Is er anders in C geen functie die uit een array de zoveelste index verwijderd ?!?!

Waarom zou je de hele file in het geheugen willen zetten? Kost aleen maar extra tijd.. Gewoon filepointer op de beginpositie zetten.

Het is het makkelijkst als je (mbv bijvoorbeeld spaties) er voor zorgt dat elk record evenveel tekens bevat. Je bestand wordt mischien wel groter, maar in dat geval kun je gewoon iets doen als fseek(recordnummer * recordgrootte) om de filepointer aan het begin van dat record neer te zetten.

[Soultaker]

Ik wilde eigenlijk verwijzen naar eerdere posts over dit onderwerp, maar ik bedacht net een in mijn ogen elegante oplossing die nog niet eerder ter sprake gekomen was. Het werkt als volgt:

code:

int dif, len;
char buf[...]; /* 4096 ofzo */
fp=fopen(filepath,"r+");

/* zoek de te verwijderen regel op */
do {
  fgets(buf,sizeof(buf),fp);
  if(...) break;
} while(!feof(fp));

/* dif = lengte van de te verwijderen regel */
dif=strlen(buf);

/* schrijf de data na de te verwijderen regel over de te verwijderen regel heen */
while(!feof(fp)&&(len=fread(buf,1,sizeof(buf),fp))
{
  /* terug naar 'dif' bytes voor dit blok */
  fseek(fp,-(len+dif),SEEK_CUR);
  fwrite(buf,1,len,fp);
  fseek(fp,dif,SEEK_CUR);
}
len=ftell(fp);
fclose(fp);
truncate(filepath,len-dif);

Allemaal niet getest dus misschien zitten er wat lompe bugs in, maar mijns inziens is dit de meest efficiente methode omdat deze geen tijdelijk bestand aanmaakt (en dus geen extra hdd ruimte nodig heeft), een constante hoeveelheid geheugen gebruikt (en het bestand dus niet in z'n geheel hoeft in te lezen) terwijl de invoer/uitvoer operaties in grote blokken uitgevoerd worden, zodat het hele gebeuren toch nog efficient werkt.

Let er wel op dat de regel in kwestie kleiner moet zijn dan je buffer. Meestal is dit echter wel te garanderen.

[RickN]

Op woensdag 03 april 2002 23:13 schreef Janoz het volgende:

[..]

Waarom zou je de hele file in het geheugen willen zetten? Kost aleen maar extra tijd.. Gewoon filepointer op de beginpositie zetten.

Het is het makkelijkst als je (mbv bijvoorbeeld spaties) er voor zorgt dat elk record evenveel tekens bevat. Je bestand wordt mischien wel groter, maar in dat geval kun je gewoon iets doen als fseek(recordnummer * recordgrootte) om de filepointer aan het begin van dat record neer te zetten.

Als je dit doet wordt niet alleen het zoeken van een record heel efficient, maar ook het verwijderen ervan. Je kunt dan namelijk het te verwijderen record gewoon overschrijven met het laatste record in de file en dan het laatste record verwijderen. Je hoeft dan dus geen grote stukken van de file te verplaatsen. Uiteraard werkt dit alleen als de records in de file ongeordend zijn. Je kunt ook overwegen om ergens in je file een lijst op te nemen met pointers naar de echte records, om het record te verwijderen hoef je dan alleen de pointer ernaar uit de lijst te halen. Het fysieke record wordt dan niet verwijderd, maar het is wel lekker snel. Vervolgens kun je af en toe alle records waar niet naar verwezen wordt verwijderen uit de file.

[Soultaker]

Op donderdag 04 april 2002 11:59 schreef RickN het volgende:
Je kunt ook overwegen om ergens in je file een lijst op te nemen met pointers naar de echte records, om het record te verwijderen hoef je dan alleen de pointer ernaar uit de lijst te halen. Het fysieke record wordt dan niet verwijderd, maar het is wel lekker snel. Vervolgens kun je af en toe alle records waar niet naar verwezen wordt verwijderen uit de file.

De methode die jij beschrijft, is vooral geschikt voor het gebruik van variable sized records. Wanneer je echter fixed sized records gebruikt, kun je nog efficienter records verwijderen, door de te verwijderen record te overschrijven met de laatste record in het bestand. Je hoeft vervolgens alleen je (relatief kleine) tabel, die de feitelijke ordening bevat, te herschrijven. Dat is natuurlijk erg efficient. Een voorwaarde voor al deze methoden is natuurlijk dat je de te verwijderen regel van te voren kan identificeren aan de hand van een beperkte hoeveelheid data (een getal ofzo).

Wat in dit geval het handigst is, hangt erg af van de toepassing. Fixed sized records zijn bijvoorbeeld erg geschikt voor een database met naw-gegevens ofzo, waarbij elk veld een redelijk beperkte lengte heeft. Als je bijvoorbeeld een email-archief wilt samenstellen, zijn fixed sized records uitermate ongeschikt, aangezien er gegarandeerd één record komt dat relatief groot is en er voor zorgt dat een relatief groot deel (denk aan meer dan de helft) van de ruimte verspilt.

[RickN]

Op donderdag 04 april 2002 12:58 schreef Soultaker het volgende:

[..]

Zoals ik hierboven liet zien, kan dat overschrijven ook prima met variable sized records.

Euh misschien moet je ff in woorden vertellen wat die code van je dan doet, maar voorzover ik het zie verschuif je alles na het te verwijderen record een stuk je op, over het te verwijderen record heen. Dat werkt inderdaad ook voor variable lengte records, maar het is niet de methode die ik voorstelde en het is lang niet zo efficient.

De methode die jij beschrijft, is vooral geschikt voor het gebruik van variable sized records.

Hier heb je het neem ik aan over het bijhouden van een lijst met pointers naar de echte records? Ja, dat is idd vooral handig bij variable sized records.

Wanneer je echter fixed sized records gebruikt, kun je nog efficienter records verwijderen, door de te verwijderen record te overschrijven met de laatste record in het bestand.

Ja, dit is dus wat ik ook voorstelde, en wat niet werkt voor variable size records.

Je hoeft vervolgens alleen je (relatief kleine) tabel, die de feitelijke ordening bevat, te herschrijven. Dat is natuurlijk erg efficient.

Dit is idd een handige methode om toch met ordening om te kunnen gaan, als dat nodig is. Maar als je deze lijst toch gaat bijhouden (omdat dat nodig is voor ordening) kun je je afvragen of je een record bij het verwijderen überhaupt wel direct fysiek wilt verwijderen of dat je alleen de pointer ernaar uit de lijst verwijderd. Zoals gezegd kun je de hele file dan af en toe een keer comprimeren door alle records waar niet meer naar verwezen wordt te verwijderen.

Een voorwaarde voor al deze methoden is natuurlijk dat je de te verwijderen regel van te voren kan identificeren aan de hand van een beperkte hoeveelheid data (een getal ofzo).

Ja, maar je kunt er natuurlijk altijd voor zorgen dat dat kan, door zo'n getal aan het record toe te voegen.

Wat in dit geval het handigst is, hangt erg af van de toepassing. Fixed sized records zijn bijvoorbeeld erg geschikt voor een database met naw-gegevens ofzo, waarbij elk veld een redelijk beperkte lengte heeft. Als je bijvoorbeeld een email-archief wilt samenstellen, zijn fixed sized records uitermate ongeschikt, aangezien er gegarandeerd één record komt dat relatief groot is en er voor zorgt dat een relatief groot deel (denk aan meer dan de helft) van de ruimte verspilt.

Ofcourse, er is bijna nooit een methode voor iets die elke situatie de beste is.

[Soultaker]

Op donderdag 04 april 2002 13:54 schreef RickN het volgende:
Euh misschien moet je ff in woorden vertellen wat die code van je dan doet, maar voorzover ik het zie verschuif je alles na het te verwijderen record een stuk je op, over het te verwijderen record heen. Dat werkt inderdaad ook voor variable lengte records, maar het is niet de methode die ik voorstelde en het is lang niet zo efficient.

Sorry, ik had verkeerd gelezen. Omdat je pas later over een tabel met offsets begon, ging ik er van uit dat je, om de ordening te behouden, wel alle volgende records over de oude heen zou willen schuiven. Mijn fout dus en mijn 'nieuwe' oplossing had jij dus al gegeven.

Ik zal ff een beetje knippen in m'n bericht.

[igmar]

Ik ben bezig met een soort van database, die al zijn records opslaat in een tekstfile, nu wil ik dat als er een record verwijderd word de gehele regel verwijderen, dus inclusief newline zodat de regel in de file echt verdwijnt.
Hoe doe ik dit?
Het is btw in Linux (ik neem aan dat dit niet echt uitmaakt)

Normaal met open(), seek(), write(), read(), etc. Indien de bestanden wat groter zijn is mmap() een stuk sneller.