Miscellaneous changes to call NsWaitDriversShutdown and remove unnecessary mutex init
/*
* The contents of this file are subject to the AOLserver Public License
* Version 1.1 (the "License"); you may not use this file except in
* compliance with the License. You may obtain a copy of the License at
* http://aolserver.com/.
*
* Software distributed under the License is distributed on an "AS IS"
* basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
* the License for the specific language governing rights and limitations
* under the License.
*
* The Original Code is AOLserver Code and related documentation
* distributed by AOL.
*
* The Initial Developer of the Original Code is America Online,
* Inc. Portions created by AOL are Copyright (C) 1999 America Online,
* Inc. All Rights Reserved.
*
* Alternatively, the contents of this file may be used under the terms
* of the GNU General Public License (the "GPL"), in which case the
* provisions of GPL are applicable instead of those above. If you wish
* to allow use of your version of this file only under the terms of the
* GPL and not to allow others to use your version of this file under the
* License, indicate your decision by deleting the provisions above and
* replace them with the notice and other provisions required by the GPL.
* If you do not delete the provisions above, a recipient may use your
* version of this file under either the License or the GPL.
*/
/*
* urlspace.c --
*
* This file implements a Trie data structure. It is used
* for "UrlSpecificData"; for example, when one registers
* a handler for all GET /foo/bar/ *.html requests, the data
* structure that holds that information is implemented herein.
* For full details see the file doc/urlspace.txt.
*/
static const char *RCSID = "@(#) $Header: /cvsroot/aolserver/aolserver/nsd/urlspace.c,v 1.11 2003/11/03 19:23:26 pkhincha Exp $, compiled: " __DATE__ " " __TIME__;
#include "nsd.h"
/*
* This optimization, when turned on, prevents the server from doing a
* whole lot of calls to Tcl_StringMatch on every lookup in urlspace.
* Instead, a strcmp is done. This hasn't been thoroughly tested, so
* it is off by default.
*
* #define __URLSPACE_OPTIMIZE__
*/
/*
* This structure defines a Node. It is the lowest-level structure in
* urlspace and contains the data the the user puts in. It holds data
* whose scope is a set of URLs, such as /foo/bar/ *.html.
* Data/cleanup functions are kept seperately for inheriting and non-
* inheriting URLs, as there could be overlap.
*/
typedef struct {
int id; /* Handle from Ns_UrlSpecificAlloc */
void *dataInherit; /* User's data */
void *dataNoInherit; /* User's data */
void (*deletefuncInherit) (void *); /* Cleanup function */
void (*deletefuncNoInherit) (void *); /* Cleanup function */
} Node;
/*
* This structure defines a trie. A trie is a tree whose nodes are
* branches and channels. It is an inherently recursive data structure,
* and each node is itself a trie. Each node represents one "part" of
* a URL; in this case, a "part" is server name, method, directory, or
* wildcard.
*/
typedef struct {
Ns_Index branches;
Ns_Index *indexnode;
} Trie;
/*
* A branch is a typical node in a Trie. The "word" is the part of the
* URL that the branch represents, and "node" is the sub-trie.
*/
typedef struct {
char *word;
Trie node;
} Branch;
/*
* A channel is much like a branch. It exists only at the second level
* (Channels come out of Junctions, which are top-level structures).
* The filter is a copy of the very last part of the URLs matched by
* branches coming out of this channel (only branches come out of channels).
* When looking for a URL, the filename part of the target URL is compared
* with the filter in each channel, and the channel is traversed only if
* there is a match
*/
typedef struct {
char *filter;
Trie trie;
} Channel;
/*
* A Junction is the top-level structure. Channels come out of a junction.
* Currently, only one junction is defined--the static global urlspace.
*/
typedef struct {
Ns_Index byname;
/*
* We've experimented with getting rid of this index because
* it is like byname but in semi-reverse lexicographical
* order. This optimization seems to work in all cases, but
* we need a thorough way of testing all cases.
*/
#ifndef __URLSPACE_OPTIMIZE__
Ns_Index byuse;
#endif
} Junction;
/*
* Local functions defined in this file
*/
static void TrieDestroy(Trie *trie);
static void NodeDestroy(Node *nodePtr);
static int CmpNodes(Node **leftPtrPtr, Node **rightPtrPtr);
static int CmpIdWithNode(int id, Node **nodePtrPtr);
static Ns_Index * IndexNodeCreate(void);
static void IndexNodeDestroy(Ns_Index *indexPtr);
static int CmpBranches(Branch **leftPtrPtr, Branch **rightPtrPtr);
static int CmpKeyWithBranch(char *key, Branch **branchPtrPtr);
static void BranchDestroy(Branch *branchPtr);
/*
* Utility functions
*/
static void MkSeq(Ns_DString *dsPtr, char *server, char *method, char *url);
#ifdef DEBUG
static void indentspace(int n);
static void PrintTrie(Trie *triePtr, int indent);
static void PrintJunction(Junction *junctionPtr);
static void PrintSeq(char *seq);
#endif
/*
* Trie functions
*/
static void TrieInit(Trie *triePtr);
static void TrieAdd(Trie *triePtr, char *seq, int id, void *data, int flags,
void (*deletefunc) (void *));
static void TrieTrunc(Trie *triePtr, int id);
static void TrieDestroy(Trie *triePtr);
static int TrieBranchTrunc(Trie *triePtr, char *seq, int id);
static void *TrieFind(Trie *triePtr, char *seq, int id, int *depthPtr);
static void *TrieFindExact(Trie *triePtr, char *seq, int id, int flags);
static void *TrieDelete(Trie *triePtr, char *seq, int id, int flags);
/*
* Channel functions
*/
#ifndef __URLSPACE_OPTIMIZE__
static int CmpChannels(Channel **leftPtrPtr, Channel **rightPtrPtr);
static int CmpKeyWithChannel(char *key, Channel **channelPtrPtr);
#endif
static int CmpChannelsAsStrings(Channel **leftPtrPtr, Channel **rightPtrPtr);
static int CmpKeyWithChannelAsStrings(char *key, Channel **channelPtrPtr);
/*
* Juntion functions
*/
static void JunctionInit(Junction *juncPtr);
static void JunctionAdd(Junction *juncPtr, char *seq, int id, void *data,
int flags, void (*deletefunc) (void *));
static void JunctionBranchTrunc(Junction *juncPtr, char *seq, int id);
static void *JunctionFind(Junction *juncPtr, char *seq, int id, int fast);
static void *JunctionFindExact(Junction *juncPtr, char *seq, int id, int flags,
int fast);
static void *JunctionDelete(Junction *juncPtr, char *seq, int id, int flags);
/*
* Static variables defined in this file
*/
static Junction urlspace; /* All URL-specific data stored here */
static Ns_Mutex lock;
/*
*----------------------------------------------------------------------
*
* NsInitUrlSpace --
*
* Initialize the urlspace API.
*
* Results:
* None.
*
* Side effects:
* None.
*
*----------------------------------------------------------------------
*/
void
NsInitUrlSpace(void)
{
Ns_MutexSetName(&lock, "ns:urlspace");
JunctionInit(&urlspace);
}
/*
*----------------------------------------------------------------------
*
* Ns_UrlSpecificAlloc --
*
* Allocate a unique ID to create a seperate virtual URL-space.
*
* Results:
* An integer handle
*
* Side effects:
* nextid will be incremented; don't call after server startup.
*
*----------------------------------------------------------------------
*/
int
Ns_UrlSpecificAlloc(void)
{
int id;
static int nextid = 0;
Ns_MutexLock(&lock);
id = nextid++;
Ns_MutexUnlock(&lock);
return id;
}
/*
*----------------------------------------------------------------------
*
* Ns_UrlSpecificSet --
*
* Associate data with a set of URLs matching a wildcard, or
* that are simply sub-URLs.
*
* Flags can be NS_OP_NOINHERIT or NS_OP_NODELETE.
*
* Results:
* None
*
* Side effects:
* Will set data in the urlspace trie.
*
*----------------------------------------------------------------------
*/
void
Ns_UrlSpecificSet(char *server, char *method, char *url, int id, void *data,
int flags, void (*deletefunc) (void *))
{
Ns_DString ds;
Ns_DStringInit(&ds);
MkSeq(&ds, server, method, url);
Ns_MutexLock(&lock);
JunctionAdd(&urlspace, ds.string, id, data, flags, deletefunc);
Ns_MutexUnlock(&lock);
Ns_DStringFree(&ds);
}
/*
*----------------------------------------------------------------------
*
* Ns_UrlSpecificGet --
*
* Find URL-specific data in the subspace identified by id that
* the passed-in URL matches
*
* Results:
* A pointer to user data, set with Ns_UrlSpecificSet
*
* Side effects:
* None
*
*----------------------------------------------------------------------
*/
void *
Ns_UrlSpecificGet(char *server, char *method, char *url, int id)
{
Ns_DString ds;
void *data;
Ns_DStringInit(&ds);
MkSeq(&ds, server, method, url);
Ns_MutexLock(&lock);
data = JunctionFind(&urlspace, ds.string, id, 0);
Ns_MutexUnlock(&lock);
Ns_DStringFree(&ds);
return data;
}
/*
*----------------------------------------------------------------------
*
* Ns_UrlSpecificGetFast --
*
* Similar to Ns_UrlSpecificGet, but doesn't support wildcards;
* on the other hand, it's a lot faster.
*
* Results:
* See Ns_UrlSpecificGet
*
* Side effects:
* None
*
*----------------------------------------------------------------------
*/
void *
Ns_UrlSpecificGetFast(char *server, char *method, char *url, int id)
{
Ns_DString ds;
void *data;
Ns_DStringInit(&ds);
MkSeq(&ds, server, method, url);
Ns_MutexLock(&lock);
data = JunctionFind(&urlspace, ds.string, id, 1);
Ns_MutexUnlock(&lock);
Ns_DStringFree(&ds);
return data;
}
/*
*----------------------------------------------------------------------
*
* Ns_UrlSpecificGetExact --
* Similar to Ns_UrlSpecificGet, but does not support URL
* inheritance
*
* Results:
* See Ns_UrlSpecificGet
*
* Side effects:
* None
*
*----------------------------------------------------------------------
*/
void *
Ns_UrlSpecificGetExact(char *server, char *method, char *url, int id,
int flags)
{
Ns_DString ds;
void *data;
Ns_DStringInit(&ds);
MkSeq(&ds, server, method, url);
Ns_MutexLock(&lock);
data = JunctionFindExact(&urlspace, ds.string, id, flags, 0);
Ns_MutexUnlock(&lock);
Ns_DStringFree(&ds);
return data;
}
/*
*----------------------------------------------------------------------
*
* Ns_UrlSpecificDestroy --
*
* Delete some urlspecific data.
*
* flags can be NS_OP_NODELETE, NS_OP_NOINHERIT and/or NS_OP_RECURSE
*
* Results:
* None
*
* Side effects:
* Will remove data from urlspace; don't call this after server
* startup.
*
*----------------------------------------------------------------------
*/
void *
Ns_UrlSpecificDestroy(char *server, char *method, char *url, int id, int flags)
{
Ns_DString ds;
void *data = NULL;
Ns_DStringInit(&ds);
MkSeq(&ds, server, method, url);
Ns_MutexLock(&lock);
if (flags & NS_OP_RECURSE) {
JunctionBranchTrunc(&urlspace, ds.string, id);
data = NULL;
} else {
data = JunctionDelete(&urlspace, ds.string, id, flags);
}
Ns_MutexUnlock(&lock);
Ns_DStringFree(&ds);
return data;
}
/*
*----------------------------------------------------------------------
*
* Ns_ServerSpecificAlloc --
*
* Allocate a unique integer to be used with Ns_ServerSpecific*
* calls
*
* Results:
* An integer handle
*
* Side effects:
* None
*
*----------------------------------------------------------------------
*/
int
Ns_ServerSpecificAlloc(void)
{
return Ns_UrlSpecificAlloc();
}
/*
*----------------------------------------------------------------------
*
* Ns_ServerSpecificSet --
*
* Set server-specific data
*
* Results:
* None
*
* Side effects:
* See Ns_UrlSpecificSet
*
*----------------------------------------------------------------------
*/
void
Ns_ServerSpecificSet(char *handle, int id, void *data, int flags,
void (*deletefunc) (void *))
{
Ns_UrlSpecificSet(handle, NULL, NULL, id, data, flags, deletefunc);
}
/*
*----------------------------------------------------------------------
*
* Ns_ServerSpecificGet --
*
* Get server-specific data.
*
* Results:
* User server-specific data.
*
* Side effects:
* None.
*
*----------------------------------------------------------------------
*/
void *
Ns_ServerSpecificGet(char *handle, int id)
{
return Ns_UrlSpecificGet(handle, NULL, NULL, id);
}
/*
*----------------------------------------------------------------------
*
* Ns_ServerSpecificDestroy --
*
* Destroy server-specific data.
*
* Results:
* None.
*
* Side effects:
* Will remove data from urlspace.
*
*----------------------------------------------------------------------
*/
void *
Ns_ServerSpecificDestroy(char *handle, int id, int flags)
{
return Ns_UrlSpecificDestroy(handle, NULL, NULL, id, flags);
}
/*
*----------------------------------------------------------------------
*
* NodeDestroy --
*
* Free a node and its data
*
* Results:
* None
*
* Side effects:
* The delete function is called and the node is freed
*
*----------------------------------------------------------------------
*/
static void
NodeDestroy(Node *nodePtr)
{
if (nodePtr == NULL) {
goto done;
}
if (nodePtr->deletefuncNoInherit != NULL) {
(*nodePtr->deletefuncNoInherit) (nodePtr->dataNoInherit);
}
if (nodePtr->deletefuncInherit != NULL) {
(*nodePtr->deletefuncInherit) (nodePtr->dataInherit);
}
ns_free(nodePtr);
done:
return;
}
/*
*----------------------------------------------------------------------
*
* CmpNodes --
*
* Compare two Nodes by id. Ns_Index calls use this as a callback.
*
* Results:
* 0 if equal, 1 if left is greater, -1 if left is less.
*
* Side effects:
* None
*
*----------------------------------------------------------------------
*/
static int
CmpNodes(Node **leftPtrPtr, Node **rightPtrPtr)
{
if ((*leftPtrPtr)->id != (*rightPtrPtr)->id) {
return ((*leftPtrPtr)->id > (*rightPtrPtr)->id) ? 1 : -1;
} else {
return 0;
}
}
/*
*----------------------------------------------------------------------
*
* CmpIdWithNode --
*
* Compare a node's ID to a passed-in ID; called by Ns_Index*
*
* Results:
* 0 if equal; 1 if id is too high; -1 if id is too low
*
* Side effects:
* None
*
*----------------------------------------------------------------------
*/
static int
CmpIdWithNode(int id, Node **nodePtrPtr)
{
if (id != (*nodePtrPtr)->id) {
return (id > (*nodePtrPtr)->id) ? 1 : -1;
} else {
return 0;
}
}
/*
*----------------------------------------------------------------------
*
* IndexNodeCreate --
*
* Initialize a trie->indexnode structure
*
* Results:
* A pointer to an appropriately initialized index
*
* Side effects:
* Memory alloacted.
*
*----------------------------------------------------------------------
*/
static Ns_Index *
IndexNodeCreate(void)
{
Ns_Index *indexPtr;
indexPtr = ns_malloc(sizeof(Ns_Index));
Ns_IndexInit(indexPtr, 5, (int (*) (const void *, const void *)) CmpNodes,
(int (*) (const void *, const void *)) CmpIdWithNode);
return indexPtr;
}
/*
*----------------------------------------------------------------------
*
* IndexNodeDestroy --
*
* Wipe out a trie->indexnode structure.
*
* Results:
* None.
*
* Side effects:
* Memory freed.
*
*----------------------------------------------------------------------
*/
static void
IndexNodeDestroy(Ns_Index *indexPtr)
{
int i;
i = Ns_IndexCount(indexPtr);
while (i--) {
NodeDestroy(Ns_IndexEl(indexPtr, i));
}
Ns_IndexDestroy(indexPtr);
ns_free(indexPtr);
}
/*
*----------------------------------------------------------------------
*
* CmpBranches --
*
* Compare two branches' word members. Called by Ns_Index*
*
* Results:
* 0 if equal, -1 if left is greater; 1 if right is greater
*
* Side effects:
* None.
*
*----------------------------------------------------------------------
*/
static int
CmpBranches(Branch **leftPtrPtr, Branch **rightPtrPtr)
{
return strcmp((*leftPtrPtr)->word, (*rightPtrPtr)->word);
}
/*
*----------------------------------------------------------------------
*
* CmpBranches --
*
* Compare a branch's word to a passed-in key; called by
* Ns_Index*.
*
* Results:
* 0 if equal, -1 if left is greater; 1 if right is greater.
*
* Side effects:
* None.
*
*----------------------------------------------------------------------
*/
static int
CmpKeyWithBranch(char *key, Branch ** branchPtrPtr)
{
return strcmp(key, (*branchPtrPtr)->word);
}
/*
*----------------------------------------------------------------------
*
* BranchDestroy --
*
* Free a branch structure
*
* Results:
* None.
*
* Side effects:
* Will free memory.
*
*----------------------------------------------------------------------
*/
static void
BranchDestroy(Branch *branchPtr)
{
ns_free(branchPtr->word);
TrieDestroy(&branchPtr->node);
ns_free(branchPtr);
}
/*
*----------------------------------------------------------------------
*
* TrieInit --
*
* Initialize a Trie data structure with 25 branches and set the
* Cmp functions for Ns_Index*.
*
* Results:
* None.
*
* Side effects:
* The trie is initialized and memory is allocated; memory is
* allocated.
*
*----------------------------------------------------------------------
*/
static void
TrieInit(Trie *triePtr)
{
Ns_IndexInit(&triePtr->branches, 25,
(int (*) (const void *, const void *)) CmpBranches,
(int (*) (const void *, const void *)) CmpKeyWithBranch);
triePtr->indexnode = NULL;
}
/*
*----------------------------------------------------------------------
*
* TrieAdd --
*
* Add something to the Trie data structure, usually to the
* variable urlspace.
*
* seq is a null-delimited string of words, terminated with
* two nulls.
* id is allocated with Ns_UrlSpecificAlloc.
* flags is a bitmask; optionally OR NS_OP_NODELETE,
* NS_OP_NOINHERIT for desired behavior.
*
* Results:
* None.
*
* Side effects:
* Memory is allocated. If a node is found and the
* NS_OP_NODELETE is not set, the current node's data is deleted.
*
*----------------------------------------------------------------------
*/
static void
TrieAdd(Trie *triePtr, char *seq, int id, void *data, int flags,
void (*deletefunc) (void *))
{
if (*seq == '\0') {
Node *nodePtr;
/*
* The entire sequence has been traversed, creating a branch
* for each word. Now it is time to make a Node.
*
* First, allocate a new node or find a matching one in existance.
*/
if (triePtr->indexnode == NULL) {
triePtr->indexnode = IndexNodeCreate();
nodePtr = NULL;
} else {
nodePtr = Ns_IndexFind(triePtr->indexnode, (void *) id);
}
if (nodePtr == NULL) {
/*
* Create and initialize a new node.
*/
nodePtr = ns_malloc(sizeof(Node));
nodePtr->id = id;
Ns_IndexAdd(triePtr->indexnode, nodePtr);
nodePtr->dataInherit = NULL;
nodePtr->dataNoInherit = NULL;
nodePtr->deletefuncInherit = NULL;
nodePtr->deletefuncNoInherit = NULL;
} else {
/*
* If NS_OP_NODELETE is NOT set, then delete the current node
* because one already exists.
*/
if ((flags & NS_OP_NODELETE) == 0) {
if ((flags & NS_OP_NOINHERIT) != 0) {
if (nodePtr->deletefuncNoInherit != NULL) {
(*nodePtr->deletefuncNoInherit)
(nodePtr->dataNoInherit);
}
} else {
if (nodePtr->deletefuncInherit != NULL) {
(*nodePtr->deletefuncInherit) (nodePtr->dataInherit);
}
}
}
}
if (flags & NS_OP_NOINHERIT) {
nodePtr->dataNoInherit = data;
nodePtr->deletefuncNoInherit = deletefunc;
} else {
nodePtr->dataInherit = data;
nodePtr->deletefuncInherit = deletefunc;
}
} else {
Branch *branchPtr;
/*
* We are parsing the middle of a sequence, such as "foo" in:
* "server1\0GET\0foo\0*.html\0"
*
* Create a new branch and recurse to add the next word in the
* sequence.
*/
branchPtr = Ns_IndexFind(&triePtr->branches, seq);
if (branchPtr == NULL) {
branchPtr = ns_malloc(sizeof(Branch));
branchPtr->word = ns_strdup(seq);
TrieInit(&branchPtr->node);
Ns_IndexAdd(&triePtr->branches, branchPtr);
}
TrieAdd(&branchPtr->node, seq + strlen(seq) + 1, id, data, flags,
deletefunc);
}
}
/*
*----------------------------------------------------------------------
*
* TrieTrunc --
*
* Wipes out all references to id. If id==-1 then it wipes out
* everything.
*
* Results:
* None
*
* Side effects:
* Nodes and branches may be destroyed/freed.
*
*----------------------------------------------------------------------
*/
static void
TrieTrunc(Trie *triePtr, int id)
{
int n;
n = Ns_IndexCount(&triePtr->branches);
if (n > 0) {
/*
* Loop over each branch and recurse.
*/
int i;
for (i = 0; i < n; i++) {
Branch *branchPtr;
branchPtr = Ns_IndexEl(&triePtr->branches, i);
TrieTrunc(&branchPtr->node, id);
}
}
if (triePtr->indexnode != NULL) {
if (id != -1) {
Node *nodePtr;
/*
* Destroy just the node for this ID
*/
nodePtr = Ns_IndexFind(triePtr->indexnode, (void *) id);
if (nodePtr != NULL) {
NodeDestroy(nodePtr);
Ns_IndexDel(triePtr->indexnode, nodePtr);
}
} else {
/*
* Destroy the whole index of nodes.
*/
IndexNodeDestroy(triePtr->indexnode);
triePtr->indexnode = NULL;
}
}
}
/*
*----------------------------------------------------------------------
*
* TrieDestroy --
*
* Delete an entire Trie.
*
* Results:
* None.
*
* Side effects:
* Will free all the elements of the trie.
*
*----------------------------------------------------------------------
*/
static void
TrieDestroy(Trie *triePtr)
{
int n;
n = Ns_IndexCount(&triePtr->branches);
if (n > 0) {
int i;
/*
* Loop over each branch and delete it
*/
for (i = 0; i < n; i++) {
Branch *branchPtr;
branchPtr = Ns_IndexEl(&triePtr->branches, i);
BranchDestroy(branchPtr);
}
Ns_IndexDestroy(&triePtr->branches);
}
if (triePtr->indexnode != NULL) {
IndexNodeDestroy(triePtr->indexnode);
}
}
/*
*----------------------------------------------------------------------
*
* TrieBranchTrunc --
*
* Cut off a branch from a trie
*
* Results:
* 0 on success, -1 on failure
*
* Side effects:
* Will delete a branch.
*
*----------------------------------------------------------------------
*/
static int
TrieBranchTrunc(Trie *triePtr, char *seq, int id)
{
if (*seq != '\0') {
Branch *branchPtr;
branchPtr = Ns_IndexFind(&triePtr->branches, seq);
/*
* If this sequence exists, recursively delete it; otherwise
* return an error.
*/
if (branchPtr != NULL) {
return TrieBranchTrunc(&branchPtr->node, seq + strlen(seq) + 1,
id);
} else {
return -1;
}
} else {
/*
* The end of the sequence has been reached. Finish up the job
* and return success.
*/
TrieTrunc(triePtr, id);
return 0;
}
}
/*
*----------------------------------------------------------------------
*
* TrieFind --
*
* Find a node in a trie matching a sequence.
*
* Results:
* Return the appropriate node's data.
*
* Side effects:
* The depth variable will be set-by-reference to the depth of
* the returned node. If no node is set, it will not be changed.
*
*----------------------------------------------------------------------
*/
static void *
TrieFind(Trie *triePtr, char *seq, int id, int *depthPtr)
{
void *data;
int ldepth;
data = NULL;
ldepth = *depthPtr;
if (triePtr->indexnode != NULL) {
Node *nodePtr;
/*
* We've reached a trie with an indexnode, which means that our
* data may be here. (If node is null that means that there
* is data at this branch, but not with this particular ID).
*/
nodePtr = Ns_IndexFind(triePtr->indexnode, (void *) id);
if (nodePtr != NULL) {
if ((*seq == '\0') && (nodePtr->dataNoInherit != NULL)) {
data = nodePtr->dataNoInherit;
} else {
data = nodePtr->dataInherit;
}
}
}
if (*seq != '\0') {
Branch *branchPtr;
/*
* We have not yet reached the end of the sequence, so
* recurse if there are any sub-branches
*/
branchPtr = Ns_IndexFind(&triePtr->branches, seq);
ldepth += 1;
if (branchPtr != NULL) {
void *p = TrieFind(&branchPtr->node, seq + strlen(seq) + 1, id,
&ldepth);
if (p != NULL) {
data = p;
*depthPtr = ldepth;
}
}
}
return data;
}
/*
*----------------------------------------------------------------------
*
* TrieFindExact --
*
* Similar to TrieFind, but will not do inheritance.
* if (flags & NS_OP_NOINHERIT) then data set with
* that flag will be returned; otherwise only data set without that
* flag will be returned.
*
* Results:
* See TrieFind.
*
* Side effects:
* None.
*
*----------------------------------------------------------------------
*/
static void *
TrieFindExact(Trie *triePtr, char *seq, int id, int flags)
{
void *data;
data = NULL;
if (*seq != '\0') {
Branch *branchPtr;
/*
* We have not reached the end of the sequence yet, so
* we must recurse.
*/
branchPtr = Ns_IndexFind(&triePtr->branches, seq);
if (branchPtr != NULL) {
data = TrieFindExact(&branchPtr->node, seq + strlen(seq) + 1, id,
flags);
}
} else if (triePtr->indexnode != NULL) {
Node *nodePtr;
/*
* We reached the end of the sequence. Grab the data from
* this node. If the flag specifies NOINHERIT, then return
* the non-inheriting data, otherwise return the inheriting
* data.
*/
nodePtr = Ns_IndexFind(triePtr->indexnode, (void *) id);
if (nodePtr != NULL) {
if (flags & NS_OP_NOINHERIT) {
data = nodePtr->dataNoInherit;
} else {
data = nodePtr->dataInherit;
}
}
}
return data;
}
/*
*----------------------------------------------------------------------
*
* TrieDelete --
*
* Delete a url, defined by a sequence, from a trie.
*
* The NS_OP_NOINHERIT bit may be set in flags to use
* noninheriting data; NS_OP_NODELETE may be set to
* skip calling the delete function.
*
* Results:
* A pointer to the now-deleted data.
*
* Side effects:
* Data may be deleted.
*
*----------------------------------------------------------------------
*/
static void *
TrieDelete(Trie *triePtr, char *seq, int id, int flags)
{
void *data;
data = NULL;
if (*seq != '\0') {
Branch *branchPtr;
/*
* We have not yet reached the end of the sequence. So
* recurse.
*/
branchPtr = Ns_IndexFind(&triePtr->branches, seq);
if (branchPtr != NULL) {
data = TrieDelete(&branchPtr->node, seq + strlen(seq) + 1, id,
flags);
}
} else if (triePtr->indexnode != NULL) {
Node *nodePtr;
/*
* We've reached the end of the sequence; if a node exists for
* this ID then delete the inheriting/noninheriting data (as
* specified in flags) and call the delte func if requested.
* The data will be set to null either way.
*/
nodePtr = Ns_IndexFind(triePtr->indexnode, (void *) id);
if (nodePtr != NULL) {
if (flags & NS_OP_NOINHERIT) {
data = nodePtr->dataNoInherit;
nodePtr->dataNoInherit = NULL;
if (nodePtr->deletefuncNoInherit != NULL) {
if (!(flags & NS_OP_NODELETE)) {
(*nodePtr->deletefuncNoInherit) (data);
}
nodePtr->deletefuncNoInherit = NULL;
}
} else {
data = nodePtr->dataInherit;
nodePtr->dataInherit = NULL;
if (nodePtr->deletefuncInherit != NULL) {
if (!(flags & NS_OP_NODELETE)) {
(*nodePtr->deletefuncInherit) (data);
}
nodePtr->deletefuncInherit = NULL;
}
}
}
}
return data;
}
#ifndef __URLSPACE_OPTIMIZE__
/*
*----------------------------------------------------------------------
*
* CmpChannels --
*
* Compare the filters of two channels.
*
* Results:
* 0: Not the case that one contains the other OR they both
* contain each other; 1: left contains right; -1: right contans
* left.
*
* Side effects:
* None.
*
*----------------------------------------------------------------------
*/
static int
CmpChannels(Channel **leftPtrPtr, Channel **rightPtrPtr)
{
int lcontainsr, rcontainsl;
lcontainsr = Tcl_StringMatch((*rightPtrPtr)->filter,
(*leftPtrPtr)->filter);
rcontainsl = Tcl_StringMatch((*leftPtrPtr)->filter,
(*rightPtrPtr)->filter);
if (lcontainsr && rcontainsl) {
return 0;
} else if (lcontainsr) {
return 1;
} else if (rcontainsl) {
return -1;
} else {
return 0;
}
}
/*
*----------------------------------------------------------------------
*
* CmpKeyWithChannel --
*
* Compare a key to a channel's filter
*
* Results:
* 0: Not the case that one contains the other OR they both
* contain each other; 1: key contains filter; -1: filter
* contains key
*
* Side effects:
* None
*
*----------------------------------------------------------------------
*/
static int
CmpKeyWithChannel(char *key, Channel **channelPtrPtr)
{
int lcontainsr, rcontainsl;
lcontainsr = Tcl_StringMatch((*channelPtrPtr)->filter, key);
rcontainsl = Tcl_StringMatch(key, (*channelPtrPtr)->filter);
if (lcontainsr && rcontainsl) {
return 0;
} else if (lcontainsr) {
return 1;
} else if (rcontainsl) {
return -1;
} else {
/*
* Neither is the case
*/
return 0;
}
}
#endif
/*
*----------------------------------------------------------------------
*
* CmpChannelsAsStrings --
*
* Compare the filters of two channels.
*
* Results:
* Same as strcmp.
*
* Side effects:
* None.
*
*----------------------------------------------------------------------
*/
static int
CmpChannelsAsStrings(Channel **leftPtrPtr, Channel **rightPtrPtr)
{
return strcmp((*leftPtrPtr)->filter, (*rightPtrPtr)->filter);
}
/*
*----------------------------------------------------------------------
*
* CmpKeyWithChannelAsStrings --
*
* Compare a string key to a channel's filter
*
* Results:
* Same as strcmp.
*
* Side effects:
* None.
*
*----------------------------------------------------------------------
*/
static int
CmpKeyWithChannelAsStrings(char *key, Channel **channelPtrPtr)
{
return strcmp(key, (*channelPtrPtr)->filter);
}
/*
*----------------------------------------------------------------------
*
* JunctionInit --
*
* Initialize a junction.
*
* Results:
* None.
*
* Side effects:
* Will set up the index in a junction.
*
*----------------------------------------------------------------------
*/
static void
JunctionInit(Junction *juncPtr)
{
#ifndef __URLSPACE_OPTIMIZE__
Ns_IndexInit(&juncPtr->byuse, 5,
(int (*) (const void *, const void *)) CmpChannels,
(int (*) (const void *, const void *)) CmpKeyWithChannel);
#endif
Ns_IndexInit(&juncPtr->byname, 5,
(int (*) (const void *, const void *)) CmpChannelsAsStrings,
(int (*) (const void *, const void *)) CmpKeyWithChannelAsStrings);
}
/*
*----------------------------------------------------------------------
*
* JunctionBranchTrunc --
*
* Truncate a branch, defined by a sequence and ID, in a
* junction
*
* Results:
* None.
*
* Side effects:
* See TrieBranchTrunc
*
*----------------------------------------------------------------------
*/
static void
JunctionBranchTrunc(Junction *juncPtr, char *seq, int id)
{
int i;
int n;
/*
* Loop over every channel in a junction and truncate the sequence in
* each.
*/
#ifndef __URLSPACE_OPTIMIZE__
n = Ns_IndexCount(&juncPtr->byuse);
for (i = 0; i < n; i++) {
Channel *channelPtr = Ns_IndexEl(&juncPtr->byuse, i);
TrieBranchTrunc(&channelPtr->trie, seq, id);
}
#else
n = Ns_IndexCount(&juncPtr->byname);
for (i = (n - 1); i >= 0; i--) {
Channel *channelPtr = Ns_IndexEl(&juncPtr->byname, i);
TrieBranchTrunc(&channelPtr->trie, seq, id);
}
#endif
}
/*
*----------------------------------------------------------------------
*
* JunctionAdd --
*
* This function is called from Ns_UrlSpecificSet which is
* usually called from Ns_RegisterRequest,
* Ns_RegisterProxyRequest, InitAliases for mapping aliases, and
* the nsperm functions TribeAlloc and Ns_AddPermission for
* adding permissions. It adds a sequence, terminating in a new
* node, to a junction.
*
* Flags may be a bit-combination of NS_OP_NOINHERIT, NS_OP_NODELETE.
* NOINHERIT sets the data as noninheriting, so only an exact sequence
* will match in the future; NODELETE means that if a node already
* exists with this sequence/ID it will not be deleted but replaced.
*
* Results:
* None.
*
* Side effects:
* Modifies seq, assuming
* seq = "handle\0method\0urltoken\0urltoken\0..\0\0\"
*
*----------------------------------------------------------------------
*/
static void
JunctionAdd(Junction *juncPtr, char *seq, int id, void *data, int flags,
void (*deletefunc) (void *))
{
Channel *channelPtr;
Ns_DString dsWord;
char *p;
int l;
int depth;
depth = 0;
/*
* Find out how deep the sequence is, and position p at the
* beginning of the last word in the sequence.
*/
for (p = seq; p[l = strlen(p) + 1] != '\0'; p += l) {
depth++;
}
Ns_DStringInit(&dsWord);
/*
* If it's a valid sequence that has a wildcard in its last element,
* append the whole string to dsWord, then cut off the last word from
* p.
* Otherwise, set dsWord to "*" because there is an implicit * wildcard
* at the end of URLs like /foo/bar
*
* dsWord will eventually be used to set or find&reuse a channel filter.
*/
if ((p != NULL) && (depth > 1) && (strchr(p, '*') || strchr(p, '?'))) {
Ns_DStringAppend(&dsWord, p);
*p = '\0';
} else {
Ns_DStringAppend(&dsWord, "*");
}
/*
* Find a channel whose filter matches what the filter on this URL
* should be.
*/
channelPtr = Ns_IndexFind(&juncPtr->byname, dsWord.string);
/*
* If no channel is found, create a new channel and add it to the
* list of channels in the junction.
*/
if (channelPtr == NULL) {
channelPtr = (Channel *) ns_malloc(sizeof(Channel));
channelPtr->filter = ns_strdup(dsWord.string);
TrieInit(&channelPtr->trie);
#ifndef __URLSPACE_OPTIMIZE__
Ns_IndexAdd(&juncPtr->byuse, channelPtr);
#endif
Ns_IndexAdd(&juncPtr->byname, channelPtr);
}
/*
* Now we need to create a sequence of branches in the trie (if no
* appropriate sequence already exists) and a node at the end of it.
* TrieAdd will do that.
*/
TrieAdd(&channelPtr->trie, seq, id, data, flags, deletefunc);
Ns_DStringFree(&dsWord);
}
/*
*----------------------------------------------------------------------
*
* JunctionFind --
*
* Locate a node for a given sequence in a junction.
* As usual sequence is "handle\0method\0urltoken\0...\0\0".
*
* The "fast" boolean switch makes it do strcmp instead of
* Tcl string matches on the filters. Not useful for wildcard
* matching.
*
* Results:
* User data
*
* Side effects:
* None.
*
*----------------------------------------------------------------------
*/
static void *
JunctionFind(Junction *juncPtr, char *seq, int id, int fast)
{
char *p;
int l;
int i, n;
void *data;
int depth;
n = 0;
/*
* After this loop, p will point at the last element in the sequence.
* n will be the number of elements in the sequence.
*/
for (p = seq; p[l = strlen(p) + 1] != '\0'; p += l) {
n++;
}
if (n < 2) {
/*
* If there are fewer than 2 elements then advance p to the
* end of the string.
*/
p += strlen(p) + 1;
}
/*
* Check filters from most restrictive to least restrictive
*/
data = NULL;
#ifndef __URLSPACE_OPTIMIZE__
l = Ns_IndexCount(&juncPtr->byuse);
#else
l = Ns_IndexCount(&juncPtr->byname);
#endif
#ifdef DEBUG
if (n >= 2) {
fprintf(stderr, "Checking Id=%d, Seq=", id);
PrintSeq(seq);
fputs("\n", stderr);
}
#endif
/*
* For __URLSPACE_OPTIMIZE__
* Basically if we use the optimize, let's reverse the order
* by which we search because the byname is in "almost" exact
* reverse lexicographical order.
*
* Loop over all the channels in the index.
*/
#ifndef __URLSPACE_OPTIMIZE__
for (i = 0; i < l; i++) {
Channel *channelPtr = Ns_IndexEl(&juncPtr->byuse, i);
#else
for (i = (l - 1); i >= 0; i--) {
Channel *channelPtr = Ns_IndexEl(&juncPtr->byname, i);
#endif
int doit;
if (fast) {
doit = !strcmp(p, channelPtr->filter);
} else {
doit = Tcl_StringMatch(p, channelPtr->filter);
}
if (doit) {
/*
* We got here because this url matches the filter
* (for example, it's *.adp).
*/
if (data == NULL) {
/*
* Nothing has been found so far. Traverse the channel
* and find the node; set data to that. Depth will be
* set to the level of the node.
*/
depth = 0;
data = TrieFind(&channelPtr->trie, seq, id, &depth);
} else {
void *candidate;
int cdepth;
/*
* Let's see if this channel has a node that also matches
* the sequence but is more specific (has a greater depth)
* that the previously found node.
*/
cdepth = 0;
candidate = TrieFind(&channelPtr->trie, seq, id, &cdepth);
if ((candidate != NULL) && (cdepth > depth)) {
data = candidate;
depth = cdepth;
}
}
}
#ifdef DEBUG
if (n >= 2) {
if (data == NULL) {
fprintf(stderr, "Channel %s: No match\n",
channelPtr->filter);
} else {
fprintf(stderr, "Channel %s: depth=%d, data=%p\n",
channelPtr->filter, depth, data);
}
}
#endif
}
#ifdef DEBUG
if (n >= 2) {
fprintf(stderr, "Done.\n");
}
#endif
return data;
}
/*
*----------------------------------------------------------------------
*
* JunctionFindExact --
*
* Find a node in a junction that exactly matches a sequence.
*
* Results:
* User data.
*
* Side effects:
* None.
*
*----------------------------------------------------------------------
*/
static void *
JunctionFindExact(Junction *juncPtr, char *seq, int id, int flags, int fast)
{
char *p;
int l;
int i;
int depth;
void *data;
depth = 0;
/*
* Set p to the last element of the sequence, and
* depth to the number of elements in the sequence.
*/
for (p = seq; p[l = strlen(p) + 1] != '\0'; p += l) {
depth++;
}
data = NULL;
/*
* First, loop through all the channels that have non-"*"
* filters looking for an exact match
*/
#ifndef __URLSPACE_OPTIMIZE__
l = Ns_IndexCount(&juncPtr->byuse);
for (i = 0; i < l; i++) {
Channel *channelPtr = Ns_IndexEl(&juncPtr->byuse, i);
#else
l = Ns_IndexCount(&juncPtr->byname);
for (i = (l - 1); i >= 0; i--) {
Channel *channelPtr = Ns_IndexEl(&juncPtr->byname, i);
#endif
if (strcmp(p, channelPtr->filter) == 0) {
/*
* The last element of the sequence exactly matches the
* filter, so this is the one. Wipe out the last word and
* return whatever node coems out of TrieFindExact.
*/
*p = '\0';
data = TrieFindExact(&channelPtr->trie, seq, id, flags);
goto done;
}
}
/*
* Now go to the channel with the "*" filter and look there for
* an exact match:
*/
#ifndef __URLSPACE_OPTIMIZE__
for (i = 0; i < l; i++) {
Channel *channelPtr = Ns_IndexEl(&juncPtr->byuse, i);
#else
for (i = (l - 1); i >= 0; i--) {
Channel *channelPtr = Ns_IndexEl(&juncPtr->byname, i);
#endif
if (strcmp("*", channelPtr->filter) == 0) {
data = TrieFindExact(&channelPtr->trie, seq, id, flags);
break;
}
}
done:
return data;
}
/*
*----------------------------------------------------------------------
*
* JunctionDelete --
*
* Delete a node from a junction matching a sequence
*
* Results:
* A pointer to the deleted node
*
* Side effects:
* The node will be deleted if NS_OP_NODELETE isn't set in flags
*
*----------------------------------------------------------------------
*/
static void *
JunctionDelete(Junction *juncPtr, char *seq, int id, int flags)
{
char *p;
int l;
int i;
int depth;
void *data;
/*
* Set p to the last element of the sequence, and
* depth to the number of elements in the sequence.
*/
depth = 0;
for (p = seq; p[l = strlen(p) + 1] != '\0'; p += l) {
depth++;
}
data = NULL;
#ifndef __URLSPACE_OPTIMIZE__
l = Ns_IndexCount(&juncPtr->byuse);
for (i = 0; (i < l) && (data == NULL); i++) {
Channel *channelPtr = Ns_IndexEl(&juncPtr->byuse, i);
#else
l = Ns_IndexCount(&juncPtr->byname);
for (i = (l - 1); (i >= 0) && (data == NULL); i--) {
Channel *channelPtr = Ns_IndexEl(&juncPtr->byname, i);
#endif
if ((depth == 2) && (strcmp(p, channelPtr->filter) == 0)) {
/*
* This filter exactly matches the last element of the
* sequence, so get the node and delete it. (This is
* server-specific data because depth is 2).
*/
*p = '\0';
data = TrieFindExact(&channelPtr->trie, seq, id, flags);
if (data != NULL) {
TrieDelete(&channelPtr->trie, seq, id, flags);
}
} else if (Tcl_StringMatch(p, channelPtr->filter)) {
/*
* The filter matches, so get the node and delete it.
*/
data = TrieFindExact(&channelPtr->trie, seq, id, flags);
if (data != NULL) {
TrieDelete(&channelPtr->trie, seq, id, flags);
}
}
}
return data;
}
/*
*----------------------------------------------------------------------
*
* MkSeq --
*
* Build a "sequence" out of a server/method/url; turns it into
* "server\0method\0urltoken\0...\0\0"
*
* Results:
* None
*
* Side effects:
* Sequence goes into ds
*
*----------------------------------------------------------------------
*/
static void
MkSeq(Ns_DString *dsPtr, char *server, char *method, char *url)
{
if ((method != NULL) && (url != NULL)) {
char *p;
int done;
/*
* It is URLspecific data, not serverspecific data
* if we get here.
*/
Ns_DStringNAppend(dsPtr, server, (int)(strlen(server) + 1));
Ns_DStringNAppend(dsPtr, method, (int)(strlen(method) + 1));
/*
* Loop over each directory in the URL and turn the slashes
* into nulls.
*/
done = 0;
while (!done && *url != '\0') {
if (*url != '/') {
int l;
p = strchr(url, '/');
if (p != NULL) {
l = p - url;
} else {
l = strlen(url);
done = 1;
}
Ns_DStringNAppend(dsPtr, url, l++);
Ns_DStringNAppend(dsPtr, "\0", 1);
url += l;
} else {
url++;
}
}
/*
* Put another null on the end to mark the end of the
* string.
*/
Ns_DStringNAppend(dsPtr, "\0", 1);
} else {
/*
* This is Server-specific data, so there's only going to
* be one element.
*/
Ns_DStringNAppend(dsPtr, server, (int)(strlen(server) + 1));
Ns_DStringNAppend(dsPtr, "\0", 1);
}
}
#ifdef DEBUG
/*
*----------------------------------------------------------------------
*
* indentspace --
*
* Print n spaces.
*
* Results:
* None.
*
* Side effects:
* Will print to stderr.
*
*----------------------------------------------------------------------
*/
static void
indentspace(int n)
{
int i;
fputc('\n', stderr);
for (i = 0; i < n; i++) {
fputc(' ', stderr);
}
}
/*
*----------------------------------------------------------------------
*
* PrintTrie --
*
* Output the trie to standard error.
*
* Results:
* None.
*
* Side effects:
* Will write to stderr.
*
*----------------------------------------------------------------------
*/
static void
PrintTrie(Trie *triePtr, int indent)
{
int i;
indentspace(indent);
fprintf(stderr, "Branches:");
for (i = 0; i < (&(triePtr->branches))->n; i++) {
Branch *branch;
branch = (Branch *) Ns_IndexEl(&(triePtr->branches), i);
indentspace(indent + 2);
fprintf(stderr, "(%s):", branch->word);
PrintTrie(&(branch->node), indent + 4);
}
indentspace(indent);
fprintf(stderr, "IndexNodes:");
if (triePtr->indexnode != NULL) {
for (i = 0; i < triePtr->indexnode->n; i++) {
Node *nodePtr;
nodePtr = (Node *) Ns_IndexEl(triePtr->indexnode, i);
indentspace(indent + 2);
if (nodePtr->dataInherit != NULL) {
fprintf(stderr, "(Id: %d, inherit): %p",
nodePtr->id, nodePtr->dataInherit);
}
if (nodePtr->dataNoInherit != NULL) {
fprintf(stderr, "(Id: %d, noinherit): %p",
nodePtr->id, nodePtr->dataNoInherit);
}
}
}
}
/*
*----------------------------------------------------------------------
*
* PrintJunction --
*
* Print a junction to std error.
*
* Results:
* None.
*
* Side effects:
* Will write to stderr.
*
*----------------------------------------------------------------------
*/
static void
PrintJunction(Junction *junctionPtr)
{
int i;
fprintf(stderr, "Junction:");
#ifndef __URLSPACE_OPTIMIZE__
for (i = 0; i < (&(junctionPtr->byuse))->n; i++) {
Channel *channelPtr;
channelPtr = (Channel *) Ns_IndexEl(&(junctionPtr->byuse), i);
#else
for (i = ((&(junctionPtr->byname))->n - 1); i >= 0; i--) {
Channel *channelPtr;
channelPtr = (Channel *) Ns_IndexEl(&(junctionPtr->byname), i);
#endif
fprintf(stderr, "\n Channel[%d]:\n", i);
fprintf(stderr, " Filter: %s\n", channelPtr->filter);
fprintf(stderr, " Trie:");
PrintTrie(&(channelPtr->trie), 4);
}
}
/*
*----------------------------------------------------------------------
*
* PrintSeq --
*
* Print a null-delimited sequence to stderr.
*
* Results:
* None.
*
* Side effects:
* Will write to stderr.
*
*----------------------------------------------------------------------
*/
static void
PrintSeq(char *seq)
{
char *p;
for (p = seq; *p != '\0'; p += strlen(p) + 1) {
if (p != seq) {
fputs(", ", stderr);
}
fputs(p, stderr);
}
}
#endif
|
Back to SourceForge.net Powered by ViewCVS 1.0-dev |