Java Code Examples for org.eclipse.jetty.util.ArrayTernaryTrie

Following code examples demonstrate how to use org.eclipse.jetty.util.ArrayTernaryTrie from jetty. These examples are extracted from various highly rated open source projects. You can directly use these code snippets or view their entire linked source code. These snippets are extracted to provide contextual information about how to use this class in the real world. These samples also let you understand some good practices on how to use org.eclipse.jetty.util.ArrayTernaryTrie and various code implementation of this class.

    
    public boolean put(PathSpec pathSpec, E resource)
    {
        MappedResource<E> entry = new MappedResource<>(pathSpec,resource);
        switch (pathSpec.group)
        {
            case EXACT:
                String exact = pathSpec.getPrefix();
                while (exact!=null && !_exactMap.put(exact,entry))
                    _exactMap=new ArrayTernaryTrie<>((ArrayTernaryTrie<MappedResource<E>>)_exactMap,1.5);
                break;
            case PREFIX_GLOB:
                String prefix = pathSpec.getPrefix();
                while (prefix!=null && !_prefixMap.put(prefix,entry))
                    _prefixMap=new ArrayTernaryTrie<>((ArrayTernaryTrie<MappedResource<E>>)_prefixMap,1.5);
                break;
            case SUFFIX_GLOB:
                String suffix = pathSpec.getSuffix();
                while (suffix!=null && !_suffixMap.put(suffix,entry))
                    _suffixMap=new ArrayTernaryTrie<>((ArrayTernaryTrie<MappedResource<E>>)_prefixMap,1.5);
                break;
            default:
        }
        
        boolean added =_mappings.add(entry);
        if (LOG.isDebugEnabled())
            LOG.debug("{} {} to {}",added?"Added":"Ignored",entry,this);
        return added;
    } 


    
    public static void main(String[] args) throws Exception
    {
        System.err.printf("%d -> %d%n",Integer.MAX_VALUE,ArrayTernaryTrie.hilo(Integer.MAX_VALUE));
        System.err.printf("%d -> %d%n",55,ArrayTernaryTrie.hilo(55));
        System.err.printf("%d -> %d%n",54,ArrayTernaryTrie.hilo(54));
        System.err.printf("%d -> %d%n",1,ArrayTernaryTrie.hilo(1));
        System.err.printf("%d -> %d%n",0,ArrayTernaryTrie.hilo(0));
        System.err.printf("%d -> %d%n",-1,ArrayTernaryTrie.hilo(-1));
        System.err.printf("%d -> %d%n",-35,ArrayTernaryTrie.hilo(-35));
        System.err.printf("%d -> %d%n",-36,ArrayTernaryTrie.hilo(-36));
        System.err.printf("%d -> %d%n",Integer.MIN_VALUE,ArrayTernaryTrie.hilo(Integer.MIN_VALUE));
        
        
        StringLookupBenchmark bm = new StringLookupBenchmark();
        
        bm.test(10000000);
        bm.test(10000000);
        bm.test(10000000);
    } 

    public ContextRoutingHandler(Map<String, ? extends Handler> handlers) {
        this.handlers = new ArrayTernaryTrie<>(false);
        for (Map.Entry<String, ? extends Handler> entry : handlers.entrySet()) {
            if (!this.handlers.put(entry.getKey(), entry.getValue())) {
                throw new IllegalStateException("Too many handlers");
            }
            addBean(entry.getValue());
        }
    } 

    @ManagedOperation("update the mapping of context path to context")
    public void mapContexts()
    {
        _contextBranches.clear();
        
        if (getHandlers()==null)
        {
            _pathBranches=new ArrayTernaryTrie<>(false,16);
            return;
        }
        
        Map<String,Branch[]> map = new HashMap<>();
        for (Handler handler:getHandlers())
        {
            Branch branch=new Branch(handler);
            for (String contextPath : branch.getContextPaths())
            {
                Branch[] branches=map.get(contextPath);
                map.put(contextPath, ArrayUtil.addToArray(branches, branch, Branch.class));
            }
            
            for (ContextHandler context : branch.getContextHandlers())
                _contextBranches.putIfAbsent(context, branch.getHandler());
        }
        
        for (Map.Entry<String,Branch[]> entry: map.entrySet())
        {
            Branch[] branches=entry.getValue();
            Branch[] sorted=new Branch[branches.length];
            int i=0;
            for (Branch branch:branches)
                if (branch.hasVirtualHost())
                    sorted[i++]=branch;
            for (Branch branch:branches)
                if (!branch.hasVirtualHost())
                    sorted[i++]=branch;
            entry.setValue(sorted);
        }
        
        int capacity=512;
        Trie<Map.Entry<String,Branch[]>> trie;
        loop: while(true)
        {
            trie=new ArrayTernaryTrie<>(false,capacity);
            for (Map.Entry<String,Branch[]> entry: map.entrySet())
            {
                if (!trie.put(entry.getKey().substring(1),entry))
                {
                    capacity+=512;
                    continue loop;
                }
            }
            break loop;
        }
            
        
        if (LOG.isDebugEnabled())
        {
            for (String ctx : trie.keySet())
                LOG.debug("{}->{}",ctx,Arrays.asList(trie.get(ctx).getValue()));
        }
        _pathBranches=trie;
    } 

    @Override
    public void clear()
    {
        _exactMap.clear();
        _prefixMap=new ArrayTernaryTrie<>(false);
        _suffixMap=new ArrayTernaryTrie<>(false);
        _default=null;
        _defaultSingletonList=null;
        _prefixDefault=null;
        super.clear();
    } 

    
    public static void setPathSpecSeparators(String s)
    {
        __pathSpecSeparators=s;
    } 

    public void mapContexts() {

        _contextBranches.clear();

        if (getHandlers()==null)
        {
            _pathBranches=new ArrayTernaryTrie<>(false,16);
            return;
        }

        Map<String, ScopedContextHandlerCollection.Branch[]> map = new HashMap<>();
        for (Handler handler:getHandlers())
        {
            ScopedContextHandlerCollection.Branch branch=new ScopedContextHandlerCollection.Branch(handler);
            for (String contextPath : branch.getContextPaths())
            {
                ScopedContextHandlerCollection.Branch[] branches=map.get(contextPath);
                map.put(contextPath, ArrayUtil.addToArray(branches, branch, ScopedContextHandlerCollection.Branch.class));
            }

            for (ContextHandler context : branch.getContextHandlers())
                _contextBranches.putIfAbsent(context, branch.getHandler());
        }

        for (Map.Entry<String, ScopedContextHandlerCollection.Branch[]> entry: map.entrySet())
        {
            ScopedContextHandlerCollection.Branch[] branches=entry.getValue();
            ScopedContextHandlerCollection.Branch[] sorted=new ScopedContextHandlerCollection.Branch[branches.length];
            int i=0;
            for (ScopedContextHandlerCollection.Branch branch:branches)
                if (branch.hasVirtualHost())
                    sorted[i++]=branch;
            for (ScopedContextHandlerCollection.Branch branch:branches)
                if (!branch.hasVirtualHost())
                    sorted[i++]=branch;
            entry.setValue(sorted);
        }

        int capacity=512;
        Trie<Map.Entry<String, ScopedContextHandlerCollection.Branch[]>> trie;
        loop: while(true)
        {
            trie=new ArrayTernaryTrie<>(false,capacity);
            for (Map.Entry<String, ScopedContextHandlerCollection.Branch[]> entry: map.entrySet())
            {
                if (!trie.put(entry.getKey().substring(1),entry))
                {
                    capacity+=512;
                    continue loop;
                }
            }
            break loop;
        }


        if (LOG.isDebugEnabled())
        {
            for (String ctx : trie.keySet())
                LOG.debug("{}->{}",ctx, Arrays.asList(trie.get(ctx).getValue()));
        }
        _pathBranches=trie;
    } 

    
    public static HttpMethod lookAheadGet(ByteBuffer buffer)
    {
        if (buffer.hasArray())
            return lookAheadGet(buffer.array(),buffer.arrayOffset()+buffer.position(),buffer.arrayOffset()+buffer.limit());
        
        int l = buffer.remaining();
        if (l>=4)
        {
            HttpMethod m = CACHE.getBest(buffer,0,l);
            if (m!=null)
            {
                int ml = m.asString().length();
                if (l>ml && buffer.get(buffer.position()+ml)==' ')
                    return m;
            }
        }
        return null;
    } 

        }

        public String getModule()
        {
            return _module;
        } 

        @Override
        public boolean test(URI uri)
        {
            if (!uri.getScheme().equals("file"))
                return false;
            Path path = Paths.get(uri);

            for (Entry entry : this)
            {
                if (!(entry instanceof LocationEntry))
                    throw new IllegalStateException();

                File file = ((LocationEntry)entry).getFile();

                if (file.isDirectory())
                {
                    if (path.startsWith(file.toPath()))
                    {
                        return true;
                    }
                } else
                {
                    if (path.equals(file.toPath()))
                    {
                        return true;
                    }
                }
            }
            return false;
        } 

    
    public static String valueParameters(String value, Map<String,String> parameters)
    {
        if (value == null) return null;

        int i = value.indexOf(';');
        if (i < 0) return value;
        if (parameters == null) return value.substring(0, i).trim();

        StringTokenizer tok1 = new QuotedStringTokenizer(value.substring(i), ";", false, true);
        while (tok1.hasMoreTokens())
        {
            String token = tok1.nextToken();
            StringTokenizer tok2 = new QuotedStringTokenizer(token, "= ");
            if (tok2.hasMoreTokens())
            {
                String paramName = tok2.nextToken();
                String paramVal = null;
                if (tok2.hasMoreTokens()) paramVal = tok2.nextToken();
                parameters.put(paramName, paramVal);
            }
        }

        return value.substring(0, i).trim();
    } 

		private static HttpCompliance compliance() {
			final Boolean strict = Boolean.getBoolean(__STRICT);
			return strict ? HttpCompliance.LEGACY : HttpCompliance.RFC7230;
		} 

                case SPACE2:
                    if (ch > HttpTokens.SPACE)
                    {
                        _string.setLength(0);
                        _string.append((char)ch);
                        if (_responseHandler!=null)
                        {
                            _length=1;
                            setState(State.REASON);
                        }
                        else
                        {
                            setState(State.REQUEST_VERSION);

                            HttpVersion version;
                            if (buffer.position()>0 && buffer.hasArray())
                                version=HttpVersion.lookAheadGet(buffer.array(),buffer.arrayOffset()+buffer.position()-1,buffer.arrayOffset()+buffer.limit());
                            else
                                version=HttpVersion.CACHE.getBest(buffer,0,buffer.remaining());
                            if (version==null)
                            {
                                if (_method==HttpMethod.PROXY)
                                {
                                    if (!(_requestHandler instanceof ProxyHandler))
                                        throw new BadMessageException();
                                    
                                    String protocol=_uri.toString();
                                    buffer.position(buffer.position()-1);
                                    String sAddr = getProxyField(buffer);
                                    String dAddr = getProxyField(buffer);
                                    int sPort = BufferUtil.takeInt(buffer);
                                    next(buffer);
                                    int dPort = BufferUtil.takeInt(buffer);
                                    next(buffer);
                                    _state=State.START;
                                    ((ProxyHandler)_requestHandler).proxied(protocol,sAddr,dAddr,sPort,dPort);
                                    return false;
                                }
                            }
                            else
                            {
                                int pos = buffer.position()+version.asString().length()-1;
                                if (pos<buffer.limit())
                                {
                                    byte n=buffer.get(pos);
                                    if (n==HttpTokens.CARRIAGE_RETURN)
                                    {
                                        _cr=true;
                                        _version=version;
                                        _string.setLength(0);
                                        buffer.position(pos+1);
                                    }
                                    else if (n==HttpTokens.LINE_FEED)
                                    {
                                        _version=version;
                                        _string.setLength(0);
                                        buffer.position(pos);
                                    }
                                }
                            }
                        }
                    } 

Advertisement
Javadoc


A Ternary Trie String lookup data structure.

This Trie is of a fixed size and

cannot grow (which can be a good thing with regards to DOS when used as a cache).

The Trie is stored in 3 arrays: char[] _tree This is semantically 2 dimensional array flattened into a 1 dimensional char array. The second dimension is that every 4 sequential elements represents a row of: character; hi index; eq index; low index, used to build a ternary trie of key strings. String[] _key An array of key values where each element matches a row in the _tree array. A non zero key element indicates that the _tree row is a complete key rather than an intermediate character of a longer key. V[] _value An array of values corresponding to the _key array

The lookup of a value will iterate through the _tree array matching characters. If the equal tree branch is followed, then the _key array is looked up to see if this is a complete match. If a match is found then the _value array is looked up to return the matching value.

This Trie may be instantiated either as case sensitive or insensitive.

This Trie is not Threadsafe and contains no mutual exclusion or deliberate memory barriers. It is intended for an ArrayTrie to be built by a single thread and then used concurrently by multiple threads and not mutated during that access. If concurrent mutations of the Trie is required external locks need to be applied. @param the Entry type

Read More
Advertisement