tools/perf/util/pstack.c

   1 /*
   2  * Simple pointer stack
   3  *
   4  * (c) 2010 Arnaldo Carvalho de Melo <[email protected]>
   5  */
   6
   7 #include "util.h"
   8 #include "pstack.h"
   9 #include "debug.h"
  10 #include <linux/kernel.h>
  11 #include <stdlib.h>
  12
  13 struct pstack {
  14         unsigned short  top;
  15         unsigned short  max_nr_entries;
  16         void            *entries[0];
  17 };
  18
  19 struct pstack *pstack__new(unsigned short max_nr_entries)
  20 {
  21         struct pstack *pstack = zalloc((sizeof(*pstack) +
  22                                        max_nr_entries * sizeof(void *)));
  23         if (pstack != NULL)
  24                 pstack->max_nr_entries = max_nr_entries;
  25         return pstack;
  26 }
  27
  28 void pstack__delete(struct pstack *pstack)
  29 {
  30         free(pstack);
  31 }
  32
  33 bool pstack__empty(const struct pstack *pstack)
  34 {
  35         return pstack->top == 0;
  36 }
  37
  38 void pstack__remove(struct pstack *pstack, void *key)
  39 {
  40         unsigned short i = pstack->top, last_index = pstack->top - 1;
  41
  42         while (i-- != 0) {
  43                 if (pstack->entries[i] == key) {
  44                         if (i < last_index)
  45                                 memmove(pstack->entries + i,
  46                                         pstack->entries + i + 1,
  47                                         (last_index - i) * sizeof(void *));
  48                         --pstack->top;
  49                         return;
  50                 }
  51         }
  52         pr_err("%s: %p not on the pstack!\n", __func__, key);
  53 }
  54
  55 void pstack__push(struct pstack *pstack, void *key)
  56 {
  57         if (pstack->top == pstack->max_nr_entries) {
  58                 pr_err("%s: top=%d, overflow!\n", __func__, pstack->top);
  59                 return;
  60         }
  61         pstack->entries[pstack->top++] = key;
  62 }
  63
  64 void *pstack__pop(struct pstack *pstack)
  65 {
  66         void *ret;
  67
  68         if (pstack->top == 0) {
  69                 pr_err("%s: underflow!\n", __func__);
  70                 return NULL;
  71         }
  72
  73         ret = pstack->entries[--pstack->top];
  74         pstack->entries[pstack->top] = NULL;
  75         return ret;
  76 }
  77
  78 void *pstack__peek(struct pstack *pstack)
  79 {
  80         if (pstack->top == 0)
  81                 return NULL;
  82         return pstack->entries[pstack->top - 1];
  83 }