Multi-linked queue

In a networking project I have multiple objects that each have a message queue (linked list). Each 开发者_如何学Cobject also has a few clients, and each client has a pointer to a node in the queue. When a client receives the message its pointer points to, its pointer goes to the next message in the queue. Now, when all the clients have received a message, I want that message to be freed so it doesn't take up memory. I did this by having a separate thread go through the objects and delete the unneeded messages, acting as a GC, but is there a better way of doing it?

Thanks.

---

You might be able to use reference counting to handle this. Assuming that all of the pointers to the queue elements are from the outside in (and never between queue elements), you can store in the queue cell a count of the number of pointers to it. Whenever you add a new pointer, you increment this reference count, and whenever a part of the program is done using the cell it drops the reference count, freeing it when it reaches zero. That way, as long as there's an outstanding pointer to the cell, it won't be freed, and as soon as the last reference to the queue cell is broken it will be reclaimed. You don't need a separate thread to do this.

---

A message has a list of subscribers.

Every time a subscriber opens the message, the subscriber count is reduced by one. So, you have a thread treading around looking for messages having subscriber count = 0.

That is a bad idea.

You should institute an object deletion queue. Every time a subscriber opens a message, it checks the subscriber count. If zero, the message subscriber itself submits the message to the deletion queue. Now the GC thread needs to monitor only the deletion queue.

Why bother to have a counter at all. The message subscriber list is a linked list of tokens. Each subscriber is associated with one token in the list. The token tells the subscriber there is a message.

If the message queue functions across a network, then a token is generated per subscriber and the token is linked into the circular list. For each token in the list, a corresponding token is generated to be sent to the subscriber. When a subscriber request message retrieval it submits its authentication token to the message queue manager. The message queue manage auths the token and allows subscriber access to the message, and then unlinks the token from the list.

Regardless if it is a network message queue or local system queue, when the last token is unlinked (it's a circular list - you would know it is the last token), the message is submitted to the deletion queue.