xref: /PHP-7.4/ext/xmlrpc/libxmlrpc/queue.c (revision 29eb3561)
1 /*
2  * Date last modified: Jan 2001
3  * Modifications by Dan Libby (dan@libby.com), including:
4  *  - various fixes, null checks, etc
5  *  - addition of Q_Iter funcs, macros
6  */
7 
8 
9 /*-**************************************************************
10  *
11  *  File : q.c
12  *
13  *  Author: Peter Yard [1993.01.02] -- 02 Jan 1993
14  *
15  *  Disclaimer: This code is released to the public domain.
16  *
17  *  Description:
18  *      Generic double ended queue (Deque pronounced DEK) for handling
19  *      any data types, with sorting.
20  *
21  *      By use of various functions in this module the caller
22  *      can create stacks, queues, lists, doubly linked lists,
23  *      sorted lists, indexed lists.  All lists are dynamic.
24  *
25  *      It is the responsibility of the caller to malloc and free
26  *      memory for insertion into the queue. A pointer to the object
27  *      is used so that not only can any data be used but various kinds
28  *      of data can be pushed on the same queue if one so wished e.g.
29  *      various length string literals mixed with pointers to structures
30  *      or integers etc.
31  *
32  *  Enhancements:
33  *      A future improvement would be the option of multiple "cursors"
34  *      so that multiple locations could occur in the one queue to allow
35  *      placemarkers and additional flexibility.  Perhaps even use queue
36  *      itself to have a list of cursors.
37  *
38  * Usage:
39  *
40  *          /x init queue x/
41  *          queue  q;
42  *          Q_Init(&q);
43  *
44  *      To create a stack :
45  *
46  *          Q_PushHead(&q, &mydata1); /x push x/
47  *          Q_PushHead(&q, &mydata2);
48  *          .....
49  *          data_ptr = Q_PopHead(&q); /x pop x/
50  *          .....
51  *          data_ptr = Q_Head(&q);   /x top of stack x/
52  *
53  *      To create a FIFO:
54  *
55  *          Q_PushHead(&q, &mydata1);
56  *          .....
57  *          data_ptr = Q_PopTail(&q);
58  *
59  *      To create a double list:
60  *
61  *          data_ptr = Q_Head(&q);
62  *          ....
63  *          data_ptr = Q_Next(&q);
64  *          data_ptr = Q_Tail(&q);
65  *          if (Q_IsEmpty(&q)) ....
66  *          .....
67  *          data_ptr = Q_Previous(&q);
68  *
69  *      To create a sorted list:
70  *
71  *          Q_PushHead(&q, &mydata1); /x push x/
72  *          Q_PushHead(&q, &mydata2);
73  *          .....
74  *          if (!Q_Sort(&q, MyFunction))
75  *              .. error ..
76  *
77  *          /x fill in key field of mydata1.
78  *           * NB: Q_Find does linear search
79  *           x/
80  *
81  *          if (Q_Find(&q, &mydata1, MyFunction))
82  *          {
83  *              /x found it, queue cursor now at correct record x/
84  *              /x can retrieve with x/
85  *              data_ptr = Q_Get(&q);
86  *
87  *              /x alter data , write back with x/
88  *              Q_Put(&q, data_ptr);
89  *          }
90  *
91  *          /x Search with binary search x/
92  *          if (Q_Seek(&q, &mydata, MyFunction))
93  *              /x etc x/
94  *
95  *
96  ****************************************************************/
97 
98 #include <stdlib.h>
99 #include <php.h>
100 #include "queue.h"
101 
102 static void QuickSort(void *list[], int low, int high,
103                       int (*Comp)(const void *, const void *));
104 static int  Q_BSearch(queue *q, void *key,
105                       int (*Comp)(const void *, const void *));
106 
107 /* The index: a pointer to pointers */
108 
109 static  void        **queue_index;
110 static  datanode    **queue_posn_index;
111 
112 
113 /***
114  *
115  ** function    : Q_Init
116  *
117  ** purpose     : Initialise queue object and pointers.
118  *
119  ** parameters  : 'queue' pointer.
120  *
121  ** returns     : True_ if init successful else False_
122  *
123  ** comments    :
124  ***/
125 
Q_Init(queue * q)126 int Q_Init(queue  *q)
127 {
128    if(q) {
129       q->head = q->tail = NULL;
130       q->cursor = q->head;
131       q->size = 0;
132       q->sorted = False_;
133    }
134 
135    return True_;
136 }
137 
138 /***
139  *
140  ** function    : Q_AtHead
141  *
142  ** purpose     : tests if cursor is at head of queue
143  *
144  ** parameters  : 'queue' pointer.
145  *
146  ** returns     : boolean - True_ is at head else False_
147  *
148  ** comments    :
149  *
150  ***/
151 
Q_AtHead(queue * q)152 int Q_AtHead(queue *q)
153 {
154    return(q && q->cursor == q->head);
155 }
156 
157 
158 /***
159  *
160  ** function    : Q_AtTail
161  *
162  ** purpose     : boolean test if cursor at tail of queue
163  *
164  ** parameters  : 'queue' pointer to test.
165  *
166  ** returns     : True_ or False_
167  *
168  ** comments    :
169  *
170  ***/
171 
Q_AtTail(queue * q)172 int Q_AtTail(queue *q)
173 {
174    return(q && q->cursor == q->tail);
175 }
176 
177 
178 /***
179  *
180  ** function    : Q_IsEmpty
181  *
182  ** purpose     : test if queue has nothing in it.
183  *
184  ** parameters  : 'queue' pointer
185  *
186  ** returns     : True_ if IsEmpty queue, else False_
187  *
188  ** comments    :
189  *
190  ***/
191 
Q_IsEmpty(queue * q)192 inline int Q_IsEmpty(queue *q)
193 {
194    return(!q || q->size == 0);
195 }
196 
197 /***
198  *
199  ** function    : Q_Size
200  *
201  ** purpose     : return the number of elements in the queue
202  *
203  ** parameters  : queue pointer
204  *
205  ** returns     : number of elements
206  *
207  ** comments    :
208  *
209  ***/
210 
Q_Size(queue * q)211 int Q_Size(queue *q)
212 {
213    return q ? q->size : 0;
214 }
215 
216 
217 /***
218  *
219  ** function    : Q_Head
220  *
221  ** purpose     : position queue cursor to first element (head) of queue.
222  *
223  ** parameters  : 'queue' pointer
224  *
225  ** returns     : pointer to data at head. If queue is IsEmpty returns NULL
226  *
227  ** comments    :
228  *
229  ***/
230 
Q_Head(queue * q)231 void *Q_Head(queue *q)
232 {
233    if(Q_IsEmpty(q))
234       return NULL;
235 
236    q->cursor = q->head;
237 
238    return  q->cursor->data;
239 }
240 
241 
242 /***
243  *
244  ** function    : Q_Tail
245  *
246  ** purpose     : locate cursor at tail of queue.
247  *
248  ** parameters  : 'queue' pointer
249  *
250  ** returns     : pointer to data at tail , if queue IsEmpty returns NULL
251  *
252  ** comments    :
253  *
254  ***/
255 
Q_Tail(queue * q)256 void *Q_Tail(queue *q)
257 {
258    if(Q_IsEmpty(q))
259       return NULL;
260 
261    q->cursor = q->tail;
262 
263    return  q->cursor->data;
264 }
265 
266 
267 /***
268  *
269  ** function    : Q_PushHead
270  *
271  ** purpose     : put a data pointer at the head of the queue
272  *
273  ** parameters  : 'queue' pointer, void pointer to the data.
274  *
275  ** returns     : True_ if success else False_ if unable to push data.
276  *
277  ** comments    :
278  *
279  ***/
280 
Q_PushHead(queue * q,void * d)281 int Q_PushHead(queue *q, void *d)
282 {
283    if(q && d) {
284       node    *n;
285       datanode *p;
286 
287       p = emalloc(sizeof(datanode));
288       if(p == NULL)
289          return False_;
290 
291       n = q->head;
292 
293       q->head = (node*)p;
294       q->head->prev = NULL;
295 
296       if(q->size == 0) {
297          q->head->next = NULL;
298          q->tail = q->head;
299       }
300       else {
301          q->head->next = (datanode*)n;
302          n->prev = q->head;
303       }
304 
305       q->head->data = d;
306       q->size++;
307 
308       q->cursor = q->head;
309 
310       q->sorted = False_;
311 
312       return True_;
313    }
314    return False_;
315 }
316 
317 
318 
319 /***
320  *
321  ** function    : Q_PushTail
322  *
323  ** purpose     : put a data element pointer at the tail of the queue
324  *
325  ** parameters  : queue pointer, pointer to the data
326  *
327  ** returns     : True_ if data pushed, False_ if data not inserted.
328  *
329  ** comments    :
330  *
331  ***/
332 
Q_PushTail(queue * q,void * d)333 int Q_PushTail(queue *q, void *d)
334 {
335    if(q && d) {
336       node        *p;
337       datanode    *n;
338 
339       n = emalloc(sizeof(datanode));
340       if(n == NULL)
341          return False_;
342 
343       p = q->tail;
344       q->tail = (node *)n;
345 
346       if(q->size == 0) {
347          q->tail->prev = NULL;
348          q->head = q->tail;
349       }
350       else {
351          q->tail->prev = (datanode *)p;
352          p->next = q->tail;
353       }
354 
355       q->tail->next = NULL;
356 
357       q->tail->data =  d;
358       q->cursor = q->tail;
359       q->size++;
360 
361       q->sorted = False_;
362 
363       return True_;
364    }
365    return False_;
366 }
367 
368 
369 
370 /***
371  *
372  ** function    : Q_PopHead
373  *
374  ** purpose     : remove and return the top element at the head of the
375  *                queue.
376  *
377  ** parameters  : queue pointer
378  *
379  ** returns     : pointer to data element or NULL if queue is IsEmpty.
380  *
381  ** comments    :
382  *
383  ***/
384 
Q_PopHead(queue * q)385 void *Q_PopHead(queue *q)
386 {
387    datanode    *n;
388    void        *d;
389 
390    if(Q_IsEmpty(q))
391       return NULL;
392 
393    d = q->head->data;
394    n = q->head->next;
395    efree(q->head);
396 
397    q->size--;
398 
399    if(q->size == 0)
400       q->head = q->tail = q->cursor = NULL;
401    else {
402       q->head = (node *)n;
403       q->head->prev = NULL;
404       q->cursor = q->head;
405    }
406 
407    q->sorted = False_;
408 
409    return d;
410 }
411 
412 
413 /***
414  *
415  ** function    : Q_PopTail
416  *
417  ** purpose     : remove element from tail of queue and return data.
418  *
419  ** parameters  : queue pointer
420  *
421  ** returns     : pointer to data element that was at tail. NULL if queue
422  *                IsEmpty.
423  *
424  ** comments    :
425  *
426  ***/
427 
Q_PopTail(queue * q)428 void *Q_PopTail(queue *q)
429 {
430    datanode    *p;
431    void        *d;
432 
433    if(Q_IsEmpty(q))
434       return NULL;
435 
436    d = q->tail->data;
437    p = q->tail->prev;
438    efree(q->tail);
439    q->size--;
440 
441    if(q->size == 0)
442       q->head = q->tail = q->cursor = NULL;
443    else {
444       q->tail = (node *)p;
445       q->tail->next = NULL;
446       q->cursor = q->tail;
447    }
448 
449    q->sorted = False_;
450 
451    return d;
452 }
453 
454 
455 
456 /***
457  *
458  ** function    : Q_Next
459  *
460  ** purpose     : Move to the next element in the queue without popping
461  *
462  ** parameters  : queue pointer.
463  *
464  ** returns     : pointer to data element of new element or NULL if end
465  *                of the queue.
466  *
467  ** comments    : This uses the cursor for the current position. Q_Next
468  *                only moves in the direction from the head of the queue
469  *                to the tail.
470  ***/
471 
Q_Next(queue * q)472 void *Q_Next(queue *q)
473 {
474    if(!q)
475       return NULL;
476 
477    if(!q->cursor || q->cursor->next == NULL)
478       return NULL;
479 
480    q->cursor = (node *)q->cursor->next;
481 
482    return  q->cursor->data ;
483 }
484 
485 
486 
487 /***
488  *
489  ** function    : Q_Previous
490  *
491  ** purpose     : Opposite of Q_Next. Move to next element closer to the
492  *                head of the queue.
493  *
494  ** parameters  : pointer to queue
495  *
496  ** returns     : pointer to data of new element else NULL if queue IsEmpty
497  *
498  ** comments    : Makes cursor move towards the head of the queue.
499  *
500  ***/
501 
Q_Previous(queue * q)502 void *Q_Previous(queue *q)
503 {
504    if(!q)
505       return NULL;
506 
507    if(q->cursor->prev == NULL)
508       return NULL;
509 
510    q->cursor = (node *)q->cursor->prev;
511 
512    return q->cursor->data;
513 }
514 
515 
Q_Iter_Del(queue * q,q_iter iter)516 void *Q_Iter_Del(queue *q, q_iter iter)
517 {
518    void        *d;
519    datanode    *n, *p;
520 
521    if(!q)
522       return NULL;
523 
524    if(iter == NULL)
525       return NULL;
526 
527    if(iter == (q_iter)q->head)
528       return Q_PopHead(q);
529 
530    if(iter == (q_iter)q->tail)
531       return Q_PopTail(q);
532 
533    n = ((node*)iter)->next;
534    p = ((node*)iter)->prev;
535    d = ((node*)iter)->data;
536 
537    efree(iter);
538 
539    if(p) {
540       p->next = n;
541    }
542    if (q->cursor == (node*)iter) {
543       if (p) {
544          q->cursor = p;
545       } else {
546          q->cursor = n;
547       }
548    }
549 
550 
551    if (n != NULL) {
552 	n->prev = p;
553    }
554 
555    q->size--;
556 
557    q->sorted = False_;
558 
559    return d;
560 }
561 
562 
563 
564 /***
565  *
566  ** function    : Q_DelCur
567  *
568  ** purpose     : Delete the current queue element as pointed to by
569  *                the cursor.
570  *
571  ** parameters  : queue pointer
572  *
573  ** returns     : pointer to data element.
574  *
575  ** comments    : WARNING! It is the responsibility of the caller to
576  *                free any memory. Queue cannot distinguish between
577  *                pointers to literals and malloced memory.
578  *
579  ***/
580 
Q_DelCur(queue * q)581 void *Q_DelCur(queue* q) {
582    if(q) {
583       return Q_Iter_Del(q, (q_iter)q->cursor);
584    }
585    return 0;
586 }
587 
588 
589 /***
590  *
591  ** function    : Q_Destroy
592  *
593  ** purpose     : Free all queue resources
594  *
595  ** parameters  : queue pointer
596  *
597  ** returns     : null.
598  *
599  ** comments    : WARNING! It is the responsibility of the caller to
600  *                free any memory. Queue cannot distinguish between
601  *                pointers to literals and malloced memory.
602  *
603  ***/
604 
Q_Destroy(queue * q)605 void Q_Destroy(queue *q)
606 {
607    while(!Q_IsEmpty(q)) {
608       Q_PopHead(q);
609    }
610 }
611 
612 
613 /***
614  *
615  ** function    : Q_Get
616  *
617  ** purpose     : get the pointer to the data at the cursor location
618  *
619  ** parameters  : queue pointer
620  *
621  ** returns     : data element pointer
622  *
623  ** comments    :
624  *
625  ***/
626 
Q_Get(queue * q)627 void *Q_Get(queue *q)
628 {
629    if(!q)
630       return NULL;
631 
632    if(q->cursor == NULL)
633       return NULL;
634    return q->cursor->data;
635 }
636 
637 
638 
639 /***
640  *
641  ** function    : Q_Put
642  *
643  ** purpose     : replace pointer to data with new pointer to data.
644  *
645  ** parameters  : queue pointer, data pointer
646  *
647  ** returns     : boolean- True_ if successful, False_ if cursor at NULL
648  *
649  ** comments    :
650  *
651  ***/
652 
Q_Put(queue * q,void * data)653 int Q_Put(queue *q, void *data)
654 {
655    if(q && data) {
656       if(q->cursor == NULL)
657          return False_;
658 
659       q->cursor->data = data;
660       return True_;
661    }
662    return False_;
663 }
664 
665 
666 /***
667  *
668  ** function    : Q_Find
669  *
670  ** purpose     : Linear search of queue for match with key in *data
671  *
672  ** parameters  : queue pointer q, data pointer with data containing key
673  *                comparison function here called Comp.
674  *
675  ** returns     : True_ if found , False_ if not in queue.
676  *
677  ** comments    : Useful for small queues that are constantly changing
678  *                and would otherwise need constant sorting with the
679  *                Q_Seek function.
680  *                For description of Comp see Q_Sort.
681  *                Queue cursor left on position found item else at end.
682  *
683  ***/
684 
Q_Find(queue * q,void * data,int (* Comp)(const void *,const void *))685 int Q_Find(queue *q, void *data,
686            int (*Comp)(const void *, const void *))
687 {
688    void *d;
689 
690    if (q == NULL) {
691 	return False_;
692    }
693 
694    d = Q_Head(q);
695    do {
696       if(Comp(d, data) == 0)
697          return True_;
698       d = Q_Next(q);
699    } while(!Q_AtTail(q));
700 
701    if(Comp(d, data) == 0)
702       return True_;
703 
704    return False_;
705 }
706 
707 /*========  Sorted Queue and Index functions   ========= */
708 
709 
QuickSort(void * list[],int low,int high,int (* Comp)(const void *,const void *))710 static void QuickSort(void *list[], int low, int high,
711                       int (*Comp)(const void *, const void *))
712 {
713    int     flag = 1, i, j;
714    void    *key, *temp;
715 
716    if(low < high) {
717       i = low;
718       j = high + 1;
719 
720       key = list[ low ];
721 
722       while(flag) {
723          i++;
724          while(Comp(list[i], key) < 0)
725             i++;
726 
727          j--;
728          while(Comp(list[j], key) > 0)
729             j--;
730 
731          if(i < j) {
732             temp = list[i];
733             list[i] = list[j];
734             list[j] = temp;
735          }
736          else  flag = 0;
737       }
738 
739       temp = list[low];
740       list[low] = list[j];
741       list[j] = temp;
742 
743       QuickSort(list, low, j-1, Comp);
744       QuickSort(list, j+1, high, Comp);
745    }
746 }
747 
748 
749 /***
750  *
751  ** function    : Q_Sort
752  *
753  ** purpose     : sort the queue and allow index style access.
754  *
755  ** parameters  : queue pointer, comparison function compatible with
756  *                with 'qsort'.
757  *
758  ** returns     : True_ if sort succeeded. False_ if error occurred.
759  *
760  ** comments    : Comp function supplied by caller must return
761  *                  -1 if data1  < data2
762  *                   0 if data1 == data2
763  *                  +1 if data1  > data2
764  *
765  *                    for Comp(data1, data2)
766  *
767  *                If queue is already sorted it frees the memory of the
768  *                old index and starts again.
769  *
770  ***/
771 
Q_Sort(queue * q,int (* Comp)(const void *,const void *))772 int Q_Sort(queue *q, int (*Comp)(const void *, const void *))
773 {
774    int         i;
775    void        *d;
776    datanode    *dn;
777 
778    /* if already sorted free memory for tag array */
779 
780    if(q->sorted) {
781       efree(queue_index);
782       efree(queue_posn_index);
783       q->sorted = False_;
784    }
785 
786    /* Now allocate memory of array, array of pointers */
787 
788    queue_index = emalloc(q->size * sizeof(q->cursor->data));
789    if(queue_index == NULL)
790       return False_;
791 
792    queue_posn_index = emalloc(q->size * sizeof(q->cursor));
793    if(queue_posn_index == NULL) {
794       efree(queue_index);
795       return False_;
796    }
797 
798    /* Walk queue putting pointers into array */
799 
800    d = Q_Head(q);
801    for(i=0; i < q->size; i++) {
802       queue_index[i] = d;
803       queue_posn_index[i] = q->cursor;
804       d = Q_Next(q);
805    }
806 
807    /* Now sort the index */
808 
809    QuickSort(queue_index, 0, q->size - 1, Comp);
810 
811    /* Rearrange the actual queue into correct order */
812 
813    dn = q->head;
814    i = 0;
815    while(dn != NULL) {
816       dn->data = queue_index[i++];
817       dn = dn->next;
818    }
819 
820    /* Re-position to original element */
821 
822    if(d != NULL)
823       Q_Find(q, d, Comp);
824    else  Q_Head(q);
825 
826    q->sorted = True_;
827 
828    return True_;
829 }
830 
831 
832 /***
833  *
834  ** function    : Q_BSearch
835  *
836  ** purpose     : binary search of queue index for node containing key
837  *
838  ** parameters  : queue pointer 'q', data pointer of key 'key',
839  *                  Comp comparison function.
840  *
841  ** returns     : integer index into array of node pointers,
842  *                or -1 if not found.
843  *
844  ** comments    : see Q_Sort for description of 'Comp' function.
845  *
846  ***/
847 
Q_BSearch(queue * q,void * key,int (* Comp)(const void *,const void *))848 static int Q_BSearch( queue *q, void *key,
849                       int (*Comp)(const void *, const void*))
850 {
851    int low, mid, hi, val;
852 
853    low = 0;
854    hi = q->size - 1;
855 
856    while(low <= hi) {
857       mid = (low + hi) / 2;
858       val = Comp(key, queue_index[ mid ]);
859 
860       if(val < 0)
861          hi = mid - 1;
862 
863       else if(val > 0)
864          low = mid + 1;
865 
866       else /* Success */
867          return mid;
868    }
869 
870    /* Not Found */
871 
872    return -1;
873 }
874 
875 
876 /***
877  *
878  ** function    : Q_Seek
879  *
880  ** purpose     : use index to locate data according to key in 'data'
881  *
882  ** parameters  : queue pointer 'q', data pointer 'data', Comp comparison
883  *                function.
884  *
885  ** returns     : pointer to data or NULL if could not find it or could
886  *                not sort queue.
887  *
888  ** comments    : see Q_Sort for description of 'Comp' function.
889  *
890  ***/
891 
Q_Seek(queue * q,void * data,int (* Comp)(const void *,const void *))892 void *Q_Seek(queue *q, void *data, int (*Comp)(const void *, const void *))
893 {
894    int idx;
895 
896    if (q == NULL) {
897 	return NULL;
898    }
899 
900    if(!q->sorted) {
901       if(!Q_Sort(q, Comp))
902          return NULL;
903    }
904 
905    idx = Q_BSearch(q, data, Comp);
906 
907    if(idx < 0)
908       return NULL;
909 
910    q->cursor = queue_posn_index[idx];
911 
912    return queue_index[idx];
913 }
914 
915 
916 
917 /***
918  *
919  ** function    : Q_Insert
920  *
921  ** purpose     : Insert an element into an indexed queue
922  *
923  ** parameters  : queue pointer 'q', data pointer 'data', Comp comparison
924  *                function.
925  *
926  ** returns     : pointer to data or NULL if could not find it or could
927  *                not sort queue.
928  *
929  ** comments    : see Q_Sort for description of 'Comp' function.
930  *                WARNING! This code can be very slow since each new
931  *                element means a new Q_Sort.  Should only be used for
932  *                the insertion of the odd element ,not the piecemeal
933  *                building of an entire queue.
934  ***/
935 
Q_Insert(queue * q,void * data,int (* Comp)(const void *,const void *))936 int Q_Insert(queue *q, void *data, int (*Comp)(const void *, const void *))
937 {
938    if (q == NULL) {
939 	return False_;
940    }
941 
942    Q_PushHead(q, data);
943 
944    if(!Q_Sort(q, Comp))
945       return False_;
946 
947    return True_;
948 }
949 
950 /* read only funcs for iterating through queue. above funcs modify queue */
Q_Iter_Head(queue * q)951 q_iter Q_Iter_Head(queue *q) {
952    return q ? (q_iter)q->head : NULL;
953 }
954 
Q_Iter_Tail(queue * q)955 q_iter Q_Iter_Tail(queue *q) {
956    return q ? (q_iter)q->tail : NULL;
957 }
958 
Q_Iter_Next(q_iter qi)959 q_iter Q_Iter_Next(q_iter qi) {
960    return qi ? (q_iter)((node*)qi)->next : NULL;
961 }
962 
Q_Iter_Prev(q_iter qi)963 q_iter Q_Iter_Prev(q_iter qi) {
964    return qi ? (q_iter)((node*)qi)->prev : NULL;
965 }
966 
Q_Iter_Get(q_iter qi)967 void * Q_Iter_Get(q_iter qi) {
968    return qi ? ((node*)qi)->data : NULL;
969 }
970 
Q_Iter_Put(q_iter qi,void * data)971 int Q_Iter_Put(q_iter qi, void* data) {
972    if(qi) {
973       ((node*)qi)->data = data;
974       return True_;
975    }
976    return False_;
977 }
978