#include <stdio.h>
#include <stdlib.h>
#include "btree.h"
/*
* Fußnotensortierprogramm optimiert auf die Aufgabe aus dem Linux-Magazin
* Ausgabe 10/08 Seite 30ff
*
* Beschränkungen: max. 2^32 Fußnoten, größte max. Nummerierung: 2^32.
* Je nach Vorsortierung max. 2^32 bytes Fußnoten oder mehr,
* bzw. beschränkt durch RAM.
*
* Funktionsweise:
* Gelesen wird von stdin, ausgegeben auf stdout. Es gibt keine Hilfe oder
* sonstige sinnvolle Ausgaben.
*
* Ich bin kein Programmierer und daher... öhm, sieht der Code
* etwas Grauenhaft aus?? k.A.
* Nach fast einem Tag Arbeit (ich wollte halt nur mal ein wenig C lernen, da
* war mir das ganze hier Recht) hab ich jetzt auch keine Lust mehr, nochmal
* drüberzugucken und noch Teile in Funktionen auszulagern etc.
*
* Meinen Teil hab ich mal (denke ich) auf geringen Speicherverbrauch
* optimiert. Daher Langsamer durch häufiges freigeben
* auch kleiner nicht benötigter Speicherbereiche(?). Speicherverbrauch ohne
* b-Baum(*altzuneu) im ungünstigsten Fall etwas mehr als der untere Teil der
* Eingabedatei, oder?
* Die Verwendete btree Implementierung ist nicht von mir und daher u.U.
* deutlich Speicherintensiver. k.A., hab keine Lust mehr noch selber was zu
* implementieren ;-)
*
* Lizenz dieser Datei: Public Domain
* Lizenz btree.c und btree.h: GPL v2.
*
* BUGs: Ich nutze eine btree-implementierung, die ich auf der LKML gefunden
* habe. Diese steht unter der GPL v2. Ich musste eine Zeile hinzufügen,
* da diese sonst nachvollziehbar Segfaults bei btree_search() lieferte.
*
* Wenn im Text irgendwo ein [XXX] auftaucht, wo XXX eine beliebige Zahl
* ist, aber [XXX] keinen Verweis auf eine Fußnote darstellt, wird dafür
* ein Verweis angelegt (die Zahl XXX also geändert), und in der
* Fußnotenliste dafür die originale Zahl wieder angegeben.
*/
//globale Variablen
int alloziierterspeicher = 0;
int *neuzualt; //flacher speicher für mapping neu->alt
int laufendenummer = 0;
btree *altzuneu; //btree für mapping alt->neu
char **fussnoten;
//funktionen für die btree-lib
unsigned int value(void * key)
{
return *(int *)key;
}
unsigned int keysize(void * key)
{
return sizeof(int);
}
unsigned int datasize(void * data)
{
return sizeof(int);
}
/*
* fehler ausgeben und programm beenden
*/
fehler(char * fehlermeldung)
{
printf(fehlermeldung);
exit(1);
}
/*
* Es wurde eine Fußnote im Text gefunden. Diese sollte eine neue Nummer
* bekommen und in die Korrespondenztabelle der alten eingefügt werden.
*/
int fn_einfuegen(char* altenummer_s)
{
int altenummer,i,neuenummer;
bt_key_val * kv = NULL;
//falls Speicher knapp wird, neuen alloziieren.
if (alloziierterspeicher<(laufendenummer+1))
{
if (alloziierterspeicher==0)
{
neuzualt=(int *)malloc(64*sizeof(int));
if (neuzualt==NULL) fehler("malloc: zu wenig speicher");
alloziierterspeicher=64;
}
else
{
alloziierterspeicher=alloziierterspeicher+(alloziierterspeicher);
neuzualt=(int *)
realloc(neuzualt,alloziierterspeicher*sizeof(int));
if (neuzualt==NULL) fehler("realloc: zu wenig speicher");
}
}
altenummer = atoi(altenummer_s);
//alte nummer schon aufgetreten?
if (laufendenummer>0)
{
kv = btree_search(altzuneu, &altenummer);
}
if (kv!=NULL)
{ //schon da -> vorhandene neue ausgeben
return *(int *) kv->val;
}
else
{ //noch nicht da -> anfügen
neuenummer = ++laufendenummer;
kv = (bt_key_val*)malloc(sizeof(*kv));
kv->key = malloc(sizeof(int));
*(int *)kv->key = altenummer;
kv->val = malloc(sizeof(int));
*(int *)kv->val = neuenummer;
btree_insert_key(altzuneu,kv);
neuzualt[neuenummer]=altenummer;
return neuenummer; //TODO: neuenummer->laufendenummer
}
//return 100; unreachable
}
/*
* Eine Klammer wurde im Text erkannt. Nun wird geprüft, ob dies auch eine
* Fußnote ist und diese ggf. aufgenommen.
*/
void klammer_im_text()
{
char fussnotennummer[10];
int i = 0, neuenummer; char c;
c=getchar();
while (c>=48 && c<=57 && i<10)
{
fussnotennummer[i]=c;
i++;
c=getchar();
}
fussnotennummer[i]=0;
if (c==93 && i>0)
{
neuenummer = fn_einfuegen(fussnotennummer);
printf("[%i]",neuenummer);
return; //neue Nummer eingefügt und ausgegeben.
}
// ist keine Fußnote, der hier eingelesene Text wird ausgegeben
printf("[%s",fussnotennummer);
putchar(c);
}
int fussnoten_folgen()
{
char trenntext[10] = "footnotes:";
char c; int i,j;
for (i=0; i<10; i++)
{
c=getchar();
if (c!=trenntext[i])
{
putchar('@');
for (j=0; j<i; j++)
putchar(trenntext[j]);
putchar(c);
return 0;
}
}
return 1;
}
int main()
{
char c;
int i,infussnote=0,altenummer,aktuellefussnotenmaxlaenge=0;
int aktuellefussnote=0,aktuellefussnotenlaenge=0,maxausgegebenefn=0;
char fussnotennummer[10];
bt_key_val * kv; //für btree_search
//btree lib initialisieren
altzuneu = btree_create(3);
altzuneu->value = value;
altzuneu->key_size = keysize;
altzuneu->data_size = datasize;
//ab hier der obere Teil (Textmodus)
while ((c=getchar())!=EOF)
{
if (c==91) klammer_im_text();
else if (c==64) {if (fussnoten_folgen()) break;}
else putchar(c);
}
//neuzualt-Speicher aufs nötigte schrumpfen
neuzualt=(int *)realloc(neuzualt,laufendenummer*sizeof(int));
//Speicher für die Zeiger auf die Fußnoten alloziieren.
fussnoten=(char **)malloc(laufendenummer*sizeof(char*));
//TODO:hier wird 1*sizeof(int) verschenkt, da fussnoten[0] nie vorkommen wird
//ab hier der untere Teil (Fußnotenmodus)
printf("@footnotes:");
alloziierterspeicher = 0;
while ((c=getchar())!=EOF)
{
if (c==91)
{
i=0;
c=getchar();
while (c>=48 && c<=57 && i<10)
{
fussnotennummer[i]=c;
i++;
c=getchar();
}
fussnotennummer[i]=0;
if (c==93 && i>0) //fussnotenanfang gefunden
{
if (aktuellefussnote) //string beenden
fussnoten[aktuellefussnote][aktuellefussnotenlaenge++]=0;
if (aktuellefussnotenmaxlaenge>aktuellefussnotenlaenge
&& aktuellefussnote) //TODO: schrumpfen könnte man auch nach ausg.
{ //platz für alte fußnote zurechtschrumpfen
fussnoten[aktuellefussnote]=(char *)realloc(
fussnoten[aktuellefussnote],aktuellefussnotenlaenge*sizeof(char));
}
//prüfen, ob vor dieser fn schon alle anderen ausgegeben wurden
if (maxausgegebenefn==aktuellefussnote-1)
{ //ja, es können weitere fussnoten ausgegeben werden
while (fussnoten[aktuellefussnote])
{
printf("[%i]%s",aktuellefussnote,fussnoten[aktuellefussnote]);
free(fussnoten[aktuellefussnote]);
fussnoten[aktuellefussnote]=NULL;
maxausgegebenefn++;
aktuellefussnote++;
}
}
aktuellefussnotenlaenge=0;
aktuellefussnotenmaxlaenge=0;
altenummer = atoi(fussnotennummer);
kv = btree_search(altzuneu, &altenummer);
if (kv==NULL)
{
printf("[unreferenziert]");
aktuellefussnote = 0;
} else //kv!=NULL
{
aktuellefussnote = *(int *) kv->val;
}
} else
{
//TODO: schon gelesene nicht-fußnoten-nummer wieder ausgeben
printf("TODO");
}
}
else if (aktuellefussnote)
{ //in fussnote: gelesenes zeichen laden
if (aktuellefussnotenmaxlaenge==0)
{
aktuellefussnotenmaxlaenge=256;
fussnoten[aktuellefussnote]=(char *)
malloc(aktuellefussnotenmaxlaenge*sizeof(char));
} else if (aktuellefussnotenmaxlaenge<aktuellefussnotenlaenge+1)
{
aktuellefussnotenmaxlaenge=aktuellefussnotenmaxlaenge+256;
fussnoten[aktuellefussnote]=(char *) realloc(
fussnoten[aktuellefussnote],aktuellefussnotenmaxlaenge*sizeof(char));
}
fussnoten[aktuellefussnote][aktuellefussnotenlaenge]=c;
aktuellefussnotenlaenge++;
}
else putchar(c); //wenn nicht in einer referenzierten Fußnote
}
if (aktuellefussnote) //string beenden
fussnoten[aktuellefussnote][aktuellefussnotenlaenge++]=0;
for (i=maxausgegebenefn+1;i<=laufendenummer;i++)
if (fussnoten[i]==NULL)
printf("[%i] Alte Zahl: %i\n",i,neuzualt[i]);
else
printf("[%i]%s",i,fussnoten[i]);
return 0;
}
