www.mikrocontroller.net

Forum: Compiler & IDEs Lexikografische Sortierung von OIDs


Autor: Thomas Finke (thomas-hn) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Andreas Schwarz (andreas) (Admin) Benutzerseite Flattr this
Datum:

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

Autor: Thomas Finke (thomas-hn) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Andreas Schwarz (andreas) (Admin) Benutzerseite Flattr this
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Jörg Wunsch (dl8dtl) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Jörg Wunsch (dl8dtl) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.