splay.h revision 5ab5018bf8f0e39957d264f33c3eeddd958ed5d8
15ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen#ifndef __SPLAY_H 25ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen#define __SPLAY_H 35ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen/*************************************************************************** 45ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen * _ _ ____ _ 55ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen * Project ___| | | | _ \| | 65ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen * / __| | | | |_) | | 75ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen * | (__| |_| | _ <| |___ 85ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen * \___|\___/|_| \_\_____| 95ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen * 105ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen * Copyright (C) 1997 - 2009, 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 145ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen * are also available at http://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 ***************************************************************************/ 245ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen 255ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsenstruct Curl_tree { 265ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen struct Curl_tree *smaller; /* smaller node */ 275ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen struct Curl_tree *larger; /* larger node */ 285ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen struct Curl_tree *same; /* points to a node with identical key */ 295ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen struct timeval key; /* this node's "sort" key */ 305ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen void *payload; /* data the splay code doesn't care about */ 315ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen}; 325ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen 335ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsenstruct Curl_tree *Curl_splay(struct timeval i, 345ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen struct Curl_tree *t); 355ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen 365ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsenstruct Curl_tree *Curl_splayinsert(struct timeval key, 375ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen struct Curl_tree *t, 385ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen struct Curl_tree *newnode); 395ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen 405ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen#if 0 415ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsenstruct Curl_tree *Curl_splayremove(struct timeval key, 425ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen struct Curl_tree *t, 435ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen struct Curl_tree **removed); 445ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen#endif 455ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen 465ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsenstruct Curl_tree *Curl_splaygetbest(struct timeval key, 475ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen struct Curl_tree *t, 485ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen struct Curl_tree **removed); 495ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen 505ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsenint Curl_splayremovebyaddr(struct Curl_tree *t, 515ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen struct Curl_tree *removenode, 525ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen struct Curl_tree **newroot); 535ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen 545ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen#define Curl_splaycomparekeys(i,j) ( ((i.tv_sec) < (j.tv_sec)) ? -1 : \ 555ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen ( ((i.tv_sec) > (j.tv_sec)) ? 1 : \ 565ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen ( ((i.tv_usec) < (j.tv_usec)) ? -1 : \ 575ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen ( ((i.tv_usec) > (j.tv_usec)) ? 1 : 0 )))) 585ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen 595ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen#ifdef DEBUGBUILD 605ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsenvoid Curl_splayprint(struct Curl_tree * t, int d, char output); 615ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen#else 625ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen#define Curl_splayprint(x,y,z) 635ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen#endif 645ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen 655ab5018bf8f0e39957d264f33c3eeddd958ed5d8Kristian Monsen#endif 66