 |
 |
| View previous topic :: View next topic |
| Author |
Message |
haxan7
Joined: 27 Jul 2013
Posts: 79
|
| Dynamic Memory to implement Queues |
 Posted: Mon Jul 06, 2015 12:16 pm |
 |
|
Would it be a good idea to implement a linked list based queue using malloc to maintain a queue of strings?
The char array would be 200 bytes each and size of queue would not increase beyond 5-6 nodes.
PIC24EP512GU810 with 536Kb ROM and 52Kb RAM so, memory is no issue.
Any advice would be much appreciated. |
|
 |
Ttelmah
Joined: 11 Mar 2010
Posts: 19339
|
|
| Posted: Mon Jul 06, 2015 1:26 pm |
|
|
Perfectly sensible.
But...
If you only have 6 nodes, and 200bytes per node, it'd be significantly _faster_ to just have it as a fixed structure.
Generally, the PIC is quite inefficient at handling indexed data.
However, having a linked list makes sense if the data size if variable, and if there is something stored with the items that makes it easy to identify the 'right' entry (CRC of the string for example). Then the walk through the list just becomes a matter of pulling the pointer forwards, and reading the 'identifier' at this point, then if it is right, accessing the string, otherwise read the next pointer. Without this 'identifier', you are just going to have to search the string, which might as well just be done without the link.
Without knowing what your strings 'are' or how they are to be used, it is difficult to know whether a linked list is a sensible way to go. |
|
|
jeremiah
Joined: 20 Jul 2010
Posts: 1322
|
|
| Posted: Mon Jul 06, 2015 1:37 pm |
|
|
| You can also implement a linked list style structure using a fixed sized array. Instead of pointers, your links (next, prev, etc.) are indexes to the array. It's quite a bit faster as long as you don't mind having a known boundary size. |
|
|
RF_Developer
Joined: 07 Feb 2011
Posts: 839
|
| Re: Dynamic Memory to implement Queues |
| Posted: Tue Jul 07, 2015 2:40 am |
|
|
| haxan7 wrote: | Would it be a good idea to implement a linked list based queue using malloc to maintain a queue of strings?
|
On 16/18 series PICs I'd say no, but on a 24/dsPIC/33 PIC with fairly decent RAM size? Okay - its a well-established, sound, technique. As people have said, if the list has a relatively small number of entries and is well-constrained then a fixed list of some sort is probably a less painful, i.e. simpler, more robust and and less prone to error, option.
Be aware that Cs dynamic memory support is very basic and, while we all got along with it okay for many years, always causes programmers problems. You need to be very careful about managing the queue, and make sure you consistently reclaim any dynamically allocated memory. Memory leaks and references to non-existant memory cause many unexplained restarts, data corruptions and unexpected results, not to mention sleepless nights.
I recommend implementing the queue in a set of closely related routines (that would be queue object in an object orientated language), doing all allocation and freeing in those routines, rather than anywhere else in your code. You also need to decide what to do if and when memory cannot be allocated - how do you recover? Indeed, can the code recover from it? |
|
|
haxan7
Joined: 27 Jul 2013
Posts: 79
|
|
| Posted: Tue Jul 07, 2015 12:45 pm |
|
|
Thanks a lot for the responses.
I went ahead and implemented the queue using linked lists, but I went a step further and implement a generic queue.
This was my first time writing code with dynamic memory allocation. Please let me know if I missed anything.
I would really appreciate your take on this.
| Code: |
#include <STDLIBM.H>
#include <stdint.h>
#define bool int
struct node{
/* Node* must be at the top */
struct node* next;
char data[1];
};
struct Queue{
struct node* head;
struct node* tail;
/* Size of Node Stuct */
uint16_t size;
/* Size of Node Struct - Size of Node* */
uint16_t dataSize;
};
bool enqueue(struct Queue* s, char* data){
if(s == NULL){
printf("Queue not initialized\n");
return 0;
}
struct node* p = malloc(s->size);
if(p == NULL){
printf("malloc() failed\r\n");
return 0;
}
/* Copy Data to Node */
// strcpy(p->data, data);
memcpy(p->data, data, s->dataSize);
p->next = NULL;
/* Add Note to Queue */
if( s->head == NULL && s->tail == NULL){
/* Queue Is empty */
s->head = s->tail = p;
}else{
/* Queue NOT empty */
s->tail->next = p;
s->tail = p;
}
return 1;
}
bool dequeue(struct Queue* s, char* data){
if(s == NULL){
printf("Queue not initialized\r\n");
return 0;
}else if( s->head == NULL && s->tail == NULL ){
printf("Queue is empty\r\n");
return 0;
}else if( s->head == NULL || s->tail == NULL ){
printf("ERROR: Something wrong with the Queue\r\n");
return 0;
}
/* Reference to the Node to be Deleted */
struct node* temp = s->head;
/* Copy Data */
if(data != NULL){
// strcpy(data, temp->data);
memcpy(data, temp->data, s->dataSize);
}
/* Move Head to the next Node */
s->head = s->head->next;
/* If Head==Tail was the only element */
if( s->head == NULL ) s->tail = NULL;
/* Deallocate Memory */
free(temp);
return 1;
}
bool isEmpty(struct Queue* s){
if(s->head == NULL){
return 1;
}
return 0;
}
bool list_delete( struct Queue* s ){
while( s->head ){
dequeue(s,NULL);
}
return 1;
}
struct Queue* list_new(uint16_t size, uint16_t dataSize){
struct Queue* p = malloc(sizeof(*p));
if(p == NULL){
printf( "LINE: %d, malloc() failed\n", __LINE__);
return NULL;
}
p->head = p->tail = NULL;
p->size = size;
p->dataSize = dataSize;
return p;
}
struct nodeString10{
struct node* next;
char data[10];
}nodeString10;
struct nodeString20{
struct node* next;
char data[20];
}nodeString20;
struct nodeFloat{
struct node* next;
float data;
}nodeFloat;
void testQueue(){
struct Queue* Queue_String10 = list_new(sizeof(nodeString10),sizeof(nodeString10.data));
struct Queue* Queue_String20 = list_new(sizeof(nodeString20),sizeof(nodeString20.data));
struct Queue* Queue_Float = list_new(sizeof(nodeFloat),sizeof(nodeFloat.data));
char temp[2 0];
float i;
for(i=0; i<20; i+=0.1){
sprintf(temp,"%.3f",i);
enqueue(Queue_String10, temp);
enqueue(Queue_String20, temp);
enqueue(Queue_Float, (char*)&i);
}
char temp1[20];
char temp2[20];
float tempFloat;
while(!isEmpty(Queue_Float)){
dequeue(Queue_String10, temp1);
dequeue(Queue_String20, temp2);
dequeue(Queue_Float, (char*)&tempFloat);
printf("%s, %s, %.3f\r\n",temp1, temp2, tempFloat);
}
}
|
|
|
|
guy
Joined: 21 Oct 2005
Posts: 291
|
|
| Posted: Wed Jul 08, 2015 12:49 am |
|
|
Throws me back to Turbo Pascal school exercises! 1992 wow 
next would be a binary tree structure 
Just to make sure we're on the same page- if all you need is a queue then you can use a simple array of strings in RAM (technically 2D char array) and work with a head and tail pointers, no need to move data across memory.
If you need to sort or push strings in between then it might be worth using a linked list. Even then I would create an array of bytes which are pointers to the strings and reorder the array very quickly if required.
Thanks anyway for sharing your code! |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
|
FAQ 
Search
Register
Profile 
Log in to check your private messages 
Log in
