Lexikografische Sortierung von OIDs

[Thomas F. (thomas-hn)]

Hallo,

für die GetNext-Anfrage bei SNMP benötige ich eine Routine, welche mir 
die Object Identifier lexikografisch sortiert.
Meine MIB besteht momentan aus einem Array aus Structs, in welchem auch 
die OIDs liegen:

MIB[a].OID[b]

a wählt hierbei das Managed Object aus.
b gibt mir die Stelle der OID an.

Für diejenigen die mit SNMP noch nichts zu tun hatten:

Die OIDs einer MIB könnten beispielsweise folgendermaßen aussehen:

MIB[0].OID[0] = 1
MIB[0].OID[1] = 3
MIB[0].OID[2] = 6
MIB[0].OID[3] = 1
MIB[0].OID[4] = 2
MIB[0].OID[5] = 1
MIB[0].OID[6] = 1
MIB[0].OID[7] = 1
MIB[0].OID[8] = 0

MIB[1].OID[0] = 1
MIB[1].OID[1] = 3
MIB[1].OID[2] = 6
MIB[1].OID[3] = 1
MIB[1].OID[4] = 2
MIB[1].OID[5] = 1
MIB[1].OID[6] = 5
MIB[1].OID[7] = 8
MIB[1].OID[8] = 0

MIB[2].OID[0] = 1
MIB[2].OID[1] = 3
MIB[2].OID[2] = 6
MIB[2].OID[3] = 1
MIB[2].OID[4] = 2
MIB[2].OID[5] = 1
MIB[2].OID[6] = 1
MIB[2].OID[7] = 3
MIB[2].OID[8] = 0

Nun sollen diese 3 Arrays lexikografisch sortiert werden, also am Ende 
soll rauskommen: 0, 2, 1 für die Reihenfolge MIB[0], MIB[2], MIB[1].

Wie kann ich dieses Sortieren ressourcenschonend in einen 8-Bit 
Mikrocontroller implementieren?

Ich hoffe mein Problem wurde deutlich.

Gruß,

Thomas

[Andreas S. (andreas) (Admin)]

heapsort(); wenn es in der avr-libc noch nicht enthalten ist, google 
nach heapsort.c.

[Thomas F. (thomas-hn)]

Wenn ich das nun nicht komplett falsch verstanden habe sortiert mir 
heapsort(); aber nur die einzelnen Einträge eines Array. Ich möchte nun 
ja aber nicht den Inhalt meiner Arrays sortieren (dies ist ja eine 
Adresse die so bleiben soll). Stattdessen sind in meinem Programm 
einzelne Variablen in dieser Baumstruktur vorhanden und jede dieser 
Variable über eine gewisse Adresse (OID bzw. Pfad über die Zweige zum 
Blatt) adressiert. Bei einer GetNext-Anfrage springe ich nun an 
irgendeine Stelle in dieser Baumstruktur und muss von dort aus das 
nächste tieferliegende Objekt, also das nächste tieferliegende Blatt, 
finden.

Ich hoffe das Problem wird nun klarer.

Thomas

[Andreas S. (andreas) (Admin)]

Die Funktion sortiert dir was du willst: ein Array von Strukturen 
(MIB[x]), ein Array von Pointern, ein Array von Indizes. Wie diese 
Arrayelemente verglichen werden bestimmst du, indem du heapsort() einen 
Pointer auf deine Vergleichsfunktion übergibst. Wenn du ein Array von 
Indizes sortieren willst sieht das ganze dann ungefähr so aus (Casts, 
"&" und "*" nach Bedarf hinzufügen):

int compar(int *a, int *b)
{
  return strcmp(MIB[*a], MIB[*b]);
}

mib_order = {0,1,2};
heapsort(mib_order, sizeof(mib_order), 1, compar);

Danach hast du in mib_order die lexikalische Reihenfolge stehen, und das 
dürfte ja reichen um weiterzukommen.

[Jörg W. (dl8dtl) (Moderator)]

qsort() ist schon dabei, heapsort() noch nicht.  Klingt wie eine
lohnenswerte Ergänzung der Bibliothek.  Andreas, kannst du die
relativen Vor- und Nachteile beider Varianten kurz beschreiben?

[Jörg W. (dl8dtl) (Moderator)]

Jörg Wunsch wrote:

> Andreas, kannst du die
> relativen Vor- und Nachteile beider Varianten kurz beschreiben?

Nochmaliges lesen der FreeBSD-manpage beantwortet die Frage eigentlich
schon:

The heapsort() function [...]  Its only advantage over qsort() is that
it uses almost no additional memory; while qsort() does not allocate
memory, it is implemented using recursion.

Ja, ich denke, das werde ich mal mit in die avr-libc aufnehmen.

[yalu (Gast)]

Gerade für µC-Anwendungen ist der Heapsort oft besser geeignet als der
Quicksort.

Zum einen, wie schon von Jörg geschrieben, wegen der günstigeren
Speichernutzung (variabler Stackverbrauch wegen Rekursion ist bei
kleinen Speichern ähnlich bäh wie malloc).

Zum anderen ist der Worst-Case-Rechenaufwand beim Heapsort O(n log n),
beim Quicksort O(n²). Im Mittel performt der Quicksort zwar trotzdem
besser, aber bei Steuerungsanwendungen u. ä. zählt meist die maximal
benötigte Zeit.