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