fork(3) download
copy 
  1. #include <stdio.h>
  2. #include <time.h>
  3. #include <limits.h>
  4. #include <stdlib.h>
  5. #include <malloc.h>
  6. #include <memory.h>
  7. #include <math.h>
  8.  
  9. #define UCHAR unsigned char
  10. #define ULONG unsigned long
  11. #define USHRT unsigned short
  12. #define dbl   double
  13.  
  14. /* Queue structure */
  15. #define QUEUE_FULL_FLAG 1
  16. #define QUEUE_EMPTY_FLAG -1
  17. #define QUEUE_OK 0
  18. //  
  19. #define BITS_ELE_KNT    12  // 4.096 elements numbered 0-4095
  20.  
  21. typedef struct  {
  22.     UCHAR   *pBuffer;   //  pointer to storage, 16 to 4096 elements
  23.     ULONG Tail  :BITS_ELE_KNT;  //  # elements, with range of 0-4095
  24.     ULONG Head  :BITS_ELE_KNT;  //  # elements, with range of 0-4095
  25.     ULONG EleBytes  :8;     //  sizeof(elements) with range of 0-256 bytes
  26.     USHRT EleKnt    :BITS_ELE_KNT +1;// 1 extra bit for # elements (1-4096)
  27.     USHRT   IsFull  :1;     // queue is full
  28.     USHRT   IsEmpty :1;     // queue is empty
  29.     USHRT   Unused  :1;     // 16th bit of USHRT
  30. }   QUEUE_DESC;
  31.  
  32. //  ---------------------------------------------------------------------------
  33. //  Function prototypes
  34. QUEUE_DESC *Q_Init(QUEUE_DESC *Q, int BitsForEleKnt, int DataTypeSz);
  35. int Q_Put(QUEUE_DESC *Q, UCHAR *pNew);
  36. int Q_Get(UCHAR *pOld, QUEUE_DESC *Q);
  37.  
  38. //  ---------------------------------------------------------------------------
  39. QUEUE_DESC *Q_Init(QUEUE_DESC *Q, int BitsForEleKnt, int DataTypeSz)    {
  40.     memset((void *)Q, 0, sizeof(QUEUE_DESC));//init flags and bit integers to zero
  41.     Q->EleKnt   =   (USHRT)pow(2.0, BitsForEleKnt);
  42.     Q->EleBytes =   DataTypeSz;
  43.     Q->Head = Q->Tail = 0;
  44.  
  45. 	if(NULL == (Q->pBuffer = (UCHAR *)calloc(Q->EleKnt, Q->EleBytes)))  {
  46.         return NULL;
  47.     }   else    {
  48.         return Q;
  49.     }
  50. }
  51.  
  52. //  ---------------------------------------------------------------------------
  53. int Q_Put(QUEUE_DESC *Q, UCHAR *pNew)   
  54. {
  55.     memcpy(Q->pBuffer + (Q->Tail * Q->EleBytes), pNew, Q->EleBytes);
  56.  
  57. 	if(Q->Tail == (Q->Head + Q->EleKnt)) {
  58.         Q->Tail += 1;   
  59.         return QUEUE_FULL_FLAG; //  queue is full
  60.     }
  61.  
  62.     Q->Tail += 1;   
  63.     return QUEUE_OK; 
  64. }
  65.  
  66. //  ---------------------------------------------------------------------------
  67. int Q_Get(UCHAR *pOld, QUEUE_DESC *Q)   
  68. {
  69.     memcpy(pOld, Q->pBuffer + (Q->Head * Q->EleBytes), Q->EleBytes);
  70.     Q->Head += 1;   
  71.  
  72.     if(Q->Head == Q->Tail)      {
  73.         return QUEUE_EMPTY_FLAG; // queue Empty - nothing to get
  74.     }
  75.  
  76.     return QUEUE_OK; // No errors
  77. }
  78.  
  79. //
  80. //  ---------------------------------------------------------------------------
  81. int main(void)    {
  82.  
  83.     int i = 0;
  84. 	QUEUE_DESC Queue, *Q;
  85.  
  86.     if(NULL == (Q = Q_Init(&Queue, BITS_ELE_KNT, sizeof(int)))) {
  87.         printf("\nProgram failed to initialize. Aborting.\n\n");
  88.         return 0;
  89.     }
  90.  
  91. 	printf("Let's try to put 10.000 elements in a circular buffer of 4.096 elements.\n");
  92. 	printf("So, before start we have:\n");
  93. 	printf("  Q->Head = %i, Q->Tail = %i\n", Q->Head, Q->Tail);
  94. 	printf("  Q->EleKnt = %i\n", Q->EleKnt);
  95.  
  96.     for (i = 0; i < 10000; i++)    
  97. 	{
  98.         int dummy = i * i;
  99.  
  100. 		if(QUEUE_FULL_FLAG == Q_Put(Q, (UCHAR *)&dummy))    {
  101.  
  102. 			printf("Oh Crap. Queue became full at %i.\n", i);
  103.             break;
  104.         }
  105.     }
  106.  
  107. 	if (i >= 10000)
  108. 		printf("WTF. Queue is still not full? BUT I JUST ADDED 10.000 ELEMENTS!? \n");
  109.  
  110. 	printf("After the loop we have the following values:\n");
  111. 	printf("  Q->Head = %i, Q->Tail = %i\n", Q->Head, Q->Tail);
  112.  
  113. 	printf("Note that 10000 mod 4096 = %i, and you overflowed the buffer %i times.\n", 10000 % 4096, 10000 / 4096);
  114.  
  115.     return 0;
  116. }
Success #stdin #stdout 0s 2396KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Let's try to put 10.000 elements in a circular buffer of 4.096 elements.
So, before start we have:
  Q->Head = 0, Q->Tail = 0
  Q->EleKnt = 4096
WTF. Queue is still not full? BUT I JUST ADDED 10.000 ELEMENTS!? 
After the loop we have the following values:
  Q->Head = 0, Q->Tail = 1808
Note that 10000 mod 4096 = 1808, and you overflowed the buffer 2 times.
https://ideone.com/doPsaB
language:
C (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!