Server Help Forum Index Server Help
Community forums for Subgame, ASSS, and bots
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   StatisticsStatistics   RegisterRegister 
 ProfileProfile   Login to check your private messagesLogin to check your private messages   LoginLogin (SSL) 

Server Help | ASSS Wiki (0) | Shanky.com
A Cicular Queue Utility Written in C

 
Post new topic   Reply to topic Printable version
 View previous topic  What is DWORD? Post :: Post help with strncpy  View next topic  
Author Message
Doc Flabby
Server Help Squatter


Joined: Feb 26 2006
Posts: 636
Offline

PostPosted: Sun Aug 17, 2008 7:38 am    Post subject: A Cicular Queue Utility Written in C Reply to topic Reply with quote

I've had a go at writing a queue class from scratch in pure C. Let me know what you think and if i've made ny glaring mistakes that will make it go wrong (buffer overflows etc). You will need to use -std=c99 to compile as it uses the lastest standards in C.

Usage Example
Code: Show/Hide

#include "queue.h"

int main() {
    Queue * q = queue_create(8);  //queue of length 8
    queue_push(q,"test");
    queue_push(q,"test2");
    queue_push(q,"test3");
    queue_push(q,"test4");
    queue_push(q,"test5");
    queue_push(q,"test6");
    queue_push(q,"test7");
    queue_push(q,"test8");
    queue_push(q,"test9");
    queue_push(q,"test10");

    char test[200];

    queue_pop(q,test);
    for(int t;t<20;t++){
        if(queue_pop(q,test)==0)
        {
         printf("popped: %s\n",test);
        }
    }
    queue_free(q); //free memory
}


queue.h
Code: Show/Hide

#ifndef QUEUE_H_INCLUDED
#define QUEUE_H_INCLUDED

typedef struct Queue Queue;

extern Queue * queue_create(int /*queue size*/);
extern int queue_push(Queue *, char * /*item to add to queue*/);
extern int queue_pop(Queue *, char * /*holds retrieved item*/);
extern int queue_size(Queue *);
extern int queue_free(Queue *);
#endif // QUEUE_H_INCLUDED

queue.c
Code: Show/Hide

    /*
    * Simple Queue
    *
    * Copyright (c) 2008, Doc Flabby
    * All rights reserved.
    *
    * Redistribution and use in source and binary forms, with or without
    * modification, are permitted provided that the following conditions are met:
    *     * Redistributions of source code must retain the above copyright
    *       notice, this list of conditions and the following disclaimer.
    *     * Redistributions in binary form must reproduce the above copyright
    *       notice, this list of conditions and the following disclaimer in the
    *       documentation and/or other materials provided with the distribution.
    *     * Neither the name of the <organization> nor the
    *       names of its contributors may be used to endorse or promote products
    *       derived from this software without specific prior written permission.
    *
    * THIS SOFTWARE IS PROVIDED BY <copyright holder> ''AS IS'' AND ANY
    * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
    * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
    * DISCLAIMED. IN NO EVENT SHALL <copyright holder> BE LIABLE FOR ANY
    * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
    * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
    * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
    * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
    * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
    * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    *
    * NOTES
    *
    * NOT THREAD SAFE
    */

//standard libs
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include "queue.h"

struct Queue
{
    char ** Content;
    unsigned int WriteCount;
    unsigned int ReadCount;
    int MaxElements;
};


extern Queue * queue_create(int NumberOfElements)
{
    Queue *queue = malloc(sizeof(Queue));
    if(queue == NULL) { printf("malloc failed\n"); return NULL; }
    queue->Content = malloc(NumberOfElements * sizeof(char*));
    memset(queue->Content,(int)NULL,NumberOfElements * sizeof(char*)); // zero array
    if(queue->Content == NULL) { printf("malloc failed\n"); return NULL; }
    queue->WriteCount = 0;
    queue->ReadCount = 0;
    queue->MaxElements = NumberOfElements;
    return queue;
}

extern int queue_push(Queue *queue, char * item)
{
   if(queue == NULL) { printf("Invalid Queue Struct\n"); return -1; }
   // In the second level
   if(queue_size(queue) >= queue->MaxElements) { printf("Queue is full, discarded new value\n"); return 1; }
   //theresb space in the queue.

   int position = queue->WriteCount % queue->MaxElements;
   printf("Added %s Current Position:%i\r\n",item,position);

   queue->Content[position] = malloc(strlen(item) + 1);
   if(queue->Content[position] == NULL) { printf("malloc failed\n"); return -1; }

   strcpy(queue->Content[position],item);
   queue->WriteCount++;


   return 0;
}

extern int queue_pop(Queue *queue, char * item)
{
    if(queue == NULL) { printf("Invalid Queue Struct"); return -1; }
    if(queue_size(queue) == 0) { printf("Queue is empty\n"); return 1; }

    int position = queue->ReadCount % queue->MaxElements;
    strcpy(item,queue->Content[position]);

    printf("Removed %s Current Position:%i\r\n",item,position);

    free(queue->Content[position]); // free memory
    queue->Content[position] = NULL; // assign null pointer to indicate no entry here
    queue->ReadCount++;  //increment read count
    return 0;
}

extern int queue_size(Queue *queue)
{
    if(queue == NULL) { printf("Invalid Queue Struct"); return -1; }
    //Number of items added to queue-number takne out = number left :>
    return queue->WriteCount - queue->ReadCount;
}

extern int queue_free(Queue *queue)
{
    if(queue == NULL) { printf("Invalid Queue Struct"); return -1; }

    for(int i = 0;i<queue->MaxElements;i++)
    {
        if(queue->Content[i]!=NULL) {
            free(queue->Content[i]);
        }
    }
    free(queue->Content);
    free(queue);
    return 0;
}


_________________
Rediscover online gaming. Get Subspace | STF The future...prehaps
Back to top
View users profile Send private message Add User to Ignore List
Samapico
No, these DO NOT look like penises, ok?


Age:31
Gender:Gender:Male
Joined: May 08 2003
Posts: 1252
Location: Montreal, Canada
Offline

PostPosted: Sun Aug 17, 2008 11:40 am    Post subject: Reply to topic Reply with quote

Would be nice with a template so it could work with any types
_________________
DCME co-developer
17th Parallel Head Sysop
Subspace: The Future
Back to top
View users profile Send private message Add User to Ignore List
Doc Flabby
Server Help Squatter


Joined: Feb 26 2006
Posts: 636
Offline

PostPosted: Sun Aug 17, 2008 12:14 pm    Post subject: Reply to topic Reply with quote

Samapico wrote:
Would be nice with a template so it could work with any types

No templates in C tongue.gif thats a C++ feature
Back to top
View users profile Send private message Add User to Ignore List
Samapico
No, these DO NOT look like penises, ok?


Age:31
Gender:Gender:Male
Joined: May 08 2003
Posts: 1252
Location: Montreal, Canada
Offline

PostPosted: Sun Aug 17, 2008 12:42 pm    Post subject: Reply to topic Reply with quote

oh, that's C, right, nvm

could it use void * instead? you'd have to specify the size each time, though
Back to top
View users profile Send private message Add User to Ignore List
tcsoccerman
Server Help Squatter


Age:25
Gender:Gender:Male
Joined: Jan 15 2007
Posts: 694
Location: Atlantis
Offline

PostPosted: Sun Aug 17, 2008 2:55 pm    Post subject: Reply to topic Reply with quote

What exactly is a queue :/
Back to top
View users profile Send private message Add User to Ignore List Send email AIM Address
D1st0rt
Miss Directed Wannabe


Age:30
Gender:Gender:Male
Joined: Aug 31 2003
Posts: 2247
Location: Blacksburg, VA
Offline

PostPosted: Sun Aug 17, 2008 3:28 pm    Post subject: Reply to topic Reply with quote

sys/queue.h has circular queues built-in:
man 3 queue
_________________

Back to top
View users profile Send private message Add User to Ignore List Visit posters website
Doc Flabby
Server Help Squatter


Joined: Feb 26 2006
Posts: 636
Offline

PostPosted: Sun Aug 17, 2008 4:38 pm    Post subject: Reply to topic Reply with quote

Ya theres loads of queue implementations out there lol tongue.gif

wiki on what a queue is
Back to top
View users profile Send private message Add User to Ignore List
Bak
?ls -s
0 in


Age:18
Gender:Gender:Male
Joined: Jun 11 2004
Posts: 1826
Location: USA
Offline

PostPosted: Sun Aug 17, 2008 9:14 pm    Post subject: Reply to topic Reply with quote

good job, now make it so you don't have to specify the size icon_smile.gif
_________________
SubSpace Discretion: A Third Generation SubSpace Client
Back to top
View users profile Send private message Add User to Ignore List AIM Address
Doc Flabby
Server Help Squatter


Joined: Feb 26 2006
Posts: 636
Offline

PostPosted: Mon Aug 18, 2008 9:32 am    Post subject: Reply to topic Reply with quote

I might give that ago once i've fixed the current problems.

- i've found one bug already i need to fix, if you store more than INT32_MAX is the write count wraps around which screws things up....

- Another problem (more design flaw than bug) is there is a high potential for buffer overflow when retrieving an item from the list, if you supply a character array that is shorter than the item being retrieved, which is quite possible as there is no way of knowing the length of the item being retrieved, you can easily over flow it fol.
Back to top
View users profile Send private message Add User to Ignore List
Snrrrub
Novice


Joined: May 29 2008
Posts: 37
Offline

PostPosted: Mon Aug 18, 2008 3:41 pm    Post subject: Reply to topic Reply with quote

I've found a few other issues that you might want to consider:

1) MaxElements should be an unsigned type
2) What if you pass in a negative value for NumberOfElements (queue_create)
3) What happens when 'item' is null in queue_push? Will you get NULL back when you pop?
4) const-correctness - queue_size does not modify the queue
5) integer return values are really bad - they should really be enums
6) what if you compile+run on a 64-bit architecture? (you're still limited to 2^32 items)

-Snrrrub
Back to top
View users profile Send private message Add User to Ignore List
Display posts from previous:   
Post new topic   Reply to topic    Server Help Forum Index -> Non-Subspace Related Coding All times are GMT - 5 Hours
Page 1 of 1

 
Jump to:  
You can post new topics in this forum
You can 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
You can attach files in this forum
You can download files in this forum
View online users | View Statistics | View Ignored List


Software by php BB © php BB Group
Server Load: 60 page(s) served in previous 5 minutes.

phpBB Created this page in 0.095473 seconds : 35 queries executed (56.6%): GZIP compression disabled