ArrayList für drei verschiedene Typen

[Xantus]

1. mit u - Xantus!
2. habe ich denn soviel Zeit, getter- und setter- Funktionen zu schreiben? Denkanstöße sind nicht mit vollständigen Lösungen bzw. Implementationen gleichzusetzen, dafür reicht wieder die Zeit noch ist es schön, so langen Code zu pasten, nur um nochmals 3 get-Funktionen zu haben, deren Funktionsweise man sich sowieso denken kann.

[uwerothfeld]

Hallo Zusammen,

also ich will dann mal wieder bissl Licht in das Dunkel bringen ;). Worum geht es? Also Kontext mäßig geht es um Sensorknoten. Dabei befinde ich mich in einer Umgebung in der wir folgende Bedingungen zu berücksichtigen haben:

1. der RAM ist extrem schmal bemessen
2. der ROM ist extrem schmal bemessen
3. soetwas wie malloc existiert nicht
4. der Prozessor ist klein und langsam (8bit bei 20Mhz oder so)
5. Energie ist knapp auf dem Knoten, sprich viel rechnen ist auch doof

benötigt werden die Listen jeweils nur zum temporären Zwischenspeichern von Werten. Also die Liste wird gefüllt, dann der erste Wert der List genommen und bearbeitet, irgendwann erhält man ein Ergebnis, dies wird sich gemerkt und das Ergebnis für den zweiten Wert auf der Liste gebildet. Und so weiter. Soviel zum Kontext. Nun will man also eine kleine, feine Lösung, mit der man dennoch wenigstens bissl arbeiten kann. Ich habe mich daher für die union Variante entschieden, da ich nicht so richtig weiß, wie ich bei void* meine Elemente dauerhaft auf den Stack bekomme. So, wie ich es jetzt habe, ist die Liste einfach global, thats it. Nun meine Frage, könnt ihr euch mal meine Lösung anschauen und sagen ob dies so ok ist, bzw. was sich verbessern lässt, bzgl. der oben genannten Punkte? Hier mein Code:

Datei data_type.h:

#ifndef _DATA_TYPE_H
#define	_DATA_TYPE_H

#ifdef	__cplusplus
extern "C" {
#endif

    typedef enum {
        SEL_VAR,
        AGG_FUNC,
        SET_PAIR
    } DATA_TYPE;

    typedef uint8_t sel_var;

    typedef struct {
        uint8_t func_nr;
        uint8_t var_nr;
    } agg_fun;

    typedef struct {
        uint8_t var_nr;
        uint32_t value;
    } set_pair;

    typedef struct {
        DATA_TYPE type;

        union {
            sel_var select;
            agg_fun agg;
            set_pair set;
        };
    } elem;

#ifdef	__cplusplus
}
#endif

#endif	/* _DATA_TYPE_H */

Datei array_list.h

#ifndef _ARRAYLIST_H
#define	_ARRAYLIST_H

#ifdef	__cplusplus
extern "C" {
#endif

    /**
     * This file defines a simple array list.
     * Its offers methods to add, remove and read elements from the 
     * list.
     */

#include "data_type.h"
#include <stdlib.h>

#define MAXLENGTH 5 
#define FIRSTPOS 0 
#define OVERFLOW 0xFF

    /**
     * Defines the list struct.
     */
    typedef struct {
        elem content[MAXLENGTH];
        int last;
    } List;

    /**
     * clears the list
     */
    void clearList(List *l);

    /**
     * adds elem e to the end of the list
     */
    void addElem(List *l, elem e);

    /**
     * returns the element at index i from list
     */
    elem* getElem(List *l, uint8_t i);

    /**
     * removes the element at the given index from the list
     */
    void removeElem(List *l, uint8_t index);

    /**
     * returns the size of the list
     */
    uint8_t listSize(List* l);

#ifdef	__cplusplus
}
#endif

#endif	/* _ARRAYLIST_H */

Datei array_list.c:

#include "array_list.h" 

/* 
 * File:   array_list.c
 *
 * Created on 20. August 2008, 13:08
 */

/**
 * clears the list
 */
void clearList(List *l) {
    l->last = FIRSTPOS;
}//End clear

/**
 * adds elem e to the end of the list
 */
void addElem(List *l, elem e) {

    if (l->last < MAXLENGTH) {
        l->content[l->last] = e;
        l->last++;
    }//End if
}//End add

/**
 * returns the element at index i from list
 */
elem* getElem(List *l, uint8_t i) {

    if (i < l->last) {
        return &l->content[i];
    }//End if

    return NULL;

}//End get

/**
 * removes the element at the given index from the list
 */
void removeElem(List *l, uint8_t index) {

    uint8_t i;

    for (i = index; i < l->last && i < MAXLENGTH; i++) {
        l->content[i] = l->content[i + 1];
    }//End for

    l->last--;
    if (l->last == OVERFLOW)
        l->last = FIRSTPOS;

    if (l->last >= MAXLENGTH)
        l->last = MAXLENGTH - 1;
}//End remove

/**
 * returns the size of the list
 */
uint8_t listSize(List* l) {
    return l->last;
}//End size

Also mich interessiert dazu eure Meinung. Ist dies ok so oder sollte man was ändern, etc. Nun noch ne weitere Frage, wie kann ich nun die MAXLENGTH variabel machen? Weil ich wie in meinen ersten Post schon sagte, die Liste insgesamt dreimal habe. Nun wäre es toll wenn ich für Liste 1 eine MAXLENGTH_1 definieren könnte und so weiter. List benutze ich als Bezeichnung für diese Struktur, da es sich um eine Datenstruktur mit einer endlichen Anzahl von Elementen handelt. Die Definition über Pointer halte ich nicht für zwingend, auch wenn sicherlich einige da anderer Meinung sind. Typsicherheit ist hingegen eine von mir persönlich als sehr angenehm empfundenen Eigenschaft, welche aber in meiner Lösung nicht gegeben ist. Da lag der Fokus mehr auf Handharbarkeit. Das mit dem Baum verstehe ich nicht, da eine Liste im Gegensatz zu einem Baum immer eine Totalordnung ist, ein Baum jedoch "nur" eine Halbordung, auch wenn er zu einer Liste degenerieren kann. Ha. Nun ist aber gut. Berichtigt mich, wenn ich mich irre.

Gruß und schon mal dank,
Uwe

[besserwisser]

@supertux
jeder, wie er s haben will.

@uwerothfeld
mal eine ganz blöde frage: wieso machst du das alles so ultra kompliziert? was du brauchst ist keine liste sondern ein simples array.

wenn man mal annimmt, dass deine zahlen messwerte sind, bekommst du von einem interrupt handler oder durch polling bei jedem durchlauf einen wert.

du allokierst zur compilierzeit derzeit einfach die maximale menge an werten. das ist schon mal ok, wenn du kein malloc hast. die frage ist nur, wieso du das über so einen komischen wrapper machen willst? es wär doch viel einfacher, das mit einem simplen pointer zu machen. das is schneller und braucht so gut wie gar keinen code.

du nimmst einen pointer auf elem, den du mit "content" initialisierst. jeden neuen messwert schreibst du an die stelle, auf die der pointer zeigt und inkrementierst diesen pointer danach.

zum berechnen der nicht-temporären werte machst du genau das gleiche und gehst somit deine "liste", die einfach nur ein array ist, durch.

es ist löblich, dass du dir viele gedanken machst, aber hier denkst du eindeutig viel zu kompliziert.

[uwerothfeld]

Morgen :),

also

besserwisser schrieb:

@uwerothfeld
mal eine ganz blöde frage: wieso machst du das alles so ultra kompliziert? was du brauchst ist keine liste sondern ein simples array.

Echt? Findest du es kompliziert? Finde ich eigentlich nicht, aber ok. Vielleicht liegt es daran, dass ich eigentlich eher aus der OO Ecke komme. Zugriffe direkt auf Datenstrukturen sind daher für mich etwas böses ;).

besserwisser schrieb:

wenn man mal annimmt, dass deine zahlen messwerte sind, bekommst du von einem interrupt handler oder durch polling bei jedem durchlauf einen wert.
du allokierst zur compilierzeit derzeit einfach die maximale menge an werten. das ist schon mal ok, wenn du kein malloc hast. die frage ist nur, wieso du das über so einen komischen wrapper machen willst?

Diese Annahme ist nicht ganz richtig. Es sind zwar quasi Messwerte, diese werden allerdings in einem Rutsch in die Liste geschrieben. Die Abarbeitung dieser Liste erfolgt dann allerdings durch verschiedene Funktionen und unterschiedliche Zeiten. Daher der Wrapper, da ich mir keine Gedanken machen wollte, wann wie und wo ich Zuzugreifen habe und ob eigentlich noch was da ist. Also Funktion A füllt die Liste und anschließend werden (hier nicht weiter wichtig) die Funktionen B und C aufgerufen, z.B. C-B-C-C-B-B-C. Nun will ich in B und C halt relativ einfach auf die Liste zugreifen können, ohne derren interna zu kennen. Daher soll mir die Liste sagen: Ich bin leer.

besserwisser schrieb:

du nimmst einen pointer auf elem, den du mit "content" initialisierst. jeden neuen messwert schreibst du an die stelle, auf die der pointer zeigt und inkrementierst diesen pointer danach.

Wie meinst das genau? Ich glaub dafür ist es noch zu früh für mich.

Im Moment ist die "Liste" in der Tat nur ein Array, richtig. Ich hätte gerne eher etwas in Richtung echter verketteter Liste gehabt, weiß aber nicht wie und ob überhaupt so etwas statisch geht, ohne Speicher zu verschwenden beim Elemente entfernen.

Gruß

[supertux]

uwerothfeld schrieb:

besserwisser schrieb:

du nimmst einen pointer auf elem, den du mit "content" initialisierst. jeden neuen messwert schreibst du an die stelle, auf die der pointer zeigt und inkrementierst diesen pointer danach.

Wie meinst das genau? Ich glaub dafür ist es noch zu früh für mich.

Im Moment ist die "Liste" in der Tat nur ein Array, richtig. Ich hätte gerne eher etwas in Richtung echter verketteter Liste gehabt, weiß aber nicht wie und ob überhaupt so etwas statisch geht, ohne Speicher zu verschwenden beim Elemente entfernen.

da du kein malloc hast (und wahrscheinlich keine sonstige Speicherverwaltungsfunktion hast, ist es schwer Speicher zur Laufzeit zu reservieren, deswegen reservierst zu zur Compilezeit den Speicher und benutzt diesen. Am einfachsten ist es dann mit einem Array. Das Problem mit dem obigen Ansatz ist es, wenn du Daten löscht, hinzufügst, wieder löscht, usw, dann fragmentiert sich der Speicher und müsstest defrgmentieren, damit du keinen Buffer Ovreflow erzeugst.

Ich hatte dieses Problem mit einem selbst geschriebenen Mikrokernel, da habe ich es so gelöst:

ich hab mir schnell eine Double-Linked-List Struktur (struct DLList) geschrieben und global ein Array vom Typ struct DLList angelegt. Dann habe ich so initialisiert, dass für 1 <= i <= max-2 gilt

array[i].next = &array[i+1];

und sonst

array[0].prev = &array[max - 1];
array[max - 1].next = NULL;

Dann hab ich 2 Zeiger deklariert, free_space = &array[0]; und list = NULL . Ich denke, jetzt siehst du, wie das funktioniert. Mit einer geeigneter Funktion kannst du immer das erste freie Feld über mem = &free_space[0] bekommen und dann mit list[curr_num_elemnts-1].next = mem; in die aktuelle List bekommen. Dann weißt du, das nächste freie Element ist mem.next und kannst somit free_space wieder anpassen:

free_space = mem.next;
mem.next = NULL; /* weil das letzte Element der 'list'-Liste,
  die Information auf das nächste freie Feld nicht mehr gebraucht,
  weil free_space auf das richtige Feld hat */

Indem du die next und prev Elemete geschickt setzt, kannst du mit 2 Pointern sowohl die freien Felder als auch die verwendeten Felder verwalten, ohne den Speicher defragmentieren zu müssen. Wenn du mal ein Bsp willst oder so, dann schick mir ne PM (persönliche Nachricht) oder Mail übers Board.

[TheTester]

Die Erklärung von Supertux erinnert mich an eine "Freispeicherliste" für homogene Elemente. Eine knappe und einleuchtende Erklärung findet sich in einer Praktikumsaufgabe unter folgendem Link http://www.cs.hm.edu/~koehler/alg_dat/alg_dat_prakt_2008/p1_ss08.pdf

Weitere Quellen welche die Idee demonstrieren wären "Introduction do Algorithms (Cormen et. al)" dort findet sich etwas unter "free list". Und Knuth spricht in seinem ersten Buch (Fundamental Algorithms) von einer "available space list" um die grundlegende Idee zu verdeutlichen.

[Tippgeber]

Wollte gerade vorschlagen, dass eine ArrayList wie man sie zumindest derzeit im Sprachgebrauch nutzt kein normales Array ist, das einfach nur wächst, sondern tatsächlich einige Listen-Eigenschaften besitzt.
Bzw. diese Sichtweise ist schlecht, es lässt sich besser formulieren als eine Liste mit einigen Array-Eigenschaften.

Denn das meiste was eine Liste kann, kann man mit einem Array auch und das Löschen und Einfügen in der Mitte geht bei einem Array halt nicht in konstanter Zeit.
Daher ist es besser wenn man von einer Liste mit Array-Eigenschaften spricht. Man bekommt dadurch nämlich eine Liste mit O(1) Zugriff auf jedes Element. Dafür wird das Löschen/Einfügen in der Mitte allerdings nicht mehr in O(1) möglich.
Über die genauen Aufwände kann man i.A. nichts genaues sagen, das kommt auf die Implementierung drauf an. Die Java-Leute haben sich da recht viel Mühe gegeben.

[uwerothfeld]

Hallo zusammen,

also an einem Beispiel wäre ich wirklich interessiert. By the way: Wo ist hier die PM Funktion??? Aber was mich wundert: Wo soll die Fragmentierung und der BufferOverflow in meiner Implementierung herkommen? Ich sehe es nicht. Das PDF ist für mich nicht richtig einsetzbar, da ich O(n) zugunsten von Speicherersparniss gerne akzeptiere. Wie gesagt, Speicher ist bei mir extrem knapp, warten kann ich zu not

Gruß
Uwe

[-fricky-]

uwerothfeld schrieb:

Zugriffe direkt auf Datenstrukturen sind daher für mich etwas böses.

diesen aberglauben solltest du dir schnell abgewöhnen, wenn du's mit solchen minimalsystemen zu tun hast.

[uwerothfeld]

hi,

ja ist schon klar aber man kann sich doch zumindest das leben einfacher machen. ich finde addElem() ist besser lesbar statt list->content[list->next++]= ... oder ähnliches.

Softwarequalität durch Design sozusagen

Gruß

[supertux]

uwerothfeld schrieb:

also an einem Beispiel wäre ich wirklich interessiert. By the way: Wo ist hier die PM Funktion???

Geh mal auf http://www.c-plusplus.net/forum/profile-var-mode-is-viewprofile-and-u-is-13057.html da ist ein "Email senden" link.

uwerothfeld schrieb:

Aber was mich wundert: Wo soll die Fragmentierung und der BufferOverflow in meiner Implementierung herkommen? Ich sehe es nicht.

Fragmentierung und BufferOverflows kommen im Verfahren vom besserwisser vor, wenn man nur ein Array anlegt und ein Zeiger darauf hat, um an die Daten zu kommen. Das hat erstmal nichts mit deinem Code zu tun.

[uwerothfeld]

hallo und noch ne frage,

wie soll mir eigentlich der verzicht auf addElem, getElem ... Codesize sparen? Ich meine wenn ich auf das Array zugreife muß ich eh jedesmal schauen, ob noch Platz ist, mir merken wieviel Elemente ich schon gespeichert habe, was das letzte Element ist ... . Ich sehe da keinen Vorteil, ob ich nun den Code dafür einmal in eine eigene Funktion kapsele oder es jedesmal vor Ort mache. Kommentare?

Uwe

[uwerothfeld]

hi,

supertux schrieb:

Fragmentierung und BufferOverflows kommen im Verfahren vom besserwisser vor, wenn man nur ein Array anlegt und ein Zeiger darauf hat, um an die Daten zu kommen. Das hat erstmal nichts mit deinem Code zu tun.

Ja das leuchtet dann ein. Wollte dennoch mal fragen, man lernt ja nie aus

[besserwisser]

ok, ich geb auf. ich habe versucht, die einfachste methode anzugeben. aber im endeffekt muss doch uwerothfeld entscheiden, wie er es programmiern will.

wieso meine funktion buffer overflows hat und den speicher fragmentiert, weiß ich nicht. vielleicht erklärt mir das jemand?

@uwerothfeld
viel glück noch und schreib es so, wie du es für richtig hälst.

[-fricky-]

besserwisser schrieb:

wieso meine funktion buffer overflows hat und den speicher fragmentiert, weiß ich nicht. vielleicht erklärt mir das jemand?

das hab' ich auch nicht verstanden. zumal die elemente ja eine feste länge haben und man immer genau weiss, wieviel noch in den buffer passt. auch bei variablen elementlängen ist das ermitteln des noch freien speicherplatzes keine hexerei. deine methode ist simpel und genau das richtige für so'n minimalsystem wie's der OP hat. allerdings würde ich das array als ringbuffer ansprechen, so dass schon mal was rausgeholt werden kann, während daten eintrudeln.

[supertux]

besserwisser schrieb:

wieso meine funktion buffer overflows hat und den speicher fragmentiert, weiß ich nicht. vielleicht erklärt mir das jemand?

ok, ich wollte nicht sagen, dass deine Funktion welche hat, sondern wenn man nur ein Array legt und ein Pointer drauf kann es halt dazu führen

struct gen_data_type memory[MAX_ELEMS];
struct gen_data_type *list = &memory[0];
...
list->data = ...;
list++;
list->data = ...;
list++; 
...
list++; /* Gefahr über die Array Grenze zu gehen */

Aber ich muss jetzt zugeben, dass beim 2. Durchlesen des ganzen Threads die Sache nicht mehr so erscheint, wie ich es am Anfang interpretiert habe. Ich hatte schon mal eine (wie auf der anderen Seite) beschriebene Liste gehabt und wenn man viele Listenoperationen insert,insert,remove,insert,usw. hat, dann hätte man entweder bei jedem remove alles nach dem gelöschten Element im Array verschieben müssen oder eine Lücke lassen (darum verwalte ich da 2 Zeiger für den freien und den belegten Speicher). Sorry, jetzt merke ich aber, dass dieser Ansatz nicht so ganz mit deinem übereinstimmt.

[-fricky-]

supertux schrieb:

list++; /* Gefahr über die Array Grenze zu gehen */

nicht wirklich. du kennst ja MAX_ELEMS und die aktuelle zeigerposition.

[supertux]

-fricky- schrieb:

supertux schrieb:

list++; /* Gefahr über die Array Grenze zu gehen */

nicht wirklich. du kennst ja MAX_ELEMS und die aktuelle zeigerposition.

natürlich kennst du die, aber der nicht aufmerksame Programmierer könnte das vergessen. Ich geb zu, hab vorhin was falsch verstanden, weil ich nur den Thread schnell überflogen bin.

[-fricky-]

supertux schrieb:

Ich geb zu, hab vorhin was falsch verstanden, weil ich nur den Thread schnell überflogen bin.

halb so schlimm. ich hab' auch nicht verstanden, wieso er einträge mittendrin löschen muss und bestimmt auch unpassende tipps gegeben.

[supertux]

-fricky- schrieb:

supertux schrieb:

Ich geb zu, hab vorhin was falsch verstanden, weil ich nur den Thread schnell überflogen bin.

halb so schlimm. ich hab' auch nicht verstanden, wieso er einträge mittendrin löschen muss und bestimmt auch unpassende tipps gegeben.

ich ging eher von einem generellen Einsatz einer Liste, da hat man nicht nur Einfüge- sondern auch Löschoperationen, deswegen habe ich das erwähnt. Aber vielleicht war es dann zu viel des Guten