Back to index

lightning-sunbird  0.9+nobinonly
stack.c
Go to the documentation of this file.
00001 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
00002 /* ***** BEGIN LICENSE BLOCK *****
00003  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00004  *
00005  * The contents of this file are subject to the Mozilla Public License Version
00006  * 1.1 (the "License"); you may not use this file except in compliance with
00007  * the License. You may obtain a copy of the License at
00008  * http://www.mozilla.org/MPL/
00009  *
00010  * Software distributed under the License is distributed on an "AS IS" basis,
00011  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00012  * for the specific language governing rights and limitations under the
00013  * License.
00014  *
00015  * The Original Code is the Netscape Portable Runtime (NSPR).
00016  *
00017  * The Initial Developer of the Original Code is
00018  * Netscape Communications Corporation.
00019  * Portions created by the Initial Developer are Copyright (C) 1998-2000
00020  * the Initial Developer. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *
00024  * Alternatively, the contents of this file may be used under the terms of
00025  * either the GNU General Public License Version 2 or later (the "GPL"), or
00026  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00027  * in which case the provisions of the GPL or the LGPL are applicable instead
00028  * of those above. If you wish to allow use of your version of this file only
00029  * under the terms of either the GPL or the LGPL, and not to allow others to
00030  * use your version of this file under the terms of the MPL, indicate your
00031  * decision by deleting the provisions above and replace them with the notice
00032  * and other provisions required by the GPL or the LGPL. If you do not delete
00033  * the provisions above, a recipient may use your version of this file under
00034  * the terms of any one of the MPL, the GPL or the LGPL.
00035  *
00036  * ***** END LICENSE BLOCK ***** */
00037 
00038 
00039 /*
00040  *
00041  * Test atomic stack operations
00042  *            
00043  *            Two stacks are created and threads add data items (each containing
00044  *            one of the first n integers) to the first stack, remove data items
00045  *            from the first stack and add them to the second stack. The primordial
00046  *            thread compares the sum of the first n integers to the sum of the
00047  *            integers in the data items in the second stack. The test succeeds if
00048  *            they are equal.
00049  */
00050  
00051 #include "nspr.h"
00052 #include "plgetopt.h"
00053 
00054 typedef struct _DataRecord {
00055        PRInt32       data;
00056        PRStackElem   link;
00057 } DataRecord;
00058 
00059 #define RECORD_LINK_PTR(lp) ((DataRecord*) ((char*) (lp) - offsetof(DataRecord,link)))
00060 
00061 #define MAX_THREAD_CNT             100
00062 #define DEFAULT_THREAD_CNT  4
00063 #define DEFAULT_DATA_CNT    100
00064 #define DEFAULT_LOOP_CNT    10000
00065 
00066 /*
00067  * sum of the first n numbers using the formula n*(n+1)/2
00068  */
00069 #define SUM_OF_NUMBERS(n) ((n & 1) ? (((n + 1)/2) * n) : ((n/2) * (n+1)))
00070 
00071 typedef struct stack_data {
00072        PRStack              *list1;
00073        PRStack              *list2;
00074        PRInt32              initial_data_value;
00075        PRInt32              data_cnt;
00076        PRInt32              loops;
00077 } stack_data;
00078 
00079 static void stackop(void *arg);
00080 
00081 static int _debug_on;
00082 
00083 PRFileDesc  *output;
00084 PRFileDesc  *errhandle;
00085 
00086 PRIntn main(PRIntn argc, char **argv)
00087 {
00088     PRInt32 rv, cnt, sum;
00089        DataRecord    *Item;
00090        PRStack              *list1, *list2;
00091        PRStackElem   *node;
00092        PRStatus rc;
00093 
00094        PRInt32 thread_cnt = DEFAULT_THREAD_CNT;
00095        PRInt32 data_cnt = DEFAULT_DATA_CNT;
00096        PRInt32 loops = DEFAULT_LOOP_CNT;
00097        PRThread **threads;
00098        stack_data *thread_args;
00099 
00100        PLOptStatus os;
00101        PLOptState *opt = PL_CreateOptState(argc, argv, "dt:c:l:");
00102 
00103        while (PL_OPT_EOL != (os = PL_GetNextOpt(opt)))
00104     {
00105               if (PL_OPT_BAD == os) continue;
00106         switch (opt->option)
00107         {
00108         case 'd':  /* debug mode */
00109                      _debug_on = 1;
00110             break;
00111         case 't':  /* thread count */
00112             thread_cnt = atoi(opt->value);
00113             break;
00114         case 'c':  /* data count */
00115             data_cnt = atoi(opt->value);
00116             break;
00117         case 'l':  /* loop count */
00118             loops = atoi(opt->value);
00119             break;
00120          default:
00121             break;
00122         }
00123     }
00124        PL_DestroyOptState(opt);
00125 
00126        PR_SetConcurrency(4);
00127 
00128     output = PR_GetSpecialFD(PR_StandardOutput);
00129     errhandle = PR_GetSpecialFD(PR_StandardError);
00130        list1 = PR_CreateStack("Stack_1");
00131        if (list1 == NULL) {
00132               PR_fprintf(errhandle, "PR_CreateStack failed - error %d\n",
00133                                                         PR_GetError());
00134               return 1;
00135        }
00136 
00137        list2 = PR_CreateStack("Stack_2");
00138        if (list2 == NULL) {
00139               PR_fprintf(errhandle, "PR_CreateStack failed - error %d\n",
00140                                                         PR_GetError());
00141               return 1;
00142        }
00143 
00144 
00145        threads = (PRThread**) PR_CALLOC(sizeof(PRThread*) * thread_cnt);
00146        thread_args = (stack_data *) PR_CALLOC(sizeof(stack_data) * thread_cnt);
00147 
00148        if (_debug_on)
00149               PR_fprintf(output,"%s: thread_cnt = %d data_cnt = %d\n", argv[0],
00150                                                  thread_cnt, data_cnt);
00151        for(cnt = 0; cnt < thread_cnt; cnt++) {
00152               PRThreadScope scope;
00153 
00154               thread_args[cnt].list1 = list1;
00155               thread_args[cnt].list2 = list2;
00156               thread_args[cnt].loops = loops;
00157               thread_args[cnt].data_cnt = data_cnt;     
00158               thread_args[cnt].initial_data_value = 1 + cnt * data_cnt;
00159 
00160               if (cnt & 1)
00161                      scope = PR_GLOBAL_THREAD;
00162               else
00163                      scope = PR_LOCAL_THREAD;
00164 
00165 
00166               threads[cnt] = PR_CreateThread(PR_USER_THREAD,
00167                                             stackop, &thread_args[cnt],
00168                                             PR_PRIORITY_NORMAL,
00169                                             scope,
00170                                             PR_JOINABLE_THREAD,
00171                                             0);
00172               if (threads[cnt] == NULL) {
00173                      PR_fprintf(errhandle, "PR_CreateThread failed - error %d\n",
00174                                                         PR_GetError());
00175                      PR_ProcessExit(2);
00176               }
00177               if (_debug_on)
00178                      PR_fprintf(output,"%s: created thread = 0x%x\n", argv[0],
00179                                                                       threads[cnt]);
00180        }
00181 
00182        for(cnt = 0; cnt < thread_cnt; cnt++) {
00183        rc = PR_JoinThread(threads[cnt]);
00184               PR_ASSERT(rc == PR_SUCCESS);
00185        }
00186 
00187        node = PR_StackPop(list1);
00188        /*
00189         * list1 should be empty
00190         */
00191        if (node != NULL) {
00192               PR_fprintf(errhandle, "Error - Stack 1 not empty\n");
00193               PR_ASSERT(node == NULL);
00194               PR_ProcessExit(4);
00195        }
00196 
00197        cnt = data_cnt * thread_cnt;
00198        sum = 0;
00199        while (cnt-- > 0) {
00200               node = PR_StackPop(list2);
00201               /*
00202                * There should be at least 'cnt' number of records
00203                */
00204               if (node == NULL) {
00205                      PR_fprintf(errhandle, "Error - PR_StackPop returned NULL\n");
00206                      PR_ProcessExit(3);
00207               }
00208               Item = RECORD_LINK_PTR(node);
00209               sum += Item->data;
00210        }
00211        node = PR_StackPop(list2);
00212        /*
00213         * there should be exactly 'cnt' number of records
00214         */
00215        if (node != NULL) {
00216               PR_fprintf(errhandle, "Error - Stack 2 not empty\n");
00217               PR_ASSERT(node == NULL);
00218               PR_ProcessExit(4);
00219        }
00220        PR_DELETE(threads);
00221        PR_DELETE(thread_args);
00222 
00223        PR_DestroyStack(list1);
00224        PR_DestroyStack(list2);
00225 
00226        if (sum == SUM_OF_NUMBERS(data_cnt * thread_cnt)) {
00227               PR_fprintf(output, "%s successful\n", argv[0]);
00228               PR_fprintf(output, "\t\tsum = 0x%x, expected = 0x%x\n", sum,
00229                                                  SUM_OF_NUMBERS(thread_cnt * data_cnt));
00230               return 0;
00231        } else {
00232               PR_fprintf(output, "%s failed: sum = 0x%x, expected = 0x%x\n",
00233                                                  argv[0], sum,
00234                                                         SUM_OF_NUMBERS(data_cnt * thread_cnt));
00235               return 2;
00236        }
00237 }
00238 
00239 static void stackop(void *thread_arg)
00240 {
00241     PRInt32 val, cnt, index, loops;
00242        DataRecord    *Items, *Item;
00243        PRStack              *list1, *list2;
00244        PRStackElem   *node;
00245        stack_data *arg = (stack_data *) thread_arg;
00246 
00247        val = arg->initial_data_value;
00248        cnt = arg->data_cnt;
00249        loops = arg->loops;
00250        list1 = arg->list1;
00251        list2 = arg->list2;
00252 
00253        /*
00254         * allocate memory for the data records
00255         */
00256        Items = (DataRecord *) PR_CALLOC(sizeof(DataRecord) * cnt);
00257        PR_ASSERT(Items != NULL);
00258        index = 0;
00259 
00260        if (_debug_on)
00261               PR_fprintf(output,
00262               "Thread[0x%x] init_val = %d cnt = %d data1 = 0x%x datan = 0x%x\n",
00263                             PR_GetCurrentThread(), val, cnt, &Items[0], &Items[cnt-1]);
00264 
00265 
00266        /*
00267         * add the data records to list1
00268         */
00269        while (cnt-- > 0) {
00270               Items[index].data = val++;
00271               PR_StackPush(list1, &Items[index].link);
00272               index++;
00273        }
00274 
00275        /*
00276         * pop data records from list1 and add them back to list1
00277         * generates contention for the stack accesses
00278         */
00279        while (loops-- > 0) {
00280               cnt = arg->data_cnt;
00281               while (cnt-- > 0) {
00282                      node = PR_StackPop(list1);
00283                      if (node == NULL) {
00284                             PR_fprintf(errhandle, "Error - PR_StackPop returned NULL\n");
00285                             PR_ASSERT(node != NULL);
00286                             PR_ProcessExit(3);
00287                      }
00288                      PR_StackPush(list1, node);
00289               }
00290        }
00291        /*
00292         * remove the data records from list1 and add them to list2
00293         */
00294        cnt = arg->data_cnt;
00295        while (cnt-- > 0) {
00296               node = PR_StackPop(list1);
00297               if (node == NULL) {
00298                      PR_fprintf(errhandle, "Error - PR_StackPop returned NULL\n");
00299                      PR_ASSERT(node != NULL);
00300                      PR_ProcessExit(3);
00301               }
00302               PR_StackPush(list2, node);
00303        }
00304        if (_debug_on)
00305               PR_fprintf(output,
00306               "Thread[0x%x] init_val = %d cnt = %d exiting\n",
00307                             PR_GetCurrentThread(), val, cnt);
00308 
00309 }
00310