thodg/libgit2/src/pqueue.c

• Show log

  Commit

• Hash : 71db842f
  Author :
  Date : 2011-03-08T14:57:03
  

  Rewrite the Revision Walker The new revision walker uses an internal Commit object storage system, custom memory allocator and much improved topological and time sorting algorithms. It's about 20x times faster than the previous implementation when browsing big repositories. The following external API calls have changed: `git_revwalk_next` returns an OID instead of a full commit object. The initial call to `git_revwalk_next` is no longer blocking when iterating through a repo with a time-sorting mode. Iterating with Topological or inverted modes still makes the initial call blocking to preprocess the commit list, but this block should be mostly unnoticeable on most repositories (topological preprocessing times at 0.3s on the git.git repo). `git_revwalk_push` and `git_revwalk_hide` now take an OID instead of a full commit object.

Download

• src/pqueue.c

• /*
   *	BORING COPYRIGHT NOTICE:
   *
   *	This file is a heavily modified version of the priority queue found
   *	in the Apache project and the libpqueue library.
   *
   *		https://github.com/vy/libpqueue
   *
   *	These are the original authors:
   *
   *		Copyright 2010 Volkan Yazıcı <volkan.yazici@gmail.com>
   *		Copyright 2006-2010 The Apache Software Foundation
   *
   *  This file is licensed under the Apache 2.0 license, which 
   *  supposedly makes it compatible with the GPLv2 that libgit2 uses.
   *
   *  Check the Apache license at:
   *
   *     http://www.apache.org/licenses/LICENSE-2.0
   *
   *  So much licensing trouble for a binary heap. Oh well.
   */
  
  #include "common.h"
  #include "pqueue.h"
  
  #define left(i)   ((i) << 1)
  #define right(i)  (((i) << 1) + 1)
  #define parent(i) ((i) >> 1)
  
  int git_pqueue_init(git_pqueue *q, size_t n, git_pqueue_cmp cmppri)
  {
  	assert(q);
  
      /* Need to allocate n+1 elements since element 0 isn't used. */
      if ((q->d = malloc((n + 1) * sizeof(void *))) == NULL)
  		return GIT_ENOMEM;
  
      q->size = 1;
      q->avail = q->step = (n + 1);  /* see comment above about n+1 */
      q->cmppri = cmppri;
  
      return GIT_SUCCESS;
  }
  
  
  void git_pqueue_free(git_pqueue *q)
  {
      free(q->d);
  	q->d = NULL;
  }
  
  
  size_t git_pqueue_size(git_pqueue *q)
  {
      /* queue element 0 exists but doesn't count since it isn't used. */
      return (q->size - 1);
  }
  
  
  static void bubble_up(git_pqueue *q, size_t i)
  {
      size_t parent_node;
      void *moving_node = q->d[i];
  
      for (parent_node = parent(i);
           ((i > 1) && q->cmppri(q->d[parent_node], moving_node));
           i = parent_node, parent_node = parent(i)) {
          q->d[i] = q->d[parent_node];
      }
  
      q->d[i] = moving_node;
  }
  
  
  static size_t maxchild(git_pqueue *q, size_t i)
  {
      size_t child_node = left(i);
  
      if (child_node >= q->size)
          return 0;
  
      if ((child_node + 1) < q->size &&
          q->cmppri(q->d[child_node], q->d[child_node + 1]))
          child_node++; /* use right child instead of left */
  
      return child_node;
  }
  
  
  static void percolate_down(git_pqueue *q, size_t i)
  {
      size_t child_node;
      void *moving_node = q->d[i];
  
      while ((child_node = maxchild(q, i)) != 0 &&
             q->cmppri(moving_node, q->d[child_node])) {
          q->d[i] = q->d[child_node];
          i = child_node;
      }
  
      q->d[i] = moving_node;
  }
  
  
  int git_pqueue_insert(git_pqueue *q, void *d)
  {
      void *tmp;
      size_t i;
      size_t newsize;
  
      if (!q) return 1;
  
      /* allocate more memory if necessary */
      if (q->size >= q->avail) {
          newsize = q->size + q->step;
          if ((tmp = realloc(q->d, sizeof(void *) * newsize)) == NULL)
              return GIT_ENOMEM;
  
          q->d = tmp;
          q->avail = newsize;
      }
  
      /* insert item */
      i = q->size++;
      q->d[i] = d;
      bubble_up(q, i);
  
      return GIT_SUCCESS;
  }
  
  
  void *git_pqueue_pop(git_pqueue *q)
  {
      void *head;
  
      if (!q || q->size == 1)
          return NULL;
  
      head = q->d[1];
      q->d[1] = q->d[--q->size];
      percolate_down(q, 1);
  
      return head;
  }
  
  
  void *git_pqueue_peek(git_pqueue *q)
  {
      if (!q || q->size == 1)
          return NULL;
      return q->d[1];
  }
  

Download