blob: a126e6cc6e73ad8554e21a611b373a25599f5a9a [file] [log] [blame]
Arnaldo Carvalho de Melo3e1bbdc32010-05-14 20:05:21 -03001/*
2 * Simple pointer stack
3 *
4 * (c) 2010 Arnaldo Carvalho de Melo <acme@redhat.com>
5 */
6
7#include "util.h"
8#include "pstack.h"
Jiri Olsa84f5d362014-07-14 23:46:48 +02009#include "debug.h"
Arnaldo Carvalho de Melo3e1bbdc32010-05-14 20:05:21 -030010#include <linux/kernel.h>
11#include <stdlib.h>
12
13struct pstack {
14 unsigned short top;
15 unsigned short max_nr_entries;
16 void *entries[0];
17};
18
19struct pstack *pstack__new(unsigned short max_nr_entries)
20{
Arnaldo Carvalho de Melo61e94512012-11-10 19:41:15 -030021 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;
Arnaldo Carvalho de Melo3e1bbdc32010-05-14 20:05:21 -030026}
27
Arnaldo Carvalho de Melo61e94512012-11-10 19:41:15 -030028void pstack__delete(struct pstack *pstack)
Arnaldo Carvalho de Melo3e1bbdc32010-05-14 20:05:21 -030029{
Arnaldo Carvalho de Melo61e94512012-11-10 19:41:15 -030030 free(pstack);
Arnaldo Carvalho de Melo3e1bbdc32010-05-14 20:05:21 -030031}
32
Arnaldo Carvalho de Melo61e94512012-11-10 19:41:15 -030033bool pstack__empty(const struct pstack *pstack)
Arnaldo Carvalho de Melo3e1bbdc32010-05-14 20:05:21 -030034{
Arnaldo Carvalho de Melo61e94512012-11-10 19:41:15 -030035 return pstack->top == 0;
Arnaldo Carvalho de Melo3e1bbdc32010-05-14 20:05:21 -030036}
37
Arnaldo Carvalho de Melo61e94512012-11-10 19:41:15 -030038void pstack__remove(struct pstack *pstack, void *key)
Arnaldo Carvalho de Melo3e1bbdc32010-05-14 20:05:21 -030039{
Arnaldo Carvalho de Melo61e94512012-11-10 19:41:15 -030040 unsigned short i = pstack->top, last_index = pstack->top - 1;
Arnaldo Carvalho de Melo3e1bbdc32010-05-14 20:05:21 -030041
42 while (i-- != 0) {
Arnaldo Carvalho de Melo61e94512012-11-10 19:41:15 -030043 if (pstack->entries[i] == key) {
Arnaldo Carvalho de Melo3e1bbdc32010-05-14 20:05:21 -030044 if (i < last_index)
Arnaldo Carvalho de Melo61e94512012-11-10 19:41:15 -030045 memmove(pstack->entries + i,
46 pstack->entries + i + 1,
Arnaldo Carvalho de Melo3e1bbdc32010-05-14 20:05:21 -030047 (last_index - i) * sizeof(void *));
Arnaldo Carvalho de Melo61e94512012-11-10 19:41:15 -030048 --pstack->top;
Arnaldo Carvalho de Melo3e1bbdc32010-05-14 20:05:21 -030049 return;
50 }
51 }
52 pr_err("%s: %p not on the pstack!\n", __func__, key);
53}
54
Arnaldo Carvalho de Melo61e94512012-11-10 19:41:15 -030055void pstack__push(struct pstack *pstack, void *key)
Arnaldo Carvalho de Melo3e1bbdc32010-05-14 20:05:21 -030056{
Arnaldo Carvalho de Melo61e94512012-11-10 19:41:15 -030057 if (pstack->top == pstack->max_nr_entries) {
58 pr_err("%s: top=%d, overflow!\n", __func__, pstack->top);
Arnaldo Carvalho de Melo3e1bbdc32010-05-14 20:05:21 -030059 return;
60 }
Arnaldo Carvalho de Melo61e94512012-11-10 19:41:15 -030061 pstack->entries[pstack->top++] = key;
Arnaldo Carvalho de Melo3e1bbdc32010-05-14 20:05:21 -030062}
63
Arnaldo Carvalho de Melo61e94512012-11-10 19:41:15 -030064void *pstack__pop(struct pstack *pstack)
Arnaldo Carvalho de Melo3e1bbdc32010-05-14 20:05:21 -030065{
66 void *ret;
67
Arnaldo Carvalho de Melo61e94512012-11-10 19:41:15 -030068 if (pstack->top == 0) {
Arnaldo Carvalho de Melo3e1bbdc32010-05-14 20:05:21 -030069 pr_err("%s: underflow!\n", __func__);
70 return NULL;
71 }
72
Arnaldo Carvalho de Melo61e94512012-11-10 19:41:15 -030073 ret = pstack->entries[--pstack->top];
74 pstack->entries[pstack->top] = NULL;
Arnaldo Carvalho de Melo3e1bbdc32010-05-14 20:05:21 -030075 return ret;
76}