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