|
Server Help Community forums for Subgame, ASSS, and bots
|
Author |
Message |
Doc Flabby Server Help Squatter
Joined: Feb 26 2006 Posts: 636 Offline
|
Posted: Sun Aug 17, 2008 7:38 am Post subject: A Cicular Queue Utility Written in C |
|
|
|
|
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
#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
#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
/*
* 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 |
|
|
Samapico No, these DO NOT look like penises, ok?
Joined: May 08 2003 Posts: 1252 Offline
|
Posted: Sun Aug 17, 2008 11:40 am Post subject: |
|
|
|
|
Would be nice with a template so it could work with any types _________________ (Insert a bunch of dead links here) |
|
Back to top |
|
|
Doc Flabby Server Help Squatter
Joined: Feb 26 2006 Posts: 636 Offline
|
Posted: Sun Aug 17, 2008 12:14 pm Post subject: |
|
|
|
|
Samapico wrote: | Would be nice with a template so it could work with any types |
No templates in C thats a C++ feature |
|
Back to top |
|
|
Samapico No, these DO NOT look like penises, ok?
Joined: May 08 2003 Posts: 1252 Offline
|
Posted: Sun Aug 17, 2008 12:42 pm Post subject: |
|
|
|
|
oh, that's C, right, nvm
could it use void * instead? you'd have to specify the size each time, though |
|
Back to top |
|
|
tcsoccerman Server Help Squatter
Age:31 Gender: Joined: Jan 15 2007 Posts: 694 Location: Atlantis Offline
|
Posted: Sun Aug 17, 2008 2:55 pm Post subject: |
|
|
|
|
What exactly is a queue :/ |
|
Back to top |
|
|
D1st0rt Miss Directed Wannabe
Age:36 Gender: Joined: Aug 31 2003 Posts: 2247 Location: Blacksburg, VA Offline
|
Posted: Sun Aug 17, 2008 3:28 pm Post subject: |
|
|
|
|
sys/queue.h has circular queues built-in:
man 3 queue _________________
|
|
Back to top |
|
|
Doc Flabby Server Help Squatter
Joined: Feb 26 2006 Posts: 636 Offline
|
Posted: Sun Aug 17, 2008 4:38 pm Post subject: |
|
|
|
|
Ya theres loads of queue implementations out there lol
wiki on what a queue is |
|
Back to top |
|
|
Bak ?ls -s 0 in
Age:25 Gender: Joined: Jun 11 2004 Posts: 1826 Location: USA Offline
|
|
Back to top |
|
|
Doc Flabby Server Help Squatter
Joined: Feb 26 2006 Posts: 636 Offline
|
Posted: Mon Aug 18, 2008 9:32 am Post subject: |
|
|
|
|
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 |
|
|
Snrrrub Novice
Joined: May 29 2008 Posts: 37 Offline
|
Posted: Mon Aug 18, 2008 3:41 pm Post subject: |
|
|
|
|
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 |
|
|
|
|
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
|
Software by php BB © php BB Group Server Load: 953 page(s) served in previous 5 minutes.
|