ArrayList für drei verschiedene Typen

wie wäre es damit, nur pointer zu speichern? void* ist dein freund. willst du an der größe des source codes sparen oder an der größe des binären codes?
die für c sauberste und wohl leserlichste version wäre, es per void* zu machen.
noch ein kommentar zu arraylist: arrays und listen sind zwei verschiedene datentypen, die nur wenig miteinander zu tun haben. was du brauchst, ist ein baum.

supertux

besserwisser schrieb:

wie wäre es damit, nur pointer zu speichern? void* ist dein freund. willst du an der größe des source codes sparen oder an der größe des binären codes?
die für c sauberste und wohl leserlichste version wäre, es per void* zu machen.
noch ein kommentar zu arraylist: arrays und listen sind zwei verschiedene datentypen, die nur wenig miteinander zu tun haben. was du brauchst, ist ein baum.

sicherlich ist der Aufwand mit void-Pointern geringer, aber ich sehe in der Handhabung mehr Nachteile: es ist alles nicht type-safe, wenn du aus einer Funktion eine Liste (oder Array meinetwegen) bekommst, musst du von Anfang an kennen, welches Datentype hinter dem void* an der 0. Stelle, an der 1. Stellen, usw. steckt. Was ist, wenn diese Festlegung erst zur Laufzeit festgestellt werden kann? Dann müsstest du separt eine weitere Liste führen, wo du nachschauen muss, um welches Datentyp es sich handelt. Das finde ich gefährlicher, weil man selbst als erfahrener Pointer-Jonglier viele Fehler machen kann.

Deswegen ist eine Lösung wie die von Xantus eher die bessere, weil du zur jedem Zeitpunkt immer das genaue Datentyp kennst. Ein bisschen aufwändiger aber im Grunde deutlich sicherer als nur mit void-Pointern zu arbeiten.

besserwisser schrieb:

was du brauchst, ist ein baum.

um sich aufzuhängen? oder wie?

@supertux
type-safe ist es mit der lösung von xantos ebenso wenig. er hat nämlich klugerweise auf die get methoden verzichtet. wieso wohl? wenn du nicht weißt, welchen typs ein element der liste ist, weißt du auch nicht, welche get-funktion du aufrufen musst. get_int, get_char, get_double? dsa ist vergleichbar mit dem casten eines void* pointers.

jetzt kommt möglicherweise das argument: "aber das speicher ich ja dazu...". stimmt. das kann ich bei einem void* pointer auch machen.

die void* methode spart außerdem code, da ich keine drei verschiedenen funktionen für alle drei datentypen brauche (get, set, print, ...).

hier, wie so oft in diesem forum, idt das problem, dass der threadersteller nicht angibt, für was er das braucht, was er will. damit kann ich schwer etwas über die sinnhaftigkeit einer solchen liste aussagen. die thread ersteller sollten immer den kontext ihrer fragen mit angeben.

supertux

besserwisser schrieb:

@supertux
type-safe ist es mit der lösung von xantos ebenso wenig. er hat nämlich klugerweise auf die get methoden verzichtet. wieso wohl? wenn du nicht weißt, welchen typs ein element der liste ist, weißt du auch nicht, welche get-funktion du aufrufen musst. get_int, get_char, get_double? dsa ist vergleichbar mit dem casten eines void* pointers.

ich hab in meinem Post geschrieben, dass xantos Lösung nicht 100% type-safe wäre sondern, dass sie sicherer als die reine void*-Lösung ist. Das ist eine Stärke und gleichzeitig eine Schwäche in C. Ich hab in meiner Arbeit sowohl mit void*-Listen als auch mit xantos-ähnlichen Listen zu tun und ich weiß, wann welche einen Vorteil hat.

Mit xantos Listen ist es generell auch nicht gewährleistet, dass man die richtige Funktion nimmt, aber du kannst wenigsten mit der Abfrage von DataTyp->what aufs Datentyp kommen, wie willst du das nur mit einem void-Zeiger machen? In beiden Fällen ist ein 'what' Member am sinvollsten.

Der Ansatz ist auch nicht der falsche, es gibt mehrere Bibliotheken, die sowas implementieren. GTK+ macht viel davon Gebrauch (sogar eine sehr ähnliche Implementierung) und dort funktioniert es auch zuverlässig.

Wenn du nur mit void-Zeigern arbeitest, musst du meisten immer vorher Speicher reservieren (und später ans Freigeben denken). Bei dem union ist das nicht der Fall; vor allem wenn du nur mit numerischen Listen (int, double, floats, usw) arbeitet, fände ich lästig für jeden Wert erstmal Speicher anfordern zu müssen anstatt set_int(liste, value), set_float usw. zu benutzen.

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:

der RAM ist extrem schmal bemessen
der ROM ist extrem schmal bemessen
soetwas wie malloc existiert nicht
der Prozessor ist klein und langsam (8bit bei 20Mhz oder so)
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

@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.

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

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

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.

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.