Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I have an assignment to implement a priority queue in C as well as make an app that uses it. I, however, only know basic-level C (I do know Java). My intuition says that I need to learn pointers.

What other stumbling blocks should I expect or prepare for? How do I go about making this secure?

share|improve this question
1  
What do you mean by "secure"? Bug free? –  Chris Pitman Feb 16 '12 at 5:37
    
You probably need to describe the host environment as well. Assuming that this is homework, it will be hosted on a desktop? –  tehnyit Feb 16 '12 at 8:20
    
@tehnyit - Yes, on Windows. –  Adel Feb 16 '12 at 14:41
    
A modified Heapsort (en.wikipedia.org/wiki/Heapsort) makes a great priority queue. –  David Thornley Feb 16 '12 at 15:27
3  
@Adel: Hacker attacks from where? What access would a cracker have to the app? If it's the ability to change the executable code or the memory that includes the queue, it's game over already. Is it if the cracker can submit arbitrary numbers of arbitrary events to the queue? –  David Thornley Feb 16 '12 at 20:30
show 1 more comment

3 Answers

up vote 8 down vote accepted

I want to say "not gonna happen". However, that wouldn't be very helpful, and perhaps not entirely accurate, either.

First of all, "security" is rather vague, but I think we can break it down:

  • Be memory-safe. Don't allocate buffers that are too small, don't dereference wild pointers, don't overrun buffers, etc.

  • Have good asymptotic complexity. Simply having an array of unsorted entries would require O(n) to pull out the item with the highest priority. Consider using a binary heap instead.

  • Don't leak memory. Every call to malloc should have a corresponding call to free.

Second of all, learn enough C to work with data structures. I'll try to provide a quick overview:

struct

Define compound data types using the struct keyword. Example:

struct Foo
{
    int n[10];
};

structs are like classes in C++ or Java, but you can't embed methods directly in them.

When you use the type, you have to say struct Foo (C++ lets you leave off the struct, but not C). To avoid this inconvenience, consider using typedef:

typedef struct Foo Foo;

Pointers

Consider a binary tree node:

struct Node
{
    int value;
    struct Node *left;
    struct Node *right;
};

Here, left and right point to other Node structures. If we were to take out the asterisks:

struct Node
{
    int value;
    struct Node left;
    struct Node right;
};

Then it would mean left and right exist right here, in this object. That would require an infinitely large object! The compiler will refuse this code.

A pointer can be thought of as:

  • A reference to another data structure

  • A number representing a location in memory. Think of memory as a giant array of bytes. The operating system decides where to put things. A pointer is an index in that array.

Allocation

So how do we ask the operating system to reserve space for an object? We call malloc:

struct Node *node = malloc(sizeof(struct Node));

malloc reserves the requested number of bytes of memory, and returns a pointer telling us where those bytes are. It doesn't initialize the memory to anything, so it currently contains garbage.

sizeof computes the size of a data type (at compile-time).

We can also allocate things directly on the stack:

struct Node node;

As in the case of malloc, node will contain garbage. Here, node is a value. We can turn it into a pointer by using C's reference operator &:

struct Node *node_ptr = &node;

The advantages of allocating on the stack are:

  • It's much faster than malloc

  • It's freed automatically

The disadvantage is that node_ptr is invalid outside of the current scope. Thus, we can't return pointers to stack-allocated structures.

Accessing structures

The structure access operator in C is .:

struct Node node;
node.value = 42;

To access a structure value behind a pointer, we can combine the * (dereference pointer) and . (structure member) operators:

(*node).value = 42; /* . has higher operator precedence */

Better yet, use the shorthand -> operator:

node->value = 42;

Simple example

Here's an example program that defines a binary tree node and basic operations on it.

/* Needed for printf and perror */
#include <stdio.h>

/* Needed for malloc, free, and exit */
#include <stdlib.h>

typedef struct Node Node;

struct Node
{
    int value;
    Node *left;
    Node *right;
};

Node *node_new(int value, Node *left, Node *right)
{
    Node *node = malloc(sizeof(Node));

    if (node == NULL) {
        perror("node_new");
        exit(EXIT_FAILURE);
    }

    node->value = value;
    node->left = left;
    node->right = right;
    return node;
}

void node_delete(Node *node)
{
    if (node != NULL) {
        node_delete(node->left);
        node_delete(node->right);
        free(node);
    }
}

void node_dump(Node *node)
{
    if (node != NULL) {
        node_dump(node->left);
        printf("%d\n", node->value);
        node_dump(node->right);
    }
}

int main(void)
{
    Node *node =
        node_new(4,
            node_new(2,
                node_new(1, NULL, NULL),
                node_new(3, NULL, NULL)
            ),
            node_new(6,
                node_new(5, NULL, NULL),
                node_new(7, NULL, NULL)
            )
        );

    node_dump(node);
    node_delete(node);
    return 0;
}

Hope this helps.

share|improve this answer
1  
Such a helpful review :D –  Farid Nouri Neshat Feb 16 '12 at 7:10
    
I ... I think you just fit most of a Learn C in 21 days book into a single answer! –  Useless Feb 16 '12 at 13:18
1  
And for future use, validate parameters to functions. Joey does this with (node != NULL) but it's nice to write out as a separate rule since "secure" is part of what you're looking for. –  Patrick Hughes Feb 16 '12 at 16:00
1  
@Adel: A simple binary search tree is inefficient for some inputs. For example, inserting items that are already sorted will construct a tree that branches to the right, and each operation will take linear time. You'll need a balancing strategy (e.g. AVL, red-black) to protect it against asymptotic complexity attacks. However, this is very tricky to implement correctly. Binary heaps are much easier to understand and implement, but they only support a subset of operations a binary search tree supports. –  Joey Adams Feb 16 '12 at 18:08
1  
@Adel: I don't think you can implement both AVL and red-black in two weeks (you only need to implement one, by the way). Don't forget that you have to make "an app that uses it" as well. Programming projects have a tendency to take about three times as long as you'd expect. –  Joey Adams Feb 16 '12 at 18:35
show 3 more comments

I think it would be best you learn this (pointers et. al.) faster by doing than by trying to learn first.

here are some pointers:

  1. A queue can be easily implemented in the form of linked list. So if you have a general idea of how linked lists (single or double) are created, by keeping a pointer for next (and previous) and update them appropriately, you are more or less done.

  2. About priority essentially you need to keep some score (as say int) on each node, so whenever you insert the node you need to traverse till the point priority is less than the priority of new entrant node. Swap the next (previous) pointers of node appropriately.

  3. About being secure, this is not very clear -but generally, to write secure code you must ensure that you do not carry finite buffers (pointers) without known lengths - and do not write data in any buffer which can potentially write down to unknown memory areas. This needs a great deal elaboration beyond the scope here.

Tips:

  1. Do not forget to malloc each node before insertino, and free after removal (or usage).

  2. Create a debug function - validate_all_nodes() and just traverse the entire list to see that all nodes are proper. Use this function every time you want to debug it.

share|improve this answer
    
Yes I know the "security" part is vague - basically it should be as secure as possible, against attacks(BO, memory leaks etc). –  Adel Feb 16 '12 at 17:04
add comment

If the set of priorities is small and virtual memory plentiful, it's a reasonable approach to use an array of queue structs, indexed by priority, where the consumer iterates the array from the high-priority end looking for a non-zero queue count. If the items queued are pointers, then a queue struct based on a 'classic' circular buffer with in/out indexes should be fine. If the priority queue is to be producer/consumer, then you need the usual pair of semaphores and a critical section, (or some other appropriate signaling/protection mechanism).

The advantages of this appoach is that it is not necessary to iterate a list, (or navigate a tree), of queued items on push/pop and also there is, in general, no malloc/free/realloc per push/pop, (ie. no contention on memory-manager either).

The memory-use issue can be mitigated by some extra code to malloc/realloc/free queue buffer space as necessary, but this obviously requires more code inside the queues lock, (especially if it is found that a queue needs to be realloced larger), impacting contention :(

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.