Map/Multimap in C, Vorschläge?

Hallo,

ich muss in C soetwas ähnliches wie eine Map/Multimap (aus C++) realisieren.
Also einfach eine Tabelle mit einer int Spalte und einer Spalte mit einem Zeiger auf (irgendwas). Der Schlüssel dabei soll die int Zahl sein. Also für eine bestimmte Zahl ein bestimmter Zeiger auf (irgendwas)

Was schlägt ihr vor? Vielleicht einfach soetwas?

irgendwas* arr[256]; /*ein Array von 256 Zeigern auf irgendwas*/

Zugegreifen könnte man ja über den Index Operator.

Was jedoch wenn ich zu jeder int Zahl mehrere Zeiger speichern möchte. Wie dann?

irgendwas* arr[256][2]; /*also immer zwei Einträge pro Dimension*/

Würde das einer Map oder Multimap aus C++ nahekommen?

CStoll

Wenn ich die C++ Container nachbilden müsste, würde ich dafür kein Array verwenden, sondern einen (balancierten) Binärbaum:

typedf struct _node
{
  Typ1 key;
  Typ2 value;
  struct _node *parent,*left,*right;
  ...//eventuell Verwaltungsdaten
} node;

Zum Einfügen wird ein neuer node per malloc() angefordert und an der richtigen Stelle in die Baumstruktur eingeklinkt (für map mußt du noch darauf achten, ob der Schlüssel schon vorkommt).

@CStoll:

sehr elegant, danke.

Habe nur eine Einschränkung:
Ich darf nichts dynamisch allokieren (ist ein embedded Gerät), es sollte also statisch vor dem compilieren klar sein wie groß die Map ist,
also nicht wie beim binären Baum mit der Zeit wachsen.

Simon2

Hi,

ist aber eigentlich auch kein Problem.
Du musst dann Deine eigene Speicherverwaltung "drunterlegen".
Im Prinzip bleibt es dann bei dem Array und der "Binärbaum" ist dann eine Verwaltungsstruktur dadrüber.

Gruß,

Simon2.

CStoll

Dann nimmst du halt als "Speicher" ein ausreichend großes node-Array und realisierst das Anlegen und Freigeben, indem du Zeiger auf dieses Array herumreichst:

node ram[RAM_SIZE];
node* first_free = ram;

void init_ram(void)
{
  int i;
  //verkette alle freien Knoten zu einer Liste
  for(i=0;i<RAM_SIZE-1;++i)
  {
     ram[i].parent=&ram[i+1];
     ram[i].left=ram[i].right=NULL;
  }
  ram[RAM_SIZE-1].parent=ram[RAM_SIZE-1].left=ram[RAM_SIZE-1].right=NULL;
}

node* alloc_node(void)
{
  if(first_free==NULL)
    error("not enough memory");
  node* pRet=first_free;
  first_free=first_free->parent;
  return pRet;
}

void free_node(node* ptr)
{
  ptr->parent = first_free;
  first_free = ptr;
}