rs-rasp.c revision 3f54fd611f536639ec30dd53c48e5ec1897cc7d9
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann/***********************************************************************
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann* *
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann* This software is part of the ast package *
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann* Copyright (c) 1996-2011 AT&T Intellectual Property *
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann* and is licensed under the *
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann* Eclipse Public License, Version 1.0 *
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann* by AT&T Intellectual Property *
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann* *
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann* A copy of the License is available at *
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann* http://www.eclipse.org/org/documents/epl-v10.html *
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann* (with md5 checksum b35adb5213ca9657e911e9befb180842) *
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann* *
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann* Information and Software Systems Research *
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann* AT&T Research *
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann* Florham Park NJ *
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann* *
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann* Phong Vo <kpv@research.att.com> *
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann* Glenn Fowler <gsf@research.att.com> *
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann* *
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann***********************************************************************/
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann/* Radix + splay tree
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann** Strategy:
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann** 1. Records are partitioned by first bytes.
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann** 2. Short records are sorted by a radix sort.
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann** 3. Long records are sorted in splay trees.
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann** 4. A final merge phase put things back together.
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann**
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann** Written by Kiem-Phong Vo (07/08/96).
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann*/
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann#include "rshdr.h"
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann#define SLOT SIZEOF_LONG
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann#define PREFIX (SLOT + 1)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmanntypedef struct rsrasp_s
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann{ Rsobj_t* empty;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann Rsobj_t* slot[SLOT][UCHAR_MAX+1];
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann Rsobj_t* tree[UCHAR_MAX+1];
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann} Rsrasp_t;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann#define SPLAYCMP(one,two,o,t,endo,mp,cr) \
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { if(one->order != two->order) \
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann cr = one->order < two->order ? -1 : 1; \
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann else \
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { if((mp = (cr = one->keylen) - two->keylen) > 0) cr -= mp; \
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann o = one->key+PREFIX; t = two->key+PREFIX; \
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann for(endo = one->key+cr;; ) \
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { if(o >= endo) { cr = mp; break; } \
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann else if((cr = (int)*o++ - (int)*t++)) break; \
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann } \
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann } \
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann#if __STD_C
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmannstatic int raspinsert(Rs_t* rs, reg Rsobj_t* obj)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann#else
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmannstatic int raspinsert(rs, obj)
2450a4210dee64b064499a3a1154129bdfc74981Daniel HausmannRs_t* rs;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmannreg Rsobj_t* obj;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann#endif
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann{
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann reg ssize_t cr, mp;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann reg uchar *o, *k;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann reg Rsobj_t *r, *root, *t, *l;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann reg uchar* endo;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann reg int index;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann Rsobj_t link;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann reg Rsrasp_t* rasp = (Rsrasp_t*)rs->methdata;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann obj->equal = NIL(Rsobj_t*);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann if((cr = obj->keylen) == 0)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { if((r = rasp->empty) )
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { EQUAL(r,obj,t); }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann else rasp->empty = obj;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann return 0;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann index = *(k = obj->key);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann if(cr == 1)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { if((r = rasp->slot[0][index]) )
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { EQUAL(r,obj,t); }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann else rasp->slot[0][index] = obj;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann return 0;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann else if((cr -= 1) < SLOT)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { if((r = rasp->slot[cr][index]) )
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann r->left->right = obj;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann else r = rasp->slot[cr][index] = obj;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann r->left = obj;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann return 0;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann#if SIZEOF_LONG == 8
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann obj->order = (((ulong)k[1]) << (CHAR_BIT*7)) |
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann (((ulong)k[2]) << (CHAR_BIT*6)) |
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann (((ulong)k[3]) << (CHAR_BIT*5)) |
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann (((ulong)k[4]) << (CHAR_BIT*4)) |
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann (((ulong)k[5]) << (CHAR_BIT*3)) |
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann (((ulong)k[6]) << (CHAR_BIT*2)) |
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann (((ulong)k[7]) << (CHAR_BIT*1)) |
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann (((ulong)k[8]) << (CHAR_BIT*0)) ;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann#else /* sizeof(long) == 4 */
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann obj->order = (k[1] << (CHAR_BIT*3)) | (k[2] << (CHAR_BIT*2)) |
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann (k[3] << (CHAR_BIT*1)) | (k[4] << (CHAR_BIT*0)) ;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann#endif
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann if(!(root = rasp->tree[index]))
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { rasp->tree[index] = obj;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann obj->left = obj->right = NIL(Rsobj_t*);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann return 0;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann SPLAYCMP(obj,root,o,k,endo,mp,cr);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann if(cr == 0)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { EQUAL(root,obj,t);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann return 0;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann for(l = r = &link;; )
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { if(cr < 0)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { if((t = root->left))
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { SPLAYCMP(obj,t,o,k,endo,mp,cr);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann if(cr < 0)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { RROTATE(root,t);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann RLINK(r,root);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann if(!(root = root->left))
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann goto no_root;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann else if(cr == 0)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { RROTATE(root,t);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann goto has_root;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann else
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { LLINK(l,t);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann RLINK(r,root);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann if(!(root = t->right))
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann goto no_root;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann else
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { RLINK(r,root);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann goto no_root;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann else /*if(cr > 0)*/
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { if((t = root->right))
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { SPLAYCMP(obj,t,o,k,endo,mp,cr);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann if(cr > 0)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { LROTATE(root,t);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann LLINK(l,root);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann if(!(root = root->right))
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann goto no_root;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann else if(cr == 0)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { LROTATE(root,t);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann goto has_root;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann else
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { RLINK(r,t);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann LLINK(l,root);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann if(!(root = t->left))
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann goto no_root;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann else
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { LLINK(l,root);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann goto no_root;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann SPLAYCMP(obj,root,o,k,endo,mp,cr);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann if(cr == 0)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann goto has_root;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann has_root:
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann EQUAL(root,obj,t);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann l->right = root->left;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann r->left = root->right;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann root->left = link.right;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann root->right = link.left;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann rasp->tree[index] = root;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann return 0;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann no_root:
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann l->right = NIL(Rsobj_t*);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann r->left = NIL(Rsobj_t*);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann obj->left = link.right;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann obj->right = link.left;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann rasp->tree[index] = obj;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann return 0;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann}
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann#if __STD_C
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmannstatic Rsobj_t* radix(Rsobj_t* list)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann#else
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmannstatic Rsobj_t* radix(list)
2450a4210dee64b064499a3a1154129bdfc74981Daniel HausmannRsobj_t* list;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann#endif
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann{
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann reg Rsobj_t *work, *r;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann reg ssize_t ph;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann reg Rsobj_t **bin, *t, *endl, *next, **lo, **maxpart;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann reg ssize_t n, maxph;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann Rsobj_t *part[UCHAR_MAX+1];
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann for(lo = part, maxpart = part + UCHAR_MAX+1; lo < maxpart; ++lo)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann *lo = NIL(Rsobj_t*);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann work = list; list = NIL(Rsobj_t*);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann work->left->right = NIL(Rsobj_t*);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann maxph = work->keylen-1;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann for(work->order = 1; work; )
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { next = work->left->right; work->left->right = NIL(Rsobj_t*);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann lo = maxpart; n = 0;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann if((ph = (ssize_t)work->order) == maxph)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { for(; work; work = work->right)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { bin = part + work->key[ph];
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann if(!(r = *bin) )
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { *bin = work;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann if(lo > bin)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann lo = bin;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann n += 1;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann else EQUAL(r,work,t);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann if(list)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann endl = (endl->right = *lo);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann else endl = (list = *lo);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann *lo = NIL(Rsobj_t*);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann for(bin = lo+1, n -= 1; n > 0; ++bin)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { if((r = *bin) )
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { n -= 1;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann endl = (endl->right = r);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann *bin = NIL(Rsobj_t*);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann work = next;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann else
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { for(; work; work = work->right)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { bin = part + work->key[ph];
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann if((r = *bin) )
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann r->left->right = work;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann else
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { r = *bin = work;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann if(lo > bin)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann lo = bin;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann n += 1;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann r->left = work;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann ph += 1;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann work = *lo; t = work->left; *lo = NIL(Rsobj_t*);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann work->order = ph;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann for(bin = lo+1, n -= 1; n > 0; ++bin)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { if((r = *bin) )
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { n -= 1;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann r->order = ph;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann t->right = r;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann t = r->left;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann *bin = NIL(Rsobj_t*);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann t->right = next;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann if(work && work->left == work)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { if(list)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann endl = (endl->right = work);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann else endl = (list = work);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann for(work = work->right; work; work = work->right)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { if(work->left != work)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann break;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann endl = (endl->right = work);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann list->left = endl;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann return list;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann}
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann#define CHARCMP(k1,k2,v,i) (v = (int)k1[i] - (int)k2[i])
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann#define STRNCMP(k1,k2,v,i,n) \
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { if(CHARCMP(k1,k2,v,1) == 0) \
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { for(i = 2; i <= n; ++i) \
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann if(CHARCMP(k1,k2,v,i) != 0) \
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann break; \
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann } \
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann#if __STD_C
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmannstatic Rsobj_t* listmerge(reg Rsobj_t* one, reg Rsobj_t* two, reg int n)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann#else
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmannstatic Rsobj_t* listmerge(one, two, n)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmannreg Rsobj_t* one;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmannreg Rsobj_t* two;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmannreg int n; /* number of bytes to compare */
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann#endif
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann{
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann reg int v, i;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann reg uchar *k1, *k2;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann reg Rsobj_t *list, *endl, *endone, *endtwo;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann endone = one->left; one->left->right = NIL(Rsobj_t*);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann endtwo = two->left; two->left->right = NIL(Rsobj_t*);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann k1 = one->key; k2 = two->key;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann STRNCMP(k1,k2,v,i,n);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann if(v <= 0)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { list = endl = one;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann if((one = one->right) )
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann k1 = one->key;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann else
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { list = endl = two;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann if((two = two->right) )
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann k2 = two->key;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann if(one && two)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { for(;;)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { STRNCMP(k1,k2,v,i,n);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann if(v <= 0)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { endl = (endl->right = one);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann if((one = one->right) )
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann k1 = one->key;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann else break;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann else
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { endl = (endl->right = two);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann if((two = two->right) )
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann k2 = two->key;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann else break;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann if(one)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { endl->right = one;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann endl = endone;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann else if(two)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { endl->right = two;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann endl = endtwo;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann list->left = endl;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann return list;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann}
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann#if __STD_C
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmannstatic Rsobj_t* flatten(reg Rsobj_t* r)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann#else
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmannstatic Rsobj_t* flatten(r)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmannreg Rsobj_t* r;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann#endif
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann{ reg Rsobj_t *t, *p, *list;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann /* find smallest element and make it head of list */
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann while((t = r->left) )
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann RROTATE(r,t);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann /* flatten tree */
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann for(list = p = r, r = r->right;; p = r, r = r->right)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { if(!r)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { list->left = p;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann return list;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann else if((t = r->left) )
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { do RROTATE(r,t);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann while((t = r->left) );
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann p->right = r;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann}
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann#if __STD_C
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmannstatic Rsobj_t* rasplist(Rs_t* rs)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann#else
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmannstatic Rsobj_t* rasplist(rs)
2450a4210dee64b064499a3a1154129bdfc74981Daniel HausmannRs_t* rs;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann#endif
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann{
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann reg Rsobj_t *r, *t, *list, *endl;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann reg int n, e;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann reg Rsrasp_t* rasp = (Rsrasp_t*)rs->methdata;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann list = endl = rasp->empty; rasp->empty = NIL(Rsobj_t*);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann for(n = 0, t = NIL(Rsobj_t*); n <= UCHAR_MAX; ++n)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann {
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann if((r = rasp->tree[n]) )
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { t = flatten(r);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann rasp->tree[n] = NIL(Rsobj_t*);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann for(e = SLOT-1; e > 0; --e)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { if(!(r = rasp->slot[e][n]) )
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann continue;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann r = radix(r);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann t = t ? listmerge(r,t,e) : r;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann rasp->slot[e][n] = NIL(Rsobj_t*);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann if((r = rasp->slot[0][n]) )
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { if((r->right = t) )
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann r->left = t->left;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann else r->left = r;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann t = r;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann rasp->slot[0][n] = NIL(Rsobj_t*);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann if(t)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { if(list)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann endl->right = t;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann else list = t;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann endl = t->left;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann t = NIL(Rsobj_t*);
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann }
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann if(list)
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann { list->left = endl;
2450a4210dee64b064499a3a1154129bdfc74981Daniel Hausmann endl->right = NIL(Rsobj_t*);
}
return list;
}
/* public method */
static Rsmethod_t _Rsrasp =
{ raspinsert,
rasplist,
sizeof(Rsrasp_t),
RS_MTRASP,
"rasp",
"Initial radix split into a forest of splay trees."
};
__DEFINE__(Rsmethod_t*, Rsrasp, &_Rsrasp);
#ifdef NoF
NoF(rsrasp)
#endif