Queue with linked list and counter in C

Question

I am implementing a queue with a linked list which is going to have data that will be send and received in the same program with simple commands and I want to add a counter to each data in the queue, values being new, pending or ack. So do I store it in an array or is there any other way because the number of counters will be huge?

#define TOTALPACKETS 100
#define WINDOW   5
#define ACK      2
#define PENDING  1
#define NEW      0 


typedef int Item ;
typedef struct node *link;  
struct node{                
    Item data;
    Item status;
    link next; 
};

int QUEUEempty(link head){
    return head==NULL;
}

void QUEUEput(link *head, link *tail, Item data, Item status){
    if (*head==NULL){
                    (*tail)=(link)malloc(sizeof(node)); 
                    (*tail)->data=data;
                    (*tail)->next=NULL;
                (*tail)->status=NEW;
                    *head=*tail;
                    return;}
    (*tail)->next=(link)malloc(sizeof(node));
    *tail=(*tail)->next;
    (*tail)->data=data;
    (*tail)->next=NULL;
    (*tail)->status=NEW;
    return;
}

Item QUEUEget(link *head){
    Item data=(*head)->data;
    Item status
    link t=*head;
    *head=(*head)->next;
    free(t);
    return data; 
}

If it's a queue then use linked list. Also use long if your counter will be very large and reuse is not an option. — drum
– drum, Commented Apr 6, 2013 at 19:18
Welcome to Stack Overflow. Please read the FAQ soon. It's difficult to help you much because you've not shown any of the code you're thinking of using. Is the linked list 'intrusive' (are the pointer(s) part of the structure that is being added to the list) or 'non-intrusive' (the list node structure includes a pointer to the data)? If it's intrusive, you add the counter to the structure. If it's non-intrusive, it isn't clear from your description where the counters might fit — or even what the counters will actually be counting. — Jonathan Leffler
– Jonathan Leffler, Commented Apr 6, 2013 at 19:32
Ok I will try to be more clear then.(I did read the FAQ though). I need a counter/pointer added to the structure used that will take one of three values (0 for NEW,1 for PENDING,2 for ACK) based on what stage the packet is after send() and receive().What I don't know about that is if after I add it in the structure, how am I going to change it? You write it as ptr->val = 0 let's say or you have to put every counter in an array to do it? — user2192519
– user2192519, Commented Apr 6, 2013 at 21:52

Jonathan Leffler · Accepted Answer · 2013-04-06 22:32:11Z

1

I like to think I'm fairly good at reading between the lines and divining the hidden intention, but I'm not able to get a good idea of what you're after. I'd make this into comments except there are too many words to fit comfortably in comments and the formatting is very limited. (It isn't really an answer — that's why it is CW.)

You talk about a 'counter' that has one of three values (NEW, PENDING, ACK). That sounds more like a state or status than a counter.

Let's try some design; you can say where this is going wrong. This assumes a non-intrusive queue design.

typedef struct Data Data;   /* This is the data that you're queueing - details TBS */

typedef struct QNode
{
    Data  *data;
    QNode *next;
    QNode *prev;
    ...possibly other data...status?
} QNode;

typedef struct Queue
{
    QNode *head;
    QNode *tail;
    ...possibly other data...counts?
} Queue;

extern int q_add(Queue *q, Data *d);    // Add datum d to queue per policy
extern int q_next(Queue *q, Data **dp); // Remove next datum from queue per policy

Now, there are at least two places where a system based on this outline could store a counter or state. One place would inside struct Data, an as yet opaque structure type. The other plausible place would be inside struct QNode. You could keep tabs on how many nodes are in each state with summary counters in struct Queue too, if that was what you are after.

With this as a starting point, what are you after? Everything is changeable at this point — but without something concrete to get going with, we're unable to help much more.

answered Apr 6, 2013 at 22:32

community wiki

Jonathan Leffler

Sign up to request clarification or add additional context in comments.

5 Comments

user2192519 Over a year ago

I edited first post with the code now that I have my computer. I want to implement the SR protocol in a single programm.I will keep sending my window-size and want to keep track of every packet inside with that status counter. Send() will change it from NEW or PENDING to PENDING , and receive() will change PENDING to ACK or PENDING. Now what I don't know is how το access every status without losing any of them in the code of those 2 functions and change their value .Hope that helps you understand.

Jonathan Leffler Over a year ago

'SR Protocol' as in 'Selective Repeat Protocol'. I'm intrigued by you dropping into Greek for 'how το access' in your comment. I dislike typedefs that include pointers, like typedef struct node *link; but I guess that's partly personal style (though a style preference shared by a lot of other programmers). For opaque types (not dereferenced to access members in user code), they're fine. For much else...well, let's say that (*tail)->next etc is verbose. I'd have link end = *tail; and then end->next etc. It's easier to understand.

Jonathan Leffler Over a year ago

I'm meditating on your updated code in the question. This line (*tail)=(link)malloc(sizeof(node)); only compiles if your C compiler is really a C++ compiler in disguise (MSVC, in other words). You haven't defined a type node (though you have defined a struct node, but C doesn't create a type node automatically, whereas C++ does).

user2192519 Over a year ago

You are probably right about C++ (I'm using Visual Studio 2008), and the Greek thing.Now on topic so I suppose it creates the node auto.You lost me a bit with your first answer ("For much else...etc"), it was just a personal statement right? So how do I add the status to it?Does it work if I use the line I already have (*tail)->status=NEW; and just use this to change the status of every packet I will be using every time? I suppose queue's tail is the one I will be using?

user2192519 Over a year ago

(*head)->status=PENDING; was what I meant. and I figure I will be getting the head packet of the queue not the tail.

Armali · Accepted Answer · 2014-06-18 12:18:54Z

You already have the status "counter" in your nodes, but (as Jonathan Leffler suggested) let's call it just state or status. In your ACK receive() of the Selective Repeat ARQ protocol implementation, there is the problem of accessing the node (not just the status, but also the data in case a retransmission is due) with the sequence number sent with the acknowledgement; we have to traverse the linked list to reach the right node, but during this traversal we can also free acknowledged nodes, so that's harmless.

Still, you could improve your data structure. We don't need an explicit state variable for every node, because states are strictly ordered. From head to tail of the list, first there are zero (or more only if you don't immediately free) ACK nodes, second there are zero or more PENDING nodes, and last there are zero or more NEW nodes. So, to maintain the state information, an index or pointer to the first NEW (and perhaps the first PENDING) node would suffice.

Collectives™ on Stack Overflow

Queue with linked list and counter in C

2 Answers 2

5 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related