Logo Search packages:      
Sourcecode: cmus version File versions  Download package

glob.c

/* 
 * Copyright 2005 Timo Hirvonen
 */

#include "glob.h"
#include "uchar.h"
#include "list.h"
#include "xmalloc.h"
#include "debug.h"

#include <string.h>

00013 struct glob_item {
      struct list_head node;
      enum {
            GLOB_STAR,
            GLOB_QMARK,
            GLOB_TEXT
      } type;
      char text[];
};

/* simplification:
 * 
 *   ??*? => ???*
 *   *?*  => ?*
 *   *?   => ?*
 *   ...
 */
static void simplify(struct list_head *head)
{
      struct list_head *item;

      item = head->next;
      while (item != head) {
            struct list_head *i, *next;
            int qcount = 0;
            int scount = 0;

            i = item;
            do {
                  struct glob_item *gi;

                  gi = container_of(i, struct glob_item, node);
                  if (gi->type == GLOB_STAR) {
                        scount++;
                  } else if (gi->type == GLOB_QMARK) {
                        qcount++;
                  } else {
                        i = i->next;
                        break;
                  }
                  i = i->next;
            } while (i != head);

            next = i;

            if (scount) {
                  /* move all qmarks to front and
                   * if there are >1 stars remove all but the last */
                  struct list_head *insert_after = item->prev;

                  i = item;
                  while (qcount) {
                        struct glob_item *gi;

                        gi = container_of(i, struct glob_item, node);
                        i = i->next;
                        if (gi->type == GLOB_QMARK) {
                              list_del(&gi->node);
                              list_add(&gi->node, insert_after);
                              qcount--;
                        }
                  }

                  i = item;
                  while (scount > 1) {
                        struct glob_item *gi;

                        gi = container_of(i, struct glob_item, node);
                        i = i->next;
                        if (gi->type == GLOB_STAR) {
                              list_del(&gi->node);
                              free(gi);
                              scount--;
                        }
                  }
            }

            item = next;
      }
}

void glob_compile(struct list_head *head, const char *pattern)
{
      int i = 0;

      list_init(head);
      while (pattern[i]) {
            struct glob_item *item;

            if (pattern[i] == '*') {
                  item = xnew(struct glob_item, 1);
                  item->type = GLOB_STAR;
                  i++;
            } else if (pattern[i] == '?') {
                  item = xnew(struct glob_item, 1);
                  item->type = GLOB_QMARK;
                  i++;
            } else {
                  int start, len, j;
                  char *str;

                  start = i;
                  len = 0;
                  while (pattern[i]) {
                        if (pattern[i] == '\\') {
                              i++;
                              len++;
                              if (pattern[i])
                                    i++;
                        } else if (pattern[i] == '*') {
                              break;
                        } else if (pattern[i] == '?') {
                              break;
                        } else {
                              i++;
                              len++;
                        }
                  }

                  item = xmalloc(sizeof(struct glob_item) + len + 1);
                  item->type = GLOB_TEXT;

                  str = item->text;
                  i = start;
                  j = 0;
                  while (j < len) {
                        if (pattern[i] == '\\') {
                              i++;
                              if (pattern[i]) {
                                    str[j++] = pattern[i++];
                              } else {
                                    str[j++] = '\\';
                              }
                        } else {
                              str[j++] = pattern[i++];
                        }
                  }
                  str[j] = 0;
            }
            list_add_tail(&item->node, head);
      }
      simplify(head);
}

void glob_free(struct list_head *head)
{
      struct list_head *item = head->next;

      while (item != head) {
            struct glob_item *gi;
            struct list_head *next = item->next;

            gi = container_of(item, struct glob_item, node);
            free(gi);
            item = next;
      }
}

static int do_glob_match(struct list_head *head, struct list_head *first, const char *text)
{
      struct list_head *item = first;

      while (item != head) {
            struct glob_item *gitem;

            gitem = container_of(item, struct glob_item, node);
            if (gitem->type == GLOB_TEXT) {
                  int len = u_strlen(gitem->text);

                  if (!u_strncase_equal_base(gitem->text, text, len))
                        return 0;
                  text += strlen(gitem->text);
            } else if (gitem->type == GLOB_QMARK) {
                  uchar u;
                  int idx = 0;

                  u = u_get_char(text, &idx);
                  if (u == 0)
                        return 0;
                  text += idx;
            } else if (gitem->type == GLOB_STAR) {
                  /* after star there MUST be normal text (or nothing),
                   * question marks have been moved before this star and
                   * other stars have been sripped (see simplify)
                   */
                  struct list_head *next;
                  struct glob_item *next_gi;
                  const char *t;
                  int tlen;

                  next = item->next;
                  if (next == head) {
                        /* this star was the last item => matched */
                        return 1;
                  }
                  next_gi = container_of(next, struct glob_item, node);
                  BUG_ON(next_gi->type != GLOB_TEXT);
                  t = next_gi->text;
                  tlen = strlen(t);
                  while (1) {
                        const char *pos;

                        pos = u_strcasestr_base(text, t);
                        if (pos == NULL)
                              return 0;
                        if (do_glob_match(head, next->next, pos + tlen))
                              return 1;
                        text = pos + 1;
                  }
            }
            item = item->next;
      }
      return text[0] == 0;
}

int glob_match(struct list_head *head, const char *text)
{
      return do_glob_match(head, head->next, text);
}

Generated by  Doxygen 1.6.0   Back to index