[Projektvorstellung] Starlight - C XML zu JSON Konverter, bitte um Feedback

[theSplit]

Hallo, ich arbeite noch am dem Projekt weiter, aber es kommt gerade ein Stolperstein:

Folgende XML ist gegeben:
Anhang anzeigen standard_small.xml (auch auf der Projektseite in Github)

Dort sind drei spezielle Array Strukturen enthalten:
Einmal in jedem "Item":
[src=xml] <incategory category="category540"/>
<incategory category="category418"/>
<incategory category="category985"/>
<incategory category="category787"/>
<incategory category="category12"/>[/src]

und das zweite "Item" hat noch folgende Einträge:
[src=xml] <incategorys category="category966"/>
...
<incategorys category="category65"/>
<incategorys category="category211"/>[/src]

Also statt "incategory" noch "incategoryS". Item 2 hat noch ein weiteres mögliche Array von "incategory" Einträgen.

Ich habe mir jetzt eine Funktion geschrieben die aus der TagListe Knoten mit gleichem Namen als Array Elemente deklariert.
Das sieht so aus, das der Knoten "Africa" zwei "Item" Einträge hat, das erste ist die "Array Root", der zweite ein Kind-Array-Element. Zusätzlich ist der letzte das "Last item" in diesem Array von "Item".

Das gleiche bei Incategory-Einträgen:
<incategory category="category540"/> ist die Wurzel/das Root Element,
<incategory category="category418"/> ein Array-Item der ersten Wurzel
[...]
<incategory category="category12"/> ein Array Item und das letzte Element der Wurzel


Soweit funktioniert das auch schon ganz korrekt - aber sobald ich ein weiteres Array von Elementen habe (in "Item" (2)) die "incategory" und "incategorys" funktioniert die Funktion nicht mehr korrekt.

Die Ausgabe sieht so aus:
Root Index ist die Wurzel zu dem ein Array Element gehört was gleichbedeutend mit tagIndex/itemIndex ist...
[src=text]Root Index: 0, itemIndex: 0, 1 entries, itemName: site
Root Index: 0, itemIndex: 1, 1 entries, itemName: regions
Root Index: 0, itemIndex: 2, 2 entries, itemName: africa
Root Index: 0, itemIndex: 3, 12 entries, itemName: item <- is array root
Root Index: 0, itemIndex: 4, 0 entries, itemName: location
Root Index: 0, itemIndex: 5, 0 entries, itemName: quantity
Root Index: 0, itemIndex: 6, 0 entries, itemName: name
Root Index: 0, itemIndex: 7, 0 entries, itemName: payment
Root Index: 0, itemIndex: 8, 1 entries, itemName: description
Root Index: 0, itemIndex: 9, 2 entries, itemName: parlist
Root Index: 0, itemIndex: 10, 1 entries, itemName: listitem <- is array root
Root Index: 0, itemIndex: 11, 1 entries, itemName: text
Root Index: 0, itemIndex: 12, 0 entries, itemName: keyword
Root Index: 10, itemIndex: 13, 1 entries, itemName: listitem <- array item (last Item)
Root Index: 0, itemIndex: 14, 0 entries, itemName: text
Root Index: 0, itemIndex: 15, 0 entries, itemName: shipping
Root Index: 16, itemIndex: 16, 0 entries, itemName: incategory <- is array root // Funktioniert
Root Index: 16, itemIndex: 17, 0 entries, itemName: incategory <- array item
Root Index: 16, itemIndex: 18, 0 entries, itemName: incategory <- array item
Root Index: 16, itemIndex: 19, 0 entries, itemName: incategory <- array item
Root Index: 16, itemIndex: 20, 0 entries, itemName: incategory <- array item (last Item) // Funktioniert
Root Index: 0, itemIndex: 21, 1 entries, itemName: mailbox
Root Index: 0, itemIndex: 22, 4 entries, itemName: mail
Root Index: 0, itemIndex: 23, 0 entries, itemName: from
Root Index: 0, itemIndex: 24, 0 entries, itemName: to
Root Index: 0, itemIndex: 25, 0 entries, itemName: date
Root Index: 0, itemIndex: 26, 2 entries, itemName: text
Root Index: 0, itemIndex: 27, 0 entries, itemName: keyword
Root Index: 0, itemIndex: 28, 0 entries, itemName: emph
Root Index: 3, itemIndex: 29, 25 entries, itemName: item <- array item (last Item)
Root Index: 0, itemIndex: 30, 0 entries, itemName: location
Root Index: 0, itemIndex: 31, 0 entries, itemName: quantity
Root Index: 0, itemIndex: 32, 0 entries, itemName: name
Root Index: 0, itemIndex: 33, 0 entries, itemName: payment
Root Index: 0, itemIndex: 34, 1 entries, itemName: description
Root Index: 0, itemIndex: 35, 0 entries, itemName: text
Root Index: 0, itemIndex: 36, 0 entries, itemName: shipping
Root Index: 37, itemIndex: 37, 0 entries, itemName: incategory <- is array root // Funktioniert
Root Index: 37, itemIndex: 38, 0 entries, itemName: incategory <- array item
Root Index: 37, itemIndex: 39, 0 entries, itemName: incategory <- array item
Root Index: 37, itemIndex: 40, 0 entries, itemName: incategory <- array item
Root Index: 37, itemIndex: 41, 0 entries, itemName: incategory <- array item
Root Index: 37, itemIndex: 42, 0 entries, itemName: incategory <- array item
Root Index: 37, itemIndex: 43, 0 entries, itemName: incategory <- array item
Root Index: 37, itemIndex: 44, 0 entries, itemName: incategory <- array item
Root Index: 37, itemIndex: 45, 0 entries, itemName: incategory <- array item // Wird nicht als letztes Element erkannt
Root Index: 0, itemIndex: 46, 1 entries, itemName: mailbox
Root Index: 0, itemIndex: 47, 4 entries, itemName: mail
Root Index: 0, itemIndex: 48, 0 entries, itemName: from
Root Index: 0, itemIndex: 49, 0 entries, itemName: to
Root Index: 0, itemIndex: 50, 0 entries, itemName: date
Root Index: 0, itemIndex: 51, 5 entries, itemName: text
Root Index: 52, itemIndex: 52, 0 entries, itemName: keyword <- is array root
Root Index: 52, itemIndex: 53, 0 entries, itemName: keyword <- array item
Root Index: 0, itemIndex: 54, 0 entries, itemName: bold
Root Index: 0, itemIndex: 55, 0 entries, itemName: emph
Root Index: 52, itemIndex: 56, 0 entries, itemName: keyword <- array item (last Item)
Root Index: 37, itemIndex: 57, 0 entries, itemName: incategorys <- array item // Hier müsste die Wurzel 57 sein + Array Root Element
Root Index: 37, itemIndex: 58, 0 entries, itemName: incategorys <- array item
Root Index: 37, itemIndex: 59, 0 entries, itemName: incategorys <- array item
Root Index: 37, itemIndex: 60, 0 entries, itemName: incategorys <- array item
Root Index: 37, itemIndex: 61, 0 entries, itemName: incategorys <- array item
Root Index: 37, itemIndex: 62, 0 entries, itemName: incategorys <- array item
Root Index: 37, itemIndex: 63, 0 entries, itemName: incategorys <- array item
Root Index: 37, itemIndex: 64, 0 entries, itemName: incategorys <- array item
Root Index: 37, itemIndex: 65, 0 entries, itemName: incategorys <- array item (last Item) // Wird als letztes Element erkannt, gehört aber eigentlich zu Root Index 57[/src]


Die C Schleife dazu, die die Wurzeln (Array root) und Kind Elemente entdecken soll, sieht so aus:
Zeile 464, in Starlight2.c

Der Code funktioniert korrekt wenn man aus der XML die zweiten "incategorys" Einträge entfernt, aber nicht wenn beide auftauchen - ich weiß aber nicht wo der Fehler liegt.

[src=c] // Analyze if we have arrayed tag items
bool hasRoot = false;
unsigned int rootIndex = 0;

for (int i = 0; i < tagCount; i++) {
//printf("ROOT: %s\n", tagList.name);

tag* lastTag = NULL;
hasRoot = false;
rootIndex = 0;

for (int j = 0; j < tagList.entrieSize; j++) {
//printf("Child: %s\n", tagList[tagList.children[j]].name);
for (int k = 0; k < tagList.entrieSize; k++) {
if (k != j) {
if (strcmp(tagList[tagList.children[k]].name, tagList[tagList.children[j]].name) == 0) {
//printf("is arrayed item\n");
tagList[tagList.children[j]].isArrayItem = true;

if (!hasRoot) {
tagList[tagList.children[j]].isArrayRoot = true;
rootIndex = tagList.children[j];
hasRoot = true;
} else {
tagList[tagList.children[j]].arrayRoot = rootIndex;
}

lastTag = &tagList[tagList.children[j]];
}
}
}
}

if (lastTag != NULL) {
lastTag->isLastItem = true;
}
}[/src]

Hat jemand eine wo mein (Denk-)Fehler liegt?

 

[Brother John]

hasRoot ist das Problem. Wenn der erst einmal auf true steht, wird er nie wieder false und alle Arrayeinträge rutschen unter den ersten Root. Rein aus dem Kopf könnte/müsste es funktionieren, wenn du hasRoot in jedem j-Schleifendurchlauf zurücksetzt.

Du könntest noch ein größeres Problem haben. In der Beispiel-XML kommen die verschiedenen Array-Tags hübsch getrennt nacheinander. Wenn das nicht mehr gegeben ist – und warum nicht category und categorys wild durcheinander mischen, oder andere Tags mitteinrein setzen? – könnte dein Ansatz, an die Nodes Array-Metadaten dranzuhängen, nicht mehr ausreichen oder zumindest ekelhaft hässlich und ineffizient in der Implementierung werden. Denk dir das nochmal durch.

 

[theSplit]

hasRoot ist das Problem. Wenn der erst einmal auf true steht, wird er nie wieder false und alle Arrayeinträge rutschen unter den ersten Root. Rein aus dem Kopf könnte/müsste es funktionieren, wenn du hasRoot in jedem j-Schleifendurchlauf zurücksetzt.

Wenn ich das probiere werden alle Tags als Array Root definiert und ein Kind wird nicht als Kind Eintrag definiert, da die Bedingung ein Kind zu erstellen mit "hasRoot" verzweigt. Das Zurücksetzen erfolgt in der obersten Schleife, in Zeile 9.

Du könntest noch ein größeres Problem haben. In der Beispiel-XML kommen die verschiedenen Array-Tags hübsch getrennt nacheinander. Wenn das nicht mehr gegeben ist – und warum nicht category und categorys wild durcheinander mischen, oder andere Tags mitteinrein setzen? – könnte dein Ansatz, an die Nodes Array-Metadaten dranzuhängen, nicht mehr ausreichen oder zumindest ekelhaft hässlich und ineffizient in der Implementierung werden.

Ich glaube wie die Schleifen funktionieren ist irritierend, weil ich die gesamte TagListe einmal durchgehe....

Heißt:
Es werden einmal über "i" in der Schleife alle Tags (inklusive aller Kinder) einmal durchschritten.
Die Kind Elemente jedes Tags werden dann zusätzlich durchschritten und mit allen anderen Kind-Elementen, in dieser Wurzel, abgeglichen. Kommt ein gleichnamiger Eintrag irgendwo vor so haben wir ein Array Item, ist es das erste haben wir eine Wurzel die als Definition für die anderen gleichnamigen Einträge dienen soll.

Das Mischen der Tags/Array verhindere ich bei der Ausgabe, das Resultat sieht so aus (Daten Tags Inhalte sind entfernt, ist auch bei der Github Variante so):

Wie man sieht ist einmal "incategory" in Item mit ID "1" intakt, beim zweiten Item sind diese vermischt.

Spoiler

[src=text]{
"site" : {
"regions" : {
"africa" : {
"item" : [{
"id" : "item0"
"location" : ""
"quantity" : ""
"name" : ""
"payment" : ""
"description" : {
"parlist" : {
"listitem" : [{
"text" : ""
"keyword" : ""
},{
"text" : ""
}]
} // Hier fehlt ein Closing Tag, das ist noch eine offene Baustelle.
"shipping" : ""
"mailbox" : {
"mail" : {
"from" : ""
"to" : ""
"date" : ""
"text" : ""
"keyword" : ""
"emph" : ""
}
},
"incategory" : [{
"category" : "category540"
},{
"category" : "category418"
},{
"category" : "category985"
},{
"category" : "category787"
},{
"category" : "category12"
}]
},{
"id" : "item1"
"location" : ""
"quantity" : ""
"name" : ""
"payment" : ""
"description" : {
"text" : ""
"shipping" : ""
"mailbox" : {
"mail" : {
"from" : ""
"to" : ""
"date" : ""
"text" : ""
"bold" : ""
"emph" : ""
"keyword" : [{
"keyword" : ""
},{
"keyword" : ""
},{
"keyword" : ""
}]
}
"incategory" : [{ // Hier sind alle beiden Tag Inhalte von Incategory und incategorys vermischt.
"category" : "category966"
},{
"category" : "category966"
},{
"category" : "category488"
},{
"category" : "category741"
},{
"category" : "category692"
},{
"category" : "category493"
},{
"category" : "category36"
},{
"category" : "category977"
},{
"category" : "category65"
},{
"category" : "category211"
},{
"category" : "category966"
},{
"category" : "category488"
},{
"category" : "category741"
},{
"category" : "category692"
},{
"category" : "category493"
},{
"category" : "category36"
},{
"category" : "category977"
},{
"category" : "category65"
},{
"category" : "category211"
}]
}]
}
}
}
}
}[/src]

Denk dir das nochmal durch.

Was das angeht habe ich noch keine andere konkrete Lösungsstrategie - ich hab die Tags aller in einer Liste nach Aufkommen, ohne Unterscheidung ob dies Kind Elemente sind oder nicht, das heißt diese sind relativ wild durcheinander geworfen so wie sie eben auftauchen beim Parsen.



Nachtrag:

Ich hab das Problem jetzt in dem Griff bekommen, auch wenn Tags an unterschiedlichen Stellen auftauchen werden diese korrekt verknüpft:

[src=c] // Analyze if we have arrayed tag items
bool hasRoot = false;
unsigned int rootIndex = 0;

for (int i = 0; i < tagCount; i++) {

hasRoot = false;
rootIndex = 0;
if (tagList.isArrayItem) {
continue;
}

for (int j = 0; j < tagCount; j++) {
if (i == j) {
continue;
}
if (tagList.parent == tagList[j].parent && strcmp(tagList.name, tagList[j].name) == 0) {

if (!hasRoot) {
tagList.isArrayRoot = true;
tagList.isArrayItem = true;
tagList.arrayRoot = i;

rootIndex = i;
hasRoot = true;
}

tagList[j].isArrayItem = true;
tagList[j].arrayRoot = rootIndex;
}
}
}

// Assign last items to arrayed tags
for (int i = 0; i < tagCount; i++) {
if (!tagList.isArrayItem) {
continue;
}

tag* lastTag = NULL;

if (tagList.isArrayRoot) {
for (int j = 0; j < tagCount; j++) {
if (!tagList[j].isArrayItem || i == j || tagList.parent != tagList[j].parent) {
continue;
}

if (strcmp(tagList.name, tagList[j].name) == 0) {
lastTag = &tagList[j];
}
}
}

if (lastTag != NULL) {
lastTag->isLastItem = true;
}
}
[/src]

 

[theSplit]

So, das Projekt scheint zu stehen, ich habe heute den JSON Writer hinzugefügt und auch noch einige Optimierungen gemacht, so das die Array und LastItem Erkennung in einer statt zwei Schleifen abgehandelt werden was den Rechenaufwand bezüglich der Arrays halbiert.

Dazu kommt das JSON nun korrekt geschrieben und verkapselt wird, bis auf einige kleine Einrücken die unoptimiert gesetzt sein könnten. Allerdings ist die Performance, was das erstellen der Array anbelangt noch arg langsam, so dauert dieser Step bei 1,5 Millionen Tags (116 MB Testfile), noch mehr als 15 Minuten (1,666,315 identifizierte Tags) und ist nebem dem Generieren der JSON der größte Step.

Auch das vermischen von Arrays Tags mit gleichem TagName wird erkannt und ausgegeben wie erwartet - dies wird auch bei der Generierung der JSON Daten berücksichtigt.

Ich bin aber zuversichtlich das die Software so verwendet werden könnte.

Ich würde mich also freuen wenn ihr fleißig testen würdet - bei Bedarf würde ich auch Binaries anbieten (auch wenn ich noch nicht raus habe wie ich unter Windows (nur 64bit) kompilieren kann).

/Edit:

Das identifizieren von Arrays dauert jetzt nur noch ein paar Sekunden, was jetzt leider noch ewig Zeit in Anspruch nimmt ist die json-Erzeugung... aber ich habe keine Ahnung ob die Erzeugung einfach so viel Zeit in Anspruch nimmt oder ob es einfach nur nicht richtig programmiert ist bzw. zu komplex, zu wenig Optimierung der Schleifen... Overhead durch Übergabe per Wert innerhalb der Rekursion...

Die CreateJsonFromTag Funktion ist ziemlich mächtig, aber vielleicht hat jemand generelle Tips wie man die Performance optimieren kann oder wo Pitfalls sind?

// Edit2

Ich hab ihn jetzt gefunden die Performance Bremse, es lag an den ganzen "strcat" Aufrufen. Ich verwende jetzt ein Custom Replacement und siehe da, das große Testfile wird in einigen Sekunden zusammengebaut und geschrieben
Dafür mußte ich zwar zwei globale Variablen verwenden, aber wenn es die Rechenzeit von gut 1.5 Stunde auf 4-5 Sekunden herunterbricht wars das total wert