1e6cd738ed3716c02557fb3a47515244e949ade39Bertrand SIMONNET#ifndef HEADER_CURL_SPLAY_H 2e6cd738ed3716c02557fb3a47515244e949ade39Bertrand SIMONNET#define HEADER_CURL_SPLAY_H 35ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen/*************************************************************************** 45ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen * _ _ ____ _ 55ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen * Project ___| | | | _ \| | 65ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen * / __| | | | |_) | | 75ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen * | (__| |_| | _ <| |___ 85ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen * \___|\___/|_| \_\_____| 95ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen * 1082be86df6ec7baa34d6169c053fd1dfe56fa858eElliott Hughes * Copyright (C) 1997 - 2017, Daniel Stenberg, <daniel@haxx.se>, et al. 115ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen * 125ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen * This software is licensed as described in the file COPYING, which 135ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen * you should have received as part of this distribution. The terms 148f1a214b8a21b66f33454790dfba97ae2f818289Alex Deymo * are also available at https://curl.haxx.se/docs/copyright.html. 155ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen * 165ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen * You may opt to use, copy, modify, merge, publish, distribute and/or sell 175ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen * copies of the Software, and permit persons to whom the Software is 185ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen * furnished to do so, under the terms of the COPYING file. 195ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen * 205ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY 215ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen * KIND, either express or implied. 225ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen * 235ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen ***************************************************************************/ 24e6cd738ed3716c02557fb3a47515244e949ade39Bertrand SIMONNET#include "curl_setup.h" 2582be86df6ec7baa34d6169c053fd1dfe56fa858eElliott Hughes#include "timeval.h" 265ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen 275ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsenstruct Curl_tree { 285ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen struct Curl_tree *smaller; /* smaller node */ 295ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen struct Curl_tree *larger; /* larger node */ 3082be86df6ec7baa34d6169c053fd1dfe56fa858eElliott Hughes struct Curl_tree *samen; /* points to the next node with identical key */ 3182be86df6ec7baa34d6169c053fd1dfe56fa858eElliott Hughes struct Curl_tree *samep; /* points to the prev node with identical key */ 3282be86df6ec7baa34d6169c053fd1dfe56fa858eElliott Hughes struct curltime key; /* this node's "sort" key */ 335ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen void *payload; /* data the splay code doesn't care about */ 345ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen}; 355ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen 3682be86df6ec7baa34d6169c053fd1dfe56fa858eElliott Hughesstruct Curl_tree *Curl_splay(struct curltime i, 375ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen struct Curl_tree *t); 385ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen 3982be86df6ec7baa34d6169c053fd1dfe56fa858eElliott Hughesstruct Curl_tree *Curl_splayinsert(struct curltime key, 405ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen struct Curl_tree *t, 415ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen struct Curl_tree *newnode); 425ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen 435ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen#if 0 4482be86df6ec7baa34d6169c053fd1dfe56fa858eElliott Hughesstruct Curl_tree *Curl_splayremove(struct curltime key, 455ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen struct Curl_tree *t, 465ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen struct Curl_tree **removed); 475ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen#endif 485ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen 4982be86df6ec7baa34d6169c053fd1dfe56fa858eElliott Hughesstruct Curl_tree *Curl_splaygetbest(struct curltime key, 505ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen struct Curl_tree *t, 515ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen struct Curl_tree **removed); 525ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen 535ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsenint Curl_splayremovebyaddr(struct Curl_tree *t, 545ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen struct Curl_tree *removenode, 555ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen struct Curl_tree **newroot); 565ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen 57486467e11b5904b3e04adc2f5fdb96fcfe65da84Alex Deymo#define Curl_splaycomparekeys(i,j) ( ((i.tv_sec) < (j.tv_sec)) ? -1 : \ 58486467e11b5904b3e04adc2f5fdb96fcfe65da84Alex Deymo ( ((i.tv_sec) > (j.tv_sec)) ? 1 : \ 595ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen ( ((i.tv_usec) < (j.tv_usec)) ? -1 : \ 608f1a214b8a21b66f33454790dfba97ae2f818289Alex Deymo ( ((i.tv_usec) > (j.tv_usec)) ? 1 : 0)))) 615ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen 625ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen#ifdef DEBUGBUILD 635ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsenvoid Curl_splayprint(struct Curl_tree * t, int d, char output); 645ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen#else 65e6cd738ed3716c02557fb3a47515244e949ade39Bertrand SIMONNET#define Curl_splayprint(x,y,z) Curl_nop_stmt 665ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen#endif 675ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen 68e6cd738ed3716c02557fb3a47515244e949ade39Bertrand SIMONNET#endif /* HEADER_CURL_SPLAY_H */ 69