1 /*
2 * Author: Magnos Martinello, <magnos@land.ufrj.br> in April, 1999.
3 *
4 * @(#)$Header: /mm2/home/cvs/bc-src/tgif/wb_buff.c,v 1.5 2009/10/02 15:31:24 william Exp $
5 */
6
7 /*
8 * TODO: rever a rotina de insercao. Analisar o buffer como sendo circular.
9 *
10 */
11
12
13 #define _INCLUDE_FROM_WB_BUFF_C_
14
15 #include "tgifdefs.h"
16
17 #include "wb_buff.e"
18
19 #if (defined(PTHREAD) || defined(HAVE_LIBPTHREAD))
20 #include <pthread.h>
21 #endif /* (defined(PTHREAD) || defined(HAVE_LIBPTHREAD)) */
22
23 #include <stdio.h>
24 #include <stdlib.h>
25
26 /*
27 Structure of each component from the buffer
28 */
29
30 typedef struct item_s {
31 void *data;
32 int size;
33 struct item_s *prev;
34 struct item_s *next;
35 } item_t;
36
37 /*******************************************************************
38 Header:
39 - Maximum number of items in the buffer
40 - Size of each item
41 - Number of items in the buffer
42 - SORTED/UNSORTED insertion
43 - Pointer to first item of the queue
44 - Pointer to last item of the queue
45 (Item is inserted in the start pointer and removed from the end pointer)
46 - Function to compare two items of the buffer
47 *******************************************************************/
48 typedef struct {
49 int n;
50 int option;
51 #if (defined(PTHREAD) || defined(HAVE_LIBPTHREAD))
52 pthread_mutex_t *mp;
53 #endif /* (defined(PTHREAD) || defined(HAVE_LIBPTHREAD)) */
54 item_t *start;
55 item_t *end;
56 int (*compar)(const void *, const void *);
57 } header_t;
58
59
60 #define INITMAXTABLE 100
61
62 int MAXTABLE=INITMAXTABLE; /* Maximum number of active buffers */
63
64 header_t **table=NULL;
65 #if (defined(PTHREAD) || defined(HAVE_LIBPTHREAD))
66 pthread_mutex_t table_mp;
67 #endif /* (defined(PTHREAD) || defined(HAVE_LIBPTHREAD)) */
68
69 #ifndef TRUE
70 #define TRUE 1
71 #define FALSE 0
72 #endif
73
74 /***********************************************************************
75 * This function creates a new buffer and returns its descriptor as *
76 * an integer *
77 **********************************************************************/
buff_init(int trash1,int trash2,int option,int (* compar)(const void *,const void *))78 int buff_init (int trash1, int trash2, int option, int (*compar)(const void *,
79 const void *))
80 {
81 header_t *header;
82 int aux;
83 static int last_used_desc = INITMAXTABLE - 1;
84 static int is_first = TRUE;
85
86 /* If option is invalid then return error */
87 if (((option & SORTED)==SORTED) && ((option & UNSORTED)==UNSORTED))
88 return(-1);
89
90 /* If insertion is sorted and no comparison function has been assigned,
91 then return error */
92 if ((option == SORTED) && (compar == NULL))
93 return(-1);
94
95 if (is_first)
96 {
97 if ((table = (header_t**)malloc(MAXTABLE*sizeof(header_t*))) == NULL)
98 {
99 fprintf(stderr,"Allocation error. (buff_init)\n");
100 exit(1);
101 }
102 is_first = FALSE;
103 }
104
105 /* Looks for an empty position in the Descriptor Table */
106 #if (defined(PTHREAD) || defined(HAVE_LIBPTHREAD))
107 #ifdef PTHREAD_MUTEX
108 pthread_mutex_lock(&table_mp);
109 #endif /* PTHREAD_MUTEX */
110 #endif /* (defined(PTHREAD) || defined(HAVE_LIBPTHREAD)) */
111 aux = last_used_desc;
112 last_used_desc = (last_used_desc + 1) % MAXTABLE;
113 while ((table[last_used_desc] != NULL) && (aux != last_used_desc))
114 last_used_desc = (last_used_desc + 1) % MAXTABLE;
115 if (!(table[last_used_desc] == NULL)){
116 last_used_desc = MAXTABLE;
117 MAXTABLE += 10;
118 table=(header_t**)realloc(table,MAXTABLE*sizeof(header_t*));
119 }
120 #if (defined(PTHREAD) || defined(HAVE_LIBPTHREAD))
121 #ifdef PTHREAD_MUTEX
122 pthread_mutex_unlock(&table_mp);
123 #endif /* PTHREAD_MUTEX */
124 #endif /* (defined(PTHREAD) || defined(HAVE_LIBPTHREAD)) */
125
126 /* Create a new header and store its pointer in the descriptor table */
127 header = (header_t *) malloc (sizeof(header_t));
128 if (header == NULL)
129 return(-1);
130 memset(header, 0, sizeof(header_t));
131 table[last_used_desc] = header;
132
133 /* Set values for attributes in the header */
134 header->n = 0;
135 #if (defined(PTHREAD) || defined(HAVE_LIBPTHREAD))
136 #ifdef PTHREAD_MUTEX
137 header->mp = malloc(sizeof(pthread_mutex_t));
138 if (header->mp == NULL)
139 return(-1);
140 memset(header->mp, 0, sizeof(pthread_mutex_t));
141 pthread_mutex_init(header->mp, NULL);
142 #endif /* PTHREAD_MUTEX */
143 #endif /* (defined(PTHREAD) || defined(HAVE_LIBPTHREAD)) */
144 header->option = option;
145 header->compar = compar;
146 header->start = header->end = NULL;
147
148 return last_used_desc;
149 }
150
buff_cleanup()151 void buff_cleanup ()
152 {
153 if (table != NULL) free(table);
154 table = NULL;
155 }
156
157 /***********************************************************************
158 * This function inserts a new item in the buffer specified by its *
159 * descriptor. The insertion may be sorted or not, depending on the *
160 * option set during the buffer initialization. It returns a negative *
161 * integer if the insertion wasn't successful. *
162 **********************************************************************/
buff_ins(int bd,const void * buffer)163 int buff_ins (int bd, const void *buffer)
164 {
165 header_t *header;
166 item_t *item, *newitem, *auxitem;
167
168 if (table[bd] == NULL)
169 return(-1);
170
171 header = table[bd];
172
173 #if (defined(PTHREAD) || defined(HAVE_LIBPTHREAD))
174 #ifdef PTHREAD_MUTEX
175 pthread_mutex_lock(header->mp);
176 #endif /* PTHREAD_MUTEX */
177 #endif /* (defined(PTHREAD) || defined(HAVE_LIBPTHREAD)) */
178
179 /* Create the new item */
180 newitem = (item_t *) malloc (sizeof(item_t));
181 if (newitem == NULL)
182 return(-1);
183 memset(newitem, 0, sizeof(item_t));
184 newitem->size = strlen((char*)buffer)+1;
185 newitem->data = (int*)malloc (newitem->size);
186 if (newitem->data == NULL)
187 return(-1);
188 strcpy((char*)(newitem->data), (char*)buffer);
189
190 /* Unsorted insertion or empty buffer */
191 if (((header->option & UNSORTED) == UNSORTED) || (header->n == 0)){
192
193 newitem->prev = header->start;
194
195 if (newitem->prev != NULL)
196 newitem->prev->next = newitem;
197
198 header->start = newitem;
199
200 if (header->end == NULL)
201 header->end=newitem;
202
203 }
204 else /* Sorted buffer */
205 if ((header->option & SORTED) == SORTED){
206
207 /* Search position where new item will be inserted according to
208 comparison function previously specified */
209 /* Search is made from begining to end and from end to begining */
210 item = header->end;
211 auxitem = header->start;
212
213 while (((item != header->start) &&
214 (header->compar(item->data,buffer)<= 0)) &&
215 ((auxitem != header->end) &&
216 (header->compar(auxitem->data,buffer)>0))){
217 item = item->next;
218 auxitem = auxitem->prev;
219 }
220
221 /* Decide wich pointer points to the correct position */
222 if (header->compar(auxitem->data, buffer)<=0)
223 {
224 item = auxitem;
225 }
226 else
227 {
228 if (item->prev!=NULL)
229 item = item->prev;
230 }
231
232 /* front insertion */
233 if (item == header->start)
234 {
235 if (header->compar(header->start->data,buffer) < 0) {
236 header->n++;
237 newitem->next = NULL;
238 newitem->prev = header->start;
239 header->start->next = newitem;
240 header->start = newitem;
241 #if (defined(PTHREAD) || defined(HAVE_LIBPTHREAD))
242 #ifdef PTHREAD_MUTEX
243 pthread_mutex_unlock(header->mp);
244 #endif /* PTHREAD_MUTEX */
245 #endif /* (defined(PTHREAD) || defined(HAVE_LIBPTHREAD)) */
246 return(0);
247 }
248 }
249
250 /* rear insertion */
251 if (header->compar(buffer, header->end->data) < 0)
252 {
253 newitem->next = header->end;
254 newitem->prev = NULL;
255 header->end->prev = newitem;
256 header->end = newitem;
257 header->n++;
258 #if (defined(PTHREAD) || defined(HAVE_LIBPTHREAD))
259 #ifdef PTHREAD_MUTEX
260 pthread_mutex_unlock(header->mp);
261 #endif /* PTHREAD_MUTEX */
262 #endif /* (defined(PTHREAD) || defined(HAVE_LIBPTHREAD)) */
263 return(0);
264 }
265
266 /* is duplicated? */
267 if ((header->option & DUPLICATED) != DUPLICATED)
268 if (header->compar(item->data, buffer)==0){
269 #if (defined(PTHREAD) || defined(HAVE_LIBPTHREAD))
270 #ifdef PTHREAD_MUTEX
271 pthread_mutex_unlock(header->mp);
272 #endif /* PTHREAD_MUTEX */
273 #endif /* (defined(PTHREAD) || defined(HAVE_LIBPTHREAD)) */
274 return(-1);
275 }
276
277 /* Set pointers */
278 if (item->next!=NULL)
279 (item->next)->prev = newitem;
280
281 newitem->next = item->next;
282 newitem->prev = item;
283 item->next = newitem;
284 }
285
286 header->n++;
287 #if (defined(PTHREAD) || defined(HAVE_LIBPTHREAD))
288 #ifdef PTHREAD_MUTEX
289 pthread_mutex_unlock(header->mp);
290 #endif /* PTHREAD_MUTEX */
291 #endif /* (defined(PTHREAD) || defined(HAVE_LIBPTHREAD)) */
292
293 return(0);
294 }
295
296 /***********************************************************************
297 * This function removes an item from the buffer especified by its *
298 * descriptor. The data stored in the item is copied to a pointer *
299 * especified by the user. It returns a negative integer if an error *
300 * occurs *
301 **********************************************************************/
buff_rem(int bd,void ** buffer)302 int buff_rem (int bd, void **buffer)
303 {
304 header_t *header;
305
306 int buffsize =0;
307
308 if (table[bd] == NULL)
309 return(-1);
310
311 header = table[bd];
312
313 #if (defined(PTHREAD) || defined(HAVE_LIBPTHREAD))
314 #ifdef PTHREAD_MUTEX
315 pthread_mutex_lock(header->mp);
316 #endif /* PTHREAD_MUTEX */
317 #endif /* (defined(PTHREAD) || defined(HAVE_LIBPTHREAD)) */
318
319 if (header->n == 0){
320 #if (defined(PTHREAD) || defined(HAVE_LIBPTHREAD))
321 #ifdef PTHREAD_MUTEX
322 pthread_mutex_unlock(header->mp);
323 #endif /* PTHREAD_MUTEX */
324 #endif /* (defined(PTHREAD) || defined(HAVE_LIBPTHREAD)) */
325 return(-1);
326 }
327
328 if ((*buffer = malloc(header->end->size * sizeof(char)))==NULL)
329 {
330 fprintf(stderr,"Allocation error. (buff_rem)\n");
331 exit(1);
332 }
333
334 buffsize = header->end->size;
335
336 memcpy(*buffer, header->end->data, header->end->size);
337 header->end = header->end->next;
338 header->n--;
339
340 #if (defined(PTHREAD) || defined(HAVE_LIBPTHREAD))
341 #ifdef PTHREAD_MUTEX
342 pthread_mutex_unlock(header->mp);
343 #endif /* PTHREAD_MUTEX */
344 #endif /* (defined(PTHREAD) || defined(HAVE_LIBPTHREAD)) */
345
346 return(buffsize);
347 }
348
349 /***********************************************************************
350 * This function disposes memory occupied by the buffer. *
351 **********************************************************************/
buff_destroy(int bd)352 int buff_destroy (int bd)
353 {
354 item_t *item=NULL, *next_item=NULL;
355 int i;
356
357 if (table[bd] == NULL)
358 return(-1);
359
360 item = table[bd]->end;
361 for (i = 0; item!=NULL; i++, item=next_item) {
362 next_item = item->next;
363 free(item->data);
364 free(item);
365 }
366
367 #if (defined(PTHREAD) || defined(HAVE_LIBPTHREAD))
368 #ifdef PTHREAD_MUTEX
369 pthread_mutex_destroy(table[bd]->mp);
370 free(table[bd]->mp);
371 #endif /* PTHREAD_MUTEX */
372 #endif /* (defined(PTHREAD) || defined(HAVE_LIBPTHREAD)) */
373 free(table[bd]);
374 table[bd] = NULL;
375
376 return(0);
377 }
378
379 /***********************************************************************
380 * This function makes all items avaiable for insertion *
381 **********************************************************************/
buff_empty(int bd)382 int buff_empty (int bd)
383 {
384 header_t *header;
385 int aux;
386
387 if (table[bd] == NULL)
388 return(-1);
389
390 header = table[bd];
391 aux = header->n;
392
393 if ( aux == buff_emptyn(bd,aux) )
394 {
395 return(0);
396 }
397 else
398 return(-1);
399
400 }
401
402 /***********************************************************************
403 * This function makes the first n items avaiable for insertion. It *
404 * returns the number of items disposed. *
405 **********************************************************************/
buff_emptyn(int bd,int n)406 int buff_emptyn (int bd, int n)
407 {
408 header_t *header;
409 int nitems, i;
410
411 if (table[bd] == NULL)
412 return(-1);
413
414
415 header = table[bd];
416 #if (defined(PTHREAD) || defined(HAVE_LIBPTHREAD))
417 #ifdef PTHREAD_MUTEX
418 pthread_mutex_lock(header->mp);
419 #endif /* PTHREAD_MUTEX */
420 #endif /* (defined(PTHREAD) || defined(HAVE_LIBPTHREAD)) */
421 nitems = header->n;
422 i = 0;
423 while ( (header->n > 0) && (i < n)) {
424 i++;
425 header->n--;
426
427 free(header->end->data);
428 free(header->end);
429
430 header->end = header->end->next;
431
432 if (header->end == header->start)
433 {
434 header->start=NULL;
435 }
436 }
437
438 #if (defined(PTHREAD) || defined(HAVE_LIBPTHREAD))
439 #ifdef PTHREAD_MUTEX
440 pthread_mutex_unlock(header->mp);
441 #endif /* PTHREAD_MUTEX */
442 #endif /* (defined(PTHREAD) || defined(HAVE_LIBPTHREAD)) */
443
444 return((nitems<n?nitems:n));
445 }
446
447 /***********************************************************************
448 * This function returns the number of active items in the buffer *
449 **********************************************************************/
450
buff_items(int bd)451 int buff_items (int bd) {
452
453 if (table[bd] == NULL)
454 return -1;
455 else
456 return table[bd]->n;
457 }
458
459 /***********************************************************************
460 * This function concatenates two buffers, creating a new unsorted *
461 * insertion buffer *
462 **********************************************************************/
buff_conc(int bd1,int bd2)463 int buff_conc (int bd1, int bd2)
464 {
465 header_t *hd1, *hd2;
466 item_t *item;
467 int nbd, i, j;
468 char *buffer=NULL;
469
470 if ( (table[bd1] == NULL) || (table[bd2] == NULL))
471 return(-1);
472
473 hd1 = table[bd1];
474 hd2 = table[bd2];
475
476 nbd = buff_init (0, 0, UNSORTED, hd1->compar);
477
478 item = hd1->end;
479 i = 0;
480
481 for (j=0;j<2;j++)
482 {
483 i = 0;
484
485 if (j==0)
486 item = hd1->end;
487 else
488 item = hd2->end;
489
490 while ((i < (j==0?hd1->n:hd2->n)))
491 {
492
493 if (item == NULL)
494 {
495 fprintf(stderr,"Internal error. (buff_conc)\n");
496 exit(1);
497 }
498 buffer = (char*) malloc (item->size);
499 if (buffer == NULL)
500 return(-1);
501 memset(buffer, 0, item->size);
502
503 memcpy(buffer, item->data, item->size);
504 buff_ins(nbd, buffer);
505 item = item->next;
506
507 i++;
508 }
509 }
510
511 if (buffer) free (buffer);
512
513 return(nbd);
514 }
515
516 /***********************************************************************
517 * This function sorts a buffer according to a comparison function *
518 * pointed to by compar *
519 **********************************************************************/
520 /*
521 int buff_sort (int bd, int (*compar)(const void *, const void *))
522 {
523 header_t *header;
524 char *buffer;
525 int i, n;
526 item_t *item;
527
528 if (table[bd] == NULL)
529 return(-1);
530
531 header = table[bd];
532
533 #if (defined(PTHREAD) || defined(HAVE_LIBPTHREAD))
534 pthread_mutex_lock(header->mp);
535 #endif
536
537 if ((header->option & SORTED) == SORTED){
538 #if (defined(PTHREAD) || defined(HAVE_LIBPTHREAD))
539 pthread_mutex_unlock(header->mp);
540 #endif
541 return(0);
542 }
543
544 if (header->compar == NULL){
545 #if (defined(PTHREAD) || defined(HAVE_LIBPTHREAD))
546 pthread_mutex_unlock(header->mp);
547 #endif
548 return(-1);
549 }
550
551 n = header->n;
552 buffer = (char*) malloc (n * header->size);
553 if (buffer == NULL)
554 return(-1);
555 memset(buffer, 0, n*header->size);
556 i = 0;
557 item = header->end;
558 while (i < n){
559 memcpy(buffer + i * header->size, item->data, header->size);
560 item = item->next;
561 i++;
562 }
563
564 qsort (buffer, n, header->size, compar);
565
566 i = 0;
567 item = header->end;
568 while (i < n){
569 memcpy(item->data, buffer + i * header->size, header->size);
570 item = item->next;
571 i++;
572 }
573
574 free (buffer);
575
576 #if (defined(PTHREAD) || defined(HAVE_LIBPTHREAD))
577 pthread_mutex_unlock(header->mp);
578 #endif
579
580 return(0);
581 }
582 */
buff_show(int bd)583 int buff_show(int bd)
584 {
585 int i;
586 item_t *item = (table[bd])->end;
587 fprintf(stderr,"Buffer info (descriptor: %d):\n",bd);
588 fprintf(stderr,"\tn: %d\n\toption: %d\n\tstart: %p\n\tend: %p\n",
589 (table[bd])->n,
590 (table[bd])->option,
591 (table[bd])->start,
592 (table[bd])->end);
593 fprintf(stderr,"\tDados: \n");
594 for (i=0; i<(table[bd])->n; i++)
595 {
596 fprintf(stderr,"\t%s (this: %p prev: %p next: %p) -> \n",(char*)item->data,
597 item,item->prev,item->next);
598 item = item->next;
599 }
600 fprintf(stderr,"\tis the first\n");
601 return (0);
602 }
603
604