1/* Licensed to the Apache Software Foundation (ASF) under one or more
2 * contributor license agreements.  See the NOTICE file distributed with
3 * this work for additional information regarding copyright ownership.
4 * The ASF licenses this file to You under the Apache License, Version 2.0
5 * (the "License"); you may not use this file except in compliance with
6 * the License.  You may obtain a copy of the License at
7 *
8 *     http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#include <assert.h>
18#include <stdio.h>
19#include <stdlib.h>
20
21#include "apr_pools.h"
22#include "apr_tables.h"
23#include "apr.h"
24#include "apr_hooks.h"
25#include "apr_hash.h"
26#include "apr_optional_hooks.h"
27#include "apr_optional.h"
28#define APR_WANT_MEMFUNC
29#define APR_WANT_STRFUNC
30#include "apr_want.h"
31
32#if 0
33#define apr_palloc(pool,size)   malloc(size)
34#endif
35
36APU_DECLARE_DATA apr_pool_t *apr_hook_global_pool = NULL;
37APU_DECLARE_DATA int apr_hook_debug_enabled = 0;
38APU_DECLARE_DATA const char *apr_hook_debug_current = NULL;
39
40/** @deprecated @see apr_hook_global_pool */
41APU_DECLARE_DATA apr_pool_t *apr_global_hook_pool = NULL;
42
43/** @deprecated @see apr_hook_debug_enabled */
44APU_DECLARE_DATA int apr_debug_module_hooks = 0;
45
46/** @deprecated @see apr_hook_debug_current */
47APU_DECLARE_DATA const char *apr_current_hooking_module = NULL;
48
49/* NB: This must echo the LINK_##name structure */
50typedef struct
51{
52    void (*dummy)(void *);
53    const char *szName;
54    const char * const *aszPredecessors;
55    const char * const *aszSuccessors;
56    int nOrder;
57} TSortData;
58
59typedef struct tsort_
60{
61    void *pData;
62    int nPredecessors;
63    struct tsort_ **ppPredecessors;
64    struct tsort_ *pNext;
65} TSort;
66
67#ifdef NETWARE
68#include "apr_private.h"
69#define get_apd                 APP_DATA* apd = (APP_DATA*)get_app_data(gLibId);
70#define s_aHooksToSort          ((apr_array_header_t *)(apd->gs_aHooksToSort))
71#define s_phOptionalHooks       ((apr_hash_t *)(apd->gs_phOptionalHooks))
72#define s_phOptionalFunctions   ((apr_hash_t *)(apd->gs_phOptionalFunctions))
73#endif
74
75static int crude_order(const void *a_,const void *b_)
76{
77    const TSortData *a=a_;
78    const TSortData *b=b_;
79
80    return a->nOrder-b->nOrder;
81}
82
83static TSort *prepare(apr_pool_t *p,TSortData *pItems,int nItems)
84{
85    TSort *pData=apr_palloc(p,nItems*sizeof *pData);
86    int n;
87
88    qsort(pItems,nItems,sizeof *pItems,crude_order);
89    for(n=0 ; n < nItems ; ++n) {
90        pData[n].nPredecessors=0;
91        pData[n].ppPredecessors=apr_pcalloc(p,nItems*sizeof *pData[n].ppPredecessors);
92        pData[n].pNext=NULL;
93        pData[n].pData=&pItems[n];
94    }
95
96    for(n=0 ; n < nItems ; ++n) {
97        int i,k;
98
99        for(i=0 ; pItems[n].aszPredecessors && pItems[n].aszPredecessors[i] ; ++i)
100            for(k=0 ; k < nItems ; ++k)
101                if(!strcmp(pItems[k].szName,pItems[n].aszPredecessors[i])) {
102                    int l;
103
104                    for(l=0 ; l < pData[n].nPredecessors ; ++l)
105                        if(pData[n].ppPredecessors[l] == &pData[k])
106                            goto got_it;
107                    pData[n].ppPredecessors[pData[n].nPredecessors]=&pData[k];
108                    ++pData[n].nPredecessors;
109                got_it:
110                    break;
111                }
112        for(i=0 ; pItems[n].aszSuccessors && pItems[n].aszSuccessors[i] ; ++i)
113            for(k=0 ; k < nItems ; ++k)
114                if(!strcmp(pItems[k].szName,pItems[n].aszSuccessors[i])) {
115                    int l;
116
117                    for(l=0 ; l < pData[k].nPredecessors ; ++l)
118                        if(pData[k].ppPredecessors[l] == &pData[n])
119                            goto got_it2;
120                    pData[k].ppPredecessors[pData[k].nPredecessors]=&pData[n];
121                    ++pData[k].nPredecessors;
122                got_it2:
123                    break;
124                }
125    }
126
127    return pData;
128}
129
130/* Topologically sort, dragging out-of-order items to the front. Note that
131   this tends to preserve things that want to be near the front better, and
132   changing that behaviour might compromise some of Apache's behaviour (in
133   particular, mod_log_forensic might otherwise get pushed to the end, and
134   core.c's log open function used to end up at the end when pushing items
135   to the back was the methedology). Also note that the algorithm could
136   go back to its original simplicity by sorting from the back instead of
137   the front.
138*/
139static TSort *tsort(TSort *pData,int nItems)
140{
141    int nTotal;
142    TSort *pHead=NULL;
143    TSort *pTail=NULL;
144
145    for(nTotal=0 ; nTotal < nItems ; ++nTotal) {
146        int n,i,k;
147
148        for(n=0 ; ; ++n) {
149            if(n == nItems)
150                assert(0);      /* we have a loop... */
151            if(!pData[n].pNext) {
152                if(pData[n].nPredecessors) {
153                    for(k=0 ; ; ++k) {
154                        assert(k < nItems);
155                        if(pData[n].ppPredecessors[k])
156                            break;
157                    }
158                    for(i=0 ; ; ++i) {
159                        assert(i < nItems);
160                        if(&pData[i] == pData[n].ppPredecessors[k]) {
161                            n=i-1;
162                            break;
163                        }
164                    }
165                } else
166                    break;
167            }
168        }
169        if(pTail)
170            pTail->pNext=&pData[n];
171        else
172            pHead=&pData[n];
173        pTail=&pData[n];
174        pTail->pNext=pTail;     /* fudge it so it looks linked */
175        for(i=0 ; i < nItems ; ++i)
176            for(k=0 ; k < nItems ; ++k)
177                if(pData[i].ppPredecessors[k] == &pData[n]) {
178                    --pData[i].nPredecessors;
179                    pData[i].ppPredecessors[k]=NULL;
180                    break;
181                }
182    }
183    pTail->pNext=NULL;  /* unfudge the tail */
184    return pHead;
185}
186
187static apr_array_header_t *sort_hook(apr_array_header_t *pHooks,
188                                     const char *szName)
189{
190    apr_pool_t *p;
191    TSort *pSort;
192    apr_array_header_t *pNew;
193    int n;
194
195    apr_pool_create(&p, apr_hook_global_pool);
196    pSort=prepare(p,(TSortData *)pHooks->elts,pHooks->nelts);
197    pSort=tsort(pSort,pHooks->nelts);
198    pNew=apr_array_make(apr_hook_global_pool,pHooks->nelts,sizeof(TSortData));
199    if(apr_hook_debug_enabled)
200        printf("Sorting %s:",szName);
201    for(n=0 ; pSort ; pSort=pSort->pNext,++n) {
202        TSortData *pHook;
203        assert(n < pHooks->nelts);
204        pHook=apr_array_push(pNew);
205        memcpy(pHook,pSort->pData,sizeof *pHook);
206        if(apr_hook_debug_enabled)
207            printf(" %s",pHook->szName);
208    }
209    if(apr_hook_debug_enabled)
210        fputc('\n',stdout);
211
212    /* destroy the pool - the sorted hooks were already copied */
213    apr_pool_destroy(p);
214
215    return pNew;
216}
217
218#ifndef NETWARE
219static apr_array_header_t *s_aHooksToSort;
220#endif
221
222typedef struct
223{
224    const char *szHookName;
225    apr_array_header_t **paHooks;
226} HookSortEntry;
227
228APU_DECLARE(void) apr_hook_sort_register(const char *szHookName,
229                                        apr_array_header_t **paHooks)
230{
231#ifdef NETWARE
232    get_apd
233#endif
234    HookSortEntry *pEntry;
235
236    if(!s_aHooksToSort)
237        s_aHooksToSort=apr_array_make(apr_hook_global_pool,1,sizeof(HookSortEntry));
238    pEntry=apr_array_push(s_aHooksToSort);
239    pEntry->szHookName=szHookName;
240    pEntry->paHooks=paHooks;
241}
242
243APU_DECLARE(void) apr_hook_sort_all(void)
244{
245#ifdef NETWARE
246    get_apd
247#endif
248    int n;
249
250    if (!s_aHooksToSort) {
251        s_aHooksToSort = apr_array_make(apr_hook_global_pool, 1, sizeof(HookSortEntry));
252    }
253
254    for(n=0 ; n < s_aHooksToSort->nelts ; ++n) {
255        HookSortEntry *pEntry=&((HookSortEntry *)s_aHooksToSort->elts)[n];
256        *pEntry->paHooks=sort_hook(*pEntry->paHooks,pEntry->szHookName);
257    }
258}
259
260#ifndef NETWARE
261static apr_hash_t *s_phOptionalHooks;
262static apr_hash_t *s_phOptionalFunctions;
263#endif
264
265APU_DECLARE(void) apr_hook_deregister_all(void)
266{
267#ifdef NETWARE
268    get_apd
269#endif
270    int n;
271
272    if (!s_aHooksToSort) {
273        return;
274    }
275
276    for(n=0 ; n < s_aHooksToSort->nelts ; ++n) {
277        HookSortEntry *pEntry=&((HookSortEntry *)s_aHooksToSort->elts)[n];
278        *pEntry->paHooks=NULL;
279    }
280    s_aHooksToSort=NULL;
281    s_phOptionalHooks=NULL;
282    s_phOptionalFunctions=NULL;
283}
284
285APU_DECLARE(void) apr_hook_debug_show(const char *szName,
286                                      const char * const *aszPre,
287                                      const char * const *aszSucc)
288{
289    int nFirst;
290
291    printf("  Hooked %s",szName);
292    if(aszPre) {
293        fputs(" pre(",stdout);
294        nFirst=1;
295        while(*aszPre) {
296            if(!nFirst)
297                fputc(',',stdout);
298            nFirst=0;
299            fputs(*aszPre,stdout);
300            ++aszPre;
301        }
302        fputc(')',stdout);
303    }
304    if(aszSucc) {
305        fputs(" succ(",stdout);
306        nFirst=1;
307        while(*aszSucc) {
308            if(!nFirst)
309                fputc(',',stdout);
310            nFirst=0;
311            fputs(*aszSucc,stdout);
312            ++aszSucc;
313        }
314        fputc(')',stdout);
315    }
316    fputc('\n',stdout);
317}
318
319/* Optional hook support */
320
321APR_DECLARE_EXTERNAL_HOOK(apr,APU,void,_optional,(void))
322
323APU_DECLARE(apr_array_header_t *) apr_optional_hook_get(const char *szName)
324{
325#ifdef NETWARE
326    get_apd
327#endif
328    apr_array_header_t **ppArray;
329
330    if(!s_phOptionalHooks)
331        return NULL;
332    ppArray=apr_hash_get(s_phOptionalHooks,szName,strlen(szName));
333    if(!ppArray)
334        return NULL;
335    return *ppArray;
336}
337
338APU_DECLARE(void) apr_optional_hook_add(const char *szName,void (*pfn)(void),
339                                        const char * const *aszPre,
340                                        const char * const *aszSucc,int nOrder)
341{
342#ifdef NETWARE
343    get_apd
344#endif
345    apr_array_header_t *pArray=apr_optional_hook_get(szName);
346    apr_LINK__optional_t *pHook;
347
348    if(!pArray) {
349        apr_array_header_t **ppArray;
350
351        pArray=apr_array_make(apr_hook_global_pool,1,
352                              sizeof(apr_LINK__optional_t));
353        if(!s_phOptionalHooks)
354            s_phOptionalHooks=apr_hash_make(apr_hook_global_pool);
355        ppArray=apr_palloc(apr_hook_global_pool,sizeof *ppArray);
356        *ppArray=pArray;
357        apr_hash_set(s_phOptionalHooks,szName,strlen(szName),ppArray);
358        apr_hook_sort_register(szName,ppArray);
359    }
360    pHook=apr_array_push(pArray);
361    pHook->pFunc=pfn;
362    pHook->aszPredecessors=aszPre;
363    pHook->aszSuccessors=aszSucc;
364    pHook->nOrder=nOrder;
365    pHook->szName=apr_hook_debug_current;
366    if(apr_hook_debug_enabled)
367        apr_hook_debug_show(szName,aszPre,aszSucc);
368}
369
370/* optional function support */
371
372APU_DECLARE(apr_opt_fn_t *) apr_dynamic_fn_retrieve(const char *szName)
373{
374#ifdef NETWARE
375    get_apd
376#endif
377    if(!s_phOptionalFunctions)
378        return NULL;
379    return (void(*)(void))apr_hash_get(s_phOptionalFunctions,szName,strlen(szName));
380}
381
382/* Deprecated */
383APU_DECLARE_NONSTD(void) apr_dynamic_fn_register(const char *szName,
384                                                  apr_opt_fn_t *pfn)
385{
386#ifdef NETWARE
387    get_apd
388#endif
389    if(!s_phOptionalFunctions)
390        s_phOptionalFunctions=apr_hash_make(apr_hook_global_pool);
391    apr_hash_set(s_phOptionalFunctions,szName,strlen(szName),(void *)pfn);
392}
393
394#if 0
395void main()
396{
397    const char *aszAPre[]={"b","c",NULL};
398    const char *aszBPost[]={"a",NULL};
399    const char *aszCPost[]={"b",NULL};
400    TSortData t1[]=
401    {
402        { "a",aszAPre,NULL },
403        { "b",NULL,aszBPost },
404        { "c",NULL,aszCPost }
405    };
406    TSort *pResult;
407
408    pResult=prepare(t1,3);
409    pResult=tsort(pResult,3);
410
411    for( ; pResult ; pResult=pResult->pNext)
412        printf("%s\n",pResult->pData->szName);
413}
414#endif
415