Show
Ignore:
Timestamp:
03/13/08 19:33:15 (6 years ago)
Author:
Theo Schlossnagle <jesus@omniti.com>
git-committer:
Theo Schlossnagle <jesus@omniti.com> 1205436795 +0000
git-parent:

[6afd275c557e7fd4812458abdbe3013685ae7bd7]

git-author:
Theo Schlossnagle <jesus@omniti.com> 1205436795 +0000
Message:

partial match works. apply command works, needs range expansion which I'll lean on pcre for. Didn't have pcre on the plain -- so here we are.

Files:

Legend:

Unmodified
Added
Removed
Modified
Copied
Moved
  • src/utils/noit_skiplist.c

    r40c5e31 r4cdbcdb  
    2626#endif 
    2727 
    28 int noit_compare_voidptr(void *a, void *b) { 
     28static int noit_skiplisti_find_compare(noit_skiplist *sl, const void *data, 
     29                                       noit_skiplist_node **ret, 
     30                                       noit_skiplist_node **prev, 
     31                                       noit_skiplist_node **next, 
     32                                       noit_skiplist_comparator_t comp); 
     33 
     34int noit_compare_voidptr(const void *a, const void *b) { 
    2935  if(a < b) return -1; 
    3036  if(a == b) return 0; 
     
    5460} 
    5561 
    56 static int indexing_comp(void *a, void *b) { 
     62static int indexing_comp(const void *a, const void *b) { 
    5763  assert(a); 
    5864  assert(b); 
    5965  return (void *)(((noit_skiplist *)a)->compare)>(void *)(((noit_skiplist *)b)->compare); 
    6066} 
    61 static int indexing_compk(void *a, void *b) { 
     67static int indexing_compk(const void *a, const void *b) { 
    6268  assert(b); 
    6369  return a>(void *)(((noit_skiplist *)b)->compare); 
     
    116122 
    117123void *noit_skiplist_find(noit_skiplist *sl, 
    118               void *data, 
    119               noit_skiplist_node **iter) { 
     124                         const void *data, 
     125                         noit_skiplist_node **iter) { 
     126  return noit_skiplist_find_neighbors(sl, data, iter, NULL, NULL); 
     127
     128void *noit_skiplist_find_neighbors(noit_skiplist *sl, 
     129                                   const void *data, 
     130                                   noit_skiplist_node **iter, 
     131                                   noit_skiplist_node **prev, 
     132                                   noit_skiplist_node **next) { 
    120133  void *ret; 
    121134  noit_skiplist_node *aiter; 
    122135  if(!sl->compare) return 0; 
    123136  if(iter) 
    124     ret = noit_skiplist_find_compare(sl, data, iter, sl->compare); 
     137    ret = noit_skiplist_find_neighbors_compare(sl, data, iter, 
     138                                               prev, next, sl->compare); 
    125139  else 
    126     ret = noit_skiplist_find_compare(sl, data, &aiter, sl->compare); 
     140    ret = noit_skiplist_find_neighbors_compare(sl, data, &aiter, 
     141                                               prev, next, sl->compare); 
    127142  return ret; 
    128 }   
     143
     144 
    129145void *noit_skiplist_find_compare(noit_skiplist *sli, 
    130                       void *data, 
    131                       noit_skiplist_node **iter, 
    132                       noit_skiplist_comparator_t comp) { 
     146                                 const void *data, 
     147                                 noit_skiplist_node **iter, 
     148                                 noit_skiplist_comparator_t comp) { 
     149  return noit_skiplist_find_neighbors_compare(sli, data, iter, 
     150                                              NULL, NULL, comp); 
     151
     152void *noit_skiplist_find_neighbors_compare(noit_skiplist *sli, 
     153                                           const void *data, 
     154                                           noit_skiplist_node **iter, 
     155                                           noit_skiplist_node **prev, 
     156                                           noit_skiplist_node **next, 
     157                                           noit_skiplist_comparator_t comp) { 
    133158  noit_skiplist_node *m = NULL; 
    134159  noit_skiplist *sl; 
     160  if(iter) *iter = NULL; 
     161  if(prev) *prev = NULL; 
     162  if(next) *next = NULL; 
    135163  if(comp==sli->compare || !sli->index) { 
    136164    sl = sli; 
     
    140168    sl= (noit_skiplist *) m->data; 
    141169  } 
    142   noit_skiplisti_find_compare(sl, data, iter, sl->comparek); 
     170  noit_skiplisti_find_compare(sl, data, iter, prev, next, sl->comparek); 
    143171  return (*iter)?((*iter)->data):(*iter); 
    144172} 
    145 int noit_skiplisti_find_compare(noit_skiplist *sl, 
    146                      void *data, 
    147                      noit_skiplist_node **ret, 
    148                      noit_skiplist_comparator_t comp) { 
     173static int noit_skiplisti_find_compare(noit_skiplist *sl, 
     174                                       const void *data, 
     175                                       noit_skiplist_node **ret, 
     176                                       noit_skiplist_node **prev, 
     177                                       noit_skiplist_node **next, 
     178                                       noit_skiplist_comparator_t comp) { 
    149179  noit_skiplist_node *m = NULL; 
    150180  int count=0; 
     181  if(ret) *ret = NULL; 
     182  if(prev) *prev = NULL; 
     183  if(next) *next = NULL; 
    151184  m = sl->top; 
    152185  while(m) { 
    153     int compared = -1; 
    154     if(m->next) compared=comp(data, m->next->data); 
    155     if(compared == 0) { 
    156 #ifdef SL_DEBUG 
    157       printf("Looking -- found in %d steps\n", count); 
    158 #endif 
    159       m=m->next; 
    160       while(m->down) m=m->down; 
     186    int compared; 
     187    compared = (m->next) ? comp(data, m->next->data) : -1; 
     188    if(compared == 0) { /* Found */ 
     189      m=m->next; /* m->next is the match */ 
     190      while(m->down) m=m->down; /* proceed to the bottom-most */ 
    161191      *ret = m; 
     192      if(prev) *prev = m->prev; 
     193      if(next) *next = m->next; 
    162194      return count; 
    163195    } 
    164     if((m->next == NULL) || (compared<0)) 
    165       m = m->down, count++; 
     196    if((m->next == NULL) || (compared<0)) { 
     197      if(m->down == NULL) { 
     198        /* This is... we're about to bail, figure out our neighbors */ 
     199        if(prev) *prev = (m == sl->bottom) ? NULL : m; 
     200        if(next) *next = m->next; 
     201      } 
     202      m = m->down; 
     203      count++; 
     204    } 
    166205    else 
    167206      m = m->next, count++; 
    168207  } 
    169 #ifdef SL_DEBUG 
    170   printf("Looking -- not found in %d steps\n", count); 
    171 #endif 
    172208  *ret = NULL; 
    173209  return count; 
     
    184220} 
    185221noit_skiplist_node *noit_skiplist_insert(noit_skiplist *sl, 
    186                               void *data) { 
     222                                         const void *data) { 
    187223  if(!sl->compare) return 0; 
    188224  return noit_skiplist_insert_compare(sl, data, sl->compare); 
     
    190226 
    191227noit_skiplist_node *noit_skiplist_insert_compare(noit_skiplist *sl, 
    192                                       void *data, 
    193                                       noit_skiplist_comparator_t comp) { 
     228                                                 const void *data, 
     229                                                 noit_skiplist_comparator_t comp) { 
    194230  noit_skiplist_node *m, *p, *tmp, *ret = NULL, **stack; 
    195231  int nh=1, ch, stacki; 
     
    262298    tmp->down = p; 
    263299    if(p) p->up=tmp; 
    264     tmp->data = data; 
     300    tmp->data = (void *)data; 
    265301    tmp->sl = sl; 
    266302    m->next = tmp; 
     
    286322} 
    287323int noit_skiplist_remove(noit_skiplist *sl, 
    288             void *data, noit_freefunc_t myfree) { 
     324                         const void *data, noit_freefunc_t myfree) { 
    289325  if(!sl->compare) return 0; 
    290326  return noit_skiplist_remove_compare(sl, data, myfree, sl->comparek); 
     
    317353} 
    318354int noit_skiplist_remove_compare(noit_skiplist *sli, 
    319                       void *data, 
    320                       noit_freefunc_t myfree, noit_skiplist_comparator_t comp) { 
     355                                 const void *data, 
     356                                 noit_freefunc_t myfree, 
     357                                 noit_skiplist_comparator_t comp) { 
    321358  noit_skiplist_node *m; 
    322359  noit_skiplist *sl; 
     
    328365    sl= (noit_skiplist *) m->data; 
    329366  } 
    330   noit_skiplisti_find_compare(sl, data, &m, comp); 
     367  noit_skiplisti_find_compare(sl, data, &m, NULL, NULL, comp); 
    331368  if(!m) return 0; 
    332369  while(m->previndex) m=m->previndex; 
  • src/utils/noit_skiplist.h

    rb62cf2b r4cdbcdb  
    2727/* This is the function type that must be implemented per object type 
    2828   that is used in a skiplist for comparisons to maintain order */ 
    29 typedef int (*noit_skiplist_comparator_t)(void *, void *); 
     29typedef int (*noit_skiplist_comparator_t)(const void *, const void *); 
    3030typedef void (*noit_freefunc_t)(void *); 
    3131 
     
    6464                             noit_skiplist_comparator_t); 
    6565noit_skiplist_node *noit_skiplist_getlist(noit_skiplist *sl); 
    66 void *noit_skiplist_find_compare(noit_skiplist *sl, void *data, 
     66void *noit_skiplist_find_compare(noit_skiplist *sl, const void *data, 
    6767                                 noit_skiplist_node **iter, 
    6868                                 noit_skiplist_comparator_t func); 
    69 void *noit_skiplist_find(noit_skiplist *sl, void *data, 
     69void *noit_skiplist_find_neighbors_compare(noit_skiplist *sl, const void *data, 
     70                                           noit_skiplist_node **iter, 
     71                                           noit_skiplist_node **prev, 
     72                                           noit_skiplist_node **next, 
     73                                           noit_skiplist_comparator_t func); 
     74void *noit_skiplist_find(noit_skiplist *sl, const void *data, 
    7075                         noit_skiplist_node **iter); 
     76void *noit_skiplist_find_neighbors(noit_skiplist *sl, const void *data, 
     77                                   noit_skiplist_node **iter, 
     78                                   noit_skiplist_node **prev, 
     79                                   noit_skiplist_node **next); 
    7180void *noit_skiplist_next(noit_skiplist *sl, noit_skiplist_node **); 
    7281void *noit_skiplist_previous(noit_skiplist *sl, noit_skiplist_node **); 
    7382 
    7483noit_skiplist_node *noit_skiplist_insert_compare(noit_skiplist *sl, 
    75                                                  void *data, 
     84                                                 const void *data, 
    7685                                                 noit_skiplist_comparator_t comp); 
    77 noit_skiplist_node *noit_skiplist_insert(noit_skiplist *sl, void *data); 
    78 int noit_skiplist_remove_compare(noit_skiplist *sl, void *data, 
     86noit_skiplist_node *noit_skiplist_insert(noit_skiplist *sl, const void *data); 
     87int noit_skiplist_remove_compare(noit_skiplist *sl, const void *data, 
    7988                                 noit_freefunc_t myfree, 
    8089                                 noit_skiplist_comparator_t comp); 
    81 int noit_skiplist_remove(noit_skiplist *sl, void *data, noit_freefunc_t myfree); 
     90int noit_skiplist_remove(noit_skiplist *sl, const void *data, 
     91                         noit_freefunc_t myfree); 
    8292int noit_skiplisti_remove(noit_skiplist *sl, noit_skiplist_node *m, 
    8393                          noit_freefunc_t myfree); 
    8494void noit_skiplist_remove_all(noit_skiplist *sl, noit_freefunc_t myfree); 
    8595 
    86 int noit_skiplisti_find_compare(noit_skiplist *sl, void *data, 
    87                                 noit_skiplist_node **ret, 
    88                                 noit_skiplist_comparator_t comp); 
    89  
    9096void *noit_skiplist_pop(noit_skiplist * a, noit_freefunc_t myfree); 
    9197void *noit_skiplist_peek(noit_skiplist * a); 
    9298 
    93 int noit_compare_voidptr(void *, void *); 
     99int noit_compare_voidptr(const void *, const void *); 
    94100 
    95101#endif