Linked list με static memory allocation

[Dr.Fuzzy]

Στο παρακάτω απλό παράδειγμα μιας linked list, προσπαθώ να δω πως μπορεί να υλοποιηθεί χωρίς pointers, pointers to pointers, pointers casting, self referential structures και γενικά dynamic memory allocation.

linked_list.h

#ifndef LINKED_LIST_H
#define LINKED_LIST_H

#include <iostream>
using namespace std;

struct Node {
   int data;
   struct Node *next;
};

extern struct Node* head;

void insert(int new_data);

#endif

linked_list.cpp

#include <cstdlib>
#include <iostream>
#include "linked_list.h"

using namespace std;

struct Node* head = NULL;

void insert(int new_data) {
   struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
   new_node->data = new_data;
   new_node->next = head;
   head = new_node;
}

main.cpp

#include "linked_list.h"
#include <iostream>
using namespace std;

void display() {
  struct Node* ptr;
  ptr = head;
  while (ptr != NULL) {
    cout << ptr->data << " ";
    ptr = ptr->next;
  }
}

int main() {
  insert(5);
  insert(6);
  insert(1);
  insert(2);
  insert(7);
  cout << "The linked list is: ";
  display();
  return 1;
}

 

Επεξ/σία 10 Φεβρουαρίου 2019 από Dr.Fuzzy

[kaliakman]

Δεν μπορώ να καταλάβω το πρόβλημα σου. Πως θα κρατάς δομή δεδομένων που δεν έχει fixed μέγεθος χωρίς να παίρνεις memory κατά το δοκουν? 

Μπορείς να φτιάξεις έναν πίνακα στατικο που θα του συμπεριφερεσαι σαν λίστα αλλά αυτό δεν έχει νόημα αν όντως θες λίστα.

Επεξ/σία 10 Φεβρουαρίου 2019 από kaliakman

[Dr.Fuzzy]

1 hour ago, kaliakman said:

Δεν μπορώ να καταλάβω το πρόβλημα σου. Πως θα κρατάς δομή δεδομένων που δεν έχει fixed μέγεθος χωρίς να παίρνεις memory κατά το δοκουν? 

Μπορείς να φτιάξεις έναν πίνακα στατικο που θα του συμπεριφερεσαι σαν λίστα αλλά αυτό δεν έχει νόημα αν όντως θες λίστα.

Το πρόβλημα ξεκινάει λόγω περιορισμών που έχει η high level synthesis που είναι απόλυτα λογικοί αφού πρόκειται για σχεδίαση υλικού και όχι instructions σε κάποιο CPU (δε θα μπω σε περισσότερες λεπτομέρειες διότι θα ξεφύγουμε).

Mπορώ για παράδειγμα να έχω ένα fixed pre-allocated memory size και πάνω σε αυτό να λειτουργεί το linked list.

 

[imitheos]

Μία γρήγορη εκδοχή χωρίς ελέγχους και με λογικά λάθη είναι η παρακάτω:

linked_list.h

#ifndef LINKED_LIST_H
#define LINKED_LIST_H

#include <iostream>
using namespace std;

struct Node {
   int data;
   int next;
   int used;
};

extern int head;
extern struct Node mynodes[100];

void insert(int new_data);


#endif /* LINKED_LIST_H */

linked_list.cpp

#include <cstdlib>
#include <iostream>
#include "linked_list.h"

using namespace std;

struct Node mynodes[100] = { 0 };
int head = 0;

void insert(int new_data) {
   int new_head = head;
   while (mynodes[new_head].used)
      new_head++;
   mynodes[new_head].data = new_data;
   mynodes[new_head].used = 1;
   if (new_head != head)
      mynodes[new_head].next = head;
   else
      mynodes[new_head].next = -1;
   head = new_head;
}

Επειδή είπες θέλεις fixed μνήμη χωρίς δεσμεύσεις και χωρίς δείκτες, ορίζουμε κατευθείαν ένα πίνακα με όσο μέγεθος θέλεις και αντί για δείκτη next έχουμε ένα ακέραιο που δείχνει στο τάδε στοιχείο του πίνακα. Με τον πίνακα φυσικά χάνεις όλη την ευκολία των linked lists.

Στο τέλος εκείνο το -1 για next θα οδηγήσει το main.cpp να προσπελάσει μνήμη που δεν πρέπει. Άλλη έλλειψη είναι ότι δεν ελέγχω αν ξεπερνάμε το 100 που δήλωσα, το new_head ξεκινά πάντα από το head οπότε δεν θα χρησιμοποιήσει ελεύθερες θέσεις που μπορεί να αφαιρέθηκαν.

Edit: Ξέχασα να αναφέρω ότι εκείνα τα  = 0, = { 0 } τα έβαλα για να είναι πιο εμφανής η λειτουργία του κώδικα αλλά δεν χρειάζονται φυσικά.

main.cpp
 

#include "linked_list.h"
#include <iostream>
using namespace std;

void display() {
  int i = head;
  while (mynodes[i].used) {
    cout << mynodes[i].data << "(" <<  i << ") ";
    i = mynodes[i].next;
  }
}

int main() {
  insert(5);
  insert(6);
  insert(1);
  insert(2);
  insert(7);
  cout << "The linked list is: ";
  display();
  return 1;
}

Φυσικά για να χρησιμοποιηθεί ο κώδικας σε κάτι ουσιαστικό θέλει ένα κάρο βελτιώσεις αλλά προσπάθησα να αλλάξω όσο το δυνατόν λιγότερα από τον κώδικά σου. Άφησα και τα cout, iostream όπως τα είχες αν και είναι το μόνο "c++" στοιχείο που βλέπω. Έβαλα εκτός από τη τιμή να τυπώνει και το στοιχείο του πίνακα σε παρένθεση.

Επεξ/σία 10 Φεβρουαρίου 2019 από imitheos

[Dr.Fuzzy]

@imitheos

Ωραίος, ναι αυτό ήθελα, μια υλοποίηση με array indexes αντί pointers και static memory allocation.

Το μόνο που άλλαξα είναι το while σε if, γιατι με while προφανώς o υπολογισμός του latency είναι undetermined διότι το loop bound είναι variable και η HLS δεν μπορεί να υπολογίσει το upper bound του loop.

Spoiler

E oχι cpp δεν το λες, αλλά μια και χρησιμοποιώ cout και cpp headers είπα να είμαι political correct...my ass bullshit!

 

Επεξ/σία 10 Φεβρουαρίου 2019 από Dr.Fuzzy

[imitheos]

1 ώρα πριν, Dr.Fuzzy είπε

@imitheos

Το μόνο που άλλαξα είναι το while σε if, γιατι με while προφανώς o υπολογισμός του latency είναι undetermined διότι το loop bound είναι variable και η HLS δεν μπορεί να υπολογίσει το upper bound του loop.

Ποιο while άλλαξες σε if; Αυτό της insert που αυξάνει την new_head; Αν ναι, το while είναι όντως άχρηστο όπως είναι τώρα ο κώδικας γιατί πάντα το new_head θα είναι head + 1. Αν όμως υλοποιήσεις μια συνάρτηση remove, τότε θα πάψει να ισχύει αυτό.

[Bloodskin]

Η linked list ειναι δυναμικο data structure για αυτο και οι συνδεσεις υλοποιουνται να δειχνουν σε blocks που δεσμευει/αποδεσμευει το προγραμμα απ το σωρο. Μπορω να φανταστω μια στατικη υλοποιηση που θα περνουσας σαν client τη λιστα σου στην insertion function και αυτη θα δηλωνει μια στατικη μεταβλητη ιδιου τυπου με το δεικτη που κανει το link , και θα τον συνδεε σ'αυτην , αλλα δεν το γλειτωνεις το segmentation fault.

Με λιγα λογια ,αν θες στατικη δομη , κι αν εχεις σταθερο αριθμο elements , φτιαξε array.

[Dr.Fuzzy]

4 hours ago, imitheos said:

Ποιο while άλλαξες σε if; Αυτό της insert που αυξάνει την new_head; Αν ναι, το while είναι όντως άχρηστο όπως είναι τώρα ο κώδικας γιατί πάντα το new_head θα είναι head + 1. Αν όμως υλοποιήσεις μια συνάρτηση remove, τότε θα πάψει να ισχύει αυτό.

Ναι το while της insert. Ναι αντιληπτό ότι θα πάψει τότε να ισχύει.

1 hour ago, Bloodskin said:

Η linked list ειναι δυναμικο data structure για αυτο και οι συνδεσεις υλοποιουνται να δειχνουν σε blocks που δεσμευει/αποδεσμευει το προγραμμα απ το σωρο. Μπορω να φανταστω μια στατικη υλοποιηση που θα περνουσας σαν client τη λιστα σου στην insertion function και αυτη θα δηλωνει μια στατικη μεταβλητη ιδιου τυπου με το δεικτη που κανει το link , και θα τον συνδεε σ'αυτην , αλλα δεν το γλειτωνεις το segmentation fault.

Με λιγα λογια ,αν θες στατικη δομη , κι αν εχεις σταθερο αριθμο elements , φτιαξε array.

Ναι αλλά δε θέλω array θέλω linked list που κάνει operate within a memory bound που καθορίζεται από το static allocation. 

Ξέχνα έννοιες όπως «προγραμμα», «σωρός», κλπ, δεν υπάρχει CPU εδώ, ο κώδικας δεν μεταφράζεται σε instructions αλλά σε ένα FSM και στη συνέχεια σε ένα ακολουθιακό κύκλωμα.

Επεξ/σία 11 Φεβρουαρίου 2019 από Dr.Fuzzy

[imitheos]

8 ώρες πριν, Dr.Fuzzy είπε

Ξέχνα έννοιες όπως «προγραμμα», «σωρός», κλπ, δεν υπάρχει CPU εδώ, ο κώδικας δεν μεταφράζεται σε instructions αλλά σε ένα FSM και στη συνέχεια σε ένα ακολουθιακό κύκλω

Μήπως τότε να έβλεπες μια προσεγμένη υλοποίηση και όχι αυτή που έδωσα;

[Dr.Fuzzy]

1 hour ago, imitheos said:

Μήπως τότε να έβλεπες μια προσεγμένη υλοποίηση και όχι αυτή που έδωσα;

Αυτό που έδωσες το ήθελα απλά ως coding proof of concept για dynamic data structures σε HLS. Διάλεξα επίτηδες τη linked list γιατί αποτελεί πχ,  foundation για μια DCEL, κλπ.

[the other one]

Χωρίς να γνωρίζω ακριβώς τις προδιαγραφές που θες, ένας custom allocator όπου θα σου επιστρέφει segments ενός given memory δε μας κάνει;

[Dr.Fuzzy]

10 hours ago, the other one said:

Χωρίς να γνωρίζω ακριβώς τις προδιαγραφές που θες, ένας custom allocator όπου θα σου επιστρέφει segments ενός given memory δε μας κάνει;

Ένα DMA για παράδειγμα;

[the other one]

Αν με το DMA εννοείς αυτό http://minirighi.sourceforge.net/html/group__KDMAAllocator.html ναι κάτι τέτοιο είχα στο νου μου.